CBSS: A New Approach for Multiagent Combinatorial Path Finding

摘要

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.