Patrik Haslum @ ANU (original) (raw)

Now a researcher in theAI group,Research School of Computer Science, within the College of Engineering and Computer Science at theAustralian National University,Canberra.I am also part-time seconded to Data61'sDecision sciences program.Previously I was with NICTA's Optimisation Research Group, also inCanberra.And before that a PhD student atLinköpings Universitet (where I worked with these people)....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., fora pair of robots to assemble a (simulated) IKEA table, formoving a sheet of paper through a printer, orexploiting IT security weaknesses. However, problems likemodel checking orcomputing genome edit distance are, in a computational sense, essentially the same.For more information, see, e.g., SiGAPS - Special Interest Group on Applications of AI Planning and Scheduling. 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 andtutorials below.

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):

• Lower bounds (on plan cost). Lower bounds are important because they provide an absolute estimate of the quality of plans found by planners that do not offer any guarantees on plan quality. However, existing lower bound functions (i.e., admissible heuristics) are usually too weak for this purpose (they are typically designed for a different purpose, viz. guiding search, and thus need to provide fast state evaluation). I'm particularly interested inincremental, or any-time, lower bound functions, i.e., functions that can provide better bounds with more runtime.
• Using planning technology to solve problems that don't look like planning problems. The so called "classical" planning problem asks us to find a sequence of transitions from an initial state to a goal state (actually, one of a set of goal states) in a discrete state space. This question is central also to many problems other than planning, such as for example diagnosis of discrete-event systems. Can methods and systems developed for planning be applied also to those problems? (The answer is, of course, "sort of".)
• 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 ofpublications below.

Student Projects

I'm always looking for students interested in working on AI planning research. For information about how to apply, see

• The College Masters and PhD programs (see also ANU information about PhD studies).
• The College honours program.
• The College summer scholarship program. I have a (short) list of suggestedstudent project topics. Some project descriptions are very general, and intended to be made more precise depending on students interests and the scope of the project.

Students

Jing Cui

Graduated 2018 (thesis @ ANU library).

Franc Ivankovic

Graduated 2018 (thesis @ ANU library).

Fazlul Hasan Siddqui

Graduated 2015 (thesis @ ANU library). Now at Dhaka University of Engineering and Technology, Bangladesh.

Debdeep Banerjee

Graduated 2015 (thesis @ ANU library). Now at Quintiq.

Publications

2018

• Patrik Haslum, Franc Ivankovic, Miquel Ramirez, Dan Gordon, Sylvie Thiebaux, Vikas Shivashankar and Dana S. Nau. Extending Classical Planning with State Constraints: Heuristics and Search for Optimal Planning. Journal of AI Research, vol. 62, p. 373-431, 2018 (JAIR on-line copy).
• Tony Allard, Charles Gretton and Patrik Haslum. A TIL-Relaxed Heuristic for Planning with Time Windows. In Proc. 28th International Conference on Automated Planning and Scheduling, 2018. (PDF from AAAI.)

2017

• Jing Cui and Patrik Haslum. Dynamic Controllability of Controllable Conditional Temporal Problems with Uncertainty. In Proc. 27th International Conference on Automated Planning and Scheduling, 2017. (PDF from AAAI.)
• Felipe Trevizan, Sylvie Thiébaux and Patrik Haslum. Occupation Measure Heuristics for Probabilistic Planning. In Proc. 27th International Conference on Automated Planning and Scheduling, 2017. (PDF from AAAI.)
• Enrico Scala, Patrik Haslum, Daniele Magazzeni and Sylvie Thiébaux. Landmarks for Numeric Planning Problems. In Proc. 26th International Joint Conference on Artificial Intelligence, p. 4384-4390, 2017 (PDF).
• Sean Dobson and Patrik Haslum. Cost-Length Tradeoff Heuristics for Bounded-Cost Search In ICAPS'17 Workshop on Heuristics and Search for Domain-Independent Planning, 2017. (Available from the workshop web page.)
• Peng Yu, Brian Williams, Cheng Fang, Jing Cui and Patrik Haslum "Resolving Over-Constrained Temporal Problems with Uncertainty through Conflict-Directed Relaxation". Journal of AI Research, vol. 60, p. 425-490, 2017 (JAIR on-line copy).

2016

• Enrico Scala, Patrik Haslum, Sylvie Thiébaux and Miquel Ramírez. Interval-based Relaxation for General Numeric Planning. In Proc. 22nd European Conference on Artifical Intelligence, p. 655-663, 2016. (PDF from IOS Press.)
• Enrico Scala, Patrik Haslum and Sylvie Thiébaux. Heuristics for Numeric Planning via Subgoaling. In Proc. 25th International Joing Conference on Artifical Intelligence, p. 3228-3234, 2016. (PDF from IJCAI.)
• Jeanette Daum, Álvaro Torralba, Jörg Hoffmann, Patrik Haslum and Ingo Weber. "Practical Undoability Checking via Contingent Planning". In Proc. 26th International Conference on Automated Planning and Scheduling, p. 106-114, 2016. (PDF from AAAI.)
• Enrico Scala, Miquel Ramírez, Patrik Haslum and Sylvie Thiébaux. Numeric Planning with Disjunctive Global Constraints via SMT. In Proc. 26th International Conference on Automated Planning and Scheduling, p. 276-284, 2016. (PDF from AAAI.)

