引用本文:李冲,张安,毕文豪.基于方向约束的A*算法[J].控制与决策,2017,32(8):1395-1402
【打印本页】   【HTML】   【下载PDF全文】   查看/发表评论  【EndNote】   【RefMan】   【BibTex】
←前一篇|后一篇→ 过刊浏览    高级检索
本文已被:浏览 316次   下载 744 本文二维码信息
码上扫一扫!
分享到: 微信 更多
基于方向约束的A*算法
李冲,张安,毕文豪
(西北工业大学电子信息学院,西安710072)
摘要:
实际机器人路径规划问题经常需要考虑路径的转弯约束以及路径起始/目标角要求,为此提出一种基于方向约束的A*算法.新算法区分同一路径点处不同方向的各条路径,通过定向扩展机制来满足路径方向约束,并采用节点合并策略和不一致队列降低算法复杂度.理论分析和典型地图集上的实验结果证明,所提算法总是能够保证给出符合转弯约束和起始/目标角约束的最短路径,且相比于现有算法,能够有效提高方向约束路径规划问题的求解能力.
关键词:  路径搜索  A*算法  转弯约束  角度约束
DOI:10.13195/j.kzyjc.2016.1134
分类号:TP18
基金项目:国家自然科学基金项目(61573283).
A* algorithm based on direction constraints
LI Chong,ZHANG An,BI Wen-hao
(School of Electronics and Information,Northwestern Polytechnical University,Xián710072,China)
Abstract:
The turning constraint and start/goal angle constraint are often needed to be considered in the actual robot path planning problem, and the A* algorithm based on direction constraints is proposed in this paper. Paths in the same path point are distinguished by their different directions in the algorithm, and the direction constraints of paths are met by the directional extension mechanism, while the node merging strategy and the inconsistent list are adopted to reduce the algorithm complexity. Theoretical analysis and experimental results on the typical map set show that the propoved algorithm can always guarantee to give the shortest path which conforms to the turning constraint and start/goal angle constraint. Compared with the existing algorithms, the proposed algorithm can improve the ability of solving path planning problem with direction constraints effectively.
Key words:  path search  A* algorithm  turning constraint  angle constraint

用微信扫一扫

用微信扫一扫