2018 |
David Speck; Florian Geißer; Robert Mattmüller Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams Inproceedings Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS 2018), 2018. @inproceedings{speck-etal-icaps2018, title = {Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams}, author = {David Speck and Florian Geißer and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2018/05/speck-etal-icaps2018.pdf}, year = {2018}, date = {2018-06-28}, booktitle = {Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS 2018)}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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; Bernhard Nebel Compiling Away Soft Trajectory Constraints in Planning Inproceedings Proceedings of the ICAPS-2018 Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2018), 2018. @inproceedings{wright-etal-keps2018, title = {Compiling Away Soft Trajectory Constraints in Planning}, author = {Benedict Wright and Robert Mattmüller and Bernhard Nebel}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2018/05/wright-etal-keps2018.pdf}, year = {2018}, date = {2018-06-26}, booktitle = {Proceedings of the ICAPS-2018 Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2018)}, abstract = {Soft goals in planning describe optional goals that should be achieved in the goal state. However, failing to achieve soft goals does not result in the plan becoming invalid. State trajectory constraints describe requirements towards the way the target goal is achieved, thus describing requirements towards the state trajectory of the final plan. Soft trajectory constraints express preferences on how the hard goals are reached, thus stating 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 LTLf and Büchi automata. With this we are able to handle such soft trajectory constraints without the need of altering the search algorithm or heuristics, using classical planners.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Soft goals in planning describe optional goals that should be achieved in the goal state. However, failing to achieve soft goals does not result in the plan becoming invalid. State trajectory constraints describe requirements towards the way the target goal is achieved, thus describing requirements towards the state trajectory of the final plan. Soft trajectory constraints express preferences on how the hard goals are reached, thus stating 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 LTLf and Büchi automata. 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; Bernhard Nebel Moral Permissibility of Action Plans Inproceedings Proceedings of the ICAPS-2018 Workshop on eXplainable AI Planning (XAIP 2018), 2018. @inproceedings{lindner-etal-xaip2018, title = {Moral Permissibility of Action Plans}, author = {Felix Lindner and Robert Mattmüller and Bernhard Nebel}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2018/06/lindner-etal-xaip2018.pdf https://www.robert-mattmueller.de/wp-content/uploads/2018/06/lindner-etal-xaip2018-slides.pdf}, year = {2018}, date = {2018-06-25}, booktitle = {Proceedings of the ICAPS-2018 Workshop on eXplainable AI Planning (XAIP 2018)}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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. |
Robert Mattmüller; Florian Geißer; Benedict Wright; Bernhard Nebel On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning Inproceedings Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018. @inproceedings{mattmueller-etal-aaai2018, title = {On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning}, author = {Robert Mattmüller and Florian Geißer and Benedict Wright and Bernhard Nebel}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2017/11/mattmueller-etal-aaai2018.pdf https://www.robert-mattmueller.de/wp-content/uploads/2018/02/mattmueller-etal-aaai2018-slides.pdf}, year = {2018}, date = {2018-02-02}, booktitle = {Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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. |
2017 |
Robert Mattmüller; Florian Geißer; Benedict Wright; Bernhard Nebel On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning Inproceedings Proceedings of the 9th Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP 2017), 2017. @inproceedings{mattmueller-etal-hsdip2017, title = {On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning}, author = {Robert Mattmüller and Florian Geißer and Benedict Wright and Bernhard Nebel}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2017/05/mattmueller-etal-hsdip2017.pdf https://www.robert-mattmueller.de/wp-content/uploads/2017/05/mattmueller-etal-hsdip2017-slides.pdf}, year = {2017}, date = {2017-06-20}, booktitle = {Proceedings of the 9th Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP 2017)}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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. |
Thorsten Engesser; Thomas Bolander; Robert Mattmüller; Bernhard Nebel Cooperative Epistemic Multi-Agent Planning for Implicit Coordination Inproceedings Proceedings of the Ninth Workshop on Methods for Modalities (M4M 2017), pp. 75–90, 2017. @inproceedings{engesser-etal-m4m2017, title = {Cooperative Epistemic Multi-Agent Planning for Implicit Coordination}, author = {Thorsten Engesser and Thomas Bolander and Robert Mattmüller and Bernhard Nebel}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2017/05/engesser-etal-m4m2017.pdf}, year = {2017}, date = {2017-01-15}, booktitle = {Proceedings of the Ninth Workshop on Methods for Modalities (M4M 2017)}, pages = {75--90}, abstract = {Epistemic planning can be used for decision making in multi-agent situations with distributed knowledge and capabilities. Recently, Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. We extend the DEL-based epistemic planning framework to include perspective shifts, allowing us to define new notions of sequential and conditional planning with implicit coordination. With these, it is possible to solve planning tasks with joint goals in a decentralized manner without the agents having to negotiate about and commit to a joint policy at plan time. First we define the central planning notions and sketch the implementation of a planning system built on those notions. Afterwards we provide some case studies in order to evaluate the planner empirically and to show that the concept is useful for multi-agent systems in practice.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Epistemic planning can be used for decision making in multi-agent situations with distributed knowledge and capabilities. Recently, Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. We extend the DEL-based epistemic planning framework to include perspective shifts, allowing us to define new notions of sequential and conditional planning with implicit coordination. With these, it is possible to solve planning tasks with joint goals in a decentralized manner without the agents having to negotiate about and commit to a joint policy at plan time. First we define the central planning notions and sketch the implementation of a planning system built on those notions. Afterwards we provide some case studies in order to evaluate the planner empirically and to show that the concept is useful for multi-agent systems in practice. |
2016 |
Thomas Keller; Florian Pommerening; Jendrik Seipp; Florian Geißer; Robert Mattmüller State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning (Extended Abstract) Inproceedings Proceedings of the 39th German Conference on Artificial Intelligence (KI 2016), 2016. @inproceedings{keller-etal-ki2016, title = {State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning (Extended Abstract)}, author = {Thomas Keller and Florian Pommerening and Jendrik Seipp and Florian Geißer and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/09/keller-etal-ki2016.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/09/keller-etal-ki2016-slides.pdf}, year = {2016}, date = {2016-09-28}, booktitle = {Proceedings of the 39th German Conference on Artificial Intelligence (KI 2016)}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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; Robert Mattmüller State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning Inproceedings Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), 2016. @inproceedings{keller-etal-ijcai2016, title = {State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning}, author = {Thomas Keller and Florian Pommerening and Jendrik Seipp and Florian Geißer and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/keller-etal-ijcai2016.pdf}, year = {2016}, date = {2016-07-09}, booktitle = {Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016)}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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; Robert Mattmüller Abstractions for Planning with State-Dependent Action Costs Inproceedings Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016), 2016. @inproceedings{geisser-etal-icaps2016, title = {Abstractions for Planning with State-Dependent Action Costs}, author = {Florian Geißer and Thomas Keller and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/geisser-etal-icaps2016.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/06/geisser-etal-icaps2016-slides.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/06/geisser-etal-icaps2016-poster.pdf }, year = {2016}, date = {2016-06-14}, booktitle = {Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016)}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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; Bernhard Nebel Better Eager Than Lazy? How Agent Types Impact the Successfulness of Implicit Coordination Inproceedings Proceedings of the ICAPS-2016 Workshop on Distributed and Multi-Agent Planning (DMAP 2016), 2016. @inproceedings{bolander-etal-dmap2016, title = {Better Eager Than Lazy? How Agent Types Impact the Successfulness of Implicit Coordination}, author = {Thomas Bolander and Thorsten Engesser and Robert Mattmüller and Bernhard Nebel}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/06/bolander-etal-dmap2016.pdf}, year = {2016}, date = {2016-06-14}, booktitle = {Proceedings of the ICAPS-2016 Workshop on Distributed and Multi-Agent Planning (DMAP 2016)}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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. |
2015 |
Johannes Aldinger; Robert Mattmüller; Moritz Göbelbecker Complexity Issues of Interval Relaxed Numeric Planning Inproceedings Proceedings of the 38th German Conference on Artificial Intelligence (KI 2015), pp. 19–31, 2015. @inproceedings{aldinger-etal-ki2015, title = {Complexity Issues of Interval Relaxed Numeric Planning}, author = {Johannes Aldinger and Robert Mattmüller and Moritz Göbelbecker}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/aldinger-etal-ki2015.pdf}, year = {2015}, date = {2015-09-21}, booktitle = {Proceedings of the 38th German Conference on Artificial Intelligence (KI 2015)}, pages = {19--31}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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; Robert Mattmüller Necessary Observations in Nondeterministic Planning Inproceedings Proceedings of the 38th German Conference on Artificial Intelligence (KI 2015), pp. 181–193, 2015. @inproceedings{speck-etal-ki2015, title = {Necessary Observations in Nondeterministic Planning}, author = {David Speck and Manuela Ortlieb and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/speck-etal-ki2015.pdf}, year = {2015}, date = {2015-09-21}, booktitle = {Proceedings of the 38th German Conference on Artificial Intelligence (KI 2015)}, pages = {181--193}, abstract = {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 agents 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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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 agents 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; Robert Mattmüller Delete Relaxations for Planning with State-Dependent Action Costs Inproceedings Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pp. 1573–1579, 2015. @inproceedings{geisser-etal-ijcai2015, title = {Delete Relaxations for Planning with State-Dependent Action Costs}, author = {Florian Geißer and Thomas Keller and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/geisser-etal-ijcai2015.pdf}, year = {2015}, date = {2015-07-25}, booktitle = {Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015)}, pages = {1573--1579}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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; Robert Mattmüller Delete Relaxations for Planning with State-Dependent Action Costs Inproceedings Proceedings of the 8th Annual Symposium on Combinatorial Search (SoCS 2015), pp. 228–229, 2015. @inproceedings{geisser-etal-socs2015, title = {Delete Relaxations for Planning with State-Dependent Action Costs}, author = {Florian Geißer and Thomas Keller and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/geisser-etal-socs2015.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/geisser-etal-socs2015-poster.pdf}, year = {2015}, date = {2015-06-12}, booktitle = {Proceedings of the 8th Annual Symposium on Combinatorial Search (SoCS 2015)}, pages = {228--229}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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; Moritz Göbelbecker Complexity Issues of Interval Relaxed Numeric Planning Inproceedings Proceedings of the ICAPS-2015 Workshop on Heuristic and Search for Domain-Independent Planning (HSDIP 2015), pp. 4–12, 2015. @inproceedings{aldinger-etal-hsdip2015, title = {Complexity Issues of Interval Relaxed Numeric Planning}, author = {Johannes Aldinger and Robert Mattmüller and Moritz Göbelbecker}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/aldinger-etal-hsdip2015.pdf}, year = {2015}, date = {2015-06-08}, booktitle = {Proceedings of the ICAPS-2015 Workshop on Heuristic and Search for Domain-Independent Planning (HSDIP 2015)}, pages = {4--12}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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; Bernhard Nebel Cooperative Epistemic Multi-Agent Planning With Implicit Coordination Inproceedings Proceedings of the ICAPS-2015 Workshop on Distributed and Multi-Agent Planning (DMAP 2015), pp. 68–76, 2015. @inproceedings{engesser-etal-dmap2015, title = {Cooperative Epistemic Multi-Agent Planning With Implicit Coordination}, author = {Thorsten Engesser and Thomas Bolander and Robert Mattmüller and Bernhard Nebel}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/engesser-etal-dmap2015.pdf}, year = {2015}, date = {2015-06-07}, booktitle = {Proceedings of the ICAPS-2015 Workshop on Distributed and Multi-Agent Planning (DMAP 2015)}, pages = {68--76}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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; Manuela Ortlieb Counterexample-Guided Abstraction Refinement for POND Planning Inproceedings Proceedings of the ICAPS-2015 Workshop on Model Checking and Automated Planning (MOCHAP 2015), pp. 13–14, 2015. @inproceedings{thiem-etal-mochap2015, title = {Counterexample-Guided Abstraction Refinement for POND Planning}, author = {Jonas Thiem and Robert Mattmüller and Manuela Ortlieb}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/thiem-etal-mochap2015.pdf}, year = {2015}, date = {2015-06-07}, booktitle = {Proceedings of the ICAPS-2015 Workshop on Model Checking and Automated Planning (MOCHAP 2015)}, pages = {13--14}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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; Martin Wehrle Stubborn Sets for Fully Observable Nondeterministic Planning Inproceedings Proceedings of the ICAPS-2015 Workshop on Model Checking and Automated Planning (MOCHAP 2015), pp. 6–12, 2015. @inproceedings{winterer-etal-mochap2015, title = {Stubborn Sets for Fully Observable Nondeterministic Planning}, author = {Dominik Winterer and Robert Mattmüller and Martin Wehrle}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/winterer-etal-mochap2015.pdf}, year = {2015}, date = {2015-06-07}, booktitle = {Proceedings of the ICAPS-2015 Workshop on Model Checking and Automated Planning (MOCHAP 2015)}, pages = {6--12}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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. |
2014 |
Andreas Hertle; Christian Dornhege; Thomas Keller; Robert Mattmüller; Manuela Ortlieb; Bernhard Nebel An Experimental Comparison of Classical, FOND and Probabilistic Planning Inproceedings Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014), pp. 297–308, 2014. @inproceedings{hertle-etal-ki2014, title = {An Experimental Comparison of Classical, FOND and Probabilistic Planning}, author = {Andreas Hertle and Christian Dornhege and Thomas Keller and Robert Mattmüller and Manuela Ortlieb and Bernhard Nebel}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/hertle-etal-ki2014.pdf}, year = {2014}, date = {2014-09-22}, booktitle = {Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014)}, pages = {297--308}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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. |
Robert Mattmüller; Manuela Ortlieb; Erik Wacker Minimizing Necessary Observations for Nondeterministic Planning Inproceedings Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014), pp. 309–320, 2014. @inproceedings{mattmueller-etal-ki2014, title = {Minimizing Necessary Observations for Nondeterministic Planning}, author = {Robert Mattmüller and Manuela Ortlieb and Erik Wacker}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/mattmueller-etal-ki2014.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/mattmueller-etal-ki2014-slides.pdf}, year = {2014}, date = {2014-09-22}, booktitle = {Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014)}, pages = {309--320}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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. |
Florian Geißer; Thomas Keller; Robert Mattmüller Past, Present, and Future: An Optimal Online Algorithm for Single-Player GDL-II Games Inproceedings Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), pp. 357–362, 2014. @inproceedings{geisser-etal-ecai2014, title = {Past, Present, and Future: An Optimal Online Algorithm for Single-Player GDL-II Games}, author = {Florian Geißer and Thomas Keller and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/geisser-etal-ecai2014.pdf}, year = {2014}, date = {2014-08-25}, booktitle = {Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014)}, pages = {357--362}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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. |
2013 |
Manuela Ortlieb; Robert Mattmüller Pattern-Database Heuristics for Partially Observable Nondeterministic Planning Inproceedings Proceedings of the 36th German Conference on Artificial Intelligence (KI 2013), pp. 140–151, 2013. @inproceedings{ortlieb-mattmueller-ki2013, title = {Pattern-Database Heuristics for Partially Observable Nondeterministic Planning}, author = {Manuela Ortlieb and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/ortlieb-mattmueller-ki2013.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/ortlieb-mattmueller-ki2013-slides.pdf}, year = {2013}, date = {2013-09-19}, booktitle = {Proceedings of the 36th German Conference on Artificial Intelligence (KI 2013)}, pages = {140--151}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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; Yusra Alkhazraji; Robert Mattmüller The Relative Pruning Power of Strong Stubborn Sets and Expansion Core Inproceedings Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), pp. 251–259, 2013. @inproceedings{wehrle-etal-icaps2013, title = {The Relative Pruning Power of Strong Stubborn Sets and Expansion Core}, author = {Martin Wehrle and Malte Helmert and Yusra Alkhazraji and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/wehrle-etal-icaps2013.pdf}, year = {2013}, date = {2013-06-10}, booktitle = {Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013)}, pages = {251--259}, abstract = {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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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. |
Robert Mattmüller Informed Progression Search for Fully Observable Nondeterministic Planning PhD Thesis Albert-Ludwigs-Universität Freiburg, 2013. @phdthesis{mattmueller-dissertation-2013, title = {Informed Progression Search for Fully Observable Nondeterministic Planning}, author = {Robert Mattmüller}, year = {2013}, date = {2013-01-13}, school = {Albert-Ludwigs-Universität Freiburg}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
2012 |
Yusra Alkhazraji; Martin Wehrle; Robert Mattmüller; Malte Helmert A Stubborn Set Algorithm for Optimal Planning Inproceedings Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012), pp. 891–892, 2012. @inproceedings{alkhazraji-etal-ecai2012, title = {A Stubborn Set Algorithm for Optimal Planning}, author = {Yusra Alkhazraji and Martin Wehrle and Robert Mattmüller and Malte Helmert}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/alkhazraji-etal-ecai2012.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/alkhazraji-etal-ecai2012-poster.pdf}, year = {2012}, date = {2012-08-27}, booktitle = {Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012)}, pages = {891--892}, abstract = {We adapt a partial order reduction technique based on stubborn sets, originally proposed for detecting dead ends in Petri Nets, to the setting of optimal planning. We demonstrate that stubborn sets can provide significant state space reductions on standard planning benchmarks, outperforming the expansion core method.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We adapt a partial order reduction technique based on stubborn sets, originally proposed for detecting dead ends in Petri Nets, to the setting of optimal planning. We demonstrate that stubborn sets can provide significant state space reductions on standard planning benchmarks, outperforming the expansion core method. |
2011 |
Hans-Jörg Peter; Rüdiger Ehlers; Robert Mattmüller Synthia: Verification and Synthesis for Timed Automata Inproceedings Proceedings of the 23rd International Conference on Computer Aided Verification (CAV 2011), pp. 649–655, 2011. @inproceedings{peter-etal-cav2011, title = {Synthia: Verification and Synthesis for Timed Automata}, author = {Hans-Jörg Peter and Rüdiger Ehlers and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/peter-etal-cav2011.pdf}, year = {2011}, date = {2011-07-14}, booktitle = {Proceedings of the 23rd International Conference on Computer Aided Verification (CAV 2011)}, pages = {649--655}, abstract = {We present Synthia, a new tool for the verification and synthesis of open real-time systems modeled as timed automata. The key novelty of Synthia is the underlying abstraction refinement approach that combines the efficient symbolic treatment of timing information by difference bound matrices (DBMs) with the usage of binary decision diagrams (BDDs) for the discrete parts of the system description. Our experiments show that the analysis of both closed and open systems greatly benefits from identifying large relevant and irrelevant system parts on coarse abstractions early in the solution process. Synthia is licensed under the GNU GPL and available from our website.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We present Synthia, a new tool for the verification and synthesis of open real-time systems modeled as timed automata. The key novelty of Synthia is the underlying abstraction refinement approach that combines the efficient symbolic treatment of timing information by difference bound matrices (DBMs) with the usage of binary decision diagrams (BDDs) for the discrete parts of the system description. Our experiments show that the analysis of both closed and open systems greatly benefits from identifying large relevant and irrelevant system parts on coarse abstractions early in the solution process. Synthia is licensed under the GNU GPL and available from our website. |
2010 |
Rüdiger Ehlers; Robert Mattmüller; Hans-Jörg Peter Combining Symbolic Representations for Solving Timed Games Inproceedings Proceedings of the 8th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS 2010), pp. 107–121, 2010. @inproceedings{ehlers-etal-formats2010, title = {Combining Symbolic Representations for Solving Timed Games}, author = {Rüdiger Ehlers and Robert Mattmüller and Hans-Jörg Peter}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/ehlers-etal-formats2010.pdf}, year = {2010}, date = {2010-09-09}, booktitle = {Proceedings of the 8th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS 2010)}, pages = {107--121}, abstract = {We present a general approach to combine symbolic state space representations for the discrete and continuous parts in the synthesis of winning strategies for timed reachability games. The combination is based on abstraction refinement where discrete symbolic techniques are used to produce a sequence of abstract timed game automata. After each refinement step, the resulting abstraction is used for computing an under- and an over-approximation of the timed winning states. The key idea is to identify large relevant and irrelevant parts of the precise weakest winning strategy already on coarse, and therefore simple, abstractions. If neither the existence nor nonexistence of a winning strategy can be established in the approximations, we use them to guide the refinement process. Based on a prototype that combines binary decision diagrams and difference bound matrices, we experimentally evaluate the technique on standard benchmarks from timed controller synthesis. The results clearly demonstrate the potential of the new approach concerning running time and memory consumption compared to the classical on-the-fly algorithm implemented in UPPAAL-Tiga.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We present a general approach to combine symbolic state space representations for the discrete and continuous parts in the synthesis of winning strategies for timed reachability games. The combination is based on abstraction refinement where discrete symbolic techniques are used to produce a sequence of abstract timed game automata. After each refinement step, the resulting abstraction is used for computing an under- and an over-approximation of the timed winning states. The key idea is to identify large relevant and irrelevant parts of the precise weakest winning strategy already on coarse, and therefore simple, abstractions. If neither the existence nor nonexistence of a winning strategy can be established in the approximations, we use them to guide the refinement process. Based on a prototype that combines binary decision diagrams and difference bound matrices, we experimentally evaluate the technique on standard benchmarks from timed controller synthesis. The results clearly demonstrate the potential of the new approach concerning running time and memory consumption compared to the classical on-the-fly algorithm implemented in UPPAAL-Tiga. |
J Benton; Kartik Talamadupula; Patrick Eyerich; Robert Mattmüller; Subbarao Kambhampati G-value Plateaus: A Challenge for Planning Inproceedings Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), pp. 259–262, 2010. @inproceedings{benton-etal-icaps2010, title = {G-value Plateaus: A Challenge for Planning}, author = {J Benton and Kartik Talamadupula and Patrick Eyerich and Robert Mattmüller and Subbarao Kambhampati}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/benton-etal-icaps2010.pdf}, year = {2010}, date = {2010-05-12}, booktitle = {Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010)}, pages = {259--262}, abstract = {Recent years have seen the development of several scalable planners, many of which follow the string of successes found in using heuristic, best-first search methods. While this provides positive reinforcement for continuing work along these lines, fundamental problems arise when handling objectives whose value does not change with each search operation. An extreme case of this occurs when handling the objective of generating a temporal plan with short makespan. Typically used heuristic search methods assume strictly positive edge costs for their guarantees on completeness and optimality to hold, while the usual fattening and advance time steps of heuristic search algorithms for temporal planning have the potential for zero-cost edges, resulting in g-value plateaus. In this paper we point out some underlying difficulties with using modern heuristic search methods for optimizing makespan and discuss how the presence of these problems contributes to the poor performance of makespan-optimizing heuristic search planners. To further illustrate this, we show empirical results on recent benchmarks using a planner made with makespan optimization in mind.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Recent years have seen the development of several scalable planners, many of which follow the string of successes found in using heuristic, best-first search methods. While this provides positive reinforcement for continuing work along these lines, fundamental problems arise when handling objectives whose value does not change with each search operation. An extreme case of this occurs when handling the objective of generating a temporal plan with short makespan. Typically used heuristic search methods assume strictly positive edge costs for their guarantees on completeness and optimality to hold, while the usual fattening and advance time steps of heuristic search algorithms for temporal planning have the potential for zero-cost edges, resulting in g-value plateaus. In this paper we point out some underlying difficulties with using modern heuristic search methods for optimizing makespan and discuss how the presence of these problems contributes to the poor performance of makespan-optimizing heuristic search planners. To further illustrate this, we show empirical results on recent benchmarks using a planner made with makespan optimization in mind. |
Robert Mattmüller; Manuela Ortlieb; Malte Helmert; Pascal Bercher Pattern Database Heuristics for Fully Observable Nondeterministic Planning Inproceedings Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), pp. 105–112, 2010. @inproceedings{mattmueller-etal-icaps2010, title = {Pattern Database Heuristics for Fully Observable Nondeterministic Planning}, author = {Robert Mattmüller and Manuela Ortlieb and Malte Helmert and Pascal Bercher}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/mattmueller-etal-icaps2010.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/mattmueller-etal-icaps2010-slides.pdf}, year = {2010}, date = {2010-05-12}, booktitle = {Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010)}, pages = {105--112}, abstract = {When planning in an uncertain environment, one is often interested in finding a contingent plan that prescribes appropriate actions for all possible states that may be encountered during the execution of the plan. We consider the problem of finding strong and strong cyclic plans for fully observable nondeterministic (FOND) planning problems. The algorithm we choose is LAO*, an informed explicit state search algorithm. We investigate the use of pattern database (PDB) heuristics to guide LAO* towards goal states. To obtain a fully domain-independent planning system, we use an automatic pattern selection procedure that performs local search in the space of pattern collections. The evaluation of our system on the FOND benchmarks of the Uncertainty Part of the International Planning Competition 2008 shows that our approach is competitive with symbolic regression search in terms of problem coverage and speed.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } When planning in an uncertain environment, one is often interested in finding a contingent plan that prescribes appropriate actions for all possible states that may be encountered during the execution of the plan. We consider the problem of finding strong and strong cyclic plans for fully observable nondeterministic (FOND) planning problems. The algorithm we choose is LAO*, an informed explicit state search algorithm. We investigate the use of pattern database (PDB) heuristics to guide LAO* towards goal states. To obtain a fully domain-independent planning system, we use an automatic pattern selection procedure that performs local search in the space of pattern collections. The evaluation of our system on the FOND benchmarks of the Uncertainty Part of the International Planning Competition 2008 shows that our approach is competitive with symbolic regression search in terms of problem coverage and speed. |
2009 |
Hans-Jörg Peter; Robert Mattmüller Component-based Abstraction Refinement for Timed Controller Synthesis Inproceedings Proceedings of the 30th IEEE Real-Time Systems Symposium (RTSS 2009), pp. 364–374, 2009. @inproceedings{peter-mattmueller-rtss2009, title = {Component-based Abstraction Refinement for Timed Controller Synthesis}, author = {Hans-Jörg Peter and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/peter-mattmueller-rtss2009.pdf}, year = {2009}, date = {2009-12-02}, booktitle = {Proceedings of the 30th IEEE Real-Time Systems Symposium (RTSS 2009)}, pages = {364--374}, abstract = {We present a novel technique for synthesizing controllers for distributed real-time environments with safety requirements. Our approach is an abstraction refinement extension to the on-the-fly algorithm by Cassez et al. from 2005. Based on partial compositions of some environment components, each refinement cycle constructs a sound abstraction that can be used to obtain under- and over-approximations of all valid controller implementations. This enables (1) early termination if an implementation does not exist in the over-approximation, or, if one does exist in the under-approximation, and (2) pruning of irrelevant moves in subsequent refinement cycles. In our refinement loop, the precision of the abstractions incrementally increases and converges to all specification-critical components. We implemented our approach in a prototype synthesis tool and evaluated it on an industrial benchmark. In comparison with the timed game solver UPPAAL-Tiga, our technique outperforms the nonincremental approach by an order of magnitude.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We present a novel technique for synthesizing controllers for distributed real-time environments with safety requirements. Our approach is an abstraction refinement extension to the on-the-fly algorithm by Cassez et al. from 2005. Based on partial compositions of some environment components, each refinement cycle constructs a sound abstraction that can be used to obtain under- and over-approximations of all valid controller implementations. This enables (1) early termination if an implementation does not exist in the over-approximation, or, if one does exist in the under-approximation, and (2) pruning of irrelevant moves in subsequent refinement cycles. In our refinement loop, the precision of the abstractions incrementally increases and converges to all specification-critical components. We implemented our approach in a prototype synthesis tool and evaluated it on an industrial benchmark. In comparison with the timed game solver UPPAAL-Tiga, our technique outperforms the nonincremental approach by an order of magnitude. |
Patrick Eyerich; Robert Mattmüller; Gabriele Röger Using the Context-enhanced Additive Heuristic for Temporal and Numeric Planning Inproceedings Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), pp. 130–137, 2009. @inproceedings{eyerich-etal-icaps2009, title = {Using the Context-enhanced Additive Heuristic for Temporal and Numeric Planning}, author = {Patrick Eyerich and Robert Mattmüller and Gabriele Röger}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/eyerich-etal-icaps2009.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/eyerich-etal-icaps2009-slides.pdf}, year = {2009}, date = {2009-09-19}, booktitle = {Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009)}, pages = {130--137}, abstract = {Planning systems for real-world applications need the ability to handle concurrency and numeric fluents. Nevertheless, the predominant approach to cope with concurrency followed by the most successful participants in the latest International Planning Competitions (IPC) is still to find a sequential plan that is rescheduled in a post-processing step. We present Temporal Fast Downward (TFD), a planning system for temporal problems that is capable of finding low-makespan plans by performing a heuristic search in a temporal search space. We show how the context-enhanced additive heuristic can be successfully used for temporal planning and how it can be extended to numeric fluents. TFD often produces plans of high quality and, evaluated according to the rating scheme of the last IPC, outperforms all state-of-the-art temporal planning systems.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Planning systems for real-world applications need the ability to handle concurrency and numeric fluents. Nevertheless, the predominant approach to cope with concurrency followed by the most successful participants in the latest International Planning Competitions (IPC) is still to find a sequential plan that is rescheduled in a post-processing step. We present Temporal Fast Downward (TFD), a planning system for temporal problems that is capable of finding low-makespan plans by performing a heuristic search in a temporal search space. We show how the context-enhanced additive heuristic can be successfully used for temporal planning and how it can be extended to numeric fluents. TFD often produces plans of high quality and, evaluated according to the rating scheme of the last IPC, outperforms all state-of-the-art temporal planning systems. |
Pascal Bercher; Robert Mattmüller Solving Non-deterministic Planning Problems with Pattern Database Heuristics Inproceedings Proceedings of the 32nd Annual Conference on Artificial Intelligence (KI 2009), pp. 57–64, 2009. @inproceedings{bercher-mattmueller-ki2009, title = {Solving Non-deterministic Planning Problems with Pattern Database Heuristics}, author = {Pascal Bercher and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/bercher-mattmueller-ki2009.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/bercher-mattmueller-ki2009-slides.pdf}, year = {2009}, date = {2009-09-17}, booktitle = {Proceedings of the 32nd Annual Conference on Artificial Intelligence (KI 2009)}, pages = {57--64}, abstract = {Non-determinism arises naturally in many real-world applications of action planning. Strong plans for this type of problems can be found using AO* search guided by an appropriate heuristic function. Most domain-independent heuristics considered in this context so far are based on the idea of ignoring delete lists and do not properly take the non-determinism into account. Therefore, we investigate the applicability of pattern database (PDB) heuristics to non-deterministic planning. PDB heuristics have emerged as rather informative in a deterministic context. Our empirical results suggest that PDB heuristics can also perform reasonably well in non-deterministic planning. Additionally, we present a generalization of the pattern additivity criterion known from classical planning to the non-deterministic setting.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Non-determinism arises naturally in many real-world applications of action planning. Strong plans for this type of problems can be found using AO* search guided by an appropriate heuristic function. Most domain-independent heuristics considered in this context so far are based on the idea of ignoring delete lists and do not properly take the non-determinism into account. Therefore, we investigate the applicability of pattern database (PDB) heuristics to non-deterministic planning. PDB heuristics have emerged as rather informative in a deterministic context. Our empirical results suggest that PDB heuristics can also perform reasonably well in non-deterministic planning. Additionally, we present a generalization of the pattern additivity criterion known from classical planning to the non-deterministic setting. |
2008 |
Pascal Bercher; Robert Mattmüller A Planning Graph Heuristic for Forward-Chaining Adversarial Planning Inproceedings Proceedings of the 18th European Conference on Artificial Intelligence (ECAI 2008), pp. 921–922, 2008. @inproceedings{bercher-mattmueller-ecai2008, title = {A Planning Graph Heuristic for Forward-Chaining Adversarial Planning}, author = {Pascal Bercher and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/bercher-mattmueller-ecai2008.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/bercher-mattmueller-ecai2008-slides.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/bercher-mattmueller-ecai2008-poster.pdf}, year = {2008}, date = {2008-07-23}, booktitle = {Proceedings of the 18th European Conference on Artificial Intelligence (ECAI 2008)}, pages = {921--922}, abstract = {In contrast to classical planning, in adversarial planning, the planning agent has to face an adversary trying to prevent him from reaching his goals. In this paper, we investigate a forward-chaining approach to adversarial planning based on the AO* algorithm. The exploration of the underlying AND/OR graph is guided by a heuristic evaluation function, inspired by the relaxed planning graph heuristic used in the FF planner. Unlike FF, our heuristic uses an adversarial planning graph with distinct proposition and action layers for the protagonist and antagonist. First results suggest that in certain planning domains, our approach yields results competitive with the state of the art.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } In contrast to classical planning, in adversarial planning, the planning agent has to face an adversary trying to prevent him from reaching his goals. In this paper, we investigate a forward-chaining approach to adversarial planning based on the AO* algorithm. The exploration of the underlying AND/OR graph is guided by a heuristic evaluation function, inspired by the relaxed planning graph heuristic used in the FF planner. Unlike FF, our heuristic uses an adversarial planning graph with distinct proposition and action layers for the protagonist and antagonist. First results suggest that in certain planning domains, our approach yields results competitive with the state of the art. |
Malte Helmert; Robert Mattmüller Accuracy of Admissible Heuristic Functions in Selected Planning Domains Inproceedings Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), pp. 938–943, 2008. @inproceedings{helmert-mattmueller-aaai2008, title = {Accuracy of Admissible Heuristic Functions in Selected Planning Domains}, author = {Malte Helmert and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/helmert-mattmueller-aaai2008.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/helmert-mattmueller-aaai2008-slides.pdf}, year = {2008}, date = {2008-07-13}, booktitle = {Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008)}, pages = {938--943}, abstract = {The efficiency of optimal planning algorithms based on heuristic search crucially depends on the accuracy of the heuristic function used to guide the search. Often, we are interested in domain-independent heuristics for planning. In order to assess the limitations of domain-independent heuristic planning, it appears interesting to analyse the (in)accuracy of common domain-independent planning heuristics in the IPC benchmark domains. For a selection of these domains, we analytically investigate the accuracy of the h+ heuristic, the hm family of heuristics, and certain (additive) pattern database heuristics, compared to the perfect heuristic h*. Whereas h+ and additive pattern database heuristics usually return cost estimates proportional to the true cost, non-additive hm and non-additive pattern-database heuristics can yield results underestimating the true cost by arbitrarily large factors.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } The efficiency of optimal planning algorithms based on heuristic search crucially depends on the accuracy of the heuristic function used to guide the search. Often, we are interested in domain-independent heuristics for planning. In order to assess the limitations of domain-independent heuristic planning, it appears interesting to analyse the (in)accuracy of common domain-independent planning heuristics in the IPC benchmark domains. For a selection of these domains, we analytically investigate the accuracy of the h+ heuristic, the hm family of heuristics, and certain (additive) pattern database heuristics, compared to the perfect heuristic h*. Whereas h+ and additive pattern database heuristics usually return cost estimates proportional to the true cost, non-additive hm and non-additive pattern-database heuristics can yield results underestimating the true cost by arbitrarily large factors. |
2007 |
Malte Helmert; Robert Mattmüller Accuracy of Admissible Heuristic Functions in Selected Planning Domains Inproceedings Proceedings of the ICAPS-2007 Workshop on Heuristics for Domain-independent Planning (HDIP 2007), 2007. @inproceedings{helmert-mattmueller-hdip2007, title = {Accuracy of Admissible Heuristic Functions in Selected Planning Domains}, author = {Malte Helmert and Robert Mattmüller}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/helmert-mattmueller-hdip2007.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/helmert-mattmueller-hdip2007-slides.pdf}, year = {2007}, date = {2007-09-22}, booktitle = {Proceedings of the ICAPS-2007 Workshop on Heuristics for Domain-independent Planning (HDIP 2007)}, abstract = {The efficiency of optimal planning algorithms based on heuristic search crucially depends on the accuracy of the heuristic function used to guide the search. Often, we are interested in domain-independent heuristics for planning. In assessing the limitations of domain-independent heuristic planning, it appears interesting to analyse the (in)accuracy of common domain-independent planning heuristics in the IPC benchmark domains. For a selection of these domains, we analytically investigate the accuracy of the h+ heuristic, the hk family of heuristics, and certain (additive) pattern database heuristics, compared to the optimal heuristic h*. Whereas h+ and additive pattern database heuristics usually return cost estimates proportional to the true cost, non-additive hk and non-additive pattern-database heuristics can yield results underestimating the true cost by arbitrarily large factors.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } The efficiency of optimal planning algorithms based on heuristic search crucially depends on the accuracy of the heuristic function used to guide the search. Often, we are interested in domain-independent heuristics for planning. In assessing the limitations of domain-independent heuristic planning, it appears interesting to analyse the (in)accuracy of common domain-independent planning heuristics in the IPC benchmark domains. For a selection of these domains, we analytically investigate the accuracy of the h+ heuristic, the hk family of heuristics, and certain (additive) pattern database heuristics, compared to the optimal heuristic h*. Whereas h+ and additive pattern database heuristics usually return cost estimates proportional to the true cost, non-additive hk and non-additive pattern-database heuristics can yield results underestimating the true cost by arbitrarily large factors. |
Robert Mattmüller; Jussi Rintanen Planning for Temporally Extended Goals as Propositional Satisfiability Inproceedings Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 1966–1971, 2007. @inproceedings{mattmueller-rintanen-ijcai2007, title = {Planning for Temporally Extended Goals as Propositional Satisfiability}, author = {Robert Mattmüller and Jussi Rintanen}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/mattmueller-rintanen-ijcai2007.pdf https://www.robert-mattmueller.de/wp-content/uploads/2016/04/mattmueller-rintanen-ijcai2007-poster.pdf}, year = {2007}, date = {2007-01-12}, booktitle = {Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007)}, pages = {1966--1971}, abstract = {Planning for temporally extended goals (TEGs) expressed as formulae of Linear-time Temporal Logic (LTL) is a proper generalization of classical planning, not only allowing to specify properties of a goal state but of the whole plan execution. Additionally, LTL formulae can be used to represent domain-specific control knowledge to speed up planning. In this paper we extend SAT-based planning for LTL goals (akin to bounded LTL model-checking in verification) to partially ordered plans, thus significantly increasing planning efficiency compared to purely sequential SAT planning. We consider a very relaxed notion of partial ordering and show how planning for LTL goals (without the next-time operator) can be translated into a SAT problem and solved very efficiently. The results extend the practical applicability of SAT-based planning to a wider class of planning problems. In addition, they could be applied to solving problems in bounded LTL model-checking more efficiently.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Planning for temporally extended goals (TEGs) expressed as formulae of Linear-time Temporal Logic (LTL) is a proper generalization of classical planning, not only allowing to specify properties of a goal state but of the whole plan execution. Additionally, LTL formulae can be used to represent domain-specific control knowledge to speed up planning. In this paper we extend SAT-based planning for LTL goals (akin to bounded LTL model-checking in verification) to partially ordered plans, thus significantly increasing planning efficiency compared to purely sequential SAT planning. We consider a very relaxed notion of partial ordering and show how planning for LTL goals (without the next-time operator) can be translated into a SAT problem and solved very efficiently. The results extend the practical applicability of SAT-based planning to a wider class of planning problems. In addition, they could be applied to solving problems in bounded LTL model-checking more efficiently. |
2006 |
Malte Helmert; Robert Mattmüller; Sven Schewe Selective Approaches for Solving Weak Games Inproceedings Proceedings of the Fourth International Symposium on Automated Technology for Verification and Analysis (ATVA 2006), pp. 200–214, 2006. @inproceedings{helmert-etal-atva2006, title = {Selective Approaches for Solving Weak Games}, author = {Malte Helmert and Robert Mattmüller and Sven Schewe}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/helmert-etal-atva2006.pdf}, year = {2006}, date = {2006-10-23}, booktitle = {Proceedings of the Fourth International Symposium on Automated Technology for Verification and Analysis (ATVA 2006)}, pages = {200--214}, abstract = {Model-checking alternating-time properties has recently attracted much interest in the verification of distributed protocols. While checking the validity of a specification in alternating-time temporal logic (ATL) against an explicit model is cheap (linear in the size of the formula and the model), the problem becomes EXPTIME-hard when symbolic models are considered. Practical ATL model-checking therefore often consumes too much computation time to be tractable. In this paper, we describe a novel approach for ATL model-checking, which constructs an explicit weak model-checking game on-the-fly. This game is then evaluated using heuristic techniques inspired by efficient evaluation algorithms for and/or-trees. To show the feasibility of our approach, we compare its performance to the ATL model-checking system MOCHA on some practical examples. Using very limited heuristic guidance, we achieve a significant speedup on these benchmarks.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Model-checking alternating-time properties has recently attracted much interest in the verification of distributed protocols. While checking the validity of a specification in alternating-time temporal logic (ATL) against an explicit model is cheap (linear in the size of the formula and the model), the problem becomes EXPTIME-hard when symbolic models are considered. Practical ATL model-checking therefore often consumes too much computation time to be tractable. In this paper, we describe a novel approach for ATL model-checking, which constructs an explicit weak model-checking game on-the-fly. This game is then evaluated using heuristic techniques inspired by efficient evaluation algorithms for and/or-trees. To show the feasibility of our approach, we compare its performance to the ATL model-checking system MOCHA on some practical examples. Using very limited heuristic guidance, we achieve a significant speedup on these benchmarks. |
Malte Helmert; Robert Mattmüller; Gabriele Röger Approximation Properties of Planning Benchmarks Inproceedings Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006), pp. 585–589, 2006. @inproceedings{helmert-etal-ecai2006, title = {Approximation Properties of Planning Benchmarks}, author = {Malte Helmert and Robert Mattmüller and Gabriele Röger}, url = {https://www.robert-mattmueller.de/wp-content/uploads/2016/04/helmert-etal-ecai2006.pdf}, year = {2006}, date = {2006-08-31}, booktitle = {Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006)}, pages = {585--589}, abstract = {For many classical planning domains, the computational complexity of non-optimal and optimal planning is known. However, little is known about the area in between the two extremes of finding some plan and finding optimal plans. In this contribution, we provide a complete classification of the propositional domains from the first four International Planning Competitions with respect to the approximation classes PO, PTAS, APX, poly-APX, and NPO.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } For many classical planning domains, the computational complexity of non-optimal and optimal planning is known. However, little is known about the area in between the two extremes of finding some plan and finding optimal plans. In this contribution, we provide a complete classification of the propositional domains from the first four International Planning Competitions with respect to the approximation classes PO, PTAS, APX, poly-APX, and NPO. |
Robert Mattmüller Planning for Temporally Extended Goals as Propositional Satisfiability Masters Thesis Albert-Ludwigs-Universität Freiburg, 2006, (In German). @mastersthesis{mattmueller-diplomarbeit-2006, title = {Planning for Temporally Extended Goals as Propositional Satisfiability}, author = {Robert Mattmüller}, year = {2006}, date = {2006-03-06}, school = {Albert-Ludwigs-Universität Freiburg}, note = {In German}, keywords = {}, pubstate = {published}, tppubtype = {mastersthesis} } |
Publications
2018 |
Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams Inproceedings Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS 2018), 2018. |
Compiling Away Soft Trajectory Constraints in Planning Inproceedings Proceedings of the ICAPS-2018 Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2018), 2018. |
Moral Permissibility of Action Plans Inproceedings Proceedings of the ICAPS-2018 Workshop on eXplainable AI Planning (XAIP 2018), 2018. |
On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning Inproceedings Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018. |
2017 |
On the Relationship Between State-Dependent Action Costs and Conditional Effects in Planning Inproceedings Proceedings of the 9th Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP 2017), 2017. |
Cooperative Epistemic Multi-Agent Planning for Implicit Coordination Inproceedings Proceedings of the Ninth Workshop on Methods for Modalities (M4M 2017), pp. 75–90, 2017. |
2016 |
State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning (Extended Abstract) Inproceedings Proceedings of the 39th German Conference on Artificial Intelligence (KI 2016), 2016. |
State-dependent Cost Partitionings for Cartesian Abstractions in Classical Planning Inproceedings Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), 2016. |
Abstractions for Planning with State-Dependent Action Costs Inproceedings Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016), 2016. |
Better Eager Than Lazy? How Agent Types Impact the Successfulness of Implicit Coordination Inproceedings Proceedings of the ICAPS-2016 Workshop on Distributed and Multi-Agent Planning (DMAP 2016), 2016. |
2015 |
Complexity Issues of Interval Relaxed Numeric Planning Inproceedings Proceedings of the 38th German Conference on Artificial Intelligence (KI 2015), pp. 19–31, 2015. |
Necessary Observations in Nondeterministic Planning Inproceedings Proceedings of the 38th German Conference on Artificial Intelligence (KI 2015), pp. 181–193, 2015. |
Delete Relaxations for Planning with State-Dependent Action Costs Inproceedings Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pp. 1573–1579, 2015. |
Delete Relaxations for Planning with State-Dependent Action Costs Inproceedings Proceedings of the 8th Annual Symposium on Combinatorial Search (SoCS 2015), pp. 228–229, 2015. |
Complexity Issues of Interval Relaxed Numeric Planning Inproceedings Proceedings of the ICAPS-2015 Workshop on Heuristic and Search for Domain-Independent Planning (HSDIP 2015), pp. 4–12, 2015. |
Cooperative Epistemic Multi-Agent Planning With Implicit Coordination Inproceedings Proceedings of the ICAPS-2015 Workshop on Distributed and Multi-Agent Planning (DMAP 2015), pp. 68–76, 2015. |
Counterexample-Guided Abstraction Refinement for POND Planning Inproceedings Proceedings of the ICAPS-2015 Workshop on Model Checking and Automated Planning (MOCHAP 2015), pp. 13–14, 2015. |
Stubborn Sets for Fully Observable Nondeterministic Planning Inproceedings Proceedings of the ICAPS-2015 Workshop on Model Checking and Automated Planning (MOCHAP 2015), pp. 6–12, 2015. |
2014 |
An Experimental Comparison of Classical, FOND and Probabilistic Planning Inproceedings Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014), pp. 297–308, 2014. |
Minimizing Necessary Observations for Nondeterministic Planning Inproceedings Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014), pp. 309–320, 2014. |
Past, Present, and Future: An Optimal Online Algorithm for Single-Player GDL-II Games Inproceedings Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), pp. 357–362, 2014. |
2013 |
Pattern-Database Heuristics for Partially Observable Nondeterministic Planning Inproceedings Proceedings of the 36th German Conference on Artificial Intelligence (KI 2013), pp. 140–151, 2013. |
The Relative Pruning Power of Strong Stubborn Sets and Expansion Core Inproceedings Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), pp. 251–259, 2013. |
Informed Progression Search for Fully Observable Nondeterministic Planning PhD Thesis Albert-Ludwigs-Universität Freiburg, 2013. |
2012 |
A Stubborn Set Algorithm for Optimal Planning Inproceedings Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012), pp. 891–892, 2012. |
2011 |
Synthia: Verification and Synthesis for Timed Automata Inproceedings Proceedings of the 23rd International Conference on Computer Aided Verification (CAV 2011), pp. 649–655, 2011. |
2010 |
Combining Symbolic Representations for Solving Timed Games Inproceedings Proceedings of the 8th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS 2010), pp. 107–121, 2010. |
G-value Plateaus: A Challenge for Planning Inproceedings Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), pp. 259–262, 2010. |
Pattern Database Heuristics for Fully Observable Nondeterministic Planning Inproceedings Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), pp. 105–112, 2010. |
2009 |
Component-based Abstraction Refinement for Timed Controller Synthesis Inproceedings Proceedings of the 30th IEEE Real-Time Systems Symposium (RTSS 2009), pp. 364–374, 2009. |
Using the Context-enhanced Additive Heuristic for Temporal and Numeric Planning Inproceedings Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), pp. 130–137, 2009. |
Solving Non-deterministic Planning Problems with Pattern Database Heuristics Inproceedings Proceedings of the 32nd Annual Conference on Artificial Intelligence (KI 2009), pp. 57–64, 2009. |
2008 |
A Planning Graph Heuristic for Forward-Chaining Adversarial Planning Inproceedings Proceedings of the 18th European Conference on Artificial Intelligence (ECAI 2008), pp. 921–922, 2008. |
Accuracy of Admissible Heuristic Functions in Selected Planning Domains Inproceedings Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), pp. 938–943, 2008. |
2007 |
Accuracy of Admissible Heuristic Functions in Selected Planning Domains Inproceedings Proceedings of the ICAPS-2007 Workshop on Heuristics for Domain-independent Planning (HDIP 2007), 2007. |
Planning for Temporally Extended Goals as Propositional Satisfiability Inproceedings Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 1966–1971, 2007. |
2006 |
Selective Approaches for Solving Weak Games Inproceedings Proceedings of the Fourth International Symposium on Automated Technology for Verification and Analysis (ATVA 2006), pp. 200–214, 2006. |
Approximation Properties of Planning Benchmarks Inproceedings Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006), pp. 585–589, 2006. |
Planning for Temporally Extended Goals as Propositional Satisfiability Masters Thesis Albert-Ludwigs-Universität Freiburg, 2006, (In German). |