A Declarative Planning System Based on Logic Programming

Research project P 14781 A Declarative Planning System Based on Logic Programming Nicola LEONE 27.11.2000 Declarative approaches to planning have been recently proposed in the literature. In these approaches, the user specifies the planning problem in a logic-based declarative formalism. Finding the desired plans is then reduced to elementary problems in computational logic such as satisfiability checking, which are solved by an efficient computational engine. The main goal of this project is to advance this line of research, and to build a declarative planning system which overcomes some shortcomings of current approaches to declarative planning. In particular, the computation of plans which are optimal according to criteria such as costs of actions or desirability of states should be supported, and computing such plans should be possible also in scenarios where the knowledge about the planning world is incomplete. The system proposed will. be based on logic programming and provide its enlarged expressive capabilities through suitable constructs in a planning language. The following subgoals will be researched: (i) the development of an advanced declarative planning language; (ii) the design and implementation of a declarative planning system supporting the proposed language; and (iii) the application of the system in various domains. To this end, we can take advantage of the knowledge and experience that we have gained in previous projects, including the successful FWF project P 1 1580-MAT. We intend to use the DLV system, which is a state-of-the-art system for disjunctive logic programming that has been developed in the quoted project, as an efficient computationa.1 engine which will serve as the basis for building the basis for building the implementation.

Planning is a challenging research area since the early days of Artificial Intelligence. The classical planning problem is the task of finding a sequence of actions leading from a given initial state to a desired goal state, where only information about actions and their preconditions and effects is available. The range of application domains ranges from classical route planning to automatic composition of Web Services. Whereas classical planning languages, such as STRIPS or PDDL, assume complete knowledge about the initial state and deterministic action effects, in real world scenarios these restrictions are often too strong. In the course of this project we have developed an expressive planning language, Kc, which allows for non-classical planning with incomplete knowledge. However, the increased expressive power of this language entail an increased complexity for computing plans: Classical search algorithms can no longer be used for solving planning problems expressed in Kc. Instead, declarative methods for problem-solving, for instance from the area of logic programming, can be fruitfully applied. In project P-14781 we have investigated several aspects of solving these problems: The developed language K c has been extended by concepts from the area of Logic Programming. The utility of these extensions could be shown in various example settings. For planning under incomplete knowledge different semantics have been defined: optimistic plans are sequences of actions, which may establish the goal, while secure plans establish the goal under any circumstances. These basic semantics have furthermore been extended to planning with action costs, where each action can have an assigned cost value. Here, we have adressed the question of finding optimal plans as well as plans which stay within a certain overall cost limit. Moreover, we have analyzed the complexity of various associated computational tasks and developed efficient transformations from planning problems to disjunctive logic programs. These methods have been implemented in the planning system DLVK , the performance of which proved to be comparable to existing approaches. Finally, we have investigated a practical application scenario, involving the design and monitoring of multi-agent systems, where the developed methods proved to be useful.