  Multi-Agent Combinatorial Path Finding (MCPF) seeks collision-free paths for
multiple agents from their initial locations to destinations, visiting a set of
intermediate target locations in the middle of the paths, while minimizing the
sum of arrival times. While a few approaches have been developed to handle
MCPF, most of them 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. MCPF is
NP-hard to solve to optimality, and the inclusion of task duration further
complicates the problem. This paper investigates heterogeneous task duration,
where the duration can be different with respect to both the agents and
targets. We develop two methods, where the first method post-processes the
paths planned by any MCPF planner to include the task duration and has no
solution optimality guarantee; and the second method considers task duration
during planning and is able to ensure solution optimality. 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.