2015

• Fazlul Hasan Siddiqui, Patrik Haslum. "Continuing Plan Quality Optimisation". Journal of AI Research, vol. 54, p. 369-435, 2015 (JAIR on-line copy).
• Frank Ivankovic, Patrik Haslum. "Optimal Planning with Axioms". In Proc. 24th International Joint Conference on Artificial Intelligence, p. 1580-1586, 2015 (PDF from IJCAI, source code and benchmarks).
• Jing Cui, Peng Yu, Cheng Fang, Patrik Haslum, Brian C. Williams. "Optimising Bounds in Simple Temporal Networks with Uncertainty under Dynamic Controllability Constraints". In Proc. 25th International Conference on Automated Planning and Scheduling, p. 52-60, 2015 (PDF from AAAI).
• Erez Karpas, David Wang, Brian C. Williams, Patrik Haslum. "Temporal Landmarks: What Must Happen, and When". In Proc. 25th International Conference on Automated Planning and Scheduling, p. 138-146, 2015 (PDF from AAAI).

2014

• Malte Helmert, Patrik Haslum, Jörg Hoffmann, Raz Nissim. "Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces".Journal of the ACM, vol 61(3), article #16 (DOI).
• Emil Keyder, Jörg Hoffmann, Patrik Haslum. "Improving Delete Relaxation Heuristics Through Explicitly Represented Conjunctions"Journal of AI Research, vol. 50, p. 487-533, 2014 (JAIR on-line copy).
• Blai Bonet, Patrik Haslum, Victor Khomenko, Sylvie Thiébaux, Walter Vogler. "Recent advances in unfolding technique". Theoretical Computer Science, vol. 551, p. 84-101, 2014 (DOI).
• Franc Ivankovic, Patrik Haslum, Sylvie Thiébaux, Vikas Shivashankar, Dana Nau. "Optimal Planning with Global Numerical State Constraints". In Proc. 24th International Conference on Automated Planning and Scheduling, p. 145-153, 2014 (PDF from AAAI).
• Jörg Hoffmann, Marcel Steinmetz and Patrik Haslum. "What does it take to render_h+(PiC)_ perfect?". In ICAPS'14 Workshop on Heuristics and Search for Domain-Independent Planning, p. 31-39, 2014. (Proceedings available from the workshop web page.)

2013

