Planning for Weakly-Coupled Partially Observable Stochastic Games

AnYuan Guo, Victor R. LesserIJCAI 2005

Introduction

Partially Observable Stochastic Games (POSGs) represent a significant challenge in multi-agent planning. They model environments where multiple agents interact under uncertainty, each possessing only a partial view of the global state. While theoretically robust, POSGs are often computationally intractable, with exact solutions limited to very small problems. This paper addresses this complexity by focusing on "weakly-coupled" games—scenarios where agents are largely independent but occasionally constrained by each other's actions, such as robots navigating a shared narrow corridor.

Methodology: Iterated Action Elimination

The authors propose a framework where agents have factored transitions and rewards. In this model, agents operate independently unless their choices are restricted by state-dependent action sets. To manage the resulting complexity, the paper introduces the Iterated Action Elimination Algorithm.

The algorithm operates through four primary steps:

  1. Bounding the Unknown: Agents calculate optimistic ($A_{opt}$) and pessimistic ($A_{pes}$) action sets. $A_{opt}$ includes all actions potentially available if other agents do not interfere, while $A_{pes}$ includes actions guaranteed to be available regardless of others' moves.
  2. MDP Decomposition: By fixing these action sets, the joint game is decomposed into individual Markov Decision Processes (MDPs), which are significantly easier to solve.
  3. Pruning: The algorithm computes upper and lower value bounds for every action. An action is pruned if its optimistic value is lower than the pessimistic value of another action, indicating it is "dominated."
  4. Iteration: Pruning actions tightens the bounds, allowing for further elimination in subsequent rounds until convergence.

Theoretically, this approach aligns with the game-theoretic concept of "iterated elimination of very weakly dominated strategies," providing a rigorous foundation for the heuristic.

Experimental Setup

The algorithm was evaluated using a custom two-agent autonomous rover exploration scenario. In this setup, two rovers explore terrain to collect rocks independently, except for a "narrow bridge" constraint that permits only one rover to pass at a time. The researchers scaled the state space from 6 to 16 states per agent to test the algorithm's performance against increasing complexity.

Results

The experimental results highlight a dramatic reduction in the policy space required for planning. By exploiting the weak coupling between agents, the algorithm collapses the search space by several orders of magnitude.

Table 1: Policy space reduction before and after pruning for varying state counts.

As shown in the table above, for a problem with 16 states, the initial policy space of approximately $5.9 \times 10^{13}$ was reduced to just 2,198 after pruning. This reduction of ten orders of magnitude transforms previously intractable problems into solvable ones.

Discussion and Conclusion

While the algorithm is highly effective for coupling via action sets, its performance may vary in environments where rewards or transitions are more deeply intertwined. Furthermore, the model assumes each agent has a complete view of its own local state, with partial observability stemming from the uncertainty of other agents' states and future actions.

Future research could explore scaling this approach to systems with many more agents or integrating it with approximate solvers to handle even larger state spaces. By focusing on the inherent independence in many multi-agent systems, this work provides a scalable path forward for complex stochastic planning.

Summary updated

BibTeX
@inproceedings{guo2005planning,
  author = {AnYuan Guo and Victor R. Lesser},
  title = {{Planning for Weakly-Coupled Partially Observable Stochastic Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure