Subject:
|
Re: an idea, can someone tell me if this is possible/been done before/etc?
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Tue, 2 Dec 2003 20:21:29 GMT
|
Original-From:
|
Gordon Elliott <gelliott@csisc.%antispam%cc>
|
Viewed:
|
1065 times
|
| |
|
|
Earlier, Jim Choate said:
> I think this is a very complicated problem for a computer as well. As a
> start look into a technical term called 'compliance'. The 'step over'
> ability of legs is one of the greatest problems in robotics.
>
> Computing is computing. How it's done doesn't usually make a big
> difference (re O() notation algorithm complexity) except in run time. The
> problem here is that the run time is a factor of the solution and not the
> problem, mixing chickens and eggs.
>
> All computing problems that don't fall into the NP class (or higher) of
> complexity are all pretty much reducable to a universal Turing machine.
> And I have zero motive to get into the P==NP? question here, other than to
> say put me in the P<>NP! group from the get go. I see no reason to expect
> exponential or factorial problems to be reducable to a group of linear
> problems.
I think it is important to understand both simplicity and complexity here.
For example a fluidic (e.g. pneumatic) cylinders have the potential for
redistribution between cylinders of load force. This is equivalent to a
computation that would require feedback and fairly complex output responses
for individual motors per leg to achieve. Additionally the air system has an
inherent spring constant (and damping) in the air pressure itself. These
aspects could give a certain degree of compliance to the system in a simple
way. Now of course using algorithmic "O()" notation, both would be linear
time processes. But the complexity (or simplicity) of constructing such a
device could be quite different, and that is probably the more important
measure!
Then on the other side, consider a higher order robotic system capable of
complex motion in a real-world environment. It could easily be expected to
process seen analysis from video cameras for planning and feedback, for
example. That would constitute a complex computational system--probably too
complex for an RCX. But understandings of "order of" issues "O()" in
computational complexity can mislead into solving the wrong problem.
Many years ago David Waltz studied analysis of visual scenes in his thesis.
He studied constraint satisfaction problems relating to scene analysis,
which is closely related to problems of visual or camera based analysis.
Several of his articles are online:
http://www.neci.nec.com/homepages/waltz/
Here is an interesting article discussing Waltz's filtering:
http://citeseer.nj.nec.com/mackworth93complexity.html (Pick format you want
for reading)
That paper shows some line drawing images that have inconsistent resolutions
of which edges are concave and which are convex. (And we are talking about
the air or space--non solid--side of the physical tangible object being
represented.) And by the way, this particular scene analysis is in principle
NP-Complete, yet can be processed for real world like problems in
approximately linear time! That was my point, that an _appearance_ of being
NP-Complete complexity does not mean it is actually going to be a
combinatorially exploding problem.
Here is an interesting paper on Genetic algorithms:
http://www-users.cs.york.ac.uk/~erh/rae/ga.pdf (Note PDF paper only)
It discusses the (generic kind) of algorithm that might make a bridge
between vision systems and feedback and learning, and also discusses the
NP-Complete problem type in that context.
But if you were to be taken blind folded to a new location, and opened your
eyes there, you would very quickly identify patterns. You could even
identify patterns that looked like fragments of the line drawings (in
general form) in the previous paper, if they happened to have that form.
That is _new_ information, as you would (in concept) have never seen the
"scene" at which you opened your eyes. Thus _learning_ is information which
you use, but the actual analysis of the scene is one that occurs just as you
open your eyes.
Now when navigating your house, or a new building with which you are
unfamiliar, you don't take out a rule and measure to determine where the
door's openings are, which are convex surfaces and which are solid, etc.
(And that is similar to a problem for a robot which is to navigate in the
real world around objects, etc.) And you don't do that by "eyeballing" it
per se, because the analysis is precisely what one is doing to reach a
conclusion, it takes an answer to that processing to give a frame in which
one could consider imagining a ruler extending to measure.
The main point is that processing can involve great complexity. But real
world processing in _real time_ is always linear time algorithms. If the
problem is too complex, they bail and use a simpler approach. The robot
always makes a decision of what to do in the next second, within the second,
and that is fixed time, "linear" time algorithm. Even if the decision is to
sit still because it is confused and needs to take more time, that result
occurred in the fixed time leading to making that decision.
So complexity "order of" or "O()" is important to understand. But it can
also be misleading. One can be mislead into thinking that an NP-Complete
problem is not solvable by real-time systems, when in fact _apparently_
NP-Complete problems are solved in linear time very often. They can take a
"maximum" of exponentially exploding time--that is very different statement.
(And one stops to think when that happens!) That does not mean that they are
not accessible to real-time systems, and that steps to mitigate or control
the combinatorial explosion are not available.
-- Gordon Elliott
PS, I just put lego-robotics@crynwr.com in the "TO" line, rather than the CC
line, and delete any other entry. It doesn't take but a second. And it does
not annoy the person to which one is responding by sending them TWO copies
of the same message.
----- Original Message -----
From: "Jim Choate" <ravage@einstein.ssz.com>
To: "Gordon Elliott" <gelliott@csisc.cc>
Cc: <lego-robotics@crynwr.com>
Sent: Tuesday, December 02, 2003 10:38 AM
Subject: Re: an idea, can someone tell me if this is possible/been done
before/etc?
>
> Somebody really should fix the 'reply to' behaviour of this list if people
> like pixel are going to complain about list delays meaning some sort of
> personal attack. Like Gordon says in his note, I've only got one lifetime
> and I'm not spending a great deal of it munging headers because some
> listmeister doesn't know/want to set the replyto: to something convenient
> and reasonable. Like pixel, I don't joing -public- lists to increase my
> -private- mail.
>
> On Tue, 2 Dec 2003, Gordon Elliott wrote:
>
> > On "complexity", I would point out that the computational power of the
> > neural pathways of the house fly thoroughly exceeds the computational
> > throughput of our most massive supercomputer clusters at the moment.
> >
> > True "adaptation" would require hardware functionally capable of • learning
> > and feedback, and that can occur at various levels of complexity. All of
> > them will be light years away from the actual biological spider or house
> > fly, but interesting effects can be demonstrated with even simple • equipment.
>
> Other than rewording what I said (through the references to the books)
> what's your point?
>
> > By the way, as humans we solve seemingly combinatorially complex • problems in
> > fractions of a second all day long. Look around your house. Judging how
> > walls intersect to get an analysis of which are convex and which are • concave
> > corners is an NP complete problem-
>
> No it isn't. All it takes is a straight ruler (or an imaginary one if
> we're eyeballing it). One measurement for each wall, and the order
> doesn't effect the outcome. That's linear and therefore -not- NP. It is in
> no way comparable to say a salesman problem where the path -does- effect
> the results.
>
> And all corners are both convex and concave, it just depends on which side
> you're looking toward at the moment.
>
> > -yet we just look up and get the answer immediately. (And there are
> > optical illusions that take us time to settle on
> > one of several interpretations, and when we finally see such an
> > interpretation we have an "oh yea" moment as a consistent pattern • emerges.)
>
> There's no 'immediate' to it, other than your own internal perception
> which can't be (and shouldn't be) trusted, even in principle.
>
> > The reason we can solve such problems quickly is that there are many • clues
> > that allow us to resolve these in more or less linear time in most • cases.
> > (So put me in the liner time group, I've only got one lifetime to do my
> > 'computing.')
>
> Mallarky, the reason we know how to solve them -perceptionaly- quickly is
> that we've spent years learning how to do it. The complexity book I refred
> to mentions a figure of 50,000 trials to train. They extend this with an
> excellent example of how children spend years playing with water or sand
> to learn those 50,000 trials.
|
|
Message has 1 Reply:
2 Messages in This Thread:
  
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
