Pathfinding algorithms

It all depends on what your input is.
In the EE classes at my college, there were teams who had to build robots to move objects around a square field. Because they knew the field was square, they'd drive the robot into a wall, then mark a (0,0) home location there, then drive around in set patterns to sweep the field looking for the target. if they bump into any other walls, they'd fix up their (0,0) point and local map orientation. They'd find the target, and internally know where they were, and so would them move the target to the end location. Usually they fielded ultrasound range finders as their input devices to "see" the world.

A lot of the DARPA challenge robots use optical cameras to get information about their suroundings. The input video is processed for different markers, like the white lines of a road. From those markers, the robot tries to determine where it is on the road and how well oriented it is along the direction of the road. Using GPS and internal map making, the car can understand the more global "where am i" so as to properly navigate intersections, or other navigation goals.

As far as stuff you may want to do entierly in the computer, take a look at:
A* (A Star) path finding on a grid.
Steering behaviors

Grid-based methods are actually pretty practical; they're often used in the context of Bayesian estimation. You might want to take a look at Probabilistic Robotics. Often you'd then compute optimal solutions to various Markov Decision Problems, etc, in what robotics people call a 'deliberative' approach. The upsides are that this approach has been very successful in solving problems like SLAM and has a good theoretical basis; the downside is that it requires a lot of computation.

An alternative philosophy is to just use 'reactive' (as opposed to 'deliberative') controllers for everything, combined in various ways, as in Behavior-Based Robotics. It often feels kind of ad-hoc, but it also often works.

Finally, while I'm listing general-purpose robotics books, I can't leave out Principles of Robot Motion, which quickly and clearly covers a broad range of topics.

Back to grids: The famous

">BigDog robot, I know uses a grid-based approach which is actually very simple: It uses a vision system to assign a cost to each cell of a grid representation of the terrain (each cell of which is actually a few meters square; the resolution isn't too high), and then at each timestep runs A* from where it is to the goal. This is combined with what is in essence a steering controller to keep it on the path, whose steering commands are interpreted by lower-level leg controllers.

For your problem I kind of like the probabilistic approach. That said, it can have various levels of complexity: You could maintain a grid representation of your entire world and update it according to Bayes' Rule, or maybe you could just use Bayes' Rule to update a probability distribution over the direction relative to the robot of the signal transmitter and use something like a bug algorithm to try to get to it. The bug algorithms are nice in a way; they're simple and reactive in the style of behavior-based robotics, but they also have completeness proofs.

So, there's a disorganized mess of ideas and references. Hopefully it contains something of value to you! :-)

[EDIT: this presentation and associated techreport might also be good to look at, at least to get a feeling for what's out there (even if they are from 2000).]

[Edited by - Emergent on June 14, 2010 7:03:22 AM]

Quote:

Original post by KulSeran A lot of the DARPA challenge robots use optical cameras to get information about their suroundings. The input video is processed for different markers, like the white lines of a road.

That makes sense to me for things like road markers, but I hear there's been a trend away from vision-based systems in many contexts in favor of just relying on expensive LIDAR systems (like this).

Thanks guys! Just the kind of info I was looking for.
Also, the big dog robot just blew me away. Great engineering.

Quote:

Original post by Emergent Back to grids: The famous ">BigDog robot, I know uses a grid-based approach which is actually very simple: It uses a vision system to assign a cost to each cell of a grid representation of the terrain (each cell of which is actually a few meters square; the resolution isn't too high), and then at each timestep runs A* from where it is to the goal. This is combined with what is in essence a steering controller to keep it on the path, whose steering commands are interpreted by lower-level leg controllers.

Where did you learn this from? And do you know anything more about the lower-level leg controllers?

Quote:

Original post by raigan Where did you learn this from? And do you know anything more about the lower-level leg controllers?

The paper "Autonomous Navigation for BigDog" was presented at ICRA this year. Unfortunately, no, I don't know how the leg controllers work (that's the really interesting part, right?).

There were also a few unusual tricks to ensure "path stability" that I left out, one of them being that A* was run from where the robot was a few seconds ago rather than from where it is now. It's still not clear to me why this is totally necessary, but it apparently fixed some problem they were having with A* occasionally switching wildly between very-different paths on consecutive frames.