About  |  Study  |  Members  |  Projects  |  Publications  |  Events  |  Search  |  Internals  |  Contact & Imprint

Planning Techniques and Action Languages

Title

Logic-based Knowledge Representation - Planning Techniques and Action Languages

Principal investigators

Gerhard Lakemeyer

Bernhard Nebel

Funding agency

Deutsche Forschungsgemeinschaft (DFG), Project NE 621/10

Project abstract

Although there is a common origin, research on automated planning on the one hand and action logics on the other hand developed rather independently over the last three decades. This is mainly due to the fact that work on action languages was concerned with formalisms of high expressiveness, whereas for planning methods, the focus had to lie on computational efficiency, yielding input languages with less expressive possibilities. However, one can observe that during the last few years, the two separate fields began to converge again. Exemplary for this trend is the development of the planning domain definition language PDDL, which extends simple STRIPS-based planning by features such as conditional effects, time, concurrency, plan constraints and preferences, and which virtually constitutes a standard in the field of planning.

The aim of this project is to integrate the latest developments in the fields of both action languages (in particual, Golog) and planning techniques (in particular, PDDL-based planners like FF and its descendants) to acquire systems that are both expressive and efficient. In the first phase of the project, this goal will be tackled by on the one hand establishing a common semantical basis for Golog and PDDL in the Situation Calculus. On the other hand, expressiveness is to be studied by means of compilation schemes. This work will provide the foundation for the embedding of state-of-the-art planning systems like FF into Golog and enhancing planners with Golog relevant features such as time, concurrency and continuous actions.

Available Golog systems as well as planners currently lack an efficient and expressive way of representing incomplete world knowledge; for means of efficiency, they usually rely on the closed world and domain closure assumptions. Since these assumptions are not realistic in practice, the second project phase will deal with extending both Golog systems and PDDL-based planners with the possibility of using incomplete knowledge in a tractable manner.

Another aspect to be studied is how to speed up the execution of Golog programs in those situations where there actually is complete information about the current world state. Instead of only calling a PDDL planner and providing it with the translation of the primitive actions of the Golog domain, entire Golog programs (that contain valuable control information in the form of macro actions that restrict the space of possible plans) shall be efficiently translated into PDDL problems that can then be solved by a planning system. A further aim is to not only embed domain-independent PDDL-based planners into Golog, but to do so also with systems such as TLPlan or TALplanner that possess the ability to consider domain knowledge to drastically reduce their search space. For that purpose it is necessary to identify sublanguages of the situation calculus that correspond to those planners' underlying input logics. Finally, the newly developed systems and methods shall be evaluated on mobile robots and appropriate benchmark problems.

Start date

01.09.2005

Duration

48 months

Collaborators

Jens Claßen

Patrick Eyerich

Gerhard Lakemeyer

Bernhard Nebel

Gabi Röger