-
David Speck, David Borukhson, Robert Mattmüller and 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), pp. 358-366.
2021.
(Show abstract)
(Hide abstract)
(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 and Marius Lindauer.
Learning Heuristic Selection with Dynamic Algorithm Configuration.
In
Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 597-605.
2021.
(Show abstract)
(Hide abstract)
(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.
-
Thorsten Engesser, Robert Mattmüller, Bernhard Nebel and Michael Thielscher.
Game description language and dynamic epistemic logic compared.
Artificial Intelligence 292. 2021.
(Show abstract)
(Hide abstract)
(Online; DOI)
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). 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 translations between those fragments of GDL-III and DEL.
-
Patrick Caspari, Robert Mattmüller and 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), pp. 32-39.
2020.
(PDF)
-
David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and 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), p. 61–69.
2020.
Superseded by the ICAPS 2021 paper by the same authors.
(Show abstract)
(Hide abstract)
(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 and 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), p. 23–31.
2020.
Superseded by the ICAPS 2021 paper "Subset-Saturated Transition Cost Partitioning".
(Show abstract)
(Hide abstract)
(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 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.
-
David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius Lindauer.
Learning Heuristic Selection with Dynamic Algorithm Configuration.
Technical Report arXiv:2006.08246,
arxiv cs.AI, 2020.
Superseded by the PRL 2020 paper by the same authors.
(Show abstract)
(Hide abstract)
(PDF; Online)
A key challenge in satisfying 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.
-
Felix Lindner, Robert Mattmüller and Bernhard Nebel.
Evaluation of the Moral Permissibility of Action
Plans.
Artificial Intelligence 287. 2020.
(Show abstract)
(Hide abstract)
(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 and 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), pp. 263-271.
2020.
(Show abstract)
(Hide abstract)
(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.
-
David Speck, Robert Mattmüller and Bernhard Nebel.
Symbolic Top-k Planning.
In
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 9967-9974.
2020.
(Show abstract)
(Hide abstract)
(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 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.
-
Sumitra Corraya, Florian Geißer, David Speck and Robert Mattmüller.
An Empirical Study of the Usefulness of State-Dependent Action Costs in Planning.
In
Proceedings of the 42nd German Conference on Artificial Intelligence
(KI 2019), pp. 123-130.
2019.
(Show abstract)
(Hide abstract)
(PDF)
(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.
-
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.
-
David Speck, Florian Geißer, Robert Mattmüller and Álvaro Torralba.
Symbolic Planning with Axioms.
In
Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS 2019), pp. 464-572.
2019.
(Show abstract)
(Hide abstract)
(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 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.
-
Felix Lindner, Robert Mattmüller and Bernhard Nebel.
Moral Permissibility of Action Plans.
In
Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19).
2019.
(Show abstract)
(Hide abstract)
(PDF)
Research in classical planning so far was 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. We address this challenge by analyzing in how far it is possible to generalize existing approaches of machine ethics to automatic planning systems. 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.
-
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.
-
Benedict Wright, Robert Mattmüller and Bernhard Nebel.
Compiling Away Soft Trajectory Constraints in Planning.
In
Proceedings of the Sixteenth COnference on Principles of Knowledge Representation and Reasoning (KR18), pp. 474-482.
2018.
(Show abstract)
(Hide abstract)
(PDF)
Soft goals in planning are optional objectives that should be achieved in the terminal state. However, failing to achieve them does not result in the plan becoming invalid. State trajectory constraints are hard requirements towards the state trajectory of the plan. Soft trajectory constraints are a combination of both: soft preferences on how the hard goals are reached, i. e., optional requirements towards the state trajectory of the plan. Such a soft trajectory constraint may require that some fact should be always true, or should be true at some point during the plan. The quality of a plan is then measured by a metric which adds the sum of all action costs and a penalty for each failed soft trajectory constraint. Keyder and Geffner showed that soft goals can be compiled away. We generalize this approach and illustrate a method of compiling soft trajectory constraints into conditional effects and state-dependent action costs using LTL f and deterministic finite automata. We provide two compilation schemes, with and without reward shaping, by rewarding and penalizing different states in the plan. With this we are able to handle such soft trajectory constraints without the need of altering the search algorithm or heuristics, using classical planners.
-
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.
-
David Speck, Florian Geißer and Robert Mattmüller.
Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams.
In
Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS 2018).
2018.
(Show abstract)
(Hide abstract)
(PDF)
(technical report with proofs; PDF)
Symbolic representations have attracted significant attention in optimal
planning. Binary Decision Diagrams (BDDs) form the basis for symbolic search
algorithms. Closely related are Algebraic Decision Diagrams (ADDs), used to
represent heuristic functions.
Also, progress was made in dealing with models that take state-dependent
action costs into account. Here, costs are represented as Edge-valued
Multi-valued Decision Diagrams (EVMDDs), which can be exponentially more
compact than the corresponding ADD representation. However, they were not
yet considered for symbolic planning.
In this work, we study EVMDD-based symbolic search for optimal planning. We
define EVMDD-based representations of state sets and transition relations,
and show how to compute the necessary operations required for EVMDD-A*. This
EVMDD-based version of symbolic A* generalizes its BDD variant, and allows
to solve planning tasks with state-dependent action costs.
We prove theoretically that our approach is sound, complete and optimal.
Additionally, we present an empirical analysis comparing EVMDD-A* to BDD-A*
and explicit A* search. Our results underscore the usefulness of symbolic
approaches and the feasibility of dealing with models that go beyond unit
costs.
-
Benedict Wright, Robert Mattmüller and Bernhard Nebel.
Compiling Away Soft Trajectory Constraints in Planning.
In
Proceedings of the Workshop on Knowledge Engineering for Planning and Scheduling (KEPS18), pp. 38-45.
2018.
(Show abstract)
(Hide abstract)
(PDF)
Soft goals in planning are optional objectives that should be achieved in the terminal state. However, failing to achieve them does not result in the plan becoming invalid. State trajectory constraints are hard requirements towards the state trajectory of the plan. Soft trajectory constraints are a combination of both: soft preferences on how the hard goals are reached, i. e., optional requirements towards the state trajectory of the plan. Such a soft trajectory constraint may require that some fact should be always true, or should be true at some point during the plan. The quality of a plan is then measured by a metric which adds the sum of all action costs and a penalty for each failed soft trajectory constraint. Keyder and Geffner showed that soft goals can be compiled away. We generalize this approach and illustrate a method of compiling soft trajectory constraints into conditional effects and state-dependent action costs using LTL f and deterministic finite automata. We provide two compilation schemes, with and without reward shaping, by rewarding and penalizing different states in the plan. With this we are able to handle such soft trajectory constraints without the need of altering the search algorithm or heuristics, using classical planners.
-
Felix Lindner, Robert Mattmüller and Bernhard Nebel.
Moral Permissibility of Action Plans.
In
Proceedings of the ICAPS Workshop on EXplainable AI Planning (XAIP).
2018.
(Show abstract)
(Hide abstract)
(PDF)
Research in classical planning so far was 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 that generated plans can have. We address this challenge by analyzing in how
far it is possible to generalize existing approaches of machine ethics to automatic planning systems.
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 complexity of making ethical judgment about plans.
-
David Speck, Florian Geißer and Robert Mattmüller.
SYMPLE: Symbolic Planning based on EVMDDs.
In
The 9th International Planning Competition (IPC 2018), pp. 82-85.
2018.
(Show abstract)
(Hide abstract)
(PDF)
SYMPLE is a classical planner which performs bidirectional
symbolic search. Symbolic search has proven to be a useful
approach to optimal classical planning and is usually based on
Binary Decision Diagrams (BDDs). Our approach is based on
an alternative data structure called Edge-valued Multi-valued
Decision Diagrams (EVMDDs), which have some structural
advantages over BDDs.
-
Robert Mattmüller, Florian Geißer, Benedict Wright and Bernhard Nebel.
On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning.
In
Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI 2018).
2018.
(Show abstract)
(Hide abstract)
(PDF)
When planning for tasks that feature both state-dependent action costs and conditional effects using relaxation heuristics, the following problem appears: handling costs and effects separately leads to worse-than-necessary heuristic values, since we may get the more useful effect at the lower cost by choosing different values of a relaxed variable when determining relaxed costs and relaxed active effects.
In this paper, we show how this issue can be avoided by representing state-dependent costs and conditional effects uniformly, both as edge-valued multi-valued decision diagrams (EVMDDs) over different sets of edge values, and then working with their product diagram. We develop a theory of EVMDDs that is general enough to encompass state-dependent action costs, conditional effects, and even their combination.
We define relaxed effect semantics in the presence of state-dependent action costs and conditional effects, and describe how this semantics can be efficiently computed using product EVMDDs. This will form the foundation for informative relaxation heuristics in the setting with state-dependent costs and conditional effects combined.
-
Benedict Wright and Robert Mattmüller.
Automated Data Management Workflow Generation with Ontologies and Planning.
In
Proceedings of the 30th Workshop on Planen/Scheduling und Konfigurieren/Entwerfen (PUK 2016).
2016.
(PDF)
-
Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer and Robert Mattmüller.
State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning (Extended Abstract).
In
Proceedings of the 39th German Conference on Artificial Intelligence (KI 2016).
2016.
(Show abstract)
(Hide abstract)
(PDF)
Abstraction heuristics are a popular method to guide optimal search algorithms in classical planning. Cost partitionings allow to sum heuristic estimates admissibly by partitioning action costs among the abstractions. We introduce state-dependent cost partitionings which take context information of actions into account, and show that an optimal state-dependent cost partitioning dominates its state-independent counterpart. We demonstrate the potential of state-dependent cost partitionings with a state-dependent variant of the recently proposed saturated cost partitioning, and show that it can sometimes improve not only over its state-independent counterpart, but even over the optimal state-independent cost partitioning.
-
Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer and Robert Mattmüller.
State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning:Full Proofs.
Technical Report CS-2016-002,
University of Basel, 2016.
(Show abstract)
(Hide abstract)
(PDF)
Abstraction heuristics are a popular method to guide optimal search algorithms in classical planning. Cost partitionings allow to sum heuristic estimates admissibly by distributing action costs among the heuristics. We introduce state-dependent cost partitionings which take context information of actions into account, and show that an optimal state-dependent cost partitioning dominates its state-independent counterpart. We demonstrate the potential of our idea with a state-dependent variant of the recently proposed saturated cost partitioning, and show that it has the potential to improve not only over its state-independent counterpart, but even over the optimal state-independent cost partitioning. Our empirical results give evidence that ignoring the context of actions in the computation of a cost partitioning leads to a significant loss of information. This technical report contains the full proofs for Theorem 1, Theorem 3 and Lemma 1.
-
Thomas Keller, Florian Pommerening, Jendrik Seipp, Florian Geißer and Robert Mattmüller.
State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning.
In
Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016).
2016.
(Show abstract)
(Hide abstract)
(PDF)
Abstraction heuristics are a popular method to guide optimal search algorithms in classical planning. Cost partitionings allow to sum heuristic estimates admissibly by distributing action costs among the heuristics. We introduce state-dependent cost partitionings which take context information of actions into account, and show that an optimal state-dependent cost partitioning dominates its state-independent counterpart. We demonstrate the potential of our idea with a state-dependent variant of the recently proposed saturated cost partitioning, and show that it has the potential to improve not only over its state-independent counterpart, but even over the optimal state-independent cost partitioning. Our empirical results give evidence that ignoring the context of actions in the computation of a cost partitioning leads to a significant loss of information.
-
Florian Geißer, Thomas Keller and Robert Mattmüller.
Abstractions for Planning with State-Dependent Action Costs.
In
Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016).
2016.
(Show abstract)
(Hide abstract)
(PDF)
Extending the classical planning formalism with state-dependent action
costs (SDAC) allows an up to exponentially more compact task encoding.
Recent work proposed to use edge-valued multi-valued decision diagrams
(EVMDDs) to represent cost functions, which allows to automatically detect
and exhibit structure in cost functions and to make heuristic estimators
accurately reflect SDAC. However, so far only the inadmissible additive
heuristic has been considered in this context. In this paper, we define
informative admissible abstraction heuristics which enable optimal
planning with SDAC. We discuss how abstract cost values can be extracted
from EVMDDs that represent concrete cost functions without adjusting them
to the selected abstraction. Our theoretical analysis shows that this is
efficiently possible for abstractions that are Cartesian or coarser. We
adapt the counterexample-guided abstraction refinement approach to derive
such abstractions. An empirical evaluation of the resulting heuristic
shows that highly accurate values can be computed quickly.
-
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 ICAPS-2016 Workshop on Distributed and Multi-Agent Planning (DMAP 2016).
2016.
Superseded by the KR18 paper by the same authors.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Epistemic planning can be used for decision making in multi-agent
situations with distributed knowledge and capabilities. Recent work
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.
-
Johannes Aldinger, Robert Mattmüller and Moritz Göbelbecker.
Complexity Issues of Interval Relaxed Numeric Planning.
In
KI 2015: Advances in Artificial Intelligence
(KI 2015).
2015.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Automated planning is computationally hard even in its most
basic form as STRIPS planning. We are interested in numeric
planning with instantaneous actions, a problem that is not
decidable in general. Relaxation is an approach to simplifying
complex problems in order to obtain guidance in the original
problem. We present a relaxation approach with intervals for
numeric planning and show that plan existence can be decided
in polynomial time for tasks where dependencies between
numeric effects are acyclic.
-
David Speck, Manuela Ortlieb and Robert Mattmüller.
Necessary Observations in Nondeterministic Planning.
In
Proceedings of the 38th German Conference on Artificial Intelligence
(KI 2015).
2015.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
An agent that interacts with a nondeterministic environment can
often only partially observe the surroundings. This necessitates
observations via sensors rendering more information about the
current world state. Sensors can be expensive in many regards
therefore it can be essential to minimize the amount of sensors
an agent requires to solve given tasks. A limitation for sensor
minimization is given by essential sensors which are always
required to solve particular problems. In this paper we present
an efficient algorithm which determines a set of necessary observation
variables. More specifically, we develop a bottom-up algorithm which
computes a set of variables which are always necessary to observe,
in order to always reach a goal state. Our experimental results show
that the knowledge about necessary observation variables can be used
to minimize the number of sensors of an agent.
-
Florian Geißer, Thomas Keller and Robert Mattmüller.
Delete Relaxations for Planning with State-Dependent Action Costs.
In
Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015).
2015.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Most work in planning focuses on tasks with state-independent or
even uniform action costs. However, supporting state-dependent
action costs admits a more compact representation of many
tasks. We investigate how to solve such tasks using heuristic
search, with a focus on delete-relaxation heuristics. We first
define a generalization of the additive heuristic to such tasks
and then discuss different ways of computing it via compilations
to tasks with state-independent action costs and more directly
by modifying the relaxed planning graph. We evaluate these
approaches theoretically and present an implementation of the
generalized additive heuristic for planning with state-dependent
action costs. To our knowledge, this gives rise to the first
approach able to handle even the hardest instances of the
combinatorial Academic Advising domain from the International
Probabilistic Planning Competition (IPPC) 2014.
-
Florian Geißer, Thomas Keller and Robert Mattmüller.
Delete Relaxations for Planning with State-Dependent Action Costs.
In
Proceedings of the 8th Annual Symposium on Combinatorial Search (SoCS 2015).
2015.
Extended abstract of the IJCAI 2015 paper by the same name.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Supporting state-dependent action costs in planning admits a
more compact representation of many tasks. We generalize the
additive heuristic and compute it by embedding decision-diagram
representations of action cost functions into the RPG. We give a
theoretical evaluation and present an implementation of the
generalized additive heuristic. This allows us to handle even
the hardest instances of the combinatorial Academic Advising
domain from the IPPC 2014.
-
Johannes Aldinger, Robert Mattmüller and Moritz Göbelbecker.
Complexity Issues of Interval Relaxed Numeric Planning.
In
Proceedings of the ICAPS-2015 Workshop on Heuristic and Search for Domain-Independent Planning (HSDIP 2015).
2015.
Superseded by the KI 2015 paper of the same name..
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Automated planning is a hard problem even in its most basic form
as STRIPS planning. We are interested in numeric planning tasks
with instantaneous actions, a problem which is not even
decidable in general. Relaxation is an approach to simplifying
complex problems in order to obtain guidance in the original
problem. In this paper we present a relaxation approach with
intervals for numeric planning and discuss the arising
complexity issues.
-
Thorsten Engesser, Thomas Bolander, Robert Mattmüller and Bernhard Nebel.
Cooperative Epistemic Multi-Agent Planning With Implicit Coordination.
In
Proceedings of the ICAPS-2015 Workshop on Distributed and Multi-Agent Planning (DMAP 2015).
2015.
Superseded by the M4M 2017 paper by the same authors.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Epistemic Planning has been used to achieve ontic and epistemic
control in multi-agent situations. We extend the formalism to
include perspective shifts, allowing us to define a class of
cooperative problems in which both action planning and execution
is done in a purely distributed fashion, meaning coordination is
only allowed implicitly by means of the available epistemic
actions. While this approach can be fruitfully applied to model
reasoning in some simple social situations, we also provide some
benchmark applications to show that the concept is useful for
multi-agent systems in practice.
-
Jonas Thiem, Robert Mattmüller and Manuela Ortlieb.
Counterexample-Guided Abstraction Refinement for POND Planning.
In
Proceedings of the ICAPS-2015 Workshop on Model Checking and Automated Planning (MOCHAP 2015).
2015.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Counterexample-guided abstraction refinement (CEGAR) allows to
gradually refine a problem definition until the required detail
for a solution is present. We propose the use of CEGAR to
demonstrate unsolvability of a planning problem while avoiding a
search through the whole state space. This allows a sensor
minimization algorithm for partially observable
non-deterministic (POND) planning problems to determine the
definitive unsolvability notably faster, which is a necessary
part of current approaches of computing the minimal sensor
variable set. We determine from our empirical results that while
the presented algorithm causes some slowdown for solvable
problems, the unsolvability is determined at a much greater
speed with this novel approach.
-
Dominik Winterer, Robert Mattmüller and Martin Wehrle.
Stubborn Sets for Fully Observable Nondeterministic Planning.
In
Proceedings of the ICAPS-2015 Workshop on Model Checking and Automated Planning (MOCHAP 2015).
2015.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
The stubborn set method is a state-space reduction technique,
originally introduced in model checking and then transfered to
classical planning. It was shown that stubborn sets
significantly improve the performance of optimal deterministic
planners by considering only a subset of applicable operators in
a state. Fully observable nondeterministic planning (FOND)
extends the formalism of classical planning by nondeterministic
operators. We show that stubborn sets are also beneficial for
FOND problems. We introduce nondeterministic stubborn sets,
stubborn sets which preserve strong cyclic plans. We follow two
approaches: Fast Incremental Planning with stubborn sets from
classical planning and LAO* search with nondeterministic
stubborn sets. Our experiments show that both approaches
increase coverage and decrease node generations when compared to
their respective baselines.
-
Robert Mattmüller, Manuela Ortlieb and Erik Wacker.
Minimizing Necessary Observations for Nondeterministic Planning.
In
Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014).
2014.
(Show abstract)
(Hide abstract)
(PDF)
Autonomous agents interact with their environments via sensors and actuators.
Motivated by the observation that sensors can be expensive, in this paper we
are concerned with the problem of minimizing the amount of sensors an agent
needs in order to successfully plan and act in a partially observable
nondeterministic environment. More specifically, we present a simple greedy
top-down algorithm in the space of observation variables that returns an
inclusion minimal set of state variables sufficient to observe in order to
find a plan. We enhance the algorithm by reusing plans from earlier iterations
and by the use of functional dependencies between variables that allows the
values of some variables to be inferred from those of other variables. Our
experimental evaluation on a number of benchmark problems shows promising
results regarding runtime, numbers of sensors and plan quality.
-
Andreas Hertle, Christian Dornhege, Thomas Keller, Robert Mattmüller, Manuela Ortlieb and Bernhard Nebel.
An Experimental Comparison of Classical, FOND and Probabilistic Planning.
In
Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014), pp. 297-308.
Springer 2014.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
Domain-independent planning in general is broadly applicable to a wide range of tasks.
Many formalisms exist that allow to describe different aspects of realistic problems.
Which one is best is not clear as usually more expressiveness comes with a cost in
planning time. Under the assumption that hard guarantees are not required, users are
faced with a decision between multiple approaches. In this work we study the effect of
nondeterministic action outcomes. As a generic model we use a probabilistic description
in the form of Markov Decision Processes (MDPs). We define abstracting translations
into a classical planning formalism and fully observable nondeterministic (FOND)
planning. Our goal is to give insight into how state-of-the-art systems perform on
different MDP planning domains. We evaluate those MDPs by running state-of-the-art
planning systems on the abstracted formalisms.
-
Florian Geißer, Thomas Keller and Robert Mattmüller.
Past, Present, and Future: An Optimal Online Algorithm for Single-Player GDL-II Games.
In
Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), pp. 357-362.
2014.
(Show abstract)
(Hide abstract)
(PDF)
(BIB)
In General Game Playing, a player receives the rules of an unknown game and
attempts to maximize his expected reward. Since 2011, the GDL-II rule language
extension allows the formulation of nondeterministic and partially observable
games. In this paper, we present an algorithm for such games, with a focus on
the single-player case. Conceptually, at each stage, the proposed Norns algorithm
distinguishes between the past, present and future steps of the game. More
specifically, a belief state tree is used to simulate a potential past that
leads to a present that is consistent with received observations. Unlike other
related methods, our method is asymptotically optimal. Moreover, augmenting the
belief state tree with iteratively improved probabilities speeds up the
process over time significantly.
As this allows a true picture of the present, we additionally present an
optimal version of the well-known UCT algorithm for partially observable
single-player games. Instead of performing hindsight optimization on a
simplified, fully observable tree, the true future is simulated on an
action-observation tree that takes partial observability into account. The
expected reward estimates of applicable actions converge towards the true
expected rewards even for moves that are only used to gather information. We
prove that our algorithm is asymptotically optimal for single-player games and
POMDPs and support our claim with an empirical evaluation.
-
Dr. Yusra Alkhazraji, Michael Katz, Robert Mattmüller, Florian Pommerening, Alexander Shleyfman and Martin Wehrle.
Metis: Arming Fast Downward with Pruning and Incremental Computation (planner abstract).
In
the 8th International Planning Competition (IPC 2014) (deterministic track).
2014.
(Show abstract)
(Hide abstract)
(PDF)
Metis is a sequential optimal planner that implements three
components on top of the Fast Downward planning system (Helmert 2006). The planner performs an A ∗ search
using the following three major components:
• an admissible incremental LM-cut heuristic (Pommeren-
ing and Helmert 2013),
• a symmetry based pruning technique (Domshlak, Katz,
and Shleyfman 2012), and
• a partial order reduction based pruning technique based
on strong stubborn sets (Wehrle and Helmert 2012).
Each of those techniques was extended to support conditional effects. In addition, Metis features a flexible invocation of partial order reduction based pruning. In what follows, we describe each of these components in detail.
-
Manuela Ortlieb and Robert Mattmüller.
Pattern-Database Heuristics for Partially Observable Nondeterministic Planning.
In
Proceedings of the 36th German Conference on Artificial Intelligence (KI 2013).
2013.
(Show abstract)
(Hide abstract)
(PDF)
(slides; PDF)
Heuristic search is the dominant approach to classical
planning. However, many realistic problems violate classical
assumptions such as determinism of action outcomes or full
observability. In this paper, we investigate how - and how
successfully - a particular classical technique, namely informed search
using an abstraction heuristic, can be transferred to
nondeterministic planning under partial observability. Specifically,
we explore pattern-database heuristics with automatically generated
patterns in the context of informed progression search for strong
cyclic planning under partial observability. To that end, we discuss
projections and how belief states can be heuristically assessed
either directly or by going back to the contained world states, and
empirically evaluate the resulting heuristics internally and
compared to a delete-relaxation and a blind approach.
From our experiments we can conclude that in terms of
guidance, it is preferable to represent both nondeterminism and
partial observability in the abstraction (instead of relaxing them),
and that the resulting abstraction heuristics significantly
outperform both blind search and a delete-relaxation approach where
nondeterminism and partial observability are also relaxed.
-
Martin Wehrle, Malte Helmert, Dr. Yusra Alkhazraji and Robert Mattmüller.
The Relative Pruning Power of Strong Stubborn Sets and Expansion Core.
In
Proceedings of the 23rd International Conference on
Automated Planning and Scheduling (ICAPS13).
2013.
(Show abstract)
(Hide abstract)
(PDF)
In the last years, pruning techniques based on partial order reduction have
found increasing attention in the planning community. One recent result is
that the expansion core method is a special case of the strong stubborn sets
method proposed in model checking. However, it is still an open question if
there exist efficiently computable strong stubborn sets with strictly
higher pruning power than expansion core. In this paper, we prove that the
pruning power of strong stubborn sets is strictly higher than the pruning
power of expansion core even for a straight-forward instantiation of strong
stubborn sets. This instantiation is as efficiently computable as expansion
core. Hence, our theoretical results suggest that strong stubborn sets should
be preferred to expansion core. Our empirical evaluation on all optimal
benchmarks from the international planning competitions up to 2011 supports
the theoretical results.
