I have a cunning plan...

[motters]

The next step after calculating an occupancy grid map is to locate the
navigable (probably vacant) space and use that to plan safe routes
around the environment. Here we can just use very standard algorithms
which have been around for many years.

In this example I've generated a simulated map of the navigable space,
which may be unrealistically perfect but is sufficient to test the
planning algorithm.

http://sentience.googlegroups.com/web/pathplanner1.jpg

This uses a fairly efficient implementation of the A* algorithm, with
the resulting path being smoothed using splines. Path planning takes
a negligible amount of time, and even if the grid map was huge it
wouldn't be unreasonable to have the robot stop to "think" about its
plan for a couple of seconds (like Baldrick out of Black Adder) before
setting off.

[ch...@diversity.co.uk]

Hi Bob,

I'm sure you've probably seen it, but Steven Lavalle's RRT planner is
quite a good alternative to A*.

I've put up a little summary at http://dotnetrobot.blogspot.com/2007/03/rapidly-exploring-random-trees.html
and have some c# code lying around that my be adaptable to this
project, though now that you have done tree storage for your 3d data,
it would probably be trivial for you.

Chris

[Bob Mottram]

I've written the path planner part of the system in such a way that potentially it could use different algorithms if A* isn't up to the job.  I imagine that for large open spaces A* would be too slow and consume too much memory to be usable, but even in this circumstance I could still down-sample the navigable space map (at present each grid square is 5cm in size) without affecting the performance of the planner much.  For this project I'm not expecting to have the robot moving around in wide open areas, since the effective range of stereo using typical webcam camera resolutions (320x240 or 640x480) is not much more than 5 metres.

The results with A* look reasonable in terms of the amount of computation needed, which is far less than for the slam algorithm or stereo correspondence.  Even if the robot needs to pause to formulate its plan that's not a big problem, and as multi core processors become increasingly common it will no longer be an issue.