A Planning Heuristic Based on Causal Graph Analysis. Helmert, ICAPs 04?

Not sure how this entered my pile, will give a cursory read

1. Starts by discussing a common heuristic for STRIPS planners, and shows how it fails in some simple problems
2. These issues stem from the fact that in these problems, an item moves from place to place, but this heuristic (h+) only pays attention to items made true as opposed to made false.  This means that it thinks an object is at any location it has ever existed at simultaneously
3. These difficulties stem from the fact that STRIPS only allows for binary values instead of allowing items to exist over a range of values (you have to see if the truck is in location 1, then location 2, etc…)
4. They propose the SAS+ planning formalism that allows state variables to exist over a finite domain (the location of the truck can only be one of {a, b, … z}
   1. Not introduced here, but seems like the make some changes
5. Strips therefore, is a subset of SAS+, where each state can only take binary values
6. Although the number of reachable states between STRIPS and SAS+ are the same, the total number of variables between the two encodings in a simple problem is 288 for SAS+ vs 1048576 for STRIPS
   1. This is relevant because many methods of generating heuristics don’t end up only in reachable states?
7. Algorithms can convert STRIPS to SAS+
8. “The basic idea of our approach is to decompose a planning task into subtasks with limited interaction”
9. SAS+ subtasks are still SAS+ problems
   1. The way subtasks are defined, if the subtask does not have a solution, then the full problem also does not have a solution
10. Variables that are not in a subtask are “projected away” and are considered to always be satisified
11. In order to make sure that important preconditions don’t disappear, causal graphs can be used
12. “Informally, the causal graph contains an arc from a source variable to a target variable if changes in the value of the target variable can depend on the value of the source variable.”
13. This is particularly helpful when variables have few ancestors in the causal graph
14. Many papers focus on domains with acyclic causal graphs, which means all operators are unary
    1. There are some domains that are cyclic in STRIPS but acyclic in SAS+
15. Oh this paper is awesome
16. Defines SAS+-1 tasks have a set variable v such that the causal graph has an edge from all variables to v and no other edges.
    1. V is called the high-level variable
    2. All other variables are called low-level variable
    3. A goal must be defined in terms of the high-level variable and not the low-level variables
17. In SAS+-1 tasks all low-level variables can be changes independently, making solutions simple
18. They claim these types of tasks are interesting because they are easy to solve buy can capture interesting problems
19. SAS+-1 also forms the basis of heuristics for full SAS+
20. Even SAS+-1 problems are hard though: np-complete.  Naturally some problem classes in it are easier
21. There is a poly algorithm for SAS+-1 problems, but it is not complete (will not always find a solution).  On the other hand, all solutions found are valid
    1. Based on Dijkstra’s
    2. It prioritizes high-level goals over low-level goals
    3. “It is not complete because it does not reinvestigate the plans used for achieving a certain high-level value”
    4. Low level variables can be thought of as resources to achieve the goal on any high-level variable
    5. During planning the complete world state is known (unlike the H+ heuristic for strips)
    6. This planner is complete in certain classes of problems
22. Similarly, the (poly-time?) algorithm for determining if a task is unsolvable will not always detect that it is unsolvable.  On the other hand, when it does compute unsolvable, it is always correct
23. Going back to full SAS+ problems, each problem can be said to be made of many smaller SAS+-1 problems
    1. Each SAS+-1 task deals with one variable and its immediate ancestors
    2. This doesn’t actually solve the problem as each solution doesn’t fit together, but provides a heuristic
    3. This approach has problems with acyclic causal graphs; there are ways to try and deal with that

Advertisements