cse574 - Notes for 03/13/03

LTL - Linear Temporal Logic
=============================

LTL allows us to make statements about sequence of steps using such steps and action descriptors as "until", "next", "always", and "eventaully". It tells us which steps should be allowed while expanding the search tree in a forward search planner.

A planner picks a state from a queue and checks if the sequence is consistant with all domain knowledge. If so, the state is expanded. Otherwise, planner picks another state from the queue. This check should be cheap. 

"Until", "next", "always" and "eventually" can represent external domain knowledge. In blocks-world, rules such as: "Good towers are those that do not violate any goal conditions" and "Keep growing good towers and avoid bad towers" are examples of knowledge that can be represented by LTL (see week8.ppt slides for gory details). 

With proper representation of domain knowledge, some planners can solve blocks-works problems consisting of 400-500 blocks in a second.

Main purpose of LTL rules is to prune states in the search tree, which does not effect soundness. It is however hard to talk about optimality (whether it's a step, an action or a resource optimality), because even if we can establish that a certain domain knowledge guarantees optimality, we would have to reconfirm it again with the smallest change in the domain description. 

Since the rules describe sequence of steps, they are more natural to write in a state-based planning than in a partially ordered plans. In POP, we don't know which order was used by planner to check for open conditions. 


Task Decomposition (HTN) Planning
==================================

HTN - Hierarchical Task Network

HTN allows us to think in terms of abstract actions. Abstract actions are eventualy expressed in primitive actions. For example an action "go_to_school" can be accomplished by any of the following actions: "bike", "walk", or "take_a_bus". In turn, these actions can be accomplished by one or more primitive actions. There can be many levels of abstraction, but only plans with primitive actions (and no abstract actions) are executable. 

We can treat an abstract action as a plan flaw. To remove the flaw, we have to pick an abstract action and see if there is a set of primitive actions into which the abstract action can be broken up into. It is similar to considering partial plans. Both have a set of steps, set of orderings and a set of causal links. 

Task reduction methods (which is an extra domain knowledge from user) are used to reduce abstract actions to primitive ones. 

Q: If all links between abstract actions are unsafe, will the plan be inconsistent when these actions will be reduced to primitive actions?

A: That depends. Here's an example of a consistent plan resulting from reduction of abstract actions with unsafe links:

Abstract actions A and B with unsafe links:
Action A needs S and gives ~Q, ~R and P
Action B needs R and gives ~S, ~P and Q


      S   -----   ~Q ~R P
     ----|  A  |----------
    /     -----           \
   /                       \
---                         -------              
   \                       /
    \     -----           /
     ----|  B  |----------
      R   -----   ~S ~P Q



Reduced to primitive actions:
Action A is reduced to A1 and A2
Action B is reduced to B1 and B2

       S   ------  P           ------  ~R ~Q
      ----|  A1  |------------|  A2  |----
    /      ------              ------     \
   /                                       \
---                                         ------
   \                                       /
    \      ------              ------     /
      ----|  B1  |------------|  B2  |----
       R   ------  ~P       Q  ------  ~S

Now actions can be scheduled: B1-A1-B2-A2 forming a valid plan (provided ~Q,~S,~R and P satisfy subgoals)


Q    ----    Q    ----    Q    ----     Q    ----    ~Q
S---| B1 |---S---| A1 |---S---| B2 |---~S---| A2 |---~S
R    ----    R    ----    R    ----     R    ----    ~R
            ~P            P             P             P


Abstract and primitive actions can be treated like parents and children. Prerequisits and effect of actions can be viewed as assets and debts. The question is which child gets assets and which child gets to pay debts. 

The more relaxed approach (showed by the previous example) lets the assets and debts be distributed among different children. Another, less flexible approach, is to specify main subaction (the oldest child) that would handle all of parents debts and assets. There are benefits to choosing this less flexible approach. We would like to think on a higher level of abstraction and be able to say that if the plan with abstract actions is inconsistent, then it will be inconsistent if these actions are reduced to primitive actions. 

Not every plan from base planner would be a valid plan for HTN. It would only make HTN incomplete if such plan could have been expressed by HTN grammar rule, but was not found. An example of a plan that might not have been found by HTN could be if our travel agent did not consider SouthWest airlines as one of the options for flight from PX to NY. It could happened because an agent assumed that we were not interested in using SouthWest.


Fantomization
-------------

Partial order planning can be supported either by:
- simple establishment: adding a causal link
- step addition: adding a step from outside of the plan
- phantom task

When we construct a plan with abstract actions, some of which might require preconditions that do not come from the plan. 
We can take the "some guy will come and do what I want" approach. This "guy" become our fantom task. It will be identified as a primitive action during reduction from abstract to primitive actions. 



When we use POP we would rather kill partial plans that are not consistant rather than an entire solution. If we delegate creating partial plans to a POP planner, we can look over its shoulder and kill a partial plan whenever we decide it becomes inconsistent. For example, if we were an English grammar parser, we would watch whether the planner composes valid English words. If the planner would start with the letter "t", we would let it continue, since there are many words that start with "t" in our dictionary. If the next letter would be "h", we would again let it continue. It the third letter would be "h" again, we would have to kill the plan, since there are no valid words beginning with "thh" in our dictionary. 
We would not be able to kill the partial plan earlier, even if the POP planner would intent to choose "t","h","h" from the start.


HTN has higher order of complexity (more constraints to satisfy) than other planners we looked at so far, but it is capable of producing solutions that are sensitive to users' needs, which cannot be expressed in basic domain description. 

SHOP is a version of HTN planning. HTN considers all schemas for action reduction, for example it would say: "you can take taxi or take bus". SHOP could say:" take bus only when you can't take taxi".