Patrick Eyerich – Publikationen

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

2013

Patrick Eyerich und Malte Helmert.
Stronger Abstraction Heuristics Through Perimeter Search.
In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS13). 2013.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

Perimeter search is a bidirectional search algorithm consisting of two phases. In the first phase, a limited regression search computes the perimeter, a region which must necessarily be passed in every solution. In the second phase, a heuristic forward search finds an optimal plan from the initial state to the perimeter.

The drawback of perimeter search is the need to compute heuristic estimates towards every state on the perimeter in the forward phase. We show that this limitation can be effectively overcome when using pattern database (PDB) heuristics in the forward phase.

The combination of perimeter search and PDB heuristics has been considered previously by Felner and Ofek for solving combinatorial puzzles. They claimed that, based on theoretical considerations and experimental evidence, the use of perimeter search in this context offers "limited or no benefits". Our theoretical and experimental results show that this assessment should be revisited.
Johannes Löhr, Patrick Eyerich, Stefan Winkler und Bernhard Nebel.
Domain Predictive Control Under Uncertain Numerical State Information.
In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS13). 2013.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

In planning, hybrid system states consisting of logical and numerical variables are usually assumed to be completely known. In particular, for numerical state variables full knowledge of their exact values is assumed. However, in real world applications states are results of noisy measurements and imperfect actuators. Therefore, a planned sequence of state transitions might fail to lead a hybrid system to the desired goal. We show how to propagate and reason about uncertain state information directly in the planning process, enabling hybrid systems to find plans that satisfy numerical goals with predefined confidence.

2012

Patrick Eyerich.
Preferring Properly: Increasing Coverage while Maintaining Quality in Anytime Temporal Planning.
In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012). 2012.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

Temporal Fast Downward (TFD) is a successful temporal planning system that is capable of dealing with numerical values. Rather than decoupling action selection from scheduling, it searches directly in the space of time-stamped states, an approach that has shown to produce plans of high quality at the price of coverage. To increase coverage, TFD incorporates deferred evaluation and preferred operators, two search techniques that usually decrease the number of heuristic calculations by a large amount. However, the current definition of preferred operators offers only limited guidance in problems where heuristic estimates are weak or where subgoals require the execution of mutex operators. In this paper, we present novel methods for refinement of this definition and show how to combine the diverse strengths of different sets of preferred operators using a restarting procedure incorporated into a multi-queue best-first search. These techniques improve TFD's coverage drastically and preserve the average solution quality, leading to a system that solves more problems than each of the competitors of the temporal satisficing track of IPC 2011 and clearly outperforms all of them in terms of IPC score.
Thomas Keller und Patrick Eyerich.
PROST: Probabilistic Planning Based on UCT.
In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012), S. 119-127. 2012.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

We present PROST, a probabilistic planning system that is based on the UCT algorithm by Kocsis and Szepesvari (2006), which has been applied successfully to many areas of planning and acting under uncertainty. The objective of this paper is to show the application of UCT to domain-independent probabilistic planning, an area it had not been applied to before. We furthermore present several enhancements to the algorithm, including a method that is able to drastically reduce the branching factor by identifying superfluous actions. We show how search depth limitation leads to a more thoroughly investigated search space in parts that are influential on the quality of a policy, and present a sound and polynomially computable detection of reward locks, states that correspond to, e.g., dead ends or goals. We describe a general Q-value initialization for unvisited nodes in the search tree that circumvents the initial random walks inherent to UCT, and leads to a faster convergence on average. We demonstrate the significant influence of the enhancements by providing a comparison on the IPPC benchmark domains.
Johannes Löhr, Patrick Eyerich, Thomas Keller und Bernhard Nebel.
A Planning Based Framework for Controlling Hybrid Systems.
In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012). 2012.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The control of dynamic systems, which aims to minimize the deviation of state variables from reference values in a contin- uous state space, is a central domain of cybernetics and con- trol theory. The objective of action planning is to find feasible state trajectories in a discrete state space from an initial state to a state satisfying the goal conditions, which in principle ad- dresses the same issue on a more abstract level. We combine these approaches to switch between dynamic system charac- teristics on the fly, and to generate control input sequences that affect both discrete and continuous state variables. Our approach (called Domain Predictive Control) is applicable to hybrid systems with linear dynamics and discretizable inputs.
Patrick Eyerich.
Preferring Properly: Increasing Coverage while Maintaining Quality in Anytime Temporal Planning.
In Proceedings of the ICAPS-12 Workshop on Heuristics and Search for Domain Independent Planning (HSDIP 2012). 2012.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

