Multi-robot systems prevail over the past decade. In particular, these systems provide an intelligent and automated solution for material transportation and information collection in smart warehouse, unmanned factories, automated ports, and many other potential scenarios. A fundamental problem in these applications is to tell the robots where they should go and how to arrive their target locations as quick as possible, namely, plan collision-free paths for the robots while minimizing their arrival times.
Exact Algorithms for MCPF
Conventionally, Multi-Agent Path Finding (MAPF) seeks an ensemble of collision-free paths for multiple agents from their respective start locations to their respective goal locations while minimizing a cost function defined over the paths. Here, we consider a generalization of MAPF where the agents must also visit a given set of intermediate target locations before reaching their goals. We refer to this generalization as Multi-Agent Combinatorial Path Finding (MCPF), which aims to find “start-target-goal” paths for the agents rather than the “start-goal” paths as in MAPF. MCPF is quite challenging as it requires both collision avoidance between agents (as present in MAPF), and target sequencing, i.e., solving Multiple Traveling Salesman Problem (MTSP) to specify the allocation and visiting orders of targets for all agents. MCPF requires handling both collision avoidance and target sequencing simultaneously, which has rarely been addressed before by MAPF or MTSP research. Both the MTSP and the MAPF are NP-hard to solve to optimality, and so is MCPF.
To handle the challenges, we develop a family of algorithms [1], [2] to find optimal, bounded sub-optimal and sub-optimal solutions to MCPF by leveraging the recent advances in both MAPF and MTSP. The main idea behind our approaches is to interleave MTSP and MAPF approaches in a princiipled way in order to provide solution quality guarantees. Our approach alternates between generating target sequences for the robots by (i) solving a MTSP where the collision avoidance constraint is relaxed, and (ii) generating collision-free paths for agents while fixing the target sequences. We instantiate this idea within the framework of dynamic programming and branch and bound, which leads to CBSS [1] and MS* [2], exact algorithms that can find optimal solutions for MCPF.
Bounded Sub-optimal Approach for MCPF
TODO
MCPF with Heterogeneous Task Duration
So far, our problem formulation and approaches simply direct the agent to visit the targets without considering the task duration, i.e., the amount of time needed for an agent to execute the task (such as picking an item) at a target location. In other words, when a robot reaches a target location to execute the task there, it takes time for the robot to finish the task, and during this period, the robot has to occupy that target location and thus blocks the paths of other agents. The inclusion of task duration further complicates the problem. When sequencing the targets, the task duration must be considered when solving the TSPs to optimally allocating the targets and finding the visiting order. Furthermore, task duration can be heterogeneous with respect to the agents and targets: different agents may take different duration for the task at the same target, and for the same agent, different targets may require different duration.
To tackle this challenge, we develop two methods. The first method post-processes the paths planned by any MCPF planner to include the task duration and has no solution optimality guarantee. It builds a temporal planning graph (TPG) that captures the precedence requirement between the waypoints along the agents’ paths, and then add the task duration to the target locations while maintaining the precedence requirement to avoid agent-agent collision. While being able to take advantage of any existing planner for MCPF, this first method only finds a sub-optimal solution to MCPF-D and the solution cost can be far away from the true optimum especially in the presence of large task duration. We instantiate this method by using our prior CBSS as the MCPF planner and name the resulting algorithm CBSS-TPG.
To find an optimal solution for MCPF-D, we develop our second method called Conflict-Based Steiner Search with Task Duration (CBSS-D), which is similar to CBSS by interleaving target sequencing and path planning. Here, CBSS-D needs to consider task duration during planning, and there are two main differences between CBSS-D and CBSS. First, CBSS-D needs to solve TSPs with task duration to find optimal target sequences for the agents to visit, and thus modifies the target sequencing part in CBSS. Second, when an agent-agent collision is detected during path planning, CBSS-D introduces a new branching rule, which is based on the task duration, to resolve the collision more efficiently than using the basic branching rule in CBSS. The numerical and simulation results show that our methods can handle up to 20 agents and 50 targets in the presence of task duration, and can execute the paths subject to robot motion disturbance.
