Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling
Edited by Derek Long, Stephen F. Smith, Daniel Borrajo, and Lee McCluskey
Cumbria, UK, June 6–10, 2005. Published by The AAAI Press, Menlo Park, California. This proceedings is also available in book format.
Please Note: Abstracts are linked to individual titles, and will appear in a separate browser window. Full-text versions of the papers are linked to the abstract text. Access to full text may be restricted to AAAI members. PDF file sizes may be large!
Contents
Sponsors / x
Preface / xi
Derek Long, Stephen F. Smith, Daniel Borrajo, and Lee McCluskey
Organizing Committee / xiii
Program Committee / xv
Invited Speaker Abstracts / xix
Applications of Planning and Scheduling
An Affectively Driven Planner for Synthetic Characters / 2
Ruth Aylett, Joao Dias, and Ana Paiva
Bringing Users and Planning Technology Together. Experiences in SIADEX / 11
Juan Fdez-Olivares, Luis Castillo, Óscar García-Pérez, and Francisco Palao
Predictive Planning for Supply Chain Management / 21
David Pardoe and Peter Stone
Scalable Planning for Distributed Stream Processing Systems / 31
Anton Riabov and Zhen Liu
Complexity of Planning and Scheduling
Bounded Branching and Modalities in Non-Deterministic Planning / 42
Blai Bonet
New Complexity Results for Classical Planning Benchmarks / 52
Malte Helmert
Constraint Reasoning for Planning and Scheduling
Efficiently Handling Temporal Knowledge in an HTN Planner / 63
Luis Castillo, Juan Fdez-Olivares, Óscar García-Pérez, and Francisco Palao
Tractable Optimal Competitive Scheduling / 73
Jeremy Frank, James Crawford, Lina Khatib, and Ronen Brafman
On Some Tractable Cases of Logical Filtering / 83
T. K. Satish Kumar and Stuart Russell
Optimal Rectangle Packing: A Meta-CSP Approach / 93
Michael D. Moffitt and Martha E. Pollack
Lemma Reusing for SAT based Planning and Scheduling / 103
Hidetomo Nabeshima, Takehide Soh, Katsumi Inoue, and Koji Iwanuma
Decision-Theoretic Planning
Solving Factored MDPs with Exponential-Family Transition Models / 114
Branislav Kveton and Milos Hauskrecht
Stochastic Over-Subscription Planning Using Hierarchies of MDPs / 121
Nicolas Meuleau, Ronen Brafman, and Emmanuel Benazera
Optimal Route Planning under Uncertainty / 131
Evdokia Nikolova, Matthew Brand, and David R. Karger
Learning in Planning and Scheduling
Learning Depth-First Search: A Unified Approach to Heuristic Search in
Deterministic and Non-Deterministic Settings, and Its Application to MDPs / 142
Blai Bonet and Héctor Geffner
Explanation-Based Acquisition of Planning Operators / 152
Geoffrey Levine and Gerald DeJong
Learning Heuristic Functions from Relaxed Plans / 162
SungWook Yoon, Alan Fern, and Robert Givan
Mixed-Initiative Planning and Scheduling
Evaluating Mixed-Initiative Systems: An Experimental Approach / 172
Gabriella Cortellessa and Amedeo Cesta
Metatheoretic Plan Summarization and Comparison / 182
Karen L. Myers
Plan and Schedule Execution, Monitoring, and Repair
Safe LTL Assumption-Based Planning / 193
Alexandre Albore and Piergiorgio Bertoli
Goal Achievement in Partially Known, Partially Observable Domains / 203
Allen Chang and Eyal Amir
Plan Stability: Replanning versus Plan Repair / 212
Maria Fox, Alfonso Gerevini, Derek Long, and Ivan Serina
Incremental Scheduling to Maximize Quality in a Dynamic Environment / 222
Anthony Gallagher, Terry L. Zimmerman, and Stephen F. Smith
Probabilistic Planning
Sequential Monte Carlo in Probabilistic Planning Reachability Heuristics / 233
Daniel Bryce, Subbarao Kambhampati, and David E. Smith
Fast Probabilistic Planning through Weighted Model Counting / 243
Carmel Domshlak and Jörg Hoffmann
Combining Knowledge Compilation and Search
for Conformant Probabilistic Planning / 253
Jinbo Huang
Concurrent Probabilistic Planning in the Graphplan Framework / 263
Iain Little and Sylvie Thiébaux
Search for Planning and Scheduling
An Empirical Study of Multi-Point Constructive Search for
Constraint-Based Scheduling / 274
J. Christopher Beck
Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs
in SAT-Based Planning / 284
Jörg Hoffmann, Carla Gomes, and Bart Selman
Friends or Foes? An AI Planning Perspective on Abstraction and Search / 294
Jörg Hoffmann, Ashish Sabharwal, and Carmel Domshlak
Memory-Efficient Symbolic Heuristic Search / 304
Rune M. Jensen, Eric A. Hansen, Simon Richards, and Rong Zhou
Looking for Shortcuts: Infeasible Search Analysis for
Oversubscribed Scheduling Problems / 314
Mark F. Rogers, Adele Howe, and Darrell Whitley
Exploiting the Power of Local Search in a Branch and Bound Algorithm
for Job Shop Scheduling / 324
Matthew J. Streeter and Stephen F. Smith
Short Papers
A Multi-Start Very Large Neighbourhood Search Approach with Local Search Methods
for Examination Timetabling / 334
Salwani Abdullah and Edmund K. Burke
SEMAPLAN: Combining Planning with Semantic Matching to Achieve Web Service
Composition / 338
Rama Akkiraju, Biplav Srivastava, Anca-Andreea Ivan, Richard Goodwin, and Tanveer Syeda-Mahmood
Planning with Temporally Extended Goals Using Heuristic Search / 342
Jorge A. Baier and Sheila A. McIlraith
Run-Time Monitoring of the Execution of Plans for Web Service Composition / 346
Fabio Barbon, Paolo Traverso, Marco Pistore, and Michele Trainotti
Incremental Maintenance of Double Precedence Graphs:
A Constraint-Based Approach / 350
Roman Barták and Ondrej Cepek
Towards Strong Cyclic Planning under Partial Observability / 354
Piergiorgio Bertoli, Alessandro Cimatti, and Marco Pistore
Automated Web Service Composition by On-the-Fly Belief Space Search / 358
Piergiorgio Bertoli, Marco Pistore, and Paolo Traverso
RRT-Plan: A Randomized Algorithm for STRIPS Planning / 362
Daniel Burfoot, Joelle Pineau, and Gregory Dudek
Motion Economy and Planning / 366
Özgen Canan and Aysenur Birtürk
Lessons Learned in Applying Domain-Independent Planning to
High-Speed Manufacturing / 370
Minh Do and Wheeler Ruml
On the Compilation of Plan Constraints and Preferences / 374
Stefan Edelkamp
Reusing and Building a Policy Library / 378
Fernando Fernández and Manuela Veloso
Durative Planning in HTNs / 382
Robert P. Goldman
Robust Execution of Temporally Flexible Plans for Bipedal Walking Devices / 386
Andreas Hofmann and Brian Williams
Learning to Do HTN Planning / 390
Okhtay Ilghami, Dana S. Nau, and Héctor Muñoz-Avila
Learning Behaviors Models for Robot Execution Control / 394
Guillaume Infantes, Félix Ingrand, and Malik Ghallab
Planning for PDDL3—An OCSP Based Approach / 398
Bharat Ranjan Kavuluri, Naresh Babu Saladi, and Deepak Khemani
A New Principle for Incremental Heuristic Search: Theoretical Results / 402
Sven Koenig and Maxim Likhachev
Resource Contention Metrics for Oversubscribed Scheduling Problems / 406
Laurence A. Kramer and Stephen F. Smith
Probabilistic Planning with Nonlinear Utility Functions / 410
Yaxin Liu and Sven Koenig
Challenges for Temporal Planning with Uncertain Durations / 414
Mausam and Daniel S. Weld
Automated Planning Using Quantum Computation / 418
S. Naguleswaran, L. B. White, and I. Fuss
Knowledge-based Middleware as an Architecture for Planning and Scheduling
Systems / 422
Bernd Schattenberg, Steffen Balzer, and Susanne Biundo
Combining Stochastic Task Models with Reinforcement Learning
for Dynamic Scheduling / 426
Malcolm J. A. Strens
Spacetrack: Trading off Quality and Utilization in Oversubscribed Schedules / 430
Andrew M. Sutton, Adele Howe, and L. Darrell Whitley
On the Use of UML.P for Modeling a Real Application as a Planning Problem / 434
Tiago Stegun Vaquero, Flavio Tonidandel, Leliane Nunes de Barros, and José Reinaldo Silva
Reconfigurable Path Planning for an Autonomous Unmanned Aerial Vehicle / 438
Mariusz Wzorek and Patrick Doherty
Optimal STRIPS Planning by Maximum Satisfiability and Accumulative Learning / 442
Zhao Xing, Yixin Chen, and Weixiong Zhang
Index / 447