Temporal Fast Downward (TFD) is a successful temporal planning system that is capable of dealing with numerical values. Rather than decoupling action selection from scheduling, it searches directly in the space of time-stamped states, an approach that has shown to produce plans of high quality at the price of coverage. To increase coverage, TFD incorporates deferred evaluation and preferred operators, two search techniques that usually decrease the number of heuristic calculations by a large amount. However, the current definition of preferred operators offers only limited guidance in problems where heuristic estimates are weak or where subgoals require the execution of mutex operators. In this paper, we present novel methods for refinement of this definition and show how to combine the diverse strengths of different sets of preferred operators using a restarting procedure incorporated into a multi-queue best-first search. These techniques improve TFD's coverage drastically and preserve the average solution quality, leading to a system that solves more problems than each of the competitors of the temporal satisficing track of IPC 2011 and clearly outperforms all of them in terms of IPC score.

2011

Thomas Keller und Patrick Eyerich.
A Polynomial All Outcome Determinization for Probabilistic Planning.
In Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp und Malte Helmert (Hrsg.), Proceedings of the 21th International Conference on Automated Planning and Scheduling (ICAPS 2011), S. 331-334. AAAI Press 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

Most predominant approaches in probabilistic planning utilize techniques from the more thoroughly investigated field of classical planning by determinizing the problem at hand. In this paper, we present a method to map probabilistic operators to an equivalent set of probabilistic operators in a novel normal form, requiring polynomial time and space. From this, we directly derive a determinization which can be used for, \eg, replanning strategies incorporating a classical planning system. Unlike previously described all outcome determinizations, the number of deterministic operators is not exponentially but polynomially bounded in the number of parallel probabilistic effects, enabling the use of more sophisticated determinization-based techniques in the future.
J. Benton, Patrick Eyerich und Subbarao Kambhampati.
Enhancing Search for Satisficing Temporal Planning with Objective-driven Decisions.
In Proceedings of the ICAPS-2011 Workshop on Heuristics for Domain-independent Planning, S. 59-65. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

Heuristic best-first search techniques have recently enjoyed ever-increasing scalability in finding satisficing solutions to a variety of automated planning problems, and temporal planning is no different. Unfortunately, achieving efficient computational performance often comes at the price of clear guidance toward solution of high quality. This fact is sharp in the case of many best-first search temporal planners, who often use a node evaluation function that is mismatched with the objective function, reducing the likelihood that plans returned will have a short makespan but increasing search performance. To help mitigate matters, we introduce a method that works to progress search on actions declared ``useful'' according to makespan, even when the original search may ignore the makespan value of search nodes. We study this method and show that it increases over all plan quality in most of the benchmark domains from the temporal track of the 2008 International Planning Competition.

2010

Kai M. Wurm, Christian Dornhege, Patrick Eyerich, Cyrill Stachniss, Bernhard Nebel und Wolfram Burgard.
Coordinated Exploration with Marsupial Teams of Robots using Temporal Symbolic Planning.
In Proceedings of the 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2010). 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

The problem of autonomously exploring an environment with a team of robots received considerable attention in the past. However, there are relatively few approaches to coordinate teams of robots that are able to deploy and retrieve other robots. Efficiently coordinating the exploration with such marsupial robots requires advanced planning mechanisms that are able to consider symbolic deployment and retrieval actions. In this paper, we propose a novel approach for coordinating the exploration with marsupial robot teams. Our method integrates a temporal symbolic planner that explicitly considers deployment and retrieval actions with a traditional cost-based assignment procedure. Our approach has been implemented and evaluated in several simulated environments and with varying team sizes. The results demonstrate that our proposed method is able to coordinate marsupial teams of robots to efficiently explore unknown environments.
Thomas Keller, Patrick Eyerich und Bernhard Nebel.
Task Planning for an Autonomous Service Robot.
In Rüdiger Dillmann, Jürgen Beyerer, Uwe Hanebeck und Tanja Schultz (Hrsg.), Proceedings on the 33rd Annual German Conference on Artificial Intelligence (KI 2010), S. 358-365. Springer-Verlag 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

In the DESIRE project an autonomous robot capable of performing service tasks in a typical kitchen environment has been developed. The overall system consists of various loosely coupled subcomponents providing particular features like manipulating objects or recognizing and interacting with humans. To bring all these subcomponents together to act as monolithic system, a high-performance planning system has been implemented. In this paper, we present this system’s basic architecture and some advanced extensions necessary to cope with the various challenges arising in dynamic and uncertain environments like those a real world service robot is usually faced with.
Patrick Eyerich, Thomas Keller und Malte Helmert.
High-Quality Policies for the Canadian Traveler's Problem.
In Maria Fox und David Poole (Hrsg.), Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2010), S. 51-58. AAAI Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

We consider the stochastic variant of the Canadian Traveler's Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost.

We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.
Patrick Eyerich, Thomas Keller und Malte Helmert.
High-Quality Policies for the Canadian Traveler's Problem (Extended Abstract).
In Ariel Felner und Nathan Sturtevant (Hrsg.), Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS 2010), S. 147-148. AAAI Press 2010.
Extended abstract of the AAAI paper by the same name.
(PDF)
J. Benton, Kartik Talamadupula, Patrick Eyerich, Robert Mattmüller und Subbarao Kambhampati.
G-value Plateaus: A Challenge for Planning.
In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 259-262. AAAI Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

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.
Moritz Göbelbecker, Thomas Keller, Patrick Eyerich, Michael Brenner und Bernhard Nebel.
Coming Up with Good Excuses: What To Do When No Plan Can be Found.
In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 81-88. AAAI Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

When using a planner-based agent architecture, many things can go wrong. First and foremost, an agent might fail to execute one of the planned actions for some reasons. Even more annoying, however, is a situation where the agent is incompetent, i.e., unable to come up with a plan. This might be due to the fact that there are principal reasons that prohibit a successful plan or simply because the task's description is incomplete or incorrect. In either case, an explanation for such a failure would be very helpful. We will address this problem and provide a formalization of coming up with excuses for not being able to find a plan. Based on that, we will present an algorithm that is able to find excuses and demonstrate that such excuses can be found in practical settings in reasonable time.
Patrick Eyerich, Thomas Keller und Malte Helmert.
High-Quality Policies for the Canadian Traveler's Problem.
In Proceedings of the ICAPS-2010 Workshop on Planning and Scheduling Under Uncertainty. 2010.
Superseded by the AAAI 2010 paper by the same name.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

We consider the stochastic variant of the Canadian Traveler's Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost.

We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.
Patrick Eyerich, Thomas Keller und Bernhard Nebel.
Combining Action and Motion Planning via Semantic Attachments.
In Proceedings of the Workshop on Combining Action and Motion Planning at ICAPS 2010 (CAMP 2010), S. 19. 2010.
Extended Abstract.
(PDF) (BIB)

2009

Christian Dornhege, Patrick Eyerich, Thomas Keller, Sebastian Trüg, Michael Brenner und Bernhard Nebel.
Semantic Attachments for Domain-Independent Planning Systems.
In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 114-121. AAAI Press 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

Solving real-world problems using symbolic planning often requires a simplified formulation of the original problem, since certain subproblems cannot be represented at all or only in a way leading to inefficiency. For example, manipulation planning may appear as a subproblem in a robotic planning context or a packing problem can be part of a logistics task. In this paper we propose an extension of PDDL for specifying semantic attachments. This allows the evaluation of grounded predicates as well as the change of fluents by externally specified functions. Furthermore, we describe a general schema of integrating semantic attachments into a forward-chaining planner and report on our experience of adding this extension to the planners FF and Temporal Fast Downward. Finally, we present some preliminary experiments using semantic attachments.
Patrick Eyerich, Robert Mattmüller und Gabriele Röger.
Using the Context-enhanced Additive Heuristic for Temporal and Numeric Planning.
In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 130-137. AAAI Press 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF) (BIB)

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.

2008

Paul Plöger, Kai Pervölz, Christoph Mies, Patrick Eyerich, Michael Brenner und Bernhard Nebel.
The DESIRE Service Robotics Initiative.
Künstliche Intelligenz 08 (4), S. 29-32. 2008.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We present some advanced hardware units and an appropriate component based SW architecture for DESIRE. As an example we describe the integration of a enhanced AI task planner which allows for higher flexibility and dependability during complex task execution.
Patrick Eyerich, Michael Brenner und Bernhard Nebel.
On the Complexity of Planning Operator Subsumption.
In Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), S. 518-527. AAAI Press 2008.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

Formal action models play a central role in several subfields of AI because they are used to model application domains, e.g., in automated planning. However, there are hitherto no automated methods for relating such domain models to each other, in particular for checking whether one is a specialization or generalization of the other. In this paper, we introduce two kinds of subsumption relations between operators, both of which are suitable for modeling and verifying hierarchies between actions and operators: applicability subsumption considers an action to be more general than another if the latter can be replaced by the first at each point in each sound sequence of actions; abstraction subsumption exploits relations between actions from an ontological point of view. For both kinds of subsumption, we prove complexity results for verifying operator subsumption in three important subclasses: The problems are NP-complete when the expressiveness of the operators is restricted to the well-known basic STRIPS formalism, Sigma_p_2-complete when we admit boolean logical operators and undecidable when the full power of the planning language ADL is permitted.

2007

Jens Claßen, Patrick Eyerich, Gerhard Lakemeyer und Bernhard Nebel.
Towards an Integration of Golog and Planning.
In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), S. 1846-1851. AAAI Press 2007.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

The action language Golog has been applied successfully to the control of robots, among other things. Perhaps its greatest advantage is that a user can write programs which constrain the search for an executable plan in a xible manner. However, when general planning is needed, Golog supports this only in principle, but does not measure up with state-of-the-art planners. In this paper we propose an integration of Golog and planning in the sense that planning problems, formulated as part of a Golog program, are solved by a modern planner during the execution of the program. Here we focus on the ADL subset of the plan language PDDL. First we show that the semantics of ADL can be understood as progression in the situation calculus, which underlies Golog, thus providing us with a correct embedding of ADL within Golog. We then show how Golog can be integrated with an existing ADL planner for closed-world initial databases and compare the performance of the resulting system with the original Golog.
Patrick Eyerich.
Subsumption deterministischer Aktionsschemata.
Diplomarbeit, Albert-Ludwigs-Universität, Freiburg, Germany 2007.
In German.
(PDF)

2006

Patrick Eyerich, Bernhard Nebel, Gerhard Lakemeyer und Jens Classen.
Golog and PDDL: What is the Relative Expressiveness?
In Proceedings of the International Symposium on Practical Cognitive Agents and Robots (PCAR 2006), S. 93-104. University of Western Australia Press 2006.
(Abstract einblenden) (Abstract ausblenden) (PDF) (BIB)

Action formalisms such as GOLOG or FLUX have been developed primarily for representing and reasoning about change in a logical framework. For this reason, expressivity was the main goal in the development of these formalisms. In another line of research, efficiency of planning methods was the topmost goal resulting in the basic STRIPS language, which has only moderate expressivity. The planning language PDDL developed since 1998 is an extension of basic STRIPS with many expressive features. Now the interesting question is how PDDL compares to GOLOG or other action languages from an expressivity point of view. We will show that a GOLOG fragment, which we call Restricted Basic Action Theories, is as expressive as the ADL fragment of PDDL. To prove this equivalence we use the compilation framework. From a practical point of view, this result can be used for employing efficient planners inside a GOLOG interpreter.
Patrick Eyerich.
Zu ADL gleichausdrucksstarke Basic-Action-Theorien im Situationskalkül.
Studienarbeit, Albert-Ludwigs-Universität, Freiburg, Germany 2006.
In German.
(PDF)