EDEN / Rovers Navigation / Motion Generation / Rough Terrain  
[ People Involved ] [ Related Publications ]  
An autonomous rover will eventually be facing
complex terrains. It should thus be given the tools that will help
it decide if its mechanical structure is able to traverse those
areas, or if it should rather avoid them and plan new trajectories
accordingly.
1. A geometric placement functionThe geometric placement function can compute the complete chassis configuration, given the current position of the rover and the current digital elevation map. This function is off course highly robotdependant, but the algorithm we use is quite generic and could be adapted with few modifications to other chassis (e.g. for Dala). As of now, it's been used only on Lama. For Lama, six angles are computed: the global pitch and roll of the chassis, as well as the pitch and roll of the front and back axles (relatively to the middle axle). The algorithm is split into two main steps:
Both steps use the same individual axle placement function, and the second step use one additional constrained placement function (which is constrained by the position of the middle axle). 1.1. Single axle placement functionOn lama, axles are made of two rigidly connected wheels. The placement consists in computing the roll and the height of the whole axle, given an horizontal position (x,y,theta) on a DEM. The algorithm is quite simple, and its main step is depicted on the two figures below.
Generally, at most two iterations are needed to obtain a realistic placement. 1.2. Constrained axle placement functionThis function is used to compute the placement of the front and back axles, which are free to rotate in pitch and roll around the middle axle. The placement of the front and back axle will give the global pitch and roll of the rover.
The principle is the following:
The two images below give an idea of the placement results we are able to obtain. The placement function for the six wheels takes about 10ms to complete on a 5x5cm DEM and a 350MHz G3 processor.
2. Reactive motion generationGiven the geometric placement function, we developped a reactive motion generator, suited for navigation on complex terrains. The principle resembles much the arcs generation, though some improvements regarding predictability have been made.
The above figure shows a set of arcs, recursively nested, on which a set of regularily spaced rover configurations are evaluated. Both the number of arcs and the nesting depth are configurable. On Lama, we use 21 arcs on the first level, and 11 arcs on the second level. The arcs are 2m long, and contain 20 configurations (spaced by 10cm). The nesting allows a more predictive solution to be found. An A* algorithm is used to explore the tree formed by the successive configurations and a cost function helps determining the best (lowest cost) arc to be followed at the current position. The cost contains two parts: a dangerousness and an interest value.
The dangerousness is computed thanks to the chassis configuration
angles: each angle 'a' has an upper limit 'm' and the dangerousness
relative to 'a' is 'd = m/(ma)^2'. The maximum 'd' obtained for
all the chassis angles is the global dangerousness of the
configuration.
Once a good arc has been found, it is followed during a variable distance (configurable), and the process iterates. On a 350MHz G3 processor, one iteration lasts between 300ms and 1500ms (depending on the terrain and the A* performance).
Simon Lacroix, Anthony Mallet, David Bonnafous. 
General Information
Robots
Rovers Navigation Autonomous Blimps
MultiRobot Cooperation
