Development of a Non-hazardous Path Planning Algorithm for Mars Rover in Real Terrain Enviroment

In order to fulfill the corresponding task successfully, a crucial issue should be addressed is the path planning for the exploration of the Mars surface owing to the environmental features of the tough terrain. Traditional path planning algorithms, such as the A* algorithm and the improved A* algorithm — the algorithm D* and the Field D*, which have been successfully implemented on the planetary rover during the expeditions of the Moon and Mars, have the problem of finding the shortest optimal path. One of the more effective algorithms derived from the modified A* refers to the Basic Theta* or the Lazy Theta* algorithms, which are faster any-angle path planning. Additionally, the algorithms can find shorter routes. In this paper, derived from a comprehensive comparison of the existing algorithms (A*, Basic Theta* and Lazy Theta*), a novel modification of the Lazy AT methodology is proposed to reduce the calculation time and obtain a shorter path. Based on the analysis of the surface feature of the Mars topography, the corresponding safety indicator is discussed. The principal hazards of the wheeled vehicles during the exploration on the surface of the Mars are the slopes and the obstacles. According to the requirements for avoiding obstacles as well as the exploration stability of the Mars rover in the period of the exploration, the following topographic coefficients have been chosen to develop the hazard indicator, i.e., the inclination angle of the terrain, the surface roughness and the height difference of the terrain. In addition, to obtain a safe trajectory in algorithm Lazy AT on the Mars surface, the terrain hazard indicator (risk indicator) for the modification of the Risk Lazy AT algorithm is also proposed in this paper. The comparing analysis modeling results of the Risk Lazy AT and Lazy Theta* has shown that our proposed algorithm Risk Lazy AT can guarantee the safety movement of a mobile object during the exploration on the surface of the planet. In light of the real-world surface features of the Mars terrain, the digital map of the planet’s surface has been developed and the spatial routing of the rover has been tested with our novel proposed algorithm, so-called Risk Lazy AT.

algorithm A*, Any-Angle Path Planning, algorithm Basic theta*, algorithm Lazy Theta*, algorithm Lazy AT, algorithm Risk Lazy AT, terrain hazard indicator

1. Carsten J., Rankin A., Ferguson D., Stentz A. Global path planning on board the mars exploration rovers. In Aerospace Conference, 2007 IEEE (pp. 1—11).

2. Tan Liguo, Fomichev A. V. Planirovanie prostranstvennogo marshruta poleta bespilotnogo letatelqnogo appalata s ispolqzovaniem metodov chactichno celochislennogo linejnogo programmirovaniya (The spatial flight route planning of unmanned aerial vehicles using the methods of mixed-integer linear programming), Vectnik moskovckogo gosudarstvennogo technicheckogo universiteta im. N. E. Baumana. Seriya "Priborostroenie", 2016 (in Russian).

3. Ferguson D., Stentz A. Using interpolation to improve path planning: The Field D* algorithm, Journal of Field Robotics, 23.2 (2006): 79—101.

4. Fomichev A. V., Tan Liguo. Razrabotka algoritma byhstroj kompensacii pogreshnostej kompleksirovannoj inercialqno-sputnikoj sistemyh navigacii malogabaritnyhch bespilotnyhch letatelqnyhch apparatov v usloviyach slozhnoj sredyh (Development of an algorithm for rapid error-compensation for small unmanned aerial vehicles with a complex inertial satellite navigation system in a complex environment), Nauka i obrazovanie: nauchnoe izdanie MGTU im. N. E. Baumana, 2015, no. 10 (in Russian).

5. Fomichev A. V., Wang Guoyan. Sravnitelqnyhq analiz me todov planirovaniya marshruta dvizheniya dlya planetochoda (Comparison analysis of path-planning methodologies for planetary rover), Informacionnyhe Sistemyh i Technologii, 2016 (in Russian).

6. Available at: https://ru.wikipedia.org/wiki/Эвристический_алгоритм/ (date of access 25.04.2018).

7. Nash A., Koenig S. Any-angle path planning, AI Magazine, 2013, vol.34, no. 4., pp. 85—107.

8. Choi S., Lee J. Y., Yu W. Fast any-angle path planning on grid maps with non-collision pruning. Robotics and Biomimetics (ROBIO), 2010 IEEE International Conference on. IEEE, 2010.

9. Uras T., Koenig S. Speeding-Up Any-Angle Path-Planning on Grids, ICAPS, 2015, pp. 234—238.

10. Nash A., Daniel K., Koenig S. Aelner A. Theta*: Any angle path planning on grids, Proceedings AAAI Conference on Artificial Intelligence, 2007, vol. 7, pp. 1177—1183.

11. Mendonca P., Goodwin S. C-Theta*: Cluster based PathPlanning on Grids. International Conference on Computational Science and Computational Intelligence.2015. Mendonca, Pramod, and Scott Goodwin. "C-Theta*: Cluster Based Path-Planning on Grids." Computational Science and Computational Intelligence (CSCI), 2015 International Conference on. IEEE, 2015, pp. 605—608.

12. Nash A., Koenig S., Tovey C. Lazy theta*: Any-angle path planning and path length analysis in 3d, Third Annual Symposium on Combinatorial Search, 2010.

13. Available at: https://en.wikipedia.org/wiki/Spirit_ (rover) / (date of access 25.04.2018). 14. Available at: https://astrogeology.usgs.gov/search/map/Phobos/MarsExpress/HRSC/Phobos_ME_HRSC_DEM_ Global_2ppd / (date of access 25.04.2018).