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

doi:10.12263/DZXB.20210718

摘要/Abstract

摘要：

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

中图分类号:

TP242

宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A*算法[J]. 电子学报, 2022, 50(8): 1943-1950.

Zhi-wei XUAN, Jian-lin MAO, Kai-xiang ZHANG . Low-Expansion A* Algorithm Based on CBS Framework for Complex Map[J]. Acta Electronica Sinica, 2022, 50(8): 1943-1950.

图/表 16

参考文献 18

1	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.
2	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.
3	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.
4	王保防, 张瑞雷, 郭健, 等. 纵向打滑状态下的轮式移动机器人编队控制[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)
5	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.
6	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.
7	SHARON G, STERN R, FELNER A, et al. Conflict-based search for optimal multi-agent pathfinding[J]. Artificial Intelligence, 2015, 219: 40-66.
8	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.
9	王乐乐, 眭泽智, 蒲志强, 等. 一种改进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)
10	尹高扬, 周绍磊, 吴青坡. 基于改进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)
11	马小陆, 梅宏. 基于改进势场蚁群算法的移动机器人全局路径规划[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)
12	DORIGO M, BIRATTARI M, STUTZLE T. Ant colony optimization[J]. IEEE computational intelligence magazine, 2006, 1(4): 28-39.
13	许凯波, 鲁海燕, 黄洋, 等. 基于双层蚁群算法和动态环境的机器人路径规划方法[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)
14	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.
15	GOLDENBERG M, FELNER A, STERN R, et al. Enhanced partial expansion A[J]. Journal of Artificial Intelligence Research, 2014, 50: 141-187.
16	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.
17	CHEW L P. Constrained delaunay triangulations[J]. Algorithmica, 1989, 4(1): 97-108.
18	STURTEVANT N R. Benchmarks for grid-based pathfinding[J]. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4(2): 144-148.

算法	运行时间/ms	节点拓展数量	路径长度
A*算法	40.98	598	62
Tie-Breaking A*算法	8.91	181	62
LEADTOC算法	16.13	178	62

算法	运行时间/ms	节点拓展数量	路径长度
A*算法	40.98	598	62
Tie-Breaking A*算法	8.91	181	62
LEADTOC算法	16.13	178	62

算法	运行时间/ms	节点拓展数量	路径长度
A*算法	610.46	12 763	415
Tie-Breaking A*算法	616.72	12 763	415
LEADTOC算法	99.97	1 265	411

算法	运行时间/ms	节点拓展数量	路径长度
A*算法	610.46	12 763	415
Tie-Breaking A*算法	616.72	12 763	415
LEADTOC算法	99.97	1 265	411

地图名称	地图大小	算例数量
den520d	257×256	269
den312d	81×65	121
lak303d	194×194	474
ht_0_hightown_a3	514×514	179
lt_undercitydungeon	177×184	312
lt_foundry_n	92×109	202
8room_000	512×512	1 607
16room_000	512×512	1 839
32room_000	512×512	1 658
darkforest	512×512	494