Risk Theta*: an Any-Angle Path Planning Algorithm based on Terrain Risk

Abstract

Risk Theta*: an any-angle path planning algorithm based on terrain risk is proposed in this paper. At first, based on statistical analysis on terrain feature of planetary surface, terrain risk index is proposed and the index map is built. Basic Theta* search is conducted on this index map to seek optimal path of lowest terrain risk. Simulation experiments show that the proposed algorithm could find out any-angle path of much lower terrain risk and comparable path length on grid map than A* and Basic Theta* which can significantly improve the rover safety, as well as satisfy the urgent demand of any-angle travel of planetary roving exploration, therefore it is fairly practical.

Keywords

Theta* / terrain risk / path planning / any-angle / heuristic search

References

[1] Thorpe C. Path relaxation: path planning for a mobile robot[C]//The 4th National Conference on Artificial Intelligence.Austin, Texas, USA:[s.n.]:1984.
[2] Ferguson D, Stentz A. Field D*: an interpolation-based path planner and replanner[C]//The 12th International Symposium of Robotics Research.San Francisco, California, USA:[s.n.]: 2005.
[3] Yap P, Burch N, Holte R, et al. Block A*: database-driven search with applications in any-angle path-planning[C]//The 25th AAAI Conference on Artificial Intelligence.San Francisco, California, USA:[s.n.],2011.
[4] Nash A, Daniel K, Koenig S, et al. Theta*: Any-angle path planning on grids[C]//The 22nd AAAI Conference on Artificial Intelligence.Vancouver, Canada:[s.n.],2007.
[5] Bresenham J. Algorithm for computer control of a digital plotter[J]. IBM Systems Journal, 1965,4(1):25-30.
[6] 汤国安,李发源,刘学军.数字高程模型教程(第二版)[M].北京:科学出版社,2010. [Tang G A, Li F Y, Liu X J. A course in digital elevation model (2nd edition)[M]. Beijing: Science Press, 2010.]
[7] 张伍,党兆龙,贾阳.月面数字地形构造方法研究[J].航天器环境工程,2008,25(4):35-40. [Zhang W, Dang Z L, Jia Y. Research on digital lunar terrain construction[J]. Spacecraft Environment Engineering, 2008,25(4):35-40.]
[8] Sun Z Z, Jia Y, Zhang H. Technological advancements and promotion roles of Chang'e-3 lunar probe mission[J]. Sci China Tech Sci, 2013,56(11):2702-2708.
[9] 贾阳,张建利,李群智,等.嫦娥三号巡视器遥操作系统设计与实现[J].中国科学:技术科学,2014,44(5):470-482. [Jia Y, Zhang J L, Li Q Z, et al. Design and realization for teleoperation system of the Chang'E-3 rover[J]. Sci Sin Tech, 2014,44(5):470-482.]