Home › About me

Temporally Expressive Planning by ASP + CLP

Introduction to automated planning

Planning is a kind of problems we solve every day, e.g., finding the path from one place to another or making a delicious dinner from raw ingredients. For centuries (yes centuries, not decades), automated planning by a machine (e.g., a computer) has been one of the dreams under the banner of artificial intelligence. Now automated planning has many awesome applications, including operating Hubble telescope and Mars rovers.

For studying planning, AI researchers model the problem first. To me, planning is about state transitions over a world by actions.

  • A world can be considered as a set of Boolean propositions and arithmetic values, e.g., whether I have worked out today and the temperature outside.
  • A state is a collection of values of those Boolean propositions and arithmetic variable, e.g., i have not worked out today and the temperature outside is 75 F.
  • An action has two parts, the conditions and effects. For example, let’s say we have an action called jogging.
    • The condition of jogging is that the temperature outside is above 70 F.
    • The effect is that I have worked out today.

    Note that an action can have more than one conditions or none. So are for effects.

  • Using the terminology introduced above, a planning problem is about finding a sequence of actions such that the state transitions start from the initial state and end in a state that satisfies the goal. For example, let the initial state be that ``I haven’t worked out today and the temperature outside is 75F’’ and let the goal be that ``I’ve worked out today.’’ The valid plan is then just one action, jogging. Of course, you may have more than one plans for a planning problem, or none.

There are still two big challenges in automated planning:

  • First, in real applications, a planning problem can be on a more complicated world and have a lot more actions, each of which has many conditions and effects. You want to compute a plan fast enough - somehow real time. Otherwise a Mars rover may fall off the cliff before it finds a plan to avoid it.
  • Second, the planning problem in the example we used above is classified as classical planning. More sophisticated cases include temporal planning and probabilistic planning. My PhD thesis is about temporal planning, where you need to deal with durative actions where continuous variables may change along time in the elapsing of the actions. Actions may be executed serially or concurrently. But there is a subcategory which does not have any serial plan, called temporally expressive planning. This is the focus of my thesis.

PDDL2.1: Representing temporally expressive planning

An HTML version of the PDDL2.1 paper

The first step of automated planning is to represent planning problems to computers via a programming language. The de facto language for this purpose is PDDL, introduced in 1998. A new version PDDL2.1, debuted in 2002, allows users to define durative actions and numerical expressions.

The next step is to build a solver which is a computer program whose input is a planning problem and the output is a valid plan. Some solvers for PDDL2.1 have been proposed soon after the introduction of PDDL2.1. But as Cushing et al. pointed out, those solvers cannot solve temporally expressive planning problems [3]. The search for a ``real’’ temporal planner started after that.

Previous solvers: PDDL2.1-to-SAT and PDDL2.1-to-CSP

Since planning is about satisfaction, many researchers adopt the idea of translating a PDDL2.1 program into a constraint programming problem, such as CSP and SAT. In this way, a PDDL solver is modularized into two parts: a translator and a constraint solver. This approach has a huge benefit that the development in constraint solving can be ported for planning easily to build a faster planner. However, those pioneering works have some drawbacks. The PDDL2.1-to-SAT approach [1] needs to discretize time and all time-dependent continuous variables. The solver may be slow because of large search space. The PDDL2.1-to-CSP approach [2] cannot solve problems with continuous effects, where values of variables change proportionally to time as actions elapse. Besides, all existing solvers, except PDDL2.1-to-SAT, cannot easily support PDDL extensions, e.g., PDDL axioms.

The idea of this type of solvers can be illustrated by the flowchart below. 

 ________________________________________
|         Input: PDDL2.1 program         |
|                   |                    |
|                   V                    |
|   __________________________________   |
|  |  PDDL2.1-to-SAT/CSP translator   |  |
|  |                |                 |  |
|  |                V                 |--+------- SAT/CSP-based PDDL2.1 solver
|  |        SAT/CSP solver            |  |
|  +----------------------------------+  |
|                   |                    |
|                   V                    |
|   Output: Plan as SAT/CSP solution     |
+----------------------------------------+

Our approach: PDDL2.1-to-AC(C)

My PhD thesis, specifically, is solving PDDL2.1 planning by translating PDDL2.1 programs into programs in a newly developed constraint and logic programming language AC(C) [4]. In this way, we can hopefully resolve the drawbacks of previous works. The language AC(C) combines logical reasoning (e.g., i haven’t worked out yet so i will jog. ) and constraint solving (e.g., 75 > 70, so i can jog). In contrast, SAT is good at logical reasoning while CSP is good at constraint solving. Since planning involves both logical reasoning and constraint solving , AC(C) sounds a better choice.

Major advantages of this approach are:

  • No need to discretize time - in contrast to SAT-based approach
  • being able to solve problems having continuous effects - in constrast to CSP-based approach
  • taking advantage from the fast development in ASP/SAT and CLP solvers
  • Easy support to PDDL extensions, such as PDDL axioms which are essentially logic programs

Technical write-ups:

I host the PDFs above at Google Docs and Ubuntu One. Please let me know if you cannot open any of them.

Publications

References

  1. Ruoyun Huang, Yixin Chen and Weixiong Zhang, A Novel Transition Based Encoding Scheme for Planning as Satisfiability, AAAI-10, 2010 (Outstanding Paper Award of AAAI-10)
  2. Yuxiao Hu, Temporally Expressive Planning as Constraint Satisfaction Problems, ICAPS-07, 2007
  3. William Cushing, Subbarao Kambhampati, Mausam and Daniel S Weld, When is Temporal Planning Really Temporal?, IJCAI-07, 2007
  4. Venna S. Mellarkod, Michael Gelfond and Yuanlin Zhang, Integrating answer set programming and constraint logic programming, Annals of Mathematics and Artificial Intelligence, 2007

Related works

Tutorials about ASP

Jia-Huai You, Introduction to Answer Set Programming, http://webdocs.cs.ualberta.ca/~you/courses/621-2010/Lecture-Notes/intro-...
Aarati Parmar, Answer Set Programming,: http://www-cs-students.stanford.edu/~aarati/slides/answersets/ans-1.html, 2000, Stanford Formal Reasoning Group
Prolog: http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/contents.html
Vladimir Lifschitz, What is Answer Set Programming, http://www.cs.utexas.edu/users/vl/papers/wiasp.pdf
Agostino Dovier and Enrico Pontelli, Present and Future Challenges for ASP Systems, http://www.springerlink.com/content/l7581u1515553756/fulltext.pdf