HTN Planning in Answer Set Programming

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:

juergen.dix@tu-clausthal.de

Images

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.

Example Scenarios

We show the following examples:

  • The Simple Travel Domain

    This domain is one of the domains included in the distribution of the SHOP planning system. The scenario for the domain is that we want to travel from one location to another in a city. We have three locations: downtown, uptown, and park. There are two possible means of transportation: by taxi and by bus. Taxi travel involves hailing the taxi, riding to the destination and paying the driver $1.50 plus $1.00 for each mile travelled. Bus travel involves hailing the bus, paying the driver $1.00, and riding to the destination. Thus, different plans are possible depending on the weather conditions, the distance between our current location and the one we want to go, and how much money we have.

    Source Codes:
    Smodels Domain Encoding, DLV Domain Encoding, SHOP Domain Description
    Problem Instances:

    Smodels Problems (p1, p2, p3, p4, p5, p6, p7, p8)
    DLV Problems (p1, p2, p3, p4, p5, p6, p7, p8)
    SHOP Problems
    Click to see a demo of how the system works!

  • The Miconic-10 Elevator Domain

    It is the simplest version of the Miconic-10 Elevator domain, which was one of the planning domains in the AIPS-2000 planning competition. It has the following specifications: (1) the planner simply has to generate plans to serve a group of passengers of whom the origin and destination floors are given, and (2) there are no constraints such as satisfying space requirements of passengers or achieving optimal elevator controls.

    Source Codes:
    Smodels Domain Encoding, DLV Domain Encoding, SHOP Domain Description
    Problem Instances:
    Smodels Problems (p1, p2, p3, p4, p5-1, p5-2, p6)
    DLV Problems (p1, p2, p3, p4, p5-1, p5-2, p6)
    SHOP Problems
  • The Zeno-Travel Domain

    It was one of the domains that were introduced as recent benchmarks in International Planning Competition (IPC-2002). This domain involves transporting people around in planes, using different modes of movement: fast and slow.

    Source Codes:
    Smodels Domain Encoding, DLV Domain Encoding, SHOP Domain Description
    Problem Instances:
    Smodels Problems (p1, p2, p3, p4, p5, p6, p7, p8,p9, p10, p11, p12, p13, p14, p15)
    DLV Problems (p1, p2, p3, p4, p5, p6, p7, p8,p9, p10, p11, p12, p13, p14, p15)
    SHOP Problems

Literature