-
Thorsten Engesser, Robert Mattmüller, Bernhard Nebel and Felicitas Ritter.
Token-based Execution Semantics for Multi-Agent Epistemic Planning.
In
Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR-2020), pp. 351-360.
2020.
(Show abstract)
(Hide abstract)
(Online; PDF)
Epistemic planning has been employed as a means to achieve implicit coordination in cooperative multi-agent systems where world knowledge is distributed between the agents, and agents plan and act individually. However, recent work has shown that even if all agents act with respect to plans that they consider optimal from their own subjective perspective, infinite executions can occur. In this paper, we analyze the idea of using a single token that can be passed around between the agents and which is used as a prerequisite for acting. We show that introducing such a token to any planning task will prevent the existence of infinite executions. We furthermore analyze the conditions under which solutions to a planning task are preserved under our tokenization.
-
Thorsten Engesser and Tim Miller.
Implicit Coordination Using FOND Planning.
In
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI-20).
2020.
To appear.
(Show abstract)
(Hide abstract)
(PDF)
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.
-
Daniel Reifsteck, Thorsten Engesser, Robert Mattmüller and Bernhard Nebel.
Epistemic Multi-agent Planning Using Monte-Carlo Tree Search.
In
KI 2019: Advances in Artificial Intelligence - 42nd German Conference on AI, pp. 277-289.
2019.
(Show abstract)
(Hide abstract)
(Online; DOI)
Coordination in multi-agent systems with partial and non-uniform observability is a practically challenging problem. We use Monte-Carlo tree search as the basis of an implicitly coordinated epistemic planning algorithm which is capable of using the knowledge distributed among the agents to find solutions in problems even with a large branching factor. We use Dynamic Epistemic Logic to represent the knowledge and the actual situation as a state of the Monte-Carlo tree search, and epistemic planning to formalize the goals and actions of a problem. Further, we describe the required modifications of the Monte-Carlo tree search when searching over epistemic states, and make use of the cooperative card game Hanabi to test our planner on larger problems. We find that the approach scales to games with up to eight cards while maintaining high playing strength.
-
Bernhard Nebel, Thomas Bolander, Thorsten Engesser, Robert Mattmüller and .
Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity (Extended Abstract).
In
Proceedings of International Joint Conference on Artificial Intelligence (IJCAI 2019), pp. 6372-6374.
2019.
-
Thorsten Engesser and Tim Miller.
Planning for Implicit Coordination using FOND.
In
Proceedings of the Workshop on Knowledge Engineering for Planning and Scheduling (KEPS19).
2019.
Superseded by the AAAI-20 paper by the same authors.
(Show abstract)
(Hide 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 identify a decidable fragment of epistemic planning that allows for arbitrary initial state uncertainty and nondeterminism, but where actions can never increase the uncertainty of the agents. We show that in this fragment, planning with and without implicit coordination can be reduced to fully observable nondeterministic (FOND) planning and that it shares the same omputational complexity. We also provide a small case study, modeling the problem of multi-agent path finding with destination uncertainty in FOND, to show that our compilation approach can be successfully applied in practice.
-
Thomas Bolander, Thorsten Engesser, Andreas Herzig, Robert Mattmüller and Bernhard Nebel.
The Dynamic Logic of Policies and Contingent Planning.
In
Logics in Artificial Intelligence - 16th European Conference (JELIA-2019), pp. 659-674.
2019.
(Show abstract)
(Hide abstract)
(Online; DOI)
In classical deterministic planning, solutions to planning tasks are simply sequences of actions, but that is not sufficient for contingent plans in non-deterministic environments. Contingent plans are often expressed through policies that map states to actions. An alternative is to specify contingent plans as programs, e.g. in the syntax of Propositional Dynamic Logic (PDL). PDL is a logic for reasoning about programs with sequential composition, test and non-deterministic choice. However, as we show in the paper, none of the existing PDL modalities directly captures the notion of a solution to a planning task under non-determinism. We add a new modality to star-free PDL correctly capturing this notion. We prove the appropriateness of the new modality by showing how to translate back and forth between policies and PDL programs under the new modality. More precisely, we show how a policy solution to a planning task gives rise to a program solution expressed via the new modality, and vice versa. We also provide an axiomatisation of our PDL extension through reduction axioms into standard star-free PDL.
-
Bernhard Nebel, Thomas Bolander, Thorsten Engesser and Robert Mattmüller.
Implicitly Coordinated Multi-Agent Path Finding under Destination
Uncertainty:
Success Guarantees and Computational Complexity.
Journal of Artificial Intelligence Research 64, pp. 497-527. 2019.
(Show abstract)
(Hide abstract)
(PDF)
In multi-agent path finding (MAPF), it is usually assumed that planning
is performed centrally and that the destinations of the
agents are common knowledge. We will drop both assumptions and analyze
under which conditions it can be guaranteed that the agents reach their
respective destinations using implicitly coordinated
plans without communication. Furthermore, we will analyze what the computational costs
associated with such a coordination regime are. As it turns out,
guarantees can be given assuming that the agents are of a certain
type. However, the implied
computational costs are quite severe. In the distributed setting, we
either have to solve a sequence of NP-complete problems or have to tolerate
exponentially longer executions. In the setting with destination
uncertainty, bounded plan existence becomes PSPACE-complete.
This clearly demonstrates the value of communicating about plans
before execution starts.
-
Thomas Bolander, Thorsten Engesser, Robert Mattmüller and Bernhard Nebel.
Better Eager Than Lazy? How Agent Types Impact the Successfulness of Implicit Coordination.
In
Proceedings of the Sixteenth Conference on Principles of Knowledge Representation and Reasoning (KR18), pp. 445-453.
2018.
(Show abstract)
(Hide abstract)
(PDF)
Epistemic planning can be used for decision making in multi-agent situations
with distributed knowledge and capabilities.
In recent work, we proposed a new notion of
strong policies with implicit coordination. With this it is possible to solve
planning tasks with joint goals from a single-agent perspective without the
agents having to negotiate about and commit to a joint policy at plan time. We
study how and under which circumstances the decentralized application of those
policies leads to the desired outcome.
-
Thorsten Engesser, Robert Mattmüller, Bernhard Nebel and Michael Thielscher.
Game Description Language and Dynamic Epistemic Logic Compared.
In
Proceedings of International Joint Conference on Artificial Intelligence (IJCAI 2018), pp. 1795-1802.
2018.
(Show abstract)
(Hide abstract)
(PDF)
Several different frameworks have been proposed to model and reason about knowledge in dynamic multi-agent settings, among them the logic-programming-based game description language GDL-III, and dynamic epistemic logic (DEL), based on possible-worlds semantics. GDL-III and DEL have complementary strengths and weaknesses in terms of ease of modeling and simplicity of semantics. In this paper, we formally study the expressiveness of GDL-III vs. DEL. We clarify the commonalities and differences between those languages, demonstrate how to bridge the differences where possible, and identify large fragments of GDL-III and DEL that are equivalent in the sense that they can be used to encode games or planning tasks that admit the same legal action sequences. We prove the latter by providing compilations between those fragments of GDL-III and DEL.
