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

宣志玮; 毛剑琳; 张凯翔

doi:10.12263/DZXB.20210718

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-12-08

- CBS框架下面向复杂地图的低拓展度A*算法
- Low-Expansion A* Algorithm Based on CBS Framework for Complex Map
- 电子学报 2022年50卷第8期页码：1943-1950
- 作者机构：
  
  1.昆明理工大学信息工程与自动化学院，云南昆明 650500
  2.昆明理工大学机电工程学院，云南昆明 650500
- 作者简介：
  
  [ "宣志玮男，1995年12月出生，云南蒙自人.昆明理工大学信息工程与自动学院硕士研究生.主要研究方向为机器人路径规划.E-mail: rangxuan@foxmail.com" ]
  [ "毛剑琳（通讯作者）女，1976年5月出生，广西桂林人.昆明理工大学教授，博士生导师.主要研究方向为通信网络资源分配与协议优化、网络化控制系统研究、智能优化及调度算法研究等." ]
  [ "张凯翔男，1993年10月出生，浙江台州人.昆明理工大学机电工程学院博士研究生.主要研究方向为机器人路径规划.E-mail: zhangkaixiang@stu.kust.edu.cn" ]
- 基金信息：
  
  云南省重大科技专项计划项目(202002AC080001)
- DOI：10.12263/DZXB.20210718
  中图分类号： TP242;
- 收稿：2021-06-06，
  
  修回：2021-07-23，
  
  纸质出版：2022-08-25
- 稿件说明：
移动端阅览
宣志玮,毛剑琳,张凯翔.CBS框架下面向复杂地图的低拓展度A*算法[J].电子学报,2022,50(08):1943-1950.

XUAN Zhi-wei,MAO Jian-lin,ZHANG Kai-xiang.Low-Expansion A* Algorithm Based on CBS Framework for Complex Map[J].ACTA ELECTRONICA SINICA,2022,50(08):1943-1950.
宣志玮,毛剑琳,张凯翔.CBS框架下面向复杂地图的低拓展度A*算法[J].电子学报,2022,50(08):1943-1950. DOI： 10.12263/DZXB.20210718.

XUAN Zhi-wei,MAO Jian-lin,ZHANG Kai-xiang.Low-Expansion A* Algorithm Based on CBS Framework for Complex Map[J].ACTA ELECTRONICA SINICA,2022,50(08):1943-1950. DOI： 10.12263/DZXB.20210718.

摘要

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

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%.

关键词

Keywords

references

MA H , LI J Y , KUMAR T K S , et al . Lifelong multi-agent path finding for online pickup and delivery tasks [C]// AAMAS'17: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems . São Paulo, Brazil : IFAAMAS Press , 2017 : 837 - 845 .

LI J Y , Sun K X , MA H , et al . Moving agents in formation in congested environments [C]// AAMAS'20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems . Auckland, New Zealand : IFAAMAS Press , 2020 : 726 - 734 .

HO F , SALTA A , GERALDES R , et al . Multi-agent path finding for UAV traffic management [C]// AAMAS'19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems . Montreal, Canada : IFAAMAS Press , 2019 : 131 - 139 .

王保防 , 张瑞雷 , 郭健 , 等 . 纵向打滑状态下的轮式移动机器人编队控制 [J]. 电子学报 , 2017 , 45 ( 1 ): 206 - 212 .

WANG B F , ZHANG R L , GUO J , et al . Formation control for car-like mobile robots under slip conditions [J]. Acta Electronica Sinica , 2017 , 45 ( 1 ): 206 - 212 . (in Chinese)

HART P E , NILSSON N J , RAPHAEL B . A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transactions on Systems Science and Cybernetics , 1968 , 4 ( 2 ): 100 - 107 .

SURYNEK P , FELNER A , STERN R , et al . Efficient SAT approach to multi-agent path finding under the sum of costs objective [C]// ECAI'16: Proceedings of the Twenty-second European Conference on Artificial Intelligence . The Hague, Netherlands : IOS Press , 2016 : 810 - 818 .

SHARON G , STERN R , FELNER A , et al . Conflict-based search for optimal multi-agent pathfinding [J]. Artificial Intelligence , 2015 , 219 : 40 - 66 .

SHARON G , STERN R , GOLDENBERG M , et al . The increasing cost tree search for optimal multi-agent pathfinding [J]. Artificial Intelligence , 2013 , 195 : 470 - 495 .

王乐乐 , 眭泽智 , 蒲志强 , 等 . 一种改进RRT的多机器人编队路径规划算法 [J]. 电子学报 , 2020 , 48 ( 11 ): 2138 - 2145 .

WANG L L , SUI Z Z , PU Z Q , et al . An improved RRT algorithm for multi-robot formation path planning [J]. Acta Electronica Sinica , 2020 , 48 ( 11 ): 2138 - 2145 . (in Chinese)

尹高扬 , 周绍磊 , 吴青坡 . 基于改进RRT算法的无人机航迹规划 [J]. 电子学报 , 2017 , 45 ( 7 ): 1764 - 1769 .

YIN G Y , ZHOU S L , WU Q P . An improved RRT algorithm for UAV path planning [J]. Acta Electronica Sinica , 2017 , 45 ( 7 ): 1764 - 1769 . (in Chinese)

马小陆 , 梅宏 . 基于改进势场蚁群算法的移动机器人全局路径规划 [J]. 机械工程学报 , 2021 , 57 ( 1 ): 19 - 27 .

MA X L , MEI H . Mobile robot global path planning based on improved ant colony system algorithm with potential field [J]. Journal of Mechanical Engineering , 2021 , 57 ( 1 ): 19 - 27 . (in Chinese)

DORIGO M , BIRATTARI M , STUTZLE T . Ant colony optimization [J]. IEEE computational intelligence magazine , 2006 , 1 ( 4 ): 28 - 39 .

许凯波 , 鲁海燕 , 黄洋 , 等 . 基于双层蚁群算法和动态环境的机器人路径规划方法 [J]. 电子学报 , 2019 , 47 ( 10 ): 2166 - 2176 .

XU K B , LU H Y , HUANG Y , et al . Robot path planning based on double-layer ant colony optimization algorithm and dynamic environment [J]. Acta Electronica Sinica , 2019 , 47 ( 10 ): 2166 - 2176 . (in Chinese)

CORRÊA A B , PEREIRA A G , RITT M . Analyzing Tie-Breaking strategies for the A* algorithm [C]// IJCAI18 ' 19 : Proceedings of the 27th International Joint Conference on Artificial Intelligence . Stockholm, Sweden : AAAI Press , 2018: 4715 - 4721 .

GOLDENBERG M , FELNER A , STERN R , et al . Enhanced partial expansion A [J]. Journal of Artificial Intelligence Research , 2014 , 50 : 141 - 187 .

FELNER A , STERN R , SHIMONY S E , et al . Search-based optimal solvers for the multi-agent pathfinding problem: Summary and challenges [C]// Proceedings of the Tenth International Symposium on Combinatorial Search . Pittsburgh, Pennsylvania, USA : AAAI Press , 2017 : 29 - 37 .

CHEW L P . Constrained delaunay triangulations [J]. Algorithmica , 1989 , 4 ( 1 ): 97 - 108 .

STURTEVANT N R . Benchmarks for grid-based pathfinding [J]. IEEE Transactions on Computational Intelligence and AI in Games , 2012 , 4 ( 2 ): 144 - 148 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于改进蚁群算法的移动机器人动态路径规划方法

基于模糊算法的移动机器人路径规划

用基于知识的遗传算法实现移动机器人路径规划

基于双层蚁群算法和动态环境的机器人路径规划方法