Congestion-Aware Multi-Agent Path Planning: Distributed Algorithm and Applications

This paper proposes a method for multi-agent path planning on a road network in the presence of congestion. We suggest a distributed method to find paths for multiple agents by introducing a probabilistic path choice achieving global goals such as the user equilibrium or the social optimum. This approach, which shows that the global goals can be achieved by local processing using only local information, can be parallelized and sped-up using massive parallel processing. The probabilistic assignment reliably copes with the case of random choices of unidentified agents or random route changes of agents who ignore our path guidance. We provide the analytical result on convergence and running time. We demonstrate and evaluate our algorithm by an implementation using asynchronous computation on multi-core computers.