19th International Conference on
Automated Planning and Scheduling

September 19-23, 2009, Thessaloniki, Greece



Schedule has been announced

Invited Speakers

The program will include invited talks from the following researchers:

Planning with Continuous Change

by Maria Fox,
European Coordinating Committee for Artificial Intelligence (ECCAI) Invited Speaker

Maria Fox 

Abstract. Continuous change occurs in almost all interesting real problems, including oil refinery management, logistics planning, mission planning for autonomous vehicles, experiment design, financial planning and energy demand and supply management. Most research communities that are concerned with action and change: the qualitative reasoning, formal verification, controls, optimisation and knowledge representation communities - also recognise the importance of continuous processes and their impact on predicting and controlling dynamic systems. In the planning community the problem of reasoning about continuous change and its implications has been explored in autonomous vehicle mission-planning using hybrid model-based reasoning and stochastic and hierarchical modelling, and in process plant management using non-linear constraint modelling. However, despite the development of planning domain modelling languages, such as PDDL+ and Opt, domains featuring autonomous processes and exogenous events have not yet been developed as benchmarks for domain-independent planning. The speaker will present some features of planning problems that distinguish them from typical problems in optimisation and control and discuss progress and open problems in planning with continuous change.

Short bio. Maria Fox is Professor of Computer Science at the University of Strathclyde. Her research includes contributions to planning domain modelling and automated static domain analysis, domain modelling languages and their formal semantics, planning for temporal and metric domains, continuous planning, plan validation and plan execution monitoring. She co-developed PDDL2.1, the temporal and metric version of PDDL, and was a co-organiser of the 3rd IPC which precipitated many new developments in temporal planning. She is an Associate Editor of Artificial Intelligence and a member of the advisory board of JAIR, having served over several years as both an editorial board member and an Associate Editor. She has also served on the programme committees of many conferences including ICAPS and IJCAI, both in PC member and Area Chair capacity and she co-chaired ICAPS-07. She has helped to build an internationally known planning group at Strathclyde, where she has also been Department Head since 2007.  

Scheduling in Dynamic, Uncertain Environments: Closing the Loop with Execution

by Stephen F. Smith

Stephen F. Smith

Abstract. Advances in sensing and web technologies now provide unprecedented ability to obtain and maintain up-to-date, real-time information on the location and status of materials and resources over time. In application areas as diverse as transportation planning, supply network management, disaster response and traffic control, it is now truly possible to base planning and scheduling decisions on actual execution state. The perceived benefit of this approach, largely unrealized at this point, is that it offers the possibility to better cope with the uncertainty inherent in large-scale, multi-agent execution environments, leading to more responsive and ultimately more effective organizational performance. This talk considers the prospects for a new class of execution-driven scheduling models. These models start from the premise that scheduling is a dynamic optimization under uncertainty problem, where new goals arrive continuously and must be weighed against current commitments, where the constraints associated with scheduled activities are uncertain, and where the resources required to execute activities are unreliable. 

Execution-driven scheduling models must also deal with the communication and coordination constraints of multiple executing agents, which frequently force or encourage distribution of problem solving effort. I will summarize threads of ongoing research in building robust schedules, managing change in dynamic over-subscribed domains, learning and exploiting models of uncertain scheduling constraints, and coordinating distributed scheduling agents; all of which contribute directly to the realization of execution-driven scheduling models. I’ll attempt to characterize where the field stands with respect to this overarching goal, and what principal challenges remain.

Short Bio. Stephen Smith is a Research Professor in the Robotics Institute at Carnegie Mellon University, where he heads the Intelligent Coordination and Logistics Laboratory. His research focuses broadly on the theory and practice of next-generation technologies for complex planning, scheduling and coordination problems. He pioneered the development and use of constraint-based search models and heuristics for solving scheduling problems, and he has led the development of innovative planning and scheduling systems for a number of complex applications. He has published over 215 technical articles on these subjects. He is Associate Editor of the Journal of Scheduling, was a founding member of the ICAPS executive council (2002-2008), and currently serves on the executive council of the International Society of Interdisciplinary Scheduling. In 2005, he received the Allen Newell Medal for Research Excellence, awarded annually by the CMU School of Computer Science. In 2007, he was elected a Fellow of AAAI.

Towards Self-Driving Cars

by Sebastian Thrun

