-
Daniel Höller, Pascal Bercher und Gregor Behnke.
Delete- and Ordering-Relaxation Heuristics for HTN Planning.
In
Proceedings of International Joint Conference on Artificial Intelligence (IJCAI 2020).
2020.
-
David Speck, Florian Geißer und Robert Mattmüller.
When Perfect is not Good Enough: On the Search Behaviour of Symbolic Heuristic Search.
In
Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020).
2020.
To appear.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
Symbolic search has proven to be a competitive approach to cost-optimal
planning, as it compactly represents sets of states by symbolic data
structures.
While heuristics for symbolic search exist, symbolic bidirectional
blind search empirically outperforms its heuristic counterpart and is
therefore the dominant search strategy.
This prompts the question of why heuristics do not seem to pay off in symbolic
search. As a first step in answering this question, we investigate the search
behaviour of symbolic heuristic search by means of BDDA*.
Previous work identified the partitioning of state sets
according to their heuristic values as the main bottleneck.
We theoretically and empirically evaluate the search behaviour of BDDA*
and reveal another fundamental problem: we prove that the use of a heuristic
does not always improve the search performance of BDDA*. In general, even
the perfect heuristic can exponentially deteriorate search performance.
-
Bernhard Nebel.
On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs.
In
Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020).
2020.
To appear.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
The determination of the computational complexity of multi-agent
pathfinding on directed graphs has been an open problem for
many years. For undirected graphs, solvability can be decided in
polynomial time, as has been shown already in the eighties. Further,
recently it has been shown that a
special case on directed graphs can be decided in polynomial time. In
this paper, we show that the problem is
NP-hard in the general case. In addition, some upper bounds are
proven.
-
Florian Geißer, David Speck und Thomas Keller.
Trial-based Heuristic Tree Search for MDPs with Factored Action Spaces.
In
Proceedings of the 13th Annual Symposium on Combinatorial Search (SoCS 2020).
2020.
To appear.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
MDPs with factored action spaces, i.e. where actions are described as assignments to a set of action variables, allow reasoning over action variables instead of action states, yet most algorithms only consider a grounded action representation. This includes algorithms that are instantiations of the trial-based heuristic tree search (THTS) framework, such as AO* or UCT.
To be able to reason over factored action spaces, we propose a generalisation of THTS where nodes that branch over all applicable actions are replaced with subtrees that consist of nodes that represent the decision for a single action variable. We show that many THTS algorithms retain their theoretical properties under the generalised framework, and show how to approximate any state-action heuristic to a heuristic for partial action assignments. This allows to guide a UCT variant that is able to create exponentially fewer nodes than the same algorithm that considers ground actions. An empirical evaluation on the benchmark set of the probabilistic track of the latest International Planning Competition validates the benefits of the approach.
-
Daniel Höller, Pascal Bercher, Gregor Behnke und Susanne Biundo.
HTN Planning as Heuristic Progression Search.
Journal of Artificial Intelligence Research, S. 835-880. 2020.
-
Gregor Behnke, Pascal Bercher, Matthias Kraus, Marvin Schiller, Kristof Mickeleit, Häge Timo, Michael Dorna, Michael Dambier, Wolfgang Minker, Birte Glimm und Susanne Biundo.
New Developments for Robert - Assisting Novice Users Even Better in DIY Projects.
In
Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020), S. 114-122.
2020.
(PDF)
-
Daniel Höller, Gregor Behnke, Pascal Bercher, Susanne Biundo, Humbert Fiorino, Damien Pellier und Ron Alford.
HDDL - A Language to Describe Hierarchical Planning Problems.
In
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), S. 6-17.
2020.
(PDF)
-
Gregor Behnke, Daniel Höller, Alexander Schmid, Pascal Bercher und Susanne Biundo.
On Succinct Groundings of HTN Planning Problems.
In
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020).
2020.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
Both search-based and translation-based planning systemsusually operate on grounded representations of the problem. Planning models, however, are commonly defined using lifted description languages. Thus, planning systems usually generate a grounded representation of the lifted model as a pre-processing step. For HTN planning models, only one method to ground lifted models has been published so far. In this paper we present a new approach for grounding HTN planning problems that produces smaller groundings in a shorter timespan than the previously published method.
-
David Speck, Robert Mattmüller und Bernhard Nebel.
Symbolic Top-k Planning.
In
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020).
2020.
To appear.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
The objective of top-k planning is to determine a set of k different plans with lowest cost for a given planning task. In practice, such a set of best plans can be preferred to a single best plan generated by ordinary optimal planners, as it allows the user to choose between different alternatives and thus take into account preferences that may be difficult to model. In this paper we show that, in general, the decision problem version of top-k planning is PSPACE-complete, as is the decision problem version of ordinary classical planning. This does not hold for polynomially bounded plans for which the decision problem turns out to be PP-hard, while the ordinary case is NP-hard. We present a novel approach to top-k planning, called SYM-K, which is based on symbolic search, and prove that SYM-K is sound and complete. Our empirical analysis shows that SYM-K exceeds the current state of the art for both small and large k.
-
Thorsten Engesser und Tim Miller.
Implicit Coordination Using FOND Planning.
In
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI-20).
2020.
To appear.
(Abstract einblenden)
(Abstract ausblenden)
(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.
-
Felix Lindner, Barbara Kuhnert, Laura Wächter und Katrin Möllney.
Perception of Creative Responses to Moral Dilemmas by a Conversational Robot.
In
Proc. ICSR 2019.
2019.
(PDF)
-
Felix Lindner und Katrin Möllney.
Extracting Reasons for Moral Judgments under Various Ethical Principles.
In
Proceedings of KI 2019.
2019.
(PDF)
-
Daniel Reifsteck, Thorsten Engesser, Robert Mattmüller und Bernhard Nebel.
Epistemic Multi-agent Planning Using Monte-Carlo Tree Search.
In
KI 2019: Advances in Artificial Intelligence - 42nd German Conference on AI, S. 277-289.
2019.
-
Sumitra Corraya, Florian Geißer, David Speck und Robert Mattmüller.
An Empirical Study of the Usefulness of State-Dependent Action Costs in Planning.
In
Proceedings of the 42th German Conference on Artificial Intelligence
(KI 2019), S. 123-130.
2019.
(Abstract einblenden)
(Abstract ausblenden)
(PDF; Online)
The vast majority of work in planning to date has focused on state-independent action costs. However, if a planning task features state-dependent costs, using a cost model with state-independent costs means either introducing a modeling error, or potentially sacrificing compactness of the model. In this paper, we investigate the conflicting priorities of modeling accuracy and compactness empirically, with a particular focus on the extent of the negative impact of reduced modeling accuracy on (a) the quality of the resulting plans, and (b) the search guidance provided by heuristics that are fed with inaccurate cost models. Our empirical results show that the plan suboptimality introduced by ignoring state-dependent costs can range, depending on the domain, from inexistent to several orders of magnitude. Furthermore, our results show that the impact on heuristic guidance additionally depends strongly on the heuristic that is used, the specifics of how exactly the costs are represented, and whether one is interested in heuristic accuracy, node expansions, or overall runtime savings.
-
Tim Schulte.
Trial-based Heuristic Tree-search for Distributed Multi-Agent Planning.
In
Proceedings of the Twelfth Annual Symposium on Combinatorial Search (SoCS 2019)
(SoCS 2019).
2019.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
We present a novel search scheme for privacy-preserving multi-agent
planning, inspired by UCT search. We compare the presented approach to
classical multi-agent forward search and evaluate it based on benchmarks
from the CoDMAP competition.
-
Bernhard Nebel, Thomas Bolander, Thorsten Engesser, Robert Mattmüller und .
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), S. 6372-6374.
2019.
-
Benedict Wright.
Workflow Generation with Planning.
FreiDok plus 2019.
Dissertation Thesis.
(PDF)
-
Florian Geißer, David Speck und Thomas Keller.
An Analysis of the Probabilistic Track of the IPC 2018.
In
Proceedings of the ICAPS-2019 Workshop on the International Planning Competition (WIPC 2019), S. 27-35.
2019.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
The International Planning Competition 2018 consisted of several tracks on classical, temporal and probabilistic planning. In this paper, we focus on the discrete MDP track of the probabilistic portion of the competition.
We discuss the changes to the input language RDDL, which give rise to new challenges for planning systems, and analyze each of the eight competition domains separately and highlight unique properties. We demonstrate flaws of the used evaluation criterion, the IPC score, and discuss the need for optimal upper bounds. An evaluation of the three top-performers, including their post-competition versions, and a brief analysis of their performance highlights the strengths and weaknesses of the individual approaches.
-
Bernhard Nebel.
Some Thoughts on Forward Induction in Multi-Agent-Path Finding Under
Destination Uncertainty.
In
Description Logic, Theory Combination, and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday.
Springer-Verlag, Berlin, Heidelberg, New York 2019.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
While the notion of implicit coordination helps to design frameworks in which agents can cooperatively act with only minimal communication, it so far lacks exploiting observations made while executing a plan. In this note, we have a look at what can be done in order to overcome this shortcoming, at least in a specialized setting.
-
Thorsten Engesser und 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.
(Abstract einblenden)
(Abstract ausblenden)
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.
-
David Speck, Florian Geißer, Robert Mattmüller und Álvaro Torralba.
Symbolic Planning with Axioms.
In
Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS 2019), S. 464-572.
2019.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
Axioms are an extension for classical planning models that allow for modeling complex preconditions and goals exponentially more compactly. Although axioms were introduced in planning more than a decade ago, modern planning techniques rarely support axioms, especially in cost-optimal planning. Symbolic search is a popular and competitive optimal planning technique based on the manipulation of sets of states. In this work, we extend symbolic search algorithms to support axioms natively. We analyze different ways of encoding derived variables and axiom rules to evaluate them in a symbolic representation. We prove that all encodings are sound and complete, and empirically show that the presented approach outperforms the previous state of the art in cost-optimal classical planning with axioms.
-
Thomas Bolander, Thorsten Engesser, Andreas Herzig, Robert Mattmüller und Bernhard Nebel.
The Dynamic Logic of Policies and Contingent Planning.
In
Logics in Artificial Intelligence - 16th European Conference (JELIA-2019), S. 659-674.
2019.
(Abstract einblenden)
(Abstract ausblenden)
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.
