.png){kind=icon}
返回
CTS-CBS: A New Approach for Multiagent Collaborative Task Sequencing and Path Finding
.png){kind=icon}
PRE
AI
DOI：10.1109/JIOT.2026.3663569.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This article addresses a generalization problem of multiagent pathfinding (MAPF), called collaborative task sequencing—MAPF (CTS-MAPF), where agents must plan collision-free paths and visit a series of intermediate task locations in an optimized order before reaching their final destinations. To address this problem, we propose a new approach, collaborative task sequencing—conflict-based search (CTS-CBS), which conducts a two-level search. At the high level, it generates a search forest, where each tree corresponds to a joint task sequence derived from the joint-traveling salesman problem (jTSP) solution. At the low level, CTS-CBS performs constrained single-agent path planning to generate paths for each agent while adhering to high-level constraints. Furthermore, we integrate explicit estimation search (EES) into CTS-CBS to enhance the search efficiency. We also provide theoretical guarantees of its solution completeness and optimality (or suboptimality with a bounded parameter). To evaluate the performance of CTS-CBS, we utilize three datasets with different map sizes, map difficulty, and agent/task numbers, and conduct comprehensive experiments. The results show that our algorithms demonstrate significant improvements in success rate and runtime, while maintaining competitive solution quality. Finally, practical robot simulation and tests demonstrate the algorithm’s applicability in real-world scenarios.
Keyword:
Conflict-based search (CBS)
integrated task sequencing and path planning
multiagent collaborative task sequencing
multiagent path finding (MAPF)
期刊
IF:
8.9
论文数:
1.4W
被引数:
7.8W
机构
引用论文
.png){kind=icon}
Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree使用单一约束树解决多智能体目标分配与路径规划问题
OAAI
OAAI分享收藏4WIDS-MAPF: Multiagent Pathfinding for Four-Wheel Independent Drive/Steering Robots4WIDS-MAPF: 四轮独立驱动/转向机器人多智能体路径规划
PREAI
分享收藏分享收藏
查看更多内容