Improved Knowledge Modeling and Its Use for Signaling in Multi-Agent Planning with Partial Observability

Shashank Shekhar, Ronen I. Brafman, Guy ShaniAAAI 2021 · DOI

Introduction

Collaborative Multi-Agent Planning (MAP) requires agents to coordinate actions toward a common goal while possessing only partial information about their environment. Traditionally, these problems are framed as Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs). However, due to their computational complexity, researchers have turned to Qualitative Dec-POMDPs (QDec), which use sets of possible states rather than complex probability distributions to improve efficiency.

The Problem with Team Knowledge

Previous state-of-the-art solvers, such as QDec-FP, utilized a "team knowledge" approach ($Kp$), treating the group as a single meta-agent with shared observations. This assumption is often flawed in real-world scenarios; if one agent senses a change, others remain unaware unless specifically informed. This discrepancy results in "illegal" plans that fail during execution because agents are asked to act on information they do not possess. This leads to excessive backtracking and prevents the discovery of plans that require implicit communication.

Methodology: The QDec-FPS Algorithm

The authors introduce QDec-FPS, which improves upon the previous model by tracking individual knowledge ($K_{\phi}p$) rather than a collective pool. This ensures that any agent performing an action actually has the knowledge required to meet that action's preconditions.

Figure 1: A temporal planning tree illustrating collaborative actions (JP) and decision branching (SB) based on sensing outcomes (T/F) for multiple agents over time steps $t_0$ to $t_5$.

Signaling Macros

A core innovation of QDec-FPS is the introduction of "signaling"—a form of implicit communication through the environment. If Agent A knows a hidden state that Agent B needs, and Agent A can change a variable that Agent B can observe, the planner can create a signaling macro:

  1. Sense: Agent A senses the hidden state.
  2. Signal: Agent A changes a visible state to reflect the hidden one.
  3. Receive: Agent B senses the changed state and deduces the hidden value.

This turns the environment into a communication channel, which is vital for scenarios where direct radio communication is unavailable or restricted.

Agent-Specific Knowledge and Plan Projection

By making knowledge agent-specific, the planner becomes more effective at task allocation. It will not assign a task to an agent that hasn't yet observed the necessary environmental cues. This realism is reflected in the projection of the joint team plan into individual agent policies.

Figure 3: The projection of a joint team plan (A) into individual plans for Agent 1 (B) and Agent 2 (C). The annotations $\phi_1$ and $\phi_2$ denote which agent possesses the specific knowledge required at each node.

Experimental Evaluation

The researchers evaluated QDec-FPS across three classic domains: Box-Pushing (BP), Table-Mover (TM), and Rovers (Ro). The results highlighted several key advantages:

  • Scalability: QDec-FPS scaled significantly better than QDec-FP as the number of agents and objects increased.
  • Solving the "Unsolvable": The algorithm successfully solved new problem instances that required signaling—problems that previous solvers could not handle because they lacked a mechanism for agents to share information through the world state.
  • Efficiency: For heterogeneous agents with different roles, QDec-FPS required far fewer re-planning attempts (backtracks), solving complex instances in seconds where older versions took minutes or failed entirely.

Discussion and Future Work

While QDec-FPS offers significant improvements, it does introduce overhead for homogeneous agent groups where the extra complexity of tracking individual knowledge may slow performance. Additionally, the current implementation requires manual selection of signaling macros, which the authors aim to automate in future research. Finally, refining the underlying logic to be more "knowledge-complete" remains a goal to ensure the planner does not underestimate agent knowledge and miss valid plans.

Summary updated

BibTeX
@inproceedings{shekhar2021improved,
  author = {Shashank Shekhar and Ronen I. Brafman and Guy Shani},
  title = {{Improved Knowledge Modeling and Its Use for Signaling in Multi-Agent Planning with Partial Observability}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17420},
}
Figure