Sebastian Thrun Abstract. Cars kill over a million people every year. The speaker will report on progress to make cars safer, more convenient, and more efficient (gas, space, utilization), through robotic technology. Building on AI advances that led the Stanford Racing Team to victory in the DARPA Grand Challenge and second place finish in the Urban Challenge, Stanford has developed advanced mapping, localization, car tracking, control, and planning methods, which enable cars to navigate in dense urban and highway environments. The speaker will survey the latest research in this area, and speculate about possible ways to get this technology into every car.

Short bio. Sebastian Thrun is a professor of computer science and electrical engineering at Stanford, where he directs the Stanford AI Lab. Thrun has published 11 books, over 300 scientific articles. Thrun is probably best known for his pioneering work on probabilistic robotics, and the victory of his team in the DARPA Grand Challenge. Thrun is a fellow of the AAAI, ECCAI, WTN, and member of the National Academy of Engineering and the German Academy of Sciences. Popular Science included Thrun in their "Brilliant Ten", Fobes Magazine as one of seven "E-Gang" members, Scientific American in their list of 50 world technology and policy leaders, and Wired awarded Thrun's robot Stanley the top spot in the most influential robots of all times. Thrun also serves as a Principal Engineer at Google where he was instrumental in the creation of Street View. Finally, he is a senior advisor to Charles River Ventures, an early stage venture capital firm.


Note: The full Conference Program in PDF format is available online (1.12MB). It will be given to participants in printed form on site.

Sunday, September 20th


Welcome Reception, at the Museum of Byzantine Culture

Monday, September 21st




Invited Talk: Towards Self-Driving Cars
 Sebastian Thrun
Hall: Aristotelis I

Chair: Alfonso Gerevini


Coffee break


Session 1: Robot Planning (Hall: Aristotelis I)
Chair: Felix Ingrand

A Human-Aware Robot Task Planner
Marcello Cirillo, Lars Karlsson, Alessandro Saffiotti

Using Physics- and Sensor-Based Simulation for High-Fidelity Temporal Projection of Realistic Robot Behavior
Lorenz Mösenlechner, Michael Beetz

Information-Theoretic Approach to Efficient Adaptive Path Planning for Mobile Robotic Environmental Sensing
Kian Hsiang Low, John M. Dolan, Pradeep Khosla

Navigation Planning in Probabilistic Roadmaps with Uncertainty
Michael Kneebone, Richard Dearden

Session 2: Search for Planning and Scheduling  (Hall: Aristotelis II)
Chair: Joerg Hoffmann

Suboptimal and Anytime Heuristic Search on Multi-Core Machines
Ethan Burns, Seth Lemons, Wheeler Ruml, Rong Zhou

Thinking Ahead in Real-Time Search
Dana Nau, Ugur Kuter, Emre Sefer

Structural-Pattern Databases
Michael Katz, Carmel Domshlak

Preferred Operators and Deferred Evaluation in Satisficing Planning
Silvia Richter, Malte Helmert


Lunch Break


Session 3: Distributed and Multiagent Planning & Scheduling  (Hall: Aristotelis I)
Sven Koenig

Fast Distributed Multi-Agent Plan Execution with Dynamic Task Assignment and Scheduling
Julie A. Shah, Patrick R. Conrad, Brian C. Williams

Multi-Agent Online Planning with Communication
Feng Wu, Shlomo Zilberstein, Xiaoping Chen

Exploiting Coordination Locales in Distributed POMDPs via Social Model Shaping
Pradeep Varakantham, Jun-young Kwak, Matthew Taylor, Janusz Marecki, Paul Scerri, Milind Tambe

Incremental Policy Generation for Finite-Horizon DEC-POMDPs
Chistopher Amato, Jilles Steeve Dibangoye, Shlomo Zilberstein

Session 4: Heuristics and Search Space Analysis (Hall: Aristotelis II)
Chair: David Smith

Improving Planning Performance Using Low-Conflict Relaxed Plans
Jorge A. Baier, Adi Botea

Inference and Decomposition in Planning Using Causal Consistent Chains
Nir Lipovetzky, Hector Geffner

Extending the Use of Inference in Temporal Planning as Forwards Search
Amanda Coles, Andrew Coles, Maria Fox, Derek Long

Using the Context-Enhanced Additive Heuristic for Temporal and Numeric Planning
Patrick Eyerich, Robert Mattmüller, Gabriele Röger


Doctoral Consortium Papers Session (presented as posters, coffee break included)
(Hall: Aristotelis I)
co-Chairs: Antonio Garrido and Eva Onaindia


Applications Showcase
(Hall: Aristotelis I)
Mark Giuliano

DSE: The DSN Scheduling Engine, A Request-Driven Scheduler for  NASA’s Deep Space Network
Mark D. Johnston, Daniel Tran, Belinda Arroyo, Chris Page

Interactive Gantt Viewer with Automated Schedule Repair
Roman Barták, Tomáš Skalický

The APSI framework: a Planning and Scheduling Software Development Environment
Amedeo Cesta, Gabriella Cortellessa, Simone Fratini, Angelo Oddi,  Riccardo Rasconi

Planning in a Smart Home: Visualization and Simulation Alexander
Lazovik, Eirini Kaldeli,  Elena Lazovik,  Marco Aiello

MissionTool: Space Mission Planning in a Public Outreach and Educational Application
Derek Long

A Mission Planning System for Underwater Gliders
David R. Thompson, Steve Chien, Matthew Arrott2 Arjuna Balasuriya, Yi Chao, Peggy Li,  Michael Meisinger, Stephanie Petillo, Oscar Schofield

PANDORA -  Program for the Advancement of Non Directed Operating Robotic Agents
Antaris Stefanos, Doulgeri Zoe, Nikolaidis Georgios, Papadopoulos Charalampos, Papanikas Georgios, Papazoglou Anestis, Petridis Vasileios, Petrou Loukas, Serenis Charalampos, Skolarikis Michalis, Tsalidis Paraskevas, Tsardoulias Emmanouil, Zolotas Christoforos  


Open Session – Talk with the demonstrators one on one

Tuesday, September 22nd


Invited Talk: Scheduling in Dynamic, Uncertain Environments: Closing the Loop with Execution
Stephen F. Smith
Hall: Aristotelis I
Chair: Amedeo Cesta


Coffee break


Session 5: Planning Utilization (Hall: Aristotelis I)
Sheila McIlraith

Continuous Orchestration of Web Services via Planning
Piergiorgio Bertoli, Raman Kazhamiakin, Massimo Paolucci, Marco Pistore, Heorhi Raik, Matthias Wagner

Composition of Partially Observable Services Exporting their Behaviour
Giuseppe De Giacomo, Riccardo De Masellis, Fabio Patrizi

An Optimal Temporally Expressive Planner: Initial Results and Application to P2P Network Optimization
Ruoyun Huang, Yixin Chen, Weixiong Zhang

Pervasive Model Adaptation: The Integration of Planning and Information Gathering in Dynamic Production Systems
Juan Liu, Lukas Kuhn, Johan de Kleer

Session 6: Planning & Scheduling under Uncertainty (Hall: Aristotelis II)
Chair: Daniel Bryce

Improved Local Search for Job Shop Scheduling with Uncertain Durations
Inés González-Rodríguez, Camino R. Vela, Jorge Puente, Alejandro Hernández-Arauzo

A Decision-Theoretic Approach to Dynamic Sensor Selection in Camera Networks
Matthijs T. J. Spaan, Pedro U. Lima

Efficient Solutions to Factored MDPs with Imprecise Transition Probabilities
Karina Valdivia Delgado, Scott Sanner, Leliane Nunes de Barros, Fabio G. Cozman

Focused Topological Value Iteration
Peng Dai, Mausam, Daniel S. Weld


Lunch Break


Best Papers Session (Hall: Aristotelis I)
Chair: Alfonso Gerevini

Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway?
Malte Helmert, Carmel Domshlak (Best paper)

Scalable, Parallel Best-First Search for Optimal Sequential Planning
Akihiro Kishimoto, Alex Fukunaga, Adi Botea
(Best paper)

Lower Bounding Klondike Solitaire with Monte-Carlo Planning
Ronald Bjarnason, Alan Fern, Prasad Tadepalli (Best student paper)

Reachability Heuristics for Scaling Planning Under Uncertainty (Best dissertation presentation)
Daniel Bryce


Coffee break


ICKEPS Results Presentation  (Hall: Aristotelis I)


ICAPS Community Meeting  (Hall: Aristotelis I)



20:00 – 23:00

Social Dinner
Hotel Macedonia Palace
(Veranda or Alexandros Hall, depending on the weather)

Wednesday, September 23rd


Invited Talk: Planning with Continuous Change
Maria Fox

European Coordinating Committee for Artificial Intelligence (ECCAI) Invited Speaker
Hall: Aristotelis I
Chair: Ioannis Refanidis


Coffee break


Short Papers Session (presented as posters) (Hall: Aristotelis I)
Chair: Amedeo Cesta

Integrating Planning and Scheduling in a CP Framework: A Transition-Based Approach
Debdeep Banerjee

Ant Search Strategies for Planning Optimization
M. Baioletti, A. Milani, V. Poggioni, F. Rossi

Acquisition of Object-Centred Domain Models from Planning Examples
S. N. Cresswell, T. L. McCluskey, M. M. West

Multi-Goal Planning for an Autonomous Blasthole Drill
Pantelis Elinas

Computing Robust Plans in Continuous Domains
Christian Fritz, Sheila McIlraith

An Automatically Configurable Portfolio-Based Planner with Macro-Actions: PbP
Alfonso E. Gerevini, Alessandro Saetti, Mauro Vallati

hm(P) = h1 (Pm): Alternative Characterisations of the Generalisation from hmax to hm
Patrik Haslum

Path-Adaptive A* for Incremental Heuristic Search in Unknown Terrain
Carlos Hernández, Pedro Meseguer, Xiaoxun Sun, Sven Koenig

Extended Goals for Composing Services
Eirini Kaldeli, Alexander Lazovik, Marco Aiello

From Discrete Mission Schedule to Continuous Implicit Trajectory Using Optimal Time Warping
François Keith, Nicolas Mansard, Sylvain Miossec, Abderrahmane Kheddar

Learning User Plan Preferences Obfuscated by Feasibility Constraints
Nan Li, William Cushing, Subbarao Kambhampati, Sungwook Yoon

Exploiting N-Gram Analysis to Predict Operator Sequences
Christian Muise, Sheila McIlraith, Jorge A. Baier, Michael Reimer

Solving Resource-Constrained Project Scheduling Problems with Time-Windows Using Iterative Improvement Algorithms
Angelo Oddi, Riccardo Rasconi

Using Distance Estimates in Heuristic Search
Jordan T. Thayer, Wheeler Ruml


Lunch Break


Session 7: Methodologies, Tools & Languages  (Hall: Aristotelis I)
Chair: Derek Long

UPMurphi: A Tool for Universal Planning on PDDL+ Problems
Giuseppe Della Penna, Daniele Magazzeni, Fabio Mercorio

A Semantics for HTN Methods
Robert P. Goldman

Semantic Attachments for Domain-Independent Planning Systems
Christian Dornhege, Patrick Eyerich, Thomas Keller, Sebastian Trüg, Michael Brenner, Bernhard Nebel

Minimal Sufficient Explanations for Factored Markov Decision Processes
Omar Zia Khan, Pascal Poupart, James P. Black

Session 8: Classical and Parallel Planning (Hall: Aristotelis II)
Carmel Domshlak

Enhancing the Context-Enhanced Additive Heuristic with Precedence Constraints
Dunbo Cai, Jörg Hoffmann, Malte Helmert

The Influence of k-Dependence on the Complexity of Planning
Omer Giménez, Anders Jonsson

Optimality Properties of Planning Via Petri Net Unfolding: A Formal Analysis
Sarah Hickmott, Sebastian Sardina

SAT-Based Parallel Planning Using a Split Representation of Actions
Nathan Robinson, Charles Gretton, Duc-Nghia Pham, Abdul Sattar


Coffee break


Session 9: Constraint Reasoning for P&S  (Hall: Aristotelis I)
Chair: Angelo Oddi

Flexible Execution of Plans with Choice
Patrick R. Conrad, Julie A. Shah, Brian C. Williams

Just-in-Time Scheduling with Constraint Programming
Jean-Noël Monette, Yves Deville, Pascal Van Hentenryck

Forward Constraint-Based Algorithms for Anytime Planning
Cédric Pralet, Gérard Verfaillie

Session 10: Conformant/Contingent Planning (Hall: Aristotelis II)
Piergiorgio Bertoli

Automatic Derivation of Memoryless Policies and Finite-State Controllers Using Classical Planners
Blai Bonet, Héctor Palacios, Héctor Geffner

A Conformant Planner with Explicit Disjunctive Representation of Belief States
Son Thanh To, Enrico Pontelli, Tran Cao Son

Dynamic Controllability of Temporally-Flexible Reactive Programs
Robert Effinger, Brian Williams, Gerard Kelly, Michael Sheehy


Closing remarks

Poster stand specifications: Width = 1 meter, Height = 2,5 meters. For a picture click here. Note that although in the picture the poster stands appear adjacent to each other, in our setup they will be separately, with enough space between them. They also will be used one-side only. Pins are not allowed to hang the posters; glue will be provided onsite. Please hang your poster as early as possible in the day of your poster session.