Arbeitsgruppe Grundlagen der Künstlichen Intelligenz

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

2008

• 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). 2008.
  To appear.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  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 Classen, Patrick Eyerich, Gerhard Lakemeyer und Bernhard Nebel.
  Towards an Integration of Golog and Planning.
  In 20th International Joint Conference on Artificial Intelligence (IJCAI 2007). AAAI Press 2007.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  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 Proc. of International Symposium on Practical Cognitive Agents and Robots. University of Western Australia Press 2006.
  (Abstract einblenden) (Abstract ausblenden) (PDF)
  

  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)