• English
• Deutsch

• University of Freiburg
• Faculty of Engineering
• Department of Computer Science

Manuela Ortlieb – Publications

(Show all abstracts) (Hide all abstracts)

2015

• David Speck, Manuela Ortlieb and Robert Mattmüller.
  Necessary Observations in Nondeterministic Planning.
  In Proceedings of the 38th German Conference on Artificial Intelligence (KI 2015). 2015.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  An agent that interacts with a nondeterministic environment can often only partially observe the surroundings. This necessitates observations via sensors rendering more information about the current world state. Sensors can be expensive in many regards therefore it can be essential to minimize the amount of sensors an agent requires to solve given tasks. A limitation for sensor minimization is given by essential sensors which are always required to solve particular problems. In this paper we present an efficient algorithm which determines a set of necessary observation variables. More specifically, we develop a bottom-up algorithm which computes a set of variables which are always necessary to observe, in order to always reach a goal state. Our experimental results show that the knowledge about necessary observation variables can be used to minimize the number of sensors of an agent.

• Jonas Thiem, Robert Mattmüller and Manuela Ortlieb.
  Counterexample-Guided Abstraction Refinement for POND Planning.
  In Proceedings of the ICAPS-2015 Workshop on Model Checking and Automated Planning (MOCHAP 2015). 2015.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Counterexample-guided abstraction refinement (CEGAR) allows to gradually refine a problem definition until the required detail for a solution is present. We propose the use of CEGAR to demonstrate unsolvability of a planning problem while avoiding a search through the whole state space. This allows a sensor minimization algorithm for partially observable non-deterministic (POND) planning problems to determine the definitive unsolvability notably faster, which is a necessary part of current approaches of computing the minimal sensor variable set. We determine from our empirical results that while the presented algorithm causes some slowdown for solvable problems, the unsolvability is determined at a much greater speed with this novel approach.

2014

• Robert Mattmüller, Manuela Ortlieb and Erik Wacker.
  Minimizing Necessary Observations for Nondeterministic Planning.
  In Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014). 2014.
  (Show abstract) (Hide abstract) (PDF)
  

  Autonomous agents interact with their environments via sensors and actuators. Motivated by the observation that sensors can be expensive, in this paper we are concerned with the problem of minimizing the amount of sensors an agent needs in order to successfully plan and act in a partially observable nondeterministic environment. More specifically, we present a simple greedy top-down algorithm in the space of observation variables that returns an inclusion minimal set of state variables sufficient to observe in order to find a plan. We enhance the algorithm by reusing plans from earlier iterations and by the use of functional dependencies between variables that allows the values of some variables to be inferred from those of other variables. Our experimental evaluation on a number of benchmark problems shows promising results regarding runtime, numbers of sensors and plan quality.

• Andreas Hertle, Christian Dornhege, Thomas Keller, Robert Mattmüller, Manuela Ortlieb and Bernhard Nebel.
  An Experimental Comparison of Classical, FOND and Probabilistic Planning.
  In Proceedings of the 37th German Conference on Artificial Intelligence (KI 2014), pp. 297-308. Springer 2014.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  Domain-independent planning in general is broadly applicable to a wide range of tasks. Many formalisms exist that allow to describe different aspects of realistic problems. Which one is best is not clear as usually more expressiveness comes with a cost in planning time. Under the assumption that hard guarantees are not required, users are faced with a decision between multiple approaches. In this work we study the effect of nondeterministic action outcomes. As a generic model we use a probabilistic description in the form of Markov Decision Processes (MDPs). We define abstracting translations into a classical planning formalism and fully observable nondeterministic (FOND) planning. Our goal is to give insight into how state-of-the-art systems perform on different MDP planning domains. We evaluate those MDPs by running state-of-the-art planning systems on the abstracted formalisms.

2013

• Manuela Ortlieb and Robert Mattmüller.
  Pattern-Database Heuristics for Partially Observable Nondeterministic Planning.
  In Proceedings of the 36th German Conference on Artificial Intelligence (KI 2013). 2013.
  (Show abstract) (Hide abstract) (PDF) (slides; PDF)
  

  Heuristic search is the dominant approach to classical planning. However, many realistic problems violate classical assumptions such as determinism of action outcomes or full observability. In this paper, we investigate how - and how successfully - a particular classical technique, namely informed search using an abstraction heuristic, can be transferred to nondeterministic planning under partial observability. Specifically, we explore pattern-database heuristics with automatically generated patterns in the context of informed progression search for strong cyclic planning under partial observability. To that end, we discuss projections and how belief states can be heuristically assessed either directly or by going back to the contained world states, and empirically evaluate the resulting heuristics internally and compared to a delete-relaxation and a blind approach. From our experiments we can conclude that in terms of guidance, it is preferable to represent both nondeterminism and partial observability in the abstraction (instead of relaxing them), and that the resulting abstraction heuristics significantly outperform both blind search and a delete-relaxation approach where nondeterminism and partial observability are also relaxed.

2012

• Silvan Sievers, Manuela Ortlieb and Malte Helmert.
  Efficient Implementation of Pattern Database Heuristics for Classical Planning.
  In Proceedings of the Fifth Annual Symposium on Combinatorial Search (SoCS 2012), pp. 105-111. AAAI Press 2012.
  (Show abstract) (Hide abstract) (PDF)
  

  Despite their general success in the heuristic search community, pattern database (PDB) heuristics have, until very recently, not been used by the most successful classical planning systems. We describe a new efficient implementation of pattern database heuristics within the Fast Downward planner. A planning system using this implementation is competitive with the state of the art in optimal planning, significantly improving over results from the previous best PDB heuristic implementation in planning.

2010

• Robert Mattmüller, Manuela Ortlieb, Malte Helmert and Pascal Bercher.
  Pattern Database Heuristics for Fully Observable Nondeterministic Planning.
  In Ronen Brafman, Héctor Geffner, Jörg Hoffmann and Henry Kautz (eds.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), pp. 105-112. AAAI Press 2010.
  (Show abstract) (Hide abstract) (PDF) (slides; PDF) (BIB)
  

  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.

• Contact Legal Information