EDEN / Rovers Navigation / Motion Generation / Navigation Strategies
 [ People Involved ] [ Related Publications ]
Navigation strategies

Rovers navigation within an unknown or partially known environment is usually quite challenging. The terrains may sometimes be rough, and contain unexpected obstacles or dead-ends. A robust and well-designed chassis is a substantial help to overcome terrains (reasonable) roughness (see On rough terrain). However, tackling rovers navigation using a local reactive navigation approach only, may lead the robots to face untractable situations. In order to avoid such issues (where a robot gets trapped in a "dead-locked" configuration, for instance), it is relevant to deal with a global representation of the world : this representation is updated iteratively (thanks to the perceptions performed by the robot during its navigation) and is processed in real-time, so that an up-to-date relevant path (regarding the current available knowledge on the world) can be available whenever required, leading to the expected location in the more efficient way.

Designing and applying means to process in this way information related to a global model, deals with navigation strategies issues.

Model of the world

The global model used to compute navigation strategies is basically a traversability map, iteratively built thanks to the processed perception data. More information related to the environment modelling (thanks to a terrain classification), is provided here. The traversability map exhibits several categories (or classes) of terrain traversability : for instance, regarding the example depicted on the right picture, two classes (flat in green and obstacle in red) are distinguished. However, such a map can be built with classifying the terrain with any number of relevant classes.

The traversability map is discretized, hence a table of cells is built, each cell encompassing attributes related to the criteria that led to its current classification. The cell's probability distribution over the terrain classes (in term of belonging's probability) is a relevant ressource for designing navigation strategies : indeed, a traversability cost can be associated to a given distribution of probabilities, so the costs of the cells over a global model of the world can be exploited in a timely manner to take decisions.

Taking the good decision

Navigating within an unknwon environment in order to reach an expected location in a timely manner, requires to be able to decide:

  • where to go,
  • what to perceive.
Designing navigation strategies leads to tailor policies to answer coherently these two questions, regarding the state of the model of the world at a given time.
The efficiency of a strategy can be measured in several ways: the distance of the path followed, the time elapsed until goal is reached, or also the energy consumed during the navigation. The two latest indicators are mainly related to the model of the robots, hence the first one is usually adopted, since it can be generalized more easily.
Some classical path finding algorithms like D* are known to fit well the problem of minimizing a path cost within a graph representing an environment : given the current knowledge of the world, this algorithm provides with a time-efficient way to compute the current best path to the goal. Whenever new information is perceived (using cameras for instance), the model of the world is updated and so are the traversability costs. The algorithm is applied iteratively, updating the best path to the goal. In unknown environments, this approach is applied to select sub-goals, up to the final goal, so that the robot move along the (current) lowest cost path. However, this approach only deals with the concern "where to go", and not "what to perceive" : the perceptions are usually simply performed iteratively in the direction of the latest planned sub-goal. However, this perception policy may not be the most relevant one : actually, this approach does not take into account the interest of perceiving such or such place during the navigation.

These considerations led us to develop a new navigation strategy tailored to consider both path planning and perception planning within a single process.

PG2P : A Perception Guided Path Planning approach

The key idea of the PG2P approach is to guide the robot toward the next place where to perform a perception, instead of a sub-goal belonging to the current D* computed best path. Hence the question "where to go" relies on the other question "what (and so where) to perceive". The heart of the PG2P algorithm is a three steps processing, that provides the clues to decide of the most relevant perception regarding both the current knowledge about the world and the expected navigation/exploration behavior of the robot. This processing relies on two different considerations :
- is a given place worths to be perceived or not (a),
- is a given place reachable (b).
We define decision functions for each of these purposes : these functions are exploited to analyse the neighbourhood of the robots in order to decide of the next most relevant perception action. The three steps of the central processing are the following :

1. To determine the access frontier around the robot : the application of the function of decision (b) onto the nodes of the robot's vicinity , allows to determine which nodes should be considered as the robot's frontier of access.

2. To choose the most promising location (among the access frontier nodes) where to perform a perception : a model of perception is applied from each node, then the effect onto the traversability costs is localy taken into account in order to establish the relevance of performing a perception from this location. The effect of the perception onto the traversability costs and the model of perception are detailed in [Gancet 2003]

3. To determine the most relevant perception direction : considering directionnal sensors, the perception direction should finally be decided. The decision function (a) let us decide which nodes are relevant to perceive, and hence the direction maximizing the interest of perception is selected.

Finally, This basic processing can be refined in order to adapt the robot's behavior to the constraints of the mission or the environment (if such constraints are known). After testing the PG2P algorithm in simulation (left picture), this paradigm is now being experimented onto two rover platforms: Lama and more recently Dala.

[Lacroix 1995]

Related Publications

[Gancet 2003]  [related pages] [abstract] [download] [copyright] [BibTeX]  [top]

J. Gancet and S. Lacroix. PG2P: A perception-guided path planning approach for long range autonomous navigation in unkown natural environments. In International Conference on Intelligent Robotics and Systems. Las Vegas, NV (USA), 2003.

[Lacroix 1995]  [related pages] [abstract] [download] [BibTeX]  [top]

S. Lacroix and R. Chatila. Motion and Perception Strategies for Outdoor Mobile Robot Navigation in Unknown Environments. In O. Khatib and J.K. Salisbury, editors, Experimental Robotics IV, volume 223, of Lecture Notes in Computer and Information Science, pages 538-547. Springer, 1995.

People Involved

Raja Chatila, Simon Lacroix, Jérémie Gancet.
  General Information
 About the EDEN Project
 Photo Gallery
 Related Projects
 Job opportunities

 The Blimp

  Rovers Navigation
 Motion control
 Environment Perception
 Environment Modeling
 Motion Generation
   Potential fields
   Circle arcs generation
   Nearest diagram method
   On rough terrains
>  Navigation Strategies

  Autonomous Blimps
 Environment Perception

  Multi-Robot Cooperation
 Multi UAV coordination