Graph Coloring to Reduce Computation Time in Prioritized Planning

arXiv (Cornell University)

Abstract

Distributing computations among agents in large networks reduces computational effort in multi-agent path finding (MAPF). One distribution strategy is prioritized planning (PP). In PP, we couple and prioritize interacting agents to achieve a desired behavior across all agents in the network. We characterize the interaction with a directed acyclic graph (DAG). The computation time for solving MAPF problem using PP is mainly determined through the longest path in this DAG. The longest path depends on the fixed undirected coupling graph and the variable prioritization. The approaches from literature to prioritize agents are numerous and pursue various goals. This article presents an approach for prioritization in PP to reduce the longest path length in the coupling DAG and thus the computation time for MAPF using PP. We prove that this problem can be mapped to a graph-coloring problem, in which the number of colors required corresponds to the longest path length in the coupling DAG. We propose a decentralized graph-coloring algorithm to determine priorities for the agents. We evaluate the approach by applying it to multi-agent motion planning (MAMP) for connected and automated vehicles (CAVs) on roads using, a variant of MAPF.

Authors 3

1. Patrick Scheffe Aachen Chair of Embedded Software

   RWTH Aachen University

   Affiliation as printed

   Chair of Embedded Software , RWTH Aachen University , Im Süsterfeld 9 , 52072 Aachen , Germany

2. Julius Kahle Aachen Chair of Embedded Software

   RWTH Aachen University

   Affiliation as printed

   Chair of Embedded Software , RWTH Aachen University , Im Süsterfeld 9 , 52072 Aachen , Germany

3. Bassam Alrifaee

   Universität der Bundeswehr München

   Affiliation as printed

   Department of Aerospace Engineering , University of the Bundeswehr Munich , Werner-Heisenberg-Weg 39 , 85579 Neubiberg , Germany