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:
choose(a): A mental action where the agent shifts its perspective to any world it considers possible.apply(a): The execution of the action across all those possible worlds.
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.
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