Towards Multi-Resolution Path Planning On-Board a Planetary Exploration Rover

Paper number

IAC-13,A3,3C,6,x18388

Author

Mr. Alexandru Rusu, Centre National d'Etudes Spatiales (CNES), France

Coauthor

Ms. Sabine Moreno, Centre National d'Etudes Spatiales (CNES), France

Coauthor

Ms. Yoko Wanatabe, Office National d’Etudes et de Recherches Aérospatiales (ONERA), France

Coauthor

Mr. Mathieu Rognant, Office National d’Etudes et de Recherches Aérospatiales (ONERA), France

Coauthor

Mr. Michel Devy, LAAS-CNRS, France

Year

2013

Abstract

The autonomous onboard navigation system of a Mars exploration robot should be designed to meet mission-specific constraints: energy consumption, memory and computation power, and time costs. In the ExoMars project of ESA, the rover navigation requirements include an ability to reach, within a single sol, targets located up to 100m away without any intervention from Earth. CNES has been developing such an autonomous rover navigation system for 20 years, and the result is a software package called EDRES which includes the algorithms necessary for autonomous movement generation and execution of the rover. A path planning module currently implemented in EDRES is a local path planner based on the A*-search algorithm. 

An objective of this research is to study dynamic path planning algorithms and their implementation techniques, and to bring improvements in performance and efficiency to this module. Three different improvements are proposed and validated in this paper. 

First, the importance of using a binary heap trees, instead of fully-sorted priority queues, in the management structure of the module is proven by improving both memory-use and computation time. Secondly, the actual A* algorithm for local path planning is replaced by Fringe Retrieving A* (FRA*), which is an incremental version of A*. It reuses previous-step information to fasten the search process when there is an overlap between the current and previous maps. The immediate results show an improvement in the memory use, but with a slight increase in computation time due to an additional process of preserving the previous-step information. 

Finally, the feasibility of applying the D* Lite algorithm to global path planning is studied. The high resolution stereo camera on ESA’s Mars Express Orbiter can provide a global map of the planet surface at a resolution of 10m/pixel, with selected areas of 2m/pixel. Global path planning with such information could be effective especially for difficult environment configurations such as large-scale dead-ends, which cannot be treated by the local path planner. We have implemented D* Lite global path planner in EDRES, and verified that its processing time for re-planning remains reasonable with respect to the rover onboard system requirements. Further research will study the possibility of fusing maps at different resolutions coming from different sources, and of using them efficiently in the path planning task within the limited memory and computation power. The developed algorithm will be tested on the IARES rover platform on the “Mars Yard” available at CNES.

Abstract document

IAC-13,A3,3C,6,x18388.brief.pdf

Manuscript document

IAC-13,A3,3C,6,x18388.pdf (🔒 authorized access only).

To get the manuscript, please contact IAF Secretariat.