• Fazlul Hasan Siddiqui, Patrik Haslum. "Plan Quality Optimisation via Block Decomposition". In Proc. 23rd International Joint Conference on Artificial Intelligence, p. 2387-2393, 2013 (PDF).
• Patrik Haslum. "Optimal Delete-Relaxed (and Semi-Relaxed) Planning with Conditional Effects". In Proc. 23rd International Joint Conference on Artificial Intelligence, p. 2291-2297, 2013 (PDF).
• Patrik Haslum. "Heuristics for Bounded-Cost Search". In Proc. 23rd International Conference on Automated Planning and Scheduling, p. 312-316, 2013 (PDF).
• Patrik Haslum, Malte Helmert, Anders Jonsson. "Safe, Strong and Tractable Relevance Analysis for Planning". In Proc. 23rd International Conference on Automated Planning and Scheduling, p. 317-321, 2013 (PDF).
• Patrik Haslum. "Propagation of PDDL3 Plan Constraints". In Proc. of the 8th Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS'13), p. 16-23, 2013. (Note: Figure 2 in the proceedings available fromthe workshop web page appears slightly damaged. Here is a correct PDF.)
• Sergio Jimenez, Patrik Haslum and Sylvie Thiebaux. "Pruning bad quality causal links in sequential satisfying planning". In Proc. of the 4th Workshop on Planning and Learning (PAL'13), p. 45-52, 2013. (Proceedings are available from the workshop web page.)

2012

• Fazlul Hasan Siddiqui, Patrik Haslum. "Block-Structured Plan Deordering". In Proc. 25th Australaisan Joint Conference on AI, 2012 (PDF).
• Patrik Haslum. "Narrative Planning: Compilations to Classical Planning".Journal of AI Research, vol. 44, p. 383-395, 2012 (JAIR on-line copy).
• Patrik Haslum, John Slaney and Sylvie Thiébaux. "Minimal Landmarks for Optimal Delete-Free Planning". In Proc. 22nd International Conference on Automated Planning and Scheduling, p. 353-357, 2012 (PDF from AAAI Press).
• Patrik Haslum. "Incremental Lower Bounds for Additive Cost Planning Problems". In Proc. 22nd International Conference on Automated Planning and Scheduling, p. 74-82, 2012 (PDF from AAAI Press).
  • Note #1: Table 1 is missing results for the two pipesworld domains (this was an oversight). The results are:

    Pipesworld NoTankage	7	17	9	7	5	28	26	0	0
    Pipesworld Tankage	3	14	5	24	23	13	12	0	0

  • Note #2: A preliminary version of this paper appeared in the ICAPS'11 workshop on Heuristics for Domain-Independent Planning. The version of the conflict extraction procedure given in that paper is incorrect. The version in the ICAPS'12 paper is correct.
• Emil Keyder, Jörg Hoffmann, and Patrik Haslum. "Semi-Relaxed Plan Heuristics". In Proc. 22nd International Conference on Automated Planning and Scheduling, p. 128-136, 2012 (PDF from AAAI Press).
• Alban Grastien, Patrik Haslum and Sylvie Thiebaux. "Conflict-Based Diagnosis of Discrete Event Systems: Theory and Practice". In Proc. International Conference on Knowledge Representation and Reasoning (KR'12), 2012.

2011

• Alban Grastien, Patrik Haslum and Sylvie Thiebaux. "Exhaustive Diagnosis of Discrete Event Systems through Exploration of the Hypothesis Space". In Proc. 22nd International Workshop on Principles of Diagnosis, 2011 (available from theworkshop page).
• Andreas Bauer, Adi Botea, Alban Grastien, Patrik Haslum and Jussi Rintanen. "Alarm processing with model-based diagnosis of discrete event systems". In Proc. 22nd International Workshop on Principles of Diagnosis, 2011 (available from theworkshop page).
• Debdeep Banerjee and Patrik Haslum. "Partial-Order Support-Link Scheduling". In Proc. 21st International Conference on Automated Planning and Scheduling, 2011 (PDF from AAAI Press).
• Patrik Haslum and Alban Grastien. "Diagnosis as Planning: Two Case Studies". In ICAPS'11 Scheduling and Planning Applications Workshop, 2011. Available from theworkshop page.
  See Resources below for PDDL models.
• Patrik Haslum. "Computing Genome Edit Distances using Domain-Independent Planning". In ICAPS'11 Scheduling and Planning Applications Workshop, 2011. Available from theworkshop page.
  See Resources below for PDDL models.

2010

• Andreas Bauer and Patrik Haslum. "LTL Goal Specifications Revisited". In Proc. 19th European Conference on AI, 2010 (now available on-line from the publisher!).
• Eric Fabre, Loig Jezequel, Patrik Haslum and Sylvie Thiebaux. "Cost-Optimal Factored Planning: Promises and Pitfalls". In Proc. 20th International Conference on Automated Planning and Scheduling, 2010 (PDF from AAAI Press).
  See Resources below for PDDL models.

2009

• Patrik Haslum. "hm(P) = h1(Pm): Alternative Characterisations of the Generalisation From_hmax_ To hm". In Proc. 19th International Conference on Automated Planning and Scheduling, 2009 (PDF from AAAI Press).
• Patrik Haslum. "Admissible Makespan Estimates for PDDL2.1 Temporal Planning". In ICAPS'09 workshop on Heuristics for Domain-independent Planning, 2009. Available from theworkshop page.
• 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, 2009. DOI: 10.1016/j.artint.2008.10.012 (PDF).Note: On-line preprint appeared in 2008.

2008

• 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 from AAAI Press).
  • Note: There is 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 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).

2007

• 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 theworkshop 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 (PDF from AAAI Press).
• 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 from IJCAI.org,slides).

Since my LiU web page has disappeared, pre-2007 publications are now listed below:

• Patrik Haslum, "Improving Heuristics Through Relaxed Search - An Analysis of TP4 and HSP*a in the 2004 Planning Competition". Journal of AI Research, vol 25, p. 233-267, 2006 (JAIR on-line copy).
• Patrik Haslum, Blai Bonet, Hector Geffner, "New Admissible Heuristics for Domain-Independent Planning". In Proc. AAAI, 2005 (postscript).
• Patrik Haslum, "Improving Heuristics Through Search" (poster/short paper). In Proc. European Conference on AI, 2004 (now available on-line from the publisher!).
• Patrik Haslum, "Patterns in Reactive Programs". In Proc. of the Cognitive Robotics Workshop, 2004. (postscript).
• Patrik Haslum and Ulrich Scholz, "Domain Knowledge in Planning: Representation and Use". In Proc. ICAPS 2003 Workshop on PDDL. (postscript).
• Patrik Haslum, "Partial State Progression: An Extension to the Bacchus-Kabanza Algorithm, with Applications to Prediction and MITL Consistency". In Proc. AIPS 2002 workshop on Planning via Model Checking (postscript).
• Patrik Haslum and Hector Geffner, "Heuristic Planning with Time and Resources". In Proc. 6th European Conference on Planning, 2001. To appear in Lecture Notes in Artificial Intelligence, Springer Verlag (postscript).
• Patrik Haslum, "Models for Prediction". In Proc. IJCAI 2001 workshop on Planning under Uncertainty (postscript).
• Patrik Haslum and Hector Geffner, "Admissible Heuristics for Optimal Planning". In Proc. 5th International Conference on Artificial Intelligence Planning and Scheduling, 2000, p. 140 - 149. AAAI Press (postscript).
  • Note: There is an error in the paper: the condition for commutativity of actions (section "Commutativity Pruning") must also include that neither action adds a precondition of the other. Commutativity is not the same as Graphplan-style "non-interference". This error is only in the paper: the implementation used the correct condition.
• Patrik Haslum and Peter Jonsson, "Planning with Reduced Operator Sets". In Proc. 5th International Conference on Artificial Intelligence Planning and Scheduling, 2000, p. 150 - 158. AAAI Press (postscript).
• Jonas Kvarnström, Patrick Doherty and Patrik Haslum, "Extending TALplanner with Concurrency and Resources". In Proc. 14th European Conference on AI, 2000 (now available on-line from the publisher!).
• Peter Jonsson, Patrik Haslum and Christer Bäckström, "Towards Efficient Universal Planning -- A Randomized Approach". Artificial Intelligence 117(1):1-29, 2000. (postscript).
• Patrik Haslum, "Model Checking by Random Walk". In Proc. 1999 ECSEL Workshop. (postscript).
• Patrik Haslum and Peter Jonsson, "Some Results on the Complexity of Planning with Incomplete Information". In Proc. of the 5th European Conference on Planning,Lecture Notes in Artificial Intelligence vol. 1809, 1999, p. 308 - 318. Springer Verlag (preprint version,postscript; final version available from Springer Link).
• Patrik Haslum, "An Investigation into the Computational Complexity of Planning in Non-Deterministic and Information-Incomplete Domains". Unpublished manuscript (postscript, 75K).

My thesis, "Admissible Heuristics for Automated Planning" (Doctoral Thesis no. 1004, Linköping University. 2006) is available from LiU E-press, should it interest anyone.

Resources

Stuff that may be of use to other researchers in my area.

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 _(n2 - 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 availablehere. The PDDL files were created with a conversion script, which is also included in the archive.
• Alternate encoding of the Promela domains (philosophers and optical telegraph).
  These encodings better capture the sparse structure of the original (deadlock detection) problem, making them amenable to solving by factored planning methods. (See the ICAPS'10 paper.)
• Alternate encoding of the Pipesworld domains.
  Similar to the above, this encoding is meant to factor better. However, it does not describe exactly the same problem as the original (IPC 2004) domain, since it uses counters for batch types instead of named batches.
• Encodings of the Genome Edit Distance (a.k.a. Genome Rearrangement) problem.
  See the second SPARK'11 paper for details.
  Note: The uncompressed size of the archive is 3.2Gb.

PDDL Encodings of DES diagnosis problems.

These planning domains and problems encode discrete event system diagnosis problems. See the first SPARK'11 paper for further details about the encoding and about the two application domains.

• The Alarm Processing for Power Networks domain.
• The WITAS Event Loss Detection domain.

INVAL

INVAL is the Independent PDDL plan Validator.
Update (6/12/16): INVAL has moved togithub.

HSP*

HSP* is a collection of planners and planning-related tools that I have developed over many years. The source code is available on the download and documentation page.

Axiom-aware heuristics for the Fast Downward planner

Source code and benchmarks for the experiments reported in theIJCAI'15 paper. This is provided as a patch on Fast Downward. See README file for installation/compilation instructions.

csdltopddl (as of 15th Jan. 2010)

(OBSOLETE)
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 onAlban 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)
• Tutorial on "Petri Nets and Their Relation to Planning", by Blai Bonet, Sarah Hickmott, Stefan Edelkamp and me. Presented at ICAPS 2009. (slides in 4-on-1 format, PDF; note: these do not include Stefans slides)
• A small course on heuristic search I did at NICTA in 2012. (slides, PDF;demo code).
• A short tutorial on "Writing Planning Domains and Problems in PDDL".

Teaching

• Lectures on planning (and sometimes other things) as part of Artificial Intelligence (COMP3620), 2007 - 2013.
• Planning part of Advanced Topics in AI (COMP8620), 2007.
  Notes and materials are available here.

A quote for the day...