CSE 574 Readings

• Planing chapter from Russell's second edition (available here on their web-site)
  1. 1994 AI mag article on introduction to POP planning by Dan Weld (goes into more gory details than is available in the R&N chapter).
  2. A short paper on AltAlt
     • 2001 AIJ paper on using planning graph to derive heuristics. (Look in particular at Sec 4.3 (Adj Sum heuristic); Section 6.1 (Bi-level PG) and 6.2 (using PGs to reduce branching factor) Section 7.2 (cost of heuristic computation), and Section 9 (in my impartial view, a beautiful account of the use of reachability heuristics in planning ;-)
  3. RePOP: 2001 AAAI paper on using planning graph heuristics in the context of partial order planning.
  4. AI Magazine paper on FF.
  5. 1997 paper on understanding and extending Graphplan (optional)

• A paper on implementing EBL memoization in graphplan (Sections 3,4 and 5 should be sufficient)
• (2/20)A paper on implementing solving planning graph by converting it into CSP (Sections 3,4,5 and 6 should be sufficient)
• (2/25)A paper on encoding planning in propositional logic (useful for different ways of encodings planning problem into SAT and its relative advantages/disadvantages)
  • (2/25)A paper talking about the relative utility of "causal encodings"

  • A tutorial article on unifying framework for the various planning approaches

  • The PDDL Reference Manual
    1. A small set of slides on PDDL by Malte Helmert

  ---

• (3/13)Papers on Knowledge-based planning
  1. Paper on "Top-down" (task reduction) HTN planning (has all the fun stuff like Phantomization, downward-unlinearizability etc.
     1. Paper on bottom-up (parsing) approach to HTN planning
     2. A paper on SHOP
  2. A paper on TLPlan

  ---

• (3/27)Papers on Metric Temporal Planning
  1. Paper on PDDL-2.1 standard (read upto--not including--section 6)
  2. Paper on SAPA
     1. Paper on Temporal TLPlan (see Section 3 for a slightly longer description of the progression search used in SAPA).
     2. Paper on TP4 (regression search for Temporal Planning
     3. Paper on Zeno (Plan-space search for Temporal Planning)
  3. Paper on LPG (Stochastic Local search)
     1. A journal length version of the above with more details
     2. A paper on ASPEN, another "fielded" local-search based metric-temporal planner

  ---

• (4/15)Papers on Temporal reasoning and scheduling:
  1. Paper temporal networks
     1. (optional) 97 paper on processinng disjunctive temporal networks.
     2. (optional) 98 survey paper on temporal reasoning (a bit to succinct).

  2. Paper on slack-based scheduling (6 pages)
     1. (optional) An idiosyncratic survey paper on constraint-based scheduling
     2. (optional) a much more up-to-date paper on propagation methods for genaralized jobshop scheduling (unary as well as multi-capacity resources)
        1. Crawford's paper on directly compiling PCP scheduling encodings to SAT (AAAI 94) (Mentioned in the class on [Apr 17, 2003])

  3. Combining Planning and Scheduling (A topic that I would really have liked to cover if I had time).
     1. David Smith's paper on Bridging the gap betwee Planning and Scheduling
     2. Hector Geffner's paper on viewing planning and scheduling as branch and bound problems. You might instead look at this shorter conference version with some implementation results.
     3. Biplav's AIJ paper on de-coupled architectures for combining planning and scheduling

  ---

• 4/16: Planning with Incompleteness
  1. Planning with incomplete information as a heuristic search in belief space (for class of 4/22)
     1. Planning-graph based heuristics for Conformant Planning

  2. Bacchus and Petrick's alternative "abstract" modeling of planning with incomplete information
  3. A progression conditional planer (based on BDD representation and A* star search
     1. AO* Search Algorithm (from Nilsson's book)