Project Members:
Duration: 2001 - 2005
Funding: Partially funded by WASP (IST-2001-37004)
Project Description:
In this research, we are interested in investigating formalisms for solving planning
problems based on Hierarchical Task Network (HTN) planning paradigms using
Answer Set Programming (ASP). HTN
planning, an approach that has led recently to very some efficient planners (e.g., SHOP, SHOP2, O-Plan, Sipe-2, etc).
The ASP paradigm evolved out of the stable semantics for logic
programs in recent years and is strongly related to nonmonotonic
logics. It also led to various very efficient implementations
(smodels, DLV). While all approaches of using ASP for planning
considered so far rely on STRIPS-STYLE planning, we
would like to consider for the first time various formulations of HTN planning systems
and define a systematic
translation method from their representation of the planning
problem into logic programs with negation. We aim to produce translations that are sound
and complete: answer sets of
the logic program obtained by our translation correspond exactly
to the solutions of the planning problem. Our approaches will not
rely on a particular system for computing answer sets and serve
several purposes. We would like to have the following contributions as we progress in our research:
- Our approach constitutes a means to evaluate ASP
systems by using well-established benchmarks from the planning
community.
- It makes the more expressive HTN planning
available in ASP.
- We are interested in investigating whether our approach outperforms action-based planning methods
formulated in ASP. Our first attempts seem to be supporting this conjecture. Also, when our our first attempts on ASP
solvers showed that the time requirements of our programs appear to grow no faster than
roughly proportional to that of a dedicated HTN planning system (SHOP). We believe this is a very encouraging result.
- We also aim to investigate the performance of ASP systems using different grounding strategies.
Contact E-Mail: dix [at] tu-clausthal.de
Project Details
Usage of Answer-Set Programming
There are several well-established methods to transform planning
problems into ASP. We developed a method to transform HTN planning problems into logic
programs, such that answer sets correspond exactly to valid plans. While the overall methodology is straightforward, the
precise encoding is cumbersome and leaves several opportunities for optimization.
Benefits of Using Answer-Set Programming
ASP makes it possible to improve and extend HTN planning in various ways:
- even more domain knowledge can be used and incorporated into the
transformed program (to prune the search space and make planning more efficient).
- ASP is well suited to deal with incomplete information (while HTN
planning is not). Therefore there are possibilities to use the transformed program to deal with
HTN planning under incomplete information.
- there are powerful methods to deal with prioritized logic programs:
these could be used in the transformed program to make HTN planning more expressive and/or more efficient.