Congestion-Aware Path Coordination Game With Markov Decision Process Dynamics

Abstract

Inspired by the path coordination problem arising from robo-taxis, warehouse management, and mixed-vehicle routing, we model a group of heterogeneous players responding to stochastic demands as a congestion game under Markov decision process dynamics. Players share a common state-action space but have unique transition dynamics, and each player’s unique cost is a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">function</i> of the joint state-action probability distribution. For a class of player cost functions, we formulate the player-specific optimization problem, prove equivalence between the Nash equilibrium and the solution of a potential minimization problem, and derive dynamic programming approaches to solve the Nash equilibrium. We apply this game to model multi-agent path coordination and introduce congestion-based cost functions that enable players to complete individual tasks while avoiding congestion with their opponents. Finally, we present a learning algorithm for finding the Nash equilibrium that has linear complexity in the number of players. We demonstrate our game model on a multi-robot warehouse path coordination problem, in which robots autonomously retrieve and deliver packages while avoiding congested paths.