Multi-agent Path Planning in Unidirectional Environments

In this paper we focus on the optimal multi-agent path planning, which is an NP-complete problem. To solve this task, we will use centralized A* search algorithm for which we propose a new heuristic. To construct our proposed heuristic, we examine the solution of multi-agent path planning via its reduction to multi-commodity flow, which is also an NP-complete problem. Our heuristic is based on relaxation of multi-commodity flow to single-commodity flow that can be solved in polynomial time. We show that this new heuristics is admissible and consistent. We also show types of problems for which our heuristic is more successful than other heuristics. Powered by TCPDF (www.tcpdf.org