电子学报 ›› 2022, Vol. 50 ›› Issue (8): 1943-1950.DOI: 10.12263/DZXB.20210718

• 学术论文 • 上一篇    下一篇

CBS框架下面向复杂地图的低拓展度A*算法

宣志玮1, 毛剑琳1, 张凯翔2   

  1. 1.昆明理工大学信息工程与自动化学院,云南 昆明 650500
    2.昆明理工大学机电工程学院,云南 昆明 650500
  • 收稿日期:2021-06-06 修回日期:2021-07-23 出版日期:2022-08-25
    • 作者简介:
    • 宣志玮 男,1995年12月出生,云南蒙自人.昆明理工大学信息工程与自动学院硕士研究生.主要研究方向为机器人路径规划.E-mail: rangxuan@foxmail.com
      毛剑琳(通讯作者) 女,1976年5月出生,广西桂林人.昆明理工大学教授,博士生导师.主要研究方向为通信网络资源分配与协议优化、网络化控制系统研究、智能优化及调度算法研究等.
      张凯翔 男,1993年10月出生,浙江台州人.昆明理工大学机电工程学院博士研究生.主要研究方向为机器人路径规划.E-mail: zhangkaixiang@stu.kust.edu.cn
    • 基金资助:
    • 云南省重大科技专项计划项目 (202002AC080001)

Low-Expansion A* Algorithm Based on CBS Framework for Complex Map

XUAN Zhi-wei1, MAO Jian-lin1, ZHANG Kai-xiang2   

  1. 1.Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming,Yunnan 650500,China
    2.Faculty of Mechanical and Electrical Engineering,Kunming University of Science and Technology,Kunming,Yunnan 650500,China
  • Received:2021-06-06 Revised:2021-07-23 Online:2022-08-25 Published:2022-09-08

摘要:

A*算法是机器人路径规划问题中的重要且常用算法之一,在地形复杂的大型地图中,路径点之间的不可视造成A*算法需要大规模节点拓展才能找到可行的优化路径,由此导致算法对存储空间的需求剧增和求解效率的降低.对此,本文针对基于冲突搜索(Conflict-Based Search,CBS)框架下的低层路径规划问题,引入三角剖分方法,给出固定障碍处理方法,融合可视性优化获得相邻点可视的优化路径,在此基础上提出分段策略,令具有动态冲突处理能力的A*算法依相邻可视点进行分段路径规划,最终获得低节点拓展度A*路径规划算法.通过标准地图数据集的仿真实验表明,在复杂地图下本文提出的算法路径长度为A*算法的98.1%~102.2%,节点拓展量降低85.4%,算法求解时间减少58.1%.

关键词: A*算法, 路径规划, Delaunay三角剖分, 移动机器人, 冲突消解

Abstract:

A* algorithm is one of the important and commonly used algorithms in path planning of robots. In large map with complex terrain, large-scale node expansion is needed in A* algorithm to find a feasible optimization path in the case of invisibility between path points. This leads to a sharp increase in the demand for storage space and a decrease in running efficiency of the algorithm. To solve low-level path planning problems based on CBS(Conflict-Based Search) framework, an A* path planning algorithm with low node expansion is proposed. Triangulation method and fixed obstacle processing method are introduced to obtain an optimized path that is visible to adjacent points. Moreover, a segmentation strategy is proposed based on integrated visibility optimization to plan the segmented path according to the adjacent visible points with dynamic collision processing ability. Simulation experiments on standard map data sets under complex terrain show that the path length of the proposed algorithm in this paper is 98.1%~102.2% as long as that of A* algorithm, compared with which, the amount of node expansion reduces by 85.4% and the running time of algorithm reduces by 58.1%.

Key words: A* algorithm, path planning, Delaunay triangulation, mobile robot, conflict resolution

中图分类号: