Patrik Haslum

Now a researcher in the AI group, College of Engineering and Computer Science at the Australian National University, Canberra. (I also belong to the Computer Science Lab, insofar as it still exists as an organisational unit.) I am also part-time seconded to NICTA's AI for the Smart Grid project. Previously with NICTA, also in Canberra. And before that a PhD student at Linköpings Universitet. ...and still working on planning. What is Planning? "Planning is the art and practice of thinking before acting." "Planning" is the name used in AI for computational problems that have to do with choosing a course of action. This may be for the purpose of creating a "plan", e.g., for a pair of robots to assemble a (simulated) IKEA table, for moving a sheet of paper through a printer, or exploiting IT security weaknesses. However, problems like model checking or computing genome edit distance are, in a computational sense, essentially the same. For more information, see, e.g., My student project topics. A short presentation I did at some point. The wikipedia page on "Automated planning and scheduling" (not terribly informative). The material in sections teaching and tutorials below. (In particular, the annotated bibliography I put together for the 2007 Advanced Topics in AI course provides a comprehensive, if somewhat dated, reading list.) What am I doing about it? Most of my work in AI planning is about generating optimal plans, i.e., plans that have minimum cost or execution time. Mostly through the use of heuristic search. But I'm interested in other stuff too, for example, analysing/understanding classes of problems ("domains") used as benchmarks in evaluation of planning algorithms, and tractable subclasses of planning problems. Some things I've been thinking about recently (and, in some cases, for quite some time): Relations between different admissible heuristics, mainly for the case of additive action cost. Progress on this has been made recently (see, e.g., the paper by Malte Helmert & Carmel Domshlak at ICAPS 2009), but some tricky questions remain. Petri nets, and the exchange of algorithms/methods between Petri net analysis and planning. Together with Sarah, Blai & Sylvie, I've looked heuristically guided unfolding, but I have the feeling many more possibilities remain. Domain-specific methods for findng optimal solutions (or at least tight bounds) for some of the common (and some not so common) planning benchmark domains. What techniques will work? What will the results say about our benchmarks, and about our quest for domain-independence? For more details of my past work, see the list of publications below.

Student Projects

• The College Masters and PhD programs (see also ANU information about PhD studies).
• The College BCS honours program.
• The College summer scholarship program.

Publications

• Patrik Haslum, "h^m(P) = h¹(P^m): Alternative Characterisations of the Generalisation From h^max To h^m". In Proc. 19th International Conference on Automated Planning and Scheduling, 2009 (PDF).
• Alfonso Gerevini, Patrik Haslum, Derek Long, Alessandro Saetti, and Yannis Dimopoulos, "Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners". In Artificial Intelligence, vol. 173 (5-6), pp. 619-668, 2008. DOI: 10.1016/j.artint.2008.10.012 (PDF).
• Blai Bonet, Patrik Haslum, Sarah Hickmott, and Sylvie Thiébaux, "Directed Unfolding of Petri Nets". In Transactions on Petri Nets and Other Models of Concurrency I, LNCS vol. 5100, 2008. DOI: 10.1007/978-3-540-89287-8_11 (PDF).
• Patrik Haslum, "A New Approach To Tractable Planning". In Proc. 18th International Conference on Automated Planning and Scheduling, 2008 (PDF).
  Note: There's an error in the paper. The first two cases for sequence rules in Table 1 should have N.max = min(N1.max, N2.max - N1.out, N3.max - (N1.out + N2.out)) (or at least something similar; the issue is that if N.out = 1, one of the N2.max and N3.max moves may already have been "consumed" (depending on where the move out originated) and N.max needs be adjusted accordingly).
• Patrik Haslum, "Quality of Solutions to IPC5 Benchmark Problems: Preliminary Results". In ICAPS'07 workshop on the International Planning Competition: Past, Present and Future, 2007. Available from the workshop page (slides). See also the IPC5 (deterministic track) website and my additional IPC5 resources page.
• Malte Helmert, Patrik Haslum and Joerg Hoffmann, "Flexible Abstraction Heuristics for Optimal Sequential Planning". In Proc. 17th International Conference on Automated Planning and Scheduling, 2007. Available from Malte's publications page.
• Patrik Haslum, Malte Helmert, Blai Bonet, Adi Botea and Sven Koenig, "Domain-Independent Construction of Pattern Database Heuristics for Cost-Optimal Planning". In Proc. AAAI'07 (PDF).
• Blai Bonet, Patrik Haslum, Sarah Hickmott, and Sylvie Thiebaux, "Directed Unfolding of Petri Nets". In Proc. of the Workshop on Unfolding and partial order techniques (UFO'07), 2007. A revised version of this paper now appears in the LNCS Transactions on Petri Nets and Other Models of Concurrency (see above).
• Patrik Haslum, "Reducing Accidental Complexity in Planning Problems". In Proc. 20th International Joint Conference on Artificial Intelligence, 2007 (PDF, slides).

For earlier publications, please refer to http://www.ida.liu.se/~pahas/.

Resources

My IPC5 resources page.

Information about some of the IPC5 benchmark domains: problem generation/conversion software, alternative domain formulations, and bounds on solution quality.

PDDL domain and problem definitions.

• The (n² - 1)-Puzzle. Includes Korf's famous 100 random 15-puzzle problems, and a collection of random 8-puzzle problems.
• Sokoban. The "Microban" problem collection. This problem collection, and many more, in original format are available here. The PDDL files were created with my conversion script.

libhspsutil (as of 27th Nov. 2009)

Source code for some utility classes used in the HSP* planner, but also used quite indiscriminately in other software I've written.

csdltopddl (as of 15th Jan. 2010)

A diagnosis-to-planning translator. Takes as input a discrete-event diagnosis model/problem in CSDL format, and generates planning problems corresponding to possible diagnosis hypotheses; each planning problem is solvable iff the corresponding hypothesis is consistent with observations.
The translator is written in java and depends heavily on Alban Grastien's CSDL package.

Tutorials

• Tutorial on "Abstraction Heuristics in Planning: PDBs and Beyond", by me and Malte Helmert. Presented at ICAPS 2008. (slides in 4-on-1 format, PDF)
• A short tutorial on "Writing Planning Domains and Problems in PDDL".

Teaching

• Guest lectures in Artificial Intelligence (COMP3620), 2007 - 2009.

  Lecture slides: Computer Vision. Robotics and Natural Language Processing.

• Planning part of Advanced Topics in AI (COMP8620), 2007.

  Notes and materials are available here.

A quote for the day...