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.

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.