Subject:
|
Re: Rover Programming
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Wed, 26 Jun 2002 11:07:41 GMT
|
Original-From:
|
Simon Brooke <simon@jasmine.org.+AntiSpam+uk>
|
Reply-To:
|
simon@/AntiSpam/jasmine.org.uk
|
Viewed:
|
913 times
|
| |
|
|
On Wednesday 26 Jun 2002 10:48 am, you wrote:
> Simon Brooke wrote:
> > (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.
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 you'll encounter an obstacle in
an assumed empty square, which will mean marking and re-routing.
> * 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.
> * 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!
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.
> 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.
> 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. 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.
> 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'.
However, of course, if you're using nibbles or bytes the granularity of
your grid must be much courser.
Cheers
Simon
--
simon@jasmine.org.uk (Simon Brooke) http://www.jasmine.org.uk/~simon/
;; Semper in faecibus sumus, sole profundum variat.
|
|
Message has 2 Replies:
 | | Re: Rover Programming
|
| (...) 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 (...) (22 years ago, 27-Jun-02, to lugnet.robotics)
| | | Re: Rover Programming
|
| (...) While we're talking about programming rovers, could someone give me an example of a 'spiral drive around behavior' in either RCX Code (v1.5) or Gordon's Brick Programmer? Or how about code with two rotation sensors attached to the (...) (22 years ago, 27-Jun-02, to lugnet.robotics)
|
Message is in Reply To:
| | Re: Rover Programming
|
| (...) Yep - VERY difficult. (...) 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. (...) Unfortunately, you need THREE (...) (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
|
|
|
|
Active threads in Robotics
|
|
|
|
|
|
