-
Pascal Bercher, Gregor Behnke, Matthias Kraus, Marvin Schiller, Dietrich Manstetten, Michael Dambier, Michael Dorna, Wolfgang Minker, Birte Glimm und Susanne Biundo.
Do It Yourself, but Not Alone: Companion-Technology for Home Improvement - Bringing a Planning-Based Interactive DIY Assistant to Life.
Künstliche Intelligenz -- Special Issue on NLP and Semantics. 2021.
(Abstract einblenden)
(Abstract ausblenden)
We report on the technology transfer project "Do it
yourself, but not alone: Companion-Technology for Home Improvement" that
was carried out by Ulm University in cooperation with Robert Bosch GmbH.
We developed a prototypical assistance system that assists a Do It
Yourself (DIY) handyman in carrying out DIY projects. The assistant,
based on various AI and dialog management capabilities, generates a
sequence of detailed instructions that users may just follow or adapt
according to their individual preferences. It features explanation
capabilities as well as pro-active support based on communication with
the user as well as with the involved tools. We report on the project’s
main achievements, including the findings of various empirical studies
conducted in various development stages of the prototype.
-
Gregor Behnke.
Block Compression and Invariant Pruning for SAT-based Totally-Ordered HTN Planning.
In
Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021).
2021.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
Translations into propositional logic are currently one of the most efficient techniques for solving Totally-Ordered HTN planning problems.
The current encodings iterate over the maximum allowed depth of decomposition.
Given this depth, they compute a tree that represents all possible decompositions up to this depth.
Based on this tree, a formula in propositional logic is created.
We show that much of the computed tree is actually useless as it cannot possibly belong to a solution.
We provide a technique for removing (parts of) these useless structures using state invariants.
We further show that is often not necessary to encode all leafs of this tree as separate timesteps, as the prior encodings did.
Instead, we can compress the leafs into blocks and encode all leafs of a block as one timestep.
We show that these changes provide an improvement over the state-of-the-art in HTN planning.
-
Daniel Höller und Gregor Behnke.
Loop Detection in the PANDA Planning System.
In
Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021).
2021.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
The International Planning Competition (IPC) in 2020 was the first one for a long time to host tracks on Hierarchical Task Network (HTN) planning. HyperTensioN, the winner of the tack on totally-ordered problems, comes with an interesting technique: it stores parts of the decomposition path in the state to mark expanded tasks and forces its depth first search to leave recursive structures in the hierarchy. This can be seen as a form of loop detection (LD) -- a technique that is not very common in HTN planning. This might be due to the spirit of encoding enough advice in the model to find plans (so that loop detection is simply not necessary), or because it becomes a computationally hard task in the general (i.e. partially-ordered) setting.
We integrated several approximate and exact techniques for LD into the progression search of the HTN planner PANDA. We test our techniques on the benchmark set of the IPC 2020. Both in the partial ordered and total ordered track, PANDA with LD performs better than the respective winner of the competition.
-
David Speck, David Borukhson, Robert Mattmüller und Bernhard Nebel.
On the Compilability and Expressive Power of State-Dependent Action Costs.
In
Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), S. 358-366.
2021.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
While state-dependent action costs are practically relevant and have been
studied before, it is still unclear if they are an essential feature of planning
tasks.
In this paper, we study to what extent state-dependent action costs are an
essential feature by analyzing under which circumstances they can be compiled away.
We give a comprehensive classification for combinations of action cost functions and possible
cost measures for the compilations.
Our theoretical results show that if both task sizes and plan lengths are to be
preserved polynomially, then the boundary between compilability and
non-compilability lies between FP and FPSPACE computable action cost
functions (under a mild assumption on the polynomial hierarchy). Preserving task
sizes polynomially and plan lengths linearly at the same time is impossible.
-
David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller und Marius Lindauer.
Learning Heuristic Selection with Dynamic Algorithm Configuration.
In
Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), S. 597-605.
2021.
(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 useful 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.
-
Dominik Drexler, Jendrik Seipp und David Speck.
Subset-Saturated Transition Cost Partitioning.
In
Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), S. 131-139.
2021.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
Cost partitioning admissibly combines the information from multiple
heuristics for optimal state-space search. One of the strongest cost
partitioning algorithms is saturated cost partitioning. It considers the
heuristics in sequence and assigns to each heuristic the minimal fraction
of the remaining costs that are needed for preserving all heuristic
estimates. Saturated cost partitioning has recently been generalized in
two directions: first, by allowing to use different costs for the
transitions induced by the same operator, and second, by preserving the
heuristic estimates for only a subset of states. In this work, we unify
these two generalizations and show that the resulting subset-saturated
transition cost partitioning algorithm usually yields stronger heuristics
than the two generalizations by themselves.
-
Daniel Höller, Gregor Behnke, Pascal Bercher und Susanne Biundo.
The PANDA Framework for Hierarchical Planning.
KI - Künstliche Intelligenz. 2021.
(Online)
-
David Speck und Michael Katz.
Symbolic Search for Oversubscription Planning.
In
Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), S. 11972-11980.
2021.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
The objective of optimal oversubscription planning is to find a plan that
yields an end state with a maximum utility while keeping plan cost under a
certain bound. In practice, the situation occurs whenever a large number of
possible, often competing goals of varying value exist, or the resources are
not sufficient to achieve all goals. In this paper, we investigate the use
of symbolic search for optimal oversubscription planning. Specifically, we
show how to apply symbolic forward search to oversubscription planning tasks
and prove that our approach is sound, complete and optimal. An empirical
analysis shows that our symbolic approach favorably competes with explicit
state-space heuristic search, the current state of the art for
oversubscription planning.
-
Gregor Behnke und David Speck.
Symbolic Search for Optimal Total-Order HTN Planning.
In
Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), S. 11744–11754.
2021.
(Abstract einblenden)
(Abstract ausblenden)
(PDF)
Symbolic search has proven to be a useful approach to optimal classical planning. In Hierarchical Task Network (HTN) planning, however, there is little work on optimal planning. One reason for this is that in HTN planning, most algorithms are based on heuristic search, and admissible heuristics have to incorporate the structure of the task network in order to be informative. In this paper, we present a novel approach to optimal (totally-ordered) HTN planning, which is based on symbolic search. An empirical analysis shows that our symbolic approach outperforms the current state of the art for optimal totally-ordered HTN planning.
-
Patrick Caspari, Robert Mattmüller und Tim Schulte.
A Framework to Prove Strong Privacy in Multi-Agent Planning.
In
Proceedings of the 6th Workshop on Distributed and Multi-Agent Planning
(DMAP 2020), S. 32-39.
2020.
(PDF)
-
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), S. 61–69.
2020.
Superseded by the ICAPS 2021 paper by the same authors.
(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), S. 23–31.
2020.
Superseded by the ICAPS 2021 paper "Subset-Saturated Transition Cost Partitioning".
(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.
-
Thorsten Engesser, Robert Mattmüller, Bernhard Nebel und 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), S. 351-360.
2020.
-
Thorsten Engesser, Robert Mattmüller, Bernhard Nebel und 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), S. 351-360.
2020.
(Abstract einblenden)
(Abstract ausblenden)
(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.
-
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)
-
Lukas Berger, Bernhard Nebel und Marco Ragni.
A Heuristic Agent in Multi-Agent Path Finding Under Destination Uncertainty.
In
KI 2020: Advances in Artificial Intelligence - 43rd German Conference on AI,, S. 259-266.
2020.
(Abstract einblenden)
(Abstract ausblenden)
Humans are capable of recognizing intentions by solely observing another agent’s actions. Hence, in a cooperative planning task, i.e., where all agents aim for all other agents to reach their respective goals, to some extend communication or a central planning instance are not necessary. In epistemic planning a recent research line investigates multi-agent planning problems (MAPF) with goal uncertainty. In this paper, we propose and analyze a round-based variation of this problem, where each agent moves or waits in each round. We show that simple heuristics from cognition can outperform in some cases an adapted formal approach on computation time and solve some new instances in some cases. Implications are discussed.
-
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)
