Adaptive Neighborhood Resizing for Stochastic Reachability in Multi-Agent Systems
For multi-agent systems requiring efficient stochastic reachability, DAMPC offers a practical trade-off between speed and convergence.
DAMPC, a distributed adaptive-horizon and adaptive-neighborhood algorithm, solves stochastic reachability in multi-agent flocking, achieving up to two-fold speed-up over AMPC with only slightly lower convergence rate.
We present DAMPC, a distributed, adaptive-horizon and adaptive-neighborhood algorithm for solving the stochastic reachability problem in multi-agent systems, in particular flocking modeled as a Markov decision process. At each time step, every agent calls a centralized, adaptive-horizon model-predictive control (AMPC) algorithm to obtain an optimal solution for its local neighborhood. Second, the agents derive the flock-wide optimal solution through a sequence of consensus rounds. Third, the neighborhood is adaptively resized using a flock-wide, cost-based Lyapunov function V. This way DAMPC improves efficiency without compromising convergence. We evaluate DAMPC's performance using statistical model checking. Our results demonstrate that, compared to AMPC, DAMPC achieves considerable speed-up (two-fold in some cases) with only a slightly lower rate of convergence. The smaller average neighborhood size and lookahead horizon demonstrate the benefits of the DAMPC approach for stochastic reachability problems involving any controllable multi-agent system that possesses a cost function.