Subject:
|
Re: Rover Programming
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Thu, 27 Jun 2002 07:30:56 GMT
|
Original-From:
|
Steve Baker <sjbaker1@airmail.=AntiSpam=net>
|
Reply-To:
|
SJBAKER1@AIRMAIL.avoidspamNET
|
Viewed:
|
805 times
|
| |
|
|
Simon Brooke wrote:
> That's one solution, but it isn't essential. The other solution is to
> assume every square is empty until you've explored it.
So how do you remember what you've already explored? I think you *need* three
states if you want your robot to curiously explore it's environment without
continually re-exploring areas that it's already visited but which proved to
be empty. If UNEXPLORED==EMPTY then you can't avoid that problem.
> Obviously, if
> you get a 'goto' instruction before you've completely mapped the
> domain, then there's a possibility that you'll encounter an obstacle in
> an assumed empty square, which will mean marking and re-routing.
That too.
> > * When you are in 'explore mode', you'll want to speed through EMPTY
> > areas, carefully seek out and probe UNKNOWN areas that are
> > adjacent to EMPTY areas - and avoid known OBSTACLE areas and UNKNOWN
> > areas that are surrounded by OBSTACLE areas. This makes it easy to
> > write robot software that's actively curious about seeking out the
> > unknown.
>
>
> Yup, but as you yourself point out, it halves the number of cells in
> your grid.
I don't think that's a real problem unless you want an insanely large
area or an insanely fine grid.
> > How big should the grid cells be? Well, they really need to be
> > significantly smaller than the width of the robot. If your robot
> > was 6 inches wide and the grid size was 12" then you could happen
> > to drive between two chair legs spaced (say) 8" apart and mark that
> > entire 12"x12" area as 'empty' - which would be a serious mistake!
>
> Ah, but that's because you're assuming complete knowledge of the
> content of the squares. I'm marking a square to say 'there's an
> obstacle here', but not assuming that an unmarked square necessarily
> has no obstacles. From this point of view it's fine to have one metre
> squares, provided that the average density of obstacles in the domain
> is less than one every square metre.
So what use is the final map? You don't know whether there are obstacles
in areas marked empty - because they *might* contain major obstacles that you
just havn't found yet and they *might* be areas that you havn't visited
before. On the other hand, the existance of a single 2x4 stud brick could
cause you to mark an entire 1x1 meter area as "no go" so the robot would
take an elaborate 2 meter detour to get around it! A row of 2x4 bricks
spaced at 0.99 meter intervals might seem like an impenetrable wall!
What use is such a map?
> > Similarly, you don't want to make the grid too fine - if you settled
> > on a one-tenth inch grid size then you'd only have enough memory for
> > a 36 inch square play area. I guess that maybe a 1" grid size would
> > be a pretty reasonable compromise.
> >
> > That gives you a 30 foot square play area - which ought to be PLENTY.
>
> *If* you can afford to devote half your physical memory to map. But
> there's a trade-off here between the sophistication of your robot's
> behaviour and the granularity of your map.
Yes - and in fact, you could do some very simple realtime compression
to scrunch that down immensely if (as you suggest) there is less than
one obstacle to each square meter - then you could run-length encode
the map and get compression ratios of the order of thousands-to-one
for a map with 1cm grid squares.
There is certainly a CPU-time vs CPU-storage trade-off here - and the
nice thing about robots is that they can generally stop if they need
some time to think!
> > However, I really doubt that you could drive around for more than
> > maybe 10 feet in a straight line - or a couple of feet in a curve
> > using dead-reckoning *alone* without accumulating an error *MUCH*
> > larger than an inch. So your map would be degrading in precision
> > faster than you could explore it! That's another reason not to
> > bother with a really high resolution grid.
>
> Essentially I think you need a 'home' location which the robot can
> recognise (perhaps with a uniquely coloured floor tile), and which it
> can regularly return to - i.e. drive to where you think home should be,
> then drive around in a spiral till you find it, then reset your
> co-ordinates.
Yes - but when you are exploring (say) 10 feet from 'home', you know
your position at home - but by the time you've driven 10 feet back to
the area you were exploring (making multiple turns around obstacles
along the way), you're positioning information is hopelessly inaccurate
again.
It would be nice to be able to work outwards from 'home', establishing
new mapped areas that could later be returned to and recognised as
already familiar landmarks so that you could resync your position *there*
without travelling all the way back to home base. The trouble with that
is recognising *which* obstacle you've re-discovered...now we get into
pattern matching with sparse data sets...Ikky stuff.
I also thought about doing this the way that Ants do it - laying a
pheremone trail. Perhaps you could have a robot that laid a trail
of Jar-Jar binks minifigs that it could follow later to get a
precise position fix!
> However, doing this sort of thing with only three
> sensors, two of which are handling roatation and one of which is
> detecting obstacles, is kind of hard - unless the 'obstacles' are
> merely marks on the floor, or you use a multiplexor or multiple RCX
> units.
Yes. Although it ought to be possible to build a drive mechanism that
only needs one rotation sensor. Suppose you had the sensor on one wheel
only and some kind of mechanism that would either lock the two wheels
together to drive in a straight line - or force the un-monitored wheel
to be stationary while the one with the sensor rotated. Then, your
software could know whether that interlock was operated or not and read
the rotation sensor *either* as a distance travelled meter *or* an
angle-turned-through sensor.
You could even do it with one motor - did you ever see one of those
*really* nasty radio controlled toys that can only go either full speed
forwards or reverse and turn to the left at the same time? Your rotation
sensor could measure the rotation of just one wheel - and you'd only need
one motor. Of course to turn 90 degrees in one direction is easy - but
turning 90 the opposite way needs a 270 degree rotation in the opposite
direction!
> > An alternative that I rather like is to allow OBSTACLE squares to
> > gradually degrade into UNKNOWN status - and for UNKNOWN squares to
> > gradually 'infect' adjacent EMPTY squares and make them UNKNOWN too.
> > If you knew the rate at which your robot lost positional precision,
> > you could control the rate of information destruction to match your
> > worst estimates...no degradation when stationary, some degradation
> > when moving in a straight line, more when turning - and a big chunk
> > of degradation whenever you detect that you hit something.
>
>
> Yeah, I like this one too, because it copes with the fact that in real
> domains, obstacles (furniture, people) move. This is the 'nibble' or
> 'byte' grid, and the values stored in the array represent the
> probability of encountering an obstacle there. The degradation should
> then be towards the middle position, so if we're using a nibble 15
> would represent 'I'm confident there's an obstacle there', and 0 would
> represent 'I'm confident there's no obstacle there'. The default
> position, towards which all cells should gradually degrade, would be 8
> 'I've no idea whether there's an obstacle there'.
Yes.
> However, of course, if you're using nibbles or bytes the granularity of
> your grid must be much courser.
But with a little simple on-the-fly data compression, I think you could
solve the storage problem. Most robots don't need much compute power because
they move insanely slowly compared to the speed of the computer inside. It
wouldn't take much to decompress as much of the 'map' as it currently needs
and place it into a small cache - recompressing that section and uncompressing
another into the space thus free'd up. If you aren't short of time, you should
be able to get spectacular compression ratios when the size and spacing of the
obstacles is large compared to the grid resolution.
I doubt that anything like that would be do-able with NQC - but with LegOS
and a fully compiled program, I think you could still get good resolution
without eating up an unreasonable fraction of your RAM.
Still, I think the poor performance you can get from dead-reckoning is
what kills you. This kind of thing would be fine with a kind of GPS type
system - but with a bunch of rotation sensors as our only navigation
mechanism, I think we're doomed.
----------------------------- Steve Baker -------------------------------
Mail : <sjbaker1@airmail.net> WorkMail: <sjbaker@link.com>
URLs : http://www.sjbaker.org
http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net
http://prettypoly.sf.net http://freeglut.sf.net
http://toobular.sf.net http://lodestone.sf.net
|
|
Message has 1 Reply:
 | | Dead reckoning (was Re: Rover Programming)
|
| (...) A systematic search pattern is one solution. Not being too anal about it is another - random walking the domain will eventually explore the whole of it, although increasingly inefficiently as time goes on. (...) It's killing me. My first (...) (22 years ago, 27-Jun-02, to lugnet.robotics)
|
Message is in Reply To:
| | Re: Rover Programming
|
| (...) That's one solution, but it isn't essential. The other solution is to assume every square is empty until you've explored it. Obviously, if you get a 'goto' instruction before you've completely mapped the domain, then there's a possibility that (...) (22 years ago, 26-Jun-02, to lugnet.robotics)
|
24 Messages in This Thread:
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
