Centralized Periodic Planning under Asynchronous Communication for Multi-Agent Monitoring
David Fornos, Federico Rossi, Dylan Shell, Daniel Selva
AI summary
Problem
Existing multi-agent planning frameworks assume flexible mobility or continuous communication, making them unsuitable for systems like UAV swarms and satellite constellations that follow fixed periodic trajectories and only communicate asynchronously. This gap leaves a critical need for coordination methods that handle delayed information flow and partial observability between periodic sync windows.
Approach
The authors formalize the problem as a Multi-Agent Asynchronous Periodic Partially Observable MDP (MA-APPOMDP) and propose two open-loop planning algorithms: an exact belief-branching method (ABBA) and a scalable sampling-based approximation (SB-ABBA) that optimizes sensor footprints over fixed patrol cycles.
Key results
- Formalization of the MA-APPOMDP framework for asynchronous periodic planning
- Development of ABBA, an exact open-loop planner branching over uncertain observations
- Development of SB-ABBA, a sampling-based approximation enabling scalability
- Empirical demonstration of higher event coverage and lower detection delay than baselines on wildfire monitoring tasks
Why it matters
It provides a tractable planning foundation for resource-constrained multi-agent systems like UAV swarms and satellite constellations, directly improving response times for disaster monitoring and environmental surveillance.
Abstract
This paper examines the problem of coordinating the observations of multiple agents constrained to periodic trajectories that communicate asynchronously with a central planner. We are motivated by settings such as active monitoring missions tracking stochastic and spatially spreading events like wildfires or flooding, where a rapid response is essential and the spatial extent can be large. In such cases, “always-on” networking may be infeasible and continuous coordination may be prohibitively costly. Periodic trajectories are a natural constraint for relevant classes of systems, e.g., UAV swarms that cycle around recharging stations or Earth observation satellite constellations; moreover, these lead to recurring com- munication opportunities with compute-capable infrastructure. We introduce the Multi-Agent Asynchronous Periodic Partially Observable MDP (MA-APPOMDP), a new planning framework that formalizes asynchronous check-in times and centralized but delayed information flow. We propose two algorithms tailored to this new model: the Asynchronous Belief Branching Algorithm (ABBA), which performs exact belief branching over unknown observations, and SB-ABBA, a sampling-based approximation where scalability is prioritized over exactness. Empirical results on different wildfire event monitoring problems show that our methods consistently achieve higher event coverage and lower detection delay than several heuristic and planning baselines, with SB-ABBA scaling to larger problem instances.