The Role of Macros in Tractable Planning. Jonsson. JAIR 2009

Basically in order to understand this in any meaningful way you need to read the paper on inverted trees.  This then is a surface treatment.

1. Introduces a class of planning problems, IR, and an algorithm that runs in poly-time (as opposed to exp) for a subset of problems in that class
2. Tractable subclasses of IR include problems whose optimal solution has exp-length in terms of the number of state features
1. How can this be poly then (if an exp-length sequence was already enumerated)?
3. “The reason that our algorithm can solve these problems in polynomial time is that subsequences of operators are frequently repeated in the solution.  Since the algorithm stores each subsequence as a macro, it never needs to generate the subsequence again.”
4. Define a relaxed causal graph, which has less edges than a conventional causal graph
1. Addtionally, a class of problems RIR is defined, relaxed IR
5. Also define notion of reversible variables and define class of planning problems AR with acyclic causal graphs and reversible variables, the algorithm introduced can solve problems in this class as well
6. Then results for IR and AR are combined to define a new class of problems AOR (planning problems with acyclic causal graphs and only some reversible variables)
7. Algorithm is like a compiler that can represent exponentially long long plans in poly-time/space
8. They also discuss projecting problems outside of these classes into these classes in order to efficiently create admissable heuristics
1. This however is exp in the number of “missing” variables (I suppose I’ll learn what that means later) so the number of these missing variables should be small
9. Macros allow for transfer (such as in tower of hanoi where more disks are used)
10. “If the causal graph is acyclic, each action a in A is unary, i.e. |Vpost(a)|=1”  Doesn’t this just mean this is deterministic?  Guess I’m not groking his notation so well, but will come back to this if the paper seems relevant
11. An inverted tree is a tree where the outdegree of each variable in the causal graph is <= 1 (by Katz, Domshlak)
12. A planning problem can be reduced to an inverted tree in certain circumstances
1. This is their definition of class IR
2. Its a tree that maintains edges only to to keep node connectivity.  Otherwise inverted tree and acyclic
13. Describe an algorithm MacroPlanner that decomposes a problem into subproblems
1. Stores solution to each subproblem as a macro
14. There is then a separate subroutine that solves the subproblems defined by another function that identifies Macros
1. Uses a form of Dijkstra’s that only expands parts of graph necessary for solution so it can still be efficient.
15. Every macro produced is well defined and solves (a part of) the original problem
16. Macroplanner produces an optimal policy (if no solution exists it correctly reports failure)
17. Complexity of macroplanner is order-3 poly (proof is related to that of Dijkstra as its similar)
18. The entire algorithm is also poly time
19. Discusses further pruning
20. Then move on past IR problems
21. Move onto RIR (relaxed inverted tree) reducible problems, which are another form of IR problems
22. Not really getting much out of this because I don’t have the proper background, stopping here.