Implicit Coordination Using FOND Planning

Thorsten Engesser, Tim MillerAAAI 2020 · DOI

Introduction

In multi-agent systems, coordination is typically managed through centralized controllers or rigid, pre-defined protocols. However, real-world scenarios often require implicit coordination, where autonomous agents must plan and act individually toward a joint goal while possessing only partial information about the environment and their peers. To achieve this, agents must engage in epistemic planning—reasoning not just about physical states, but about the knowledge and beliefs of other agents.

Presented at AAAI 2020, this research explores a practical subset of epistemic planning that can be reduced to standard Fully Observable Nondeterministic (FOND) planning. This reduction allows agents to "put themselves in each other's shoes" using nondeterminism to simulate perspective, achieving coordination with the same computational complexity as standard planning.

Bridging Epistemic Logic and Practical Planning

General epistemic planning is undecidable, making it a significant hurdle for practical applications. The authors address this by identifying a "FOND fragment" of Dynamic Epistemic Logic (DEL). In this fragment, actions can alter the world or provide information but are restricted from increasing the total uncertainty an agent faces.

The core innovation lies in Action Splitting and Perspective Shifting. Epistemic actions are compiled into two distinct FOND components:

  1. choose(a): A mental action where the agent shifts its perspective to any world it considers possible.
  2. apply(a): The execution of the action across all those possible worlds.
Figure 2: The compilation process splits actions into 'choose' and 'apply' phases to simulate an agent's internal uncertainty through nondeterministic transitions.

By treating different possible states as nondeterministic outcomes, an agent can develop a subjectively strong policy. This is a plan that the agent knows will succeed, regardless of which "possible world" is actually the real one.

Evaluation: MAPF with Destination Uncertainty

The approach was evaluated using the Multi-Agent Path Finding with Destination Uncertainty (MAPF/DU) benchmark. In this scenario, multiple agents navigate a grid toward private destinations. Agents must avoid collisions and proactively clear paths for others, despite not knowing exactly where their peers are headed.

The researchers tested their FOND-compiled models against a state-of-the-art specialized DEL-based planner across various "corridor" maps, scaling the number of agents and the complexity of the environment.

Performance and Scalability

The results demonstrate that leveraging existing, highly optimized FOND solvers provides a significant advantage over specialized epistemic engines. By translating the problem into standard PDDL, the authors could utilize the Fast Forward (FF) heuristic, which offers robust search guidance.

Figure 5: Runtime performance across varying corridor sizes. The FOND-based approach using the FF heuristic (h_FF) significantly outperforms both blind search and the specialized DEL planner.

As shown in the performance data, the specialized DEL planner quickly reached memory limits (32GB) as agent counts increased. In contrast, the FOND-based approach remained scalable. For a 3-agent problem, the FF-guided search completed in under 10 seconds, whereas a blind search took nearly 1,000 seconds.

Conclusion and Future Directions

This work proves that for a specific fragment of epistemic logic, implicit coordination is EXPTIME-complete—the same complexity class as standard FOND planning. This parity allows the broader planning community to access complex epistemic reasoning without bespoke logic engines.

While the current framework requires explicit world enumeration and assumes no new uncertainty is introduced (e.g., no "forgetting"), it opens the door for more sophisticated multi-agent coordination. Future work may extend these techniques to competitive environments or integrate them with Monte Carlo Tree Search (MCTS) to handle larger state spaces.

Summary updated

BibTeX
@inproceedings{engesser2020implicit,
  author = {Thorsten Engesser and Tim Miller},
  title = {{Implicit Coordination Using FOND Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i05.6204},
}
Figure