Abstract
Resource constraints frequently complicate multi-agent planning problems. Existing algorithms for resource-constrained, multi-agent planning problems rely on the assumption that the constraints are deterministic. However, frequently resource constraints are themselves subject to uncertainty from external influences. Uncertainty about constraints is especially challenging when agents must execute in an environment where communication is unreliable, making on-line coordination difficult. In those cases, it is a significant challenge to find coordinated allocations at plan time depending on availability at run time. To address these limitations, we propose to extend algorithms for constrained multi-agent planning problems to handle stochastic resource constraints. We show how to factorize resource limit uncertainty and use this to develop novel algorithms to plan policies for stochastic constraints. We evaluate the algorithms on a search-and-rescue problem and on a power-constrained planning domain where the resource constraints are decided by nature. We show that plans taking into account all potential realizations of the constraint obtain significantly better utility than planning for the expectation, while causing fewer constraint violations.
Introduction
In many multi-agent systems, agents must share a limited pool of resources, such as bandwidth, battery power, or physical space. Traditional planning models, such as Multi-agent Markov Decision Processes (MMDPs), typically assume deterministic resource constraints. However, real-world resource levels are often unpredictable: solar energy depends on cloud cover, and network capacity fluctuates with external traffic.
This unpredictability is particularly problematic when agents cannot communicate in real-time due to interference or distance. If agents independently plan based on the "average" expected resource, they risk collective over-consumption during periods of low availability, leading to system failure. Conversely, overly conservative planning wastes utility. This work addresses the challenge of "preallocating" resource usage policies at plan-time so agents can act independently and safely during execution.
Methodology: Stochastic Resource-Constrained MMDPs
The authors introduce the Stochastic Resource-Constrained Multi-agent Markov Decision Process (SRC-MMDP). The key innovation is factoring the uncertain resource limit into a separate, exogenous Markov Chain integrated into the state space. By observing this "resource state" (e.g., current weather conditions), agents can adjust their behavior locally without explicit communication.
Two primary algorithmic approaches are developed:
- Preallocation MILP (Mixed Integer Linear Program): A "safety-first" approach that computes deterministic resource assignments. It guarantees that agents' combined actions never violate the hard constraint, regardless of the realized resource level.
- Constrained MDP (CMDP): A "performance-first" approach that relaxes hard constraints to be met in expectation. This linear programming formulation is significantly more scalable than the MILP, though it allows for occasional violations.
Additionally, a replanning scheme is proposed for intermittent communication scenarios, allowing agents to synchronize and update policies whenever a connection is available.
Experimental Evaluation
The algorithms were tested on two domains:
- Coordinated Search and Rescue (SAR): A single-step problem where agents commit rescue teams to a disaster based on a resource limit revealed only at mission time.
- Thermostatically Controlled Loads (TCLs): A long-horizon energy management problem where heaters maintain temperatures while staying under a fluctuating power limit from renewable energy.
Key Insights: The Flaw of Averages
A central finding is that planning for the mean resource level ($E(X)$) is often suboptimal. As shown in Figure 1, policies that consider the full distribution of resource levels ($P(X=x)$) achieve higher utility and significantly lower over-capacity frequencies compared to expectation-based planning.
By augmenting the state with the resource limit, agents achieve "implicit coordination." They react to the same external signal, allowing them to remain synchronized without active communication.
Key Results and Scalability
The experiments demonstrate a clear trade-off between safety and tractability. While the MILP provides worst-case guarantees, its complexity grows exponentially with the number of resource levels. In contrast, the CMDP approach scales polynomially.
As illustrated in Figure 2, the CMDP approach maintains near-linear scaling for both the number of agents and the planning horizon, whereas the MILP approach fails to scale beyond short horizons. Furthermore, even infrequent communication (e.g., every 16 steps) was found to drastically reduce violations when using stochastic-aware policies.
Conclusion
This research highlights the importance of accounting for resource uncertainty in multi-agent planning. The proposed SRC-MMDP framework and associated algorithms provide a path toward more robust systems in unpredictable environments. While the MILP approach offers safety guarantees for small-scale problems, the CMDP approach provides a scalable alternative for larger systems. Future work will explore Lagrangian decomposition to improve MILP scaling and methods to bound violation probabilities within the CMDP framework.
Summary updated