A Hierarchical Approach for Joint Task Allocation and Path Planning

This letter addresses the joint task allocation and path planning problem, whereby a fleet of vehicles must be optimally assigned to service multiple given tasks while their planned paths must be collision-free. Such a problem composed of two tightly coupled optimization problems has a high complexity with the number of tasks and the number of vehicles, thus optimal solvers do not scale to large size instances. Therefore, we propose a novel method to solve this problem, HTAPPS, which introduces a hierarchical resolution framework. Our proposed approach decomposes a given instance into three levels of abstractions and associated amount of details that progressively filter the search space. This allows us to reduce the computational effort required when performing task allocation and multi-agent path planning jointly. We perform simulations on automated warehouse scenarios, and compare our approach to baseline solvers. The obtained results show that our proposed approach is able to solve large size instances within a limited time.