Decentralized Planning for Non-dedicated Agent Teams with Submodular Rewards in Uncertain Environments

Pritee Agrawal, Pradeep Varakantham, William YeohUAI 2018 · OpenReview

Abstract

This paper addresses the challenge of decentralized planning for multi-agent teams where members may unexpectedly depart. By exploiting submodularity in reward functions, we develop efficient greedy algorithms that allow remaining agents to reconfigure plans in real-time. Our proposed methods achieve over 90% of optimal performance with millisecond-level latency, significantly outperforming traditional offline approaches in scalability and responsiveness.

Introduction

In many real-world multi-agent scenarios, such as disaster rescue or security patrolling, agents are not always "dedicated" to a single task for the entire mission. Agents may leave the team due to mechanical failure, battery depletion, or reassignment to higher-priority emergencies. Traditional models like Decentralized Markov Decision Processes (Dec-MDPs) typically assume a fixed team composition. When agents leave, the remaining team must adapt to cover gaps. However, finding an optimal new plan is NEXP-complete, making it impossible to re-solve from scratch during a mission. Existing offline approaches that account for every possible exit scenario fail to scale as the number of agents or targets grows.

Methodology: Submodular ND-TI-Dec-MDP

We introduce the Submodular ND-TI-Dec-MDP (Non-Dedicated Transition Independent Decentralized MDP) framework. The core innovation lies in leveraging submodularity—the principle of diminishing returns where adding an agent to a small team provides a larger reward boost than adding one to a large team.

We propose three algorithmic approaches:

  1. ND-GREEDY: An online approach using "Lazy Greedy" optimization to re-solve the problem upon agent departure.
  2. OFFLINE-GREEDY: A sampling-based approach that creates a robust joint policy based on various "what-if" scenarios of agent availability.
  3. OFFLINE-ONLINE: Our primary contribution. This method generates multiple randomized "selection orders" (agent rankings) offline. During execution, the system instantly selects the best pre-computed order fitting the remaining team, moving the computational burden to the pre-mission phase.

Experimental Evaluation

The methods were evaluated on two main benchmarks: Security Games, involving metro rail network defense, and Sensor Networks, involving grid-based target tracking. The researchers utilized 1,500 samples of agent availability to create rigorous training and testing datasets.

Key Results

Experiments demonstrate that the Offline-Online approach offers the optimal balance of quality and speed.

Average Team Utility across varying numbers of agents and targets. The proposed Offline-Online method performs comparably to computationally intensive benchmarks.

As shown in Figure 1, the proposed methods achieved utility nearly identical to the "Offline Optimal" (Dec-OPT) benchmark. Crucially, while re-solving a plan (Dec-O-Rev) can take up to 40 minutes, the Offline-Online approach makes decisions in milliseconds, enabling deployment in real-time robotics and sensor networks.

Online quality guarantees (bounds) for different effectiveness parameters (epsilon). Results show that performance often reaches 90-99% of the theoretical optimum.

Submodularity provides a theoretical performance guarantee of at least 50% of the optimum. In practice, our "online bounds" (Figure 2) show that the algorithms typically achieve 90-99% optimality across various team sizes and effectiveness parameters (epsilon).

Conclusion

The Offline-Online approach proves that preparing a diverse set of "good enough" plans ahead of time allows for reactive handling of unexpected changes without performance degradation. Future work will explore more complex agent interactions where transition independence does not hold, or scenarios involving adversarial agent departures.

Summary updated

BibTeX
@inproceedings{agrawal2018decentralized,
  author = {Pritee Agrawal and Pradeep Varakantham and William Yeoh},
  title = {{Decentralized Planning for Non-dedicated Agent Teams with Submodular Rewards in Uncertain Environments}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=9F3KLpyw0},
}
Figure