2024/10/23 by Casselman, Adam, Li, Sarah H. Q., Abraham P. Vinod +2 · 1 citation
Decision Sciences · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Electrical engineering #Multiagent Systems (cs.MA) #Robotics (cs.RO) #Simulation Techniques and Applications #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2410.17690
openalex publication_date 2024/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We optimize finite horizon multi-agent reach-avoid Markov decision process (MDP) via local feedback policies. The global feedback policy solution yields global optimality but its communication complexity, memory usage and computation complexity scale exponentially with the number of agents. We mitigate this exponential dependency by restricting the solution space to local feedback policies and show that local feedback policies are rank-one factorizations of global feedback policies, which provides a principled approach to reducing communication complexity and memory usage. Additionally, by demonstrating that multi-agent reach-avoid MDPs over local feedback policies has a potential game structure, we show that iterative best response is a tractable multi-agent learning scheme with guaranteed convergence to deterministic Nash equilibrium, and derive each agent's best response via multiplicative dynamic program (DP) over the joint state space. Numerical simulations across different MDPs and agent sets show that the peak memory usage and offline computation complexity are significantly reduced while the approximation error to the optimal global reach-avoid objective is maintained.