.png){kind=icon}
返回
CBSS: A New Approach for Multiagent Combinatorial Path Finding
.png){kind=icon}
PRE
AI
DOI：10.1109/TRO.2023.3266993.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Conventional multiagent path finding (MAPF) problems aim to compute an ensemble of collision-free paths for multiple agents from their respective starting locations to preallocated destinations. This article considers a generalized version of MAPF called multiagent combinatorial path finding, where agents must collectively visit a large number of intermediate target locations along their paths before arriving at destinations. This problem involves not only planning collision-free paths for multiple agents but also assigning targets and specifying the visiting order for each agent (i.e., target sequencing). To solve the problem, we leverage conflict-based search (CBS) for MAPF and propose a novel approach called conflict-based Steiner search (CBSS). CBSS interleaves 1) the collision resolution strategy in CBS to bypass the curse of dimensionality in MAPF and 2) multiple traveling salesman algorithms to handle the combinatorics in target sequencing, to compute optimal or bounded suboptimal paths for agents while visiting all the targets. We also develop two variants of CBSS that trade off runtime against solution optimality. Our test results verify the advantage of CBSS over the baselines in terms of computing cheaper paths and improving success rates within a runtime limit for up to 20 agents and 50 targets. Finally, we run both Gazebo simulation and physical robot tests to validate that the planned paths are executable.
Keyword:
Robots
Task analysis
Sequential analysis
Search problems
Collision avoidance
Planning
Costs
Multiagent path finding (MAPF)
path planning for multiple mobile robots or agents
traveling salesman problem (TSP)
期刊
IF:
10.5
论文数:
3.3K
被引数:
2.8W
机构
引用论文
.png){kind=icon}
Today's Traveling Salesmen Problem Heterogeneous, Multiple Depot, Multiple UAV Routing Problem当今旅行商问题异构、多仓库、多无人机路由问题
PREAI
分享收藏Electronic excitations during grazing scattering of hydrogen atoms on KI(001) and LiF(001) surfaces
PREAI
分享收藏
查看更多内容