Implicit Coordination Using FOND Planning

Authors

  • Thorsten Engesser University of Freiburg
  • Tim Miller University of Melbourne

DOI:

https://doi.org/10.1609/aaai.v34i05.6204

Abstract

Epistemic planning can be used to achieve implicit coordination in cooperative multi-agent settings where knowledge and capabilities are distributed between the agents. In these scenarios, agents plan and act on their own without having to agree on a common plan or protocol beforehand. However, epistemic planning is undecidable in general. In this paper, we show how implicit coordination can be achieved in a simpler, propositional setting by using nondeterminism as a means to allow the agents to take the other agents' perspectives. We identify a decidable fragment of epistemic planning that allows for arbitrary initial state uncertainty and non-determinism, but where actions can never increase the uncertainty of the agents. We show that in this fragment, planning for implicit coordination can be reduced to a version of fully observable nondeterministic (FOND) planning and that it thus has the same computational complexity as FOND planning. We provide a small case study, modeling the problem of multi-agent path finding with destination uncertainty in FOND, to show that our approach can be successfully applied in practice.

Downloads

Published

2020-04-03

How to Cite

Engesser, T., & Miller, T. (2020). Implicit Coordination Using FOND Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05), 7151-7159. https://doi.org/10.1609/aaai.v34i05.6204

Issue

Section

AAAI Technical Track: Multiagent Systems