Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling
Edited by Susanne Biundo, Karen Myers, and Kanna Rajan
Monterey, California, June 5–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
Preface / ix
Susanne Biundo, Karen Myers, and Kanna Rajan
ICAPS 2005 Organizing Committee / xi
ICAPS 2005 Program Committee / xiii
ICAPS 2005 Sponsors / xv
ICAPS 2005 Best Paper Prizes / xvi
Applications of Planning and Scheduling
Automated Composition of Web Services by Planning in Asynchronous Domains / 2
Marco Pistore, Paolo Traverso, and Piergiorgio Bertoli
Course of Action Generation for Cyber Security Using Classical Planning / 12
Mark Boddy, Johnathan Gohde, Tom Haigh, and Steven Harp
Minimizing Breaks in Sport Scheduling with Local Search / 22
Pascal van Hentenryck and Yannis Vergados
On-line Planning and Scheduling for High-speed Manufacturing / 30
Wheeler Ruml, Minh B. Do, and Markus P. J. Fromherz
Activity Planning for the Mars Exploration Rovers / 40
John L. Bresina, Ari K. Jónsson, Paul H. Morris, and Kanna Rajan
Search for Planning and Scheduling
External Symbolic Heuristic Search with Pattern Databases / 51
Stefan Edelkamp
Characterizing the Distribution of Low-Makespan Schedules in the Job Shop Scheduling Problem / 61
Matthew J. Streeter and Stephen F. Smith
Contingent Planning via Heuristic Forward Search with Implicit Belief States / 71
Jörg Hoffmann and Ronen I. Brafman
Randomized Large Neighborhood Search for Cumulative Scheduling / 81
Daniel Godard, Philippe Laborie, and Wim Nuijten
Beam-Stack Search: Integrating Backtracking with Beam Search / 90
Rong Zhou and Eric A. Hansen
A Generalized Framework for Lifelong Planning A* / 99
Maxim Likhachev and Sven Koenig
Temporal Planning
On the Tractability of Restricted Disjunctive Temporal Problems / 110
T. K. Satish Kumar
Concurrent Probabilistic Temporal Planning / 120
Mausam and Daniel Weld
Search Control in Planning for Temporally Extended Goals / 130
Froduald Kabanza and Sylvie Thiébaux
Planning and Scheduling for Uncertain and Dynamic Environments
Pruning Conformant Plans by Counting Models on Compiled d-DNNF Representations / 141
Héctor Palacios, Blai Bonet, Adnan Darwiche, and Héctor Geffner
Fast Exact Planning in Markov Decision Processes / 151
H. Brendan McMahan and Geoffrey J. Gordon
Plan Repair as an Extension of Planning / 161
Roman van der Krogt and Mathijs de Weerdt
Online Stochastic Optimization without Distributions / 171
Russell Bent and Pascal van Hentenryck
Overconstrained Problems
Planning with Goal Preferences and Constraints / 182
Ronen I. Brafman and Yuri Chernyavsky
Planning Graph Heuristics for Selecting Objectives in Over-subscription Planning Problems / 192
Romeo Sanchez Nigenda and Subbarao Kambhampati
Solving Over-constrained Disjunctive Temporal Problems with Preferences / 202
Bart Peintner, Michael D. Moffitt, and Martha E. Pollack
Retaining Flexibility to Maximize Quality: When the Scheduler Has the Right to Decide Activity Durations / 212
Xiaofang Wang and Stephen F. Smith
Domain Models and Learning
Discovering Planning Invariants as Anomalies in State Descriptions / 223
Proshanto Mukherji and Lenhart K. Schubert
Learning Partial-Order Macros from Solutions / 231
Adi Botea, Martin Müller, and Jonathan Schaeffer
Learning Action Models from Plan Examples with Incomplete Knowledge / 241
Qiang Yang, Kangheng Wu, and Yunfei Jiang
Anytime Planning and Scheduling
Enabling Fast Flexible Planning through Incremental Temporal Reasoning with Conflict Extraction / 252
I-hsiang Shu, Robert Effinger, and Brian Williams
Anytime Dynamic A*: An Anytime, Replanning Algorithm / 262
Maxim Likhachev, David Ferguson, Geoffrey J. Gordon, Anthony Stentz, and Sebastian Thrun
Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems / 272
Laurence A. Kramer and Stephen F. Smith
Combined and New Techniques for Planning
Planning as Mixed-initiative Goal Manipulation / 282
Michael T. Cox and Chen Zhang
Satisfiability Planning with Constraints on the Number of Actions / 292
Markus Büttner and Jussi Rintanen
A Hierarchical Task-Network Planner based on Symbolic Model Checking / 300
Ugur Kuter, Dana Nau, Marco Pistore, and Paolo Traverso
Reviving Integer Programming Approaches for AI Planning: A Branch-and-Cut Framework / 310
Menkes van den Briel, Thomas Vossen, and Subbarao Kambhampati
Genetic Planning Using Variable Length Chromosomes / 320
Alexandru Horia Brie and Philippe Morignot
Index / 331