单边矩形扩展A*算法

morinson

单边矩形扩展A*算法

单边矩形扩展A-算法.pdf (647.37 KB, 下载次数: 0)

2017-9-3 12:24 上传

点击文件名下载附件
下载积分: 金钱 -1

单边矩形扩展A*算法

李冲, 张安, 毕文豪

西北工业大学，陕西 西安 710129

Single-Boundary Rectangle Expansion A* Algorithm

LI Chong, ZHANG An, BI Wenhao

Northwestern Polytechnical University, Xi'an 710129, China

全文: PDF (648 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS) 摘要 提出了一种新的单边矩形扩展A*（REA*）算法．新算法采用受迫扩展规则，在以矩形单元探索地图的过程中，用单条公共边取代相邻矩形的2条冗余独立边，从而提高了算法效率，简化了终止条件，优化了路径质量．在无需对地图进行预处理的情况下，算法速度比传统A*算法提高1个数量级以上．算法能够保证得到栅格最优的路径点序列，且最终路径（由路径点间直线组成）总是比栅格最优路径更短．典型地图集上的实验结果表明，相比于现有REA*算法，新算法提高了对复杂地图的处理能力和算法效率上限．新算法路径长度更短，路径转折次数更少，因此路径质量更优．除了在低复杂且不开阔的地图上外，新算法平均效率也高于REA*算法． 关键词 ： 路径搜索,  启发式算法,  栅格图,  A*算法,  路径平衡性    Abstract：A new single-boundary rectangle expansion A* (REA*) algorithm is presented. The new algorithm adopts the forced expansion rule, and the two redundant adjacent boundaries between adjacent rectangles are replaced with a shared boundary during the process of exploring map in rectangular units, which will improve the efficiency, simplify the termination conditions and optimize the quality of the result paths. Without any offline pre-processing, the new algorithm can speed up a highly optimized A* algorithm by an order of magnitude and more. The algorithm guarantees the grid-optimal path point sequence, while the final result path (which consists of the straight lines between path points) is always shorter than grid-optimal path. Experimental results on typical benchmark problem sets show that compared with the existing REA* algorithms, the ability to deal with complex maps and the upper limit of the algorithm efficiency are improved by the proposed algorithm. The shorter result paths and less turning points are achieved with the proposed algorithm, so the quality of result paths are better. The average speed of the proposed algorithm is also better than that of REA*, except in the low complex and low open maps. Key words： path search           heuristic algorithms           grid           A* algorithm           breaking path symmetries 收稿日期: 2016-08-29      出版日期: 2016-12-26 1: TP18 基金资助:国家自然科学基金（61573283） 通讯作者: 李冲，lichong@mail.nwpu.edu.cn    E-mail: lichong@mail.nwpu.edu.cn 作者简介: 李冲（1989-），男，博士生．研究领域：无人机自主控制，人工智能，任务规划． 张安（1962-），男，博士，教授．研究领域：航空武器火力控制技术，复杂系统建模与仿真，智能指挥与控制工程． 毕文豪（1986-），男，博士生．研究领域：航空火力控制技术，先进航空电子集成技术． 引用本文:    李冲, 张安, 毕文豪. 单边矩形扩展A*算法[J]. 机器人, 2017, 39(1): 46-56.         LI Chong, ZHANG An, BI Wenhao. Single-Boundary Rectangle Expansion A* Algorithm. ROBOT, 2017, 39(1): 46-56. 链接本文:   http://robot.sia.cn/CN/10.13973/j.cnki.robot.2017.0046    或     http://robot.sia.cn/CN/Y2017/V39/I1/46