Not sure how this entered my pile, will give a cursory read
- Starts by discussing a common heuristic for STRIPS planners, and shows how it fails in some simple problems
- 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
- 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…)
- 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}
- Not introduced here, but seems like the make some changes
- Strips therefore, is a subset of SAS+, where each state can only take binary values
- 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
- This is relevant because many methods of generating heuristics don’t end up only in reachable states?
- Algorithms can convert STRIPS to SAS+
- “The basic idea of our approach is to decompose a planning task into subtasks with limited interaction”
- SAS+ subtasks are still SAS+ problems
- The way subtasks are defined, if the subtask does not have a solution, then the full problem also does not have a solution
- Variables that are not in a subtask are “projected away” and are considered to always be satisified
- In order to make sure that important preconditions don’t disappear, causal graphs can be used
- “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.”
- This is particularly helpful when variables have few ancestors in the causal graph
- Many papers focus on domains with acyclic causal graphs, which means all operators are unary
- There are some domains that are cyclic in STRIPS but acyclic in SAS+
- Oh this paper is awesome
- 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.
- V is called the high-level variable
- All other variables are called low-level variable
- A goal must be defined in terms of the high-level variable and not the low-level variables
- In SAS+-1 tasks all low-level variables can be changes independently, making solutions simple
- They claim these types of tasks are interesting because they are easy to solve buy can capture interesting problems
- SAS+-1 also forms the basis of heuristics for full SAS+
- Even SAS+-1 problems are hard though: np-complete. Naturally some problem classes in it are easier
- 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
- Based on Dijkstra’s
- It prioritizes high-level goals over low-level goals
- “It is not complete because it does not reinvestigate the plans used for achieving a certain high-level value”
- Low level variables can be thought of as resources to achieve the goal on any high-level variable
- During planning the complete world state is known (unlike the H+ heuristic for strips)
- This planner is complete in certain classes of problems
- 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
- Going back to full SAS+ problems, each problem can be said to be made of many smaller SAS+-1 problems
- Each SAS+-1 task deals with one variable and its immediate ancestors
- This doesn’t actually solve the problem as each solution doesn’t fit together, but provides a heuristic
- This approach has problems with acyclic causal graphs; there are ways to try and deal with that
Advertisements