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
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.
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:
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.
- where to go,
- what to perceive.
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
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
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.
|| [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.
|| [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.
Raja Chatila, Simon Lacroix, Jérémie Gancet.