2nd Workshop on Heuristics
for Domain-independent Planning

Thessaloniki, Greece, September 19th, 2009


News   |  Workshop Description   |  Important Dates   |  Submission Procedure   |  Workshop Program   |  Organizers and Program Committee


August 19, 2009: All the workshop papers are now accessible via the workshop program.
August 3, 2009: Workshop program
June 21, 2009: Due to numerous requests related to the time pressure caused by camera-ready versions deadline for ICAPS, we decided to extend the submission period for the workshop to until June 28th, 2009.

April 6, 2009: Call for papers

Workshop Description

The automatic derivation of heuristic estimators to guide the search has become one of the main approaches in domain-independent planning. The approach works: very large problems, with many state variables and operators can be solved in this way, that could not be solved before, and the approach appears to scale up better than others.

The first workshop on heuristics for domain-independent planning, held in conjunction with ICAPS 2007, was very successful. Many ideas presented at that workshop have led to contributions at major conferences such as ICAPS 2008 and AAAI 2008 and pushed the frontier of research on heuristic planning in several directions, both theoretically and practically. The workshop, as well as work on heuristic search that has been published since then, has also shown that there are many exciting open research opportunities in this area. Given the considerable success of the past workshop, we would like to institutionalize it by turning it into a biennial event.

We look for contributions that would help us understand better the ideas underlying current heuristics, their limitations, and the ways for overcoming them. Contributions do not have to show that a new heuristic or new variation of a known heuristic 'beats the competition'. While performance measured in the number of evaluated nodes, time, and solution quality remains relevant, in this workshop we seek above all crisp and meaningful ideas and understanding. The ideas have to make sense computationally, but there is no need to wrap them with many others into a planner that can be 'competitive' with state-of-the-art planners. Also, rather than merely being interested in the 'largest' problems that current heuristic search planners can solve, we are equally interested in the simplest problems that they can't actually solve well.

In addition to heuristic search for classical planning, which was the main focus of the previous incarnation of this workshop, we are very interested in new ideas on heuristic schemes for more general settings, such as temporal planning, planning under uncertainty and adversarial planning.

Workshop Program

Workshop Overview
Session I
(Session chair: Carmel Domshlak)
  1. Determinize, Solve, and Generalize: Classical Planning for MDP Heuristics
    Andrey Kolobov, Mausam and Daniel Weld

  2. Reachability Heuristics for Planning in Incomplete Domains
    Jared Robertson and Daniel Bryce

  3. Requirements on Heuristic Functions when Using A* in Domains with Transpositions
    Nir Pochter and Jeffrey Rosenschein

  4. Planning with h+ in Theory and Practice
    Christoph Betz and Malte Helmert

Coffee Break
Session II
(Session chair: Jörg Hoffmann)
  1. Admissible Makespan Estimates for PDDL2.1 Temporal Planning
    Patrik Haslum

  2. Towards Search Control via Dependency Graphs in Europa2
    Sara Bernardini and David E. Smith

  3. Improving relaxed-plan-based heuristics via simulated execution of relaxed-plans
    Dunbo Cai, Minghao Yin and Jianan Wang

  4. Combining Heuristic Estimators for Satisficing Planning
    Gabriele Röger and Malte Helmert

Lunch Break

Structure TBD.

Coffee Break
Session III
(Session chair: Malte Helmert)
  1. Viewing Landmarks as Temporally Extended Goals
    Letao Wang, Jorge Baier and Sheila McIlraith

  2. Abstractions += Landmarks
    Carmel Domshlak, Michael Katz and Sagi Lefler

  3. Path-based Heuristics (Preliminary Version)
    Nir Lipovetzky and Hector Geffner

  4. A Unified View of Cost-Based Heuristics
    Raquel Fuentetaja, Daniel Borrajo and Carlos Linares López

Submission Procedure

Papers or position statements ranging from 4 to 6 pages in AAAI format style, are invited. See http://www.aaai.org/Publications/Author/author.php for formatting instructions.

The submission is via Easychair site of the workshop.

As the workshop is not an archival conference, multiple submissions are permitted. Work that is a strict subset of that recently previously published in an archival journal should be presented as a short position statement. The workshop is planned to be a full 1-day format, but the precise format is to be decided as a function of the contributions received.

We strive to have two types of presentations: long and short (15-20 and 5-10 minutes), as well as 1-2 discussion sessions where the audience members are encouraged to participate. (In 2007 we haven't planned such discussion sessions, but they have emerged anyway, and became an important part of the workshop.) As a further stimulus to audience participation, the organisers will provide a commentary following each session of talks.

Important Dates

Submission Deadline: June 23rd, 2009 June 28rd, 2009 (anywhere on Earth).
Notifications: July 22nd, 2009.
Camera-Ready Paper Submissions: August 3rd, 2009.
Edited Working Notes: August 8th, 2009.
Workshop: September 19th, 2009.

Organizers and Program Committee


Carmel Domshlak Technion Haifa, Israel
Malte Helmert University of Freiburg Freiburg, Germany
Joerg Hoffmann SAP Research Karlsruhe, Germany

Program Committee

J. Benton Arizona State University Tempe, AZ, USA
Blai Bonet Universidad Simon Bolivar Caracas, Venezuela
Dan Bryce Utah State University Logan, UT, USA
Hector Geffner Universitat Pompeu Fabra Barcelona, Spain
Eric Hansen Mississippi State University Mississippi State, MS, USA
Patrik Haslum NICTA and ANU Canberra, Australia
Rob Holte University of Alberta Edmonton, Alberta, Canada
Adele Howe Colorado State University Fort Collins, CO, USA
Sven Koenig University of Southern California Los Angeles, CA, USA
Derek Long University of Strathclyde Glasgow, UK
Wheeler Ruml University of New Hampshire Durham, NH, USA
Rong Zhou PARC Palo Alto, CA, USA