Subject:
|
Re: Rover Programming
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Wed, 26 Jun 2002 09:48:27 GMT
|
Original-From:
|
Steve Baker <sjbaker1@+avoidspam+airmail.net>
|
Reply-To:
|
sjbaker1@airmail.SAYNOTOSPAMnet
|
Viewed:
|
663 times
|
| |
|
|
Simon Brooke wrote:
> The primary problem is dead reckoning navigation - which is hard on the
> 'out of the box' RIS because it's very hard to make a robot that can
> turn a controlled amount or travel a controlled distance.
Yep - VERY difficult.
> Actually mapping the domain is not hard and can be done in any decet
> programming languages.
It's *really* hard with any of the Lego Firmware options (eg NQC) because
you can't access really large amounts of RAM. However, you could stand
a chance with LegOS and GCC.
> There are two fundamental possiblities:
> (1) Create a two dimensional array of bits. Treat each bit as a square
> unit of floor. The size of the unit is up to you. If the robot is able
> to traverse the square, it leaves the bit clear; if it hits anything,
> it sets the bit. It can build up its map either by doing a box search
> of the domain (i.e. trundling up and down like a lawnmower) or just by
> random walking it.
>
> > From any point it can then plot the shortest route home which does not
> pass through any marked square.
Unfortunately, you need THREE states - EMPTY, OBSTACLE and UNKNOWN.
* 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.
* When you are in 'go somewhere' mode, you'll need to try to go through
only the EMPTY areas - avoiding OBSTACLE and UNKNOWN squares by a
large enough margin to avoid collisions.
> The advantage of the bitmap is that it's easy to
> process; the disadvantage (particularly in 32k of RAM) is that you
> can't map an area in very great resolution.
Let's do some analysis:
Let's suppose you could use half of the RCX's RAM for the bitmap,
that would allow 256k bits - which (at one bit per location) would
allow a 512x512 grid. At two bits per grid cell, you are down to 362x362.
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!
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.
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.
Unless someone comes up with a MUCH more accurate dead-reckoning solution,
(and I think that's unlikely) I don't think this can work without some kind
of absolute position reference.
I thought about mapping a small area - then moving off somewhere else - then
returning to the original area to see how far it's moved...I guess that with
some fancy pattern recognition, you could continually re-sync parts of your
map to allow for the robot's positioning error - but then when you actually
came to *USE* the map, it would become *useless* rather quickly.
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.
With that scheme, navigable 'gaps' between furniture would gradually narrow
and then vanish as your ability to accurately know how to get through them
degrades.
My problem is that for any robot I ever built, the map would degrade much
faster than you could create it.
Generalized free-roaming navigation is a *very* hard problem with the
standard set of RCX sensors. That's why I think some kind of 'landmark'
recognition scheme is truly needed.
----------------------------- 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 3 Replies:
 | | 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)
| | | RE: Rover Programming
|
| Steve Baker Wrote: (...) I'm going to add a proviso here - when you hit something that you shouldn't have hit! Anyways, this is a very interesting idea, Steve. The bitmap analysis is fine. I don't think any of us with kids and a reasonably large (...) (22 years ago, 26-Jun-02, to lugnet.robotics)
| | | Re: Rover Programming
|
| I've been thinking a bit about using landmarks imitating ants. You should know that ants use different types of self-produced chemicals to mark the places they have been and the paths to follow. Using this with robots would mean using a light sensor (...) (22 years ago, 27-Jun-02, to lugnet.robotics)
|
Message is in Reply To:
| | Re: Rover Programming
|
| (...) OK, why does it need to communicate with the PC? The primary problem is dead reckoning navigation - which is hard on the 'out of the box' RIS because it's very hard to make a robot that can turn a controlled amount or travel a controlled (...) (22 years ago, 24-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
|
|
|
|
