An Improved Theta* Algorithm Based on Terrain Directional Traversability
-
摘要: 提出了一种基于Basic Theta*改进的任意航向路径规划算法,利用星球巡视器在俯仰和滚转方向上抗倾覆能力的差异,对不同航向上的地形可通行性进行了分析,分别区别出障碍以及方向性障碍,并在此基础上将Basic Theta*扩展节点时的可视性检查改进为可通过性检查,从而筛选出能够通过方向性障碍的路径.仿真实验表明,该算法克服了Basic Theta*算法的局限性,能够更加充分地利用巡视器特性,在复杂地形上找到传统方法无法通行的最短路径,扩展了巡视器的行驶范围和工作能力,对于巡视器穿越崎岖地形及撞击坑底探测等星球表面特殊任务具有实用价值.Abstract: An improved any-angle path planning algorithm based on Basic Theta* algorithm is proposed.Utilizing the difference between the pitch and roll anti-overturning stability of planetary rover,terrain traversability relevant to rover heading is analyzed to distinguish obstacles and directional obstacles.Based on the obstacle map,the visibility check in node-expanding process of Basic Theta* is improved to a traversability check,hence paths that could traverse directional obstacles could be screened.Simulation experiments show that,the proposed algorithm overcomes the limitation of Basic Theta* as well as it could utilize rover characteristics more thoroughly and find the shortest path on complex terrains which are not traversable in traditional methods.It extends the rovers'range and working capability,hence it is practical for rough terrain trek,exploration of the bottom of crater and such special missions on planetary surface.
-
Key words:
- Theta* algorithm /
- Directional traversability /
- Path planning /
- Any-angle /
- Heuristic search
-
[1] THORPE C. Path relaxation:path planning for a mobile robot[C]//Proceedings of the 4th National Confe-rence on Artificial Intelligence. Menlo Park:The AAAI Press, 1984:318-321 [2] FERGUSON D, STENTZ A. Using interpolation to improve path planning:the field D* algorithm[J]. J. Field Robot., 2006, 23(2):79-101 [3] YAP P, BURCH N, HOLTE R, et al. Block A*:database-driven search with applications in any-angle path-planning[C]//Proceedings of the 25th AAAI Conference on Artificial Intelligence. Menlo Park:The AAAI Press, 2011:120-125 [4] NASH A, DANIEL K, KOENIG S, et al. Theta*:any-angle path planning on grids[J]. J. Artif. Intell. Res., 2010, 39(1):533-579 [5] NILSSON N. A mobile automaton:An application of artificial intelligence techniques[C]//Proceedings of the 1st International Joint Conference on Artificial Intelligence. Menlo Park:IJCAI, 1969:509-520 [6] NASH A, KOENIG S, LIKHACHEV M. Incremental Phi*:incremental any-angle path planning on grids[C]//Proceedings of the 21st International Joint Conference on Artificial Intelligence. Menlo Park:The AAAI Press, 2009:1824-1830 [7] Šišlák D, VOLF P, Pěchou?ek M. Accelerated A* trajectory planning:grid-based path planning comparison[C]//Proceedings of ICAPS 2009 Workshop on Planning and Plan Execution for Real-World Systems. Menlo Park:The AAAI Press, 2009:74-81 [8] HARABOR D, GRASTIEN A. An optimal any-angle pathfinding algorithm[C]//Proceedings of the 23rd International Conference on Automated Planning and Scheduling. Menlo Park:The AAAI Press, 2013:308-311 [9] BRESENHAM J. Algorithm for computer control of a di-gital plotter[J]. IBM Syst. J., 1965, 4(1):25-30 [10] ZHANG W, DANG Z L, JIA Y. Research on digital lunar terrain construction[J]. Spacecraft Envir. Eng., 2008, 25(4):35-40(张伍, 党兆龙, 贾阳. 月面数字地形构造方法研究[J]. 航天器环境工程, 2008, 25(4):35-40) -
点击查看大图
计量
- 文章访问数: 1180
- HTML全文浏览量: 131
- PDF下载量: 849
- 被引次数: 0
下载:
