Certifying agent groups to improve multi-agent coordination planning
Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs
Multiagent Systems
Summary
Planning how multiple agents interact can be tricky because agents far apart might still need to coordinate later, and some rewards from cooperation can be hard to reach. The authors propose a method called Reachability-Certified Subteam Decomposition (RCSD) that uses information about how fast agents can move toward each other and how valuable their cooperation might be. This method helps group agents so that calculating joint plans becomes easier while keeping the plans close to optimal. Their experiments show RCSD reduces planning errors compared to simpler methods and can be efficiently applied to systems with many agents.
multi-agent systemsMarkov decision processesagent coordinationreward decompositionreachabilitypolicy regretstate-feedback policiespersistent communicationsubteam decomposition
Authors
Xiangwu Wang, Chengwei Cao, Hongyuan Tang
Abstract
Persistent communication limits force a multi-agent system to decide which agents may coordinate throughout a rollout. Current proximity alone is insufficient: separated agents may interact later, whereas a large pair reward may remain unreachable until it is heavily discounted. We introduce Reachability-Certified Subteam Decomposition (RCSD) for finite multi-agent Markov decision processes with factorized physical dynamics, finite-range ordered pair rewards, and almost-sure motion bounds. RCSD combines a speed-limit lower bound on pairwise contact time with a reward envelope to form a current-state affinity. For any capacity-valid persistent partition, the sum of cut affinities bounds the reward-deletion error of every unchanged stationary Markov state-feedback policy. A product of team-optimal policies for the resulting cut MDP incurs at most twice this certificate in regret against the centralized optimum. Both bounds are worst-case tight. On a controlled five-agent family, RCSD-Exact reduces aggregate normalized execution regret by 56.0%, 28.8%, and 25.3% relative to uniform, distance-only, and envelope-only partitions. A separate stochastic two-dimensional study finds no bound violation over 384 exact-partition and 1,440 restricted-controller evaluations. Exact four-agent evidence favors RCSD over uniform and distance-only grouping; raw evidence for current contact is borderline and envelope-only is unresolved. Across balanced 8-20-agent strata, controller-library utility is mixed: pointwise paired intervals favor RCSD over distance and current contact, include zero for uniform, and favor envelope-only and Value-MIP over RCSD. Partition construction remains subsecond in median up to 100 agents; this last result does not include affinity formation or MDP planning.