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

XUAN Zhi-wei; MAO Jian-lin; ZHANG Kai-xiang

doi:10.12263/DZXB.20210718

您当前的位置：

首页 >

文章列表页 >

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

PAPERS | 更新时间：2025-12-08

- Low-Expansion A* Algorithm Based on CBS Framework for Complex Map
- ACTA ELECTRONICA SINICA Vol. 50, Issue 8, Pages: 1943-1950(2022)
- 作者机构：
  
  1.昆明理工大学信息工程与自动化学院，云南昆明 650500
  2.昆明理工大学机电工程学院，云南昆明 650500
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20210718
  CLC： TP242;
- Received：06 June 2021，
  
  Revised：2021-07-23，
  
  Published：25 August 2022
- 稿件说明：
移动端阅览
宣志玮,毛剑琳,张凯翔.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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Dynamic Path Planning for Mobile Robot Based on Improved Ant Colony Optimization Algorithm

Mobile Robot Path Planning Based on Fuzzy Algorithms

A Knowledge Based Genetic Algorithm for Path Planning of a Mobile Robot

Robot Path Planning Based on Double-Layer Ant Colony Optimization Algorithm and Dynamic Environment

Related Author

Zhi-wei XUAN

Jian-lin MAO

Kai-xiang ZHANG

LIU Chang-an

YAN Xiao-hu

LIU Chun-yang

WU Hua

CHEN Wei-dong

Related Institution

Faculty of Information Engineering and Automation， Kunming University of Science and Technology

Faculty of Mechanical and Electrical Engineering， Kunming University of Science and Technology

School of Control and Computer Engineering, North China Electric Power University

Information Institute,Yanshan University

School of Computer Science and Technology, Harbin Institute of Technology

⁰