-
David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller und Marius Lindauer.
Learning Heuristic Selection with Dynamic Algorithm Configuration.
In
Proceedings of the Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning (PRL 2020).
2020.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
A key challenge in satisficing planning is to use multiple heuristics within one
heuristic search. An aggregation of multiple heuristic estimates, for example by
taking the maximum, has the disadvantage that bad estimates of a single heuristic
can negatively affect the whole search. Since the performance
of a heuristic varies from instance to instance, approaches
such as algorithm selection can be successfully applied. In
addition, alternating between multiple heuristics during the
search makes it possible to use all heuristics equally and improve performance.
However, all these approaches ignore the internal search dynamics of a planning
system, which can help to select the most helpful heuristics for the current expansion
step. We show that dynamic algorithm configuration can be used for dynamic heuristic
selection which takes into account the internal search dynamics of a planning system.
Furthermore, we prove that this approach generalizes over existing approaches and that
it can exponentially improve the performance of the heuristic search. To learn dynamic
heuristic selection, we propose an approach based on reinforcement learning and show
empirically that domain-wise learned policies, which take the internal search dynamics
of a planning system into account, can exceed existing approaches in terms of coverage.
-
Dominik Drexler, David Speck und Robert Mattmüller.
Subset-Saturated Transition Cost Partitioning for Optimal Classical Planning.
In
Proceedings of the 12th Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP 2020).
2020.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
Cost partitioning admissibly combines the information from
multiple heuristics for state-space search. We use a greedy
method called saturated cost partitioning that considers the
heuristics in sequence and assigns the minimal fraction of the
remaining costs that it needs to preserve the heuristic estimates.
In this work, we address the problem of using more
expressive transition cost functions with saturated cost partitioning
to obtain stronger heuristics. Our contribution is
subset-saturated transition cost partitioning that combines the
concepts of using transition cost functions and prioritizing
states that look more important during the search. Our empirical
evaluation shows that this approach still causes too much
computational overhead but leads to more informed heuristics.
-
Matthias Kraus, Marvin Schiller, Gregor Behnke, Pascal Bercher, Michael Dorna, Michael Dambier, Birte Glimm, Susanne Biundo und Wolfgang Minker.
``Was that successful?'' On Integrating Proactive Meta-Dialogue in a DIY-Assistant using Multimodal Cues.
In
Proceedings of the 2020 International Conference on Multimodal Interaction (ICMI 2020).
2020.
(PDF)
-
Daniel Höller, Pascal Bercher, Gregor Behnke und Susanne Biundo.
HTN Plan Repair via Model Transformation.
In
Proceedings of the 42+1st Annual German Conference on Artificial Intelligence (KI 2020).
2020.
(PDF)
-
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.
-
Felix Lindner, Robert Mattmüller und Bernhard Nebel.
Evaluation of the Moral Permissibility of Action
Plans.
Artificial Intelligence. 2020.
To appear.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
Research in classical planning so far has been mainly concerned with
generating a satisficing or an optimal plan. However, if such
systems are used to make decisions that are relevant to humans, one
should also consider the ethical consequences generated plans can have.
Traditionally, ethical principles are formulated
in an action-based manner, allowing to judge the execution
of one action. We show how such a judgment can be generalized to
plans. Further, we study the computational complexity of making ethical judgment
about plans.
-
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), S. 263-271.
2020.
(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.
(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.
-
Roman Bartak, Simona Ondrckova, Adrien Maillard, Gregor Behnke und Pascal Bercher.
A Novel Parsing-based Approach for Verification of Hierarchical Plans.
In
Proceedings of the 32nd International Conference on Tools with Artificial Intelligence (ICTAI 2020).
2020.
-
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), S. 38-47.
2020.
(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.
-
David Speck, Robert Mattmüller und Bernhard Nebel.
Symbolic Top-k Planning.
In
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), S. 9967-9974.
2020.
(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.
-
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. 343-347.
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.
-
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)
