Workshop on "Integrating Planning Into Scheduling"

ICAPS 2004 Workshop Program

Workshop on "Integrating Planning Into Scheduling"
(WIPIS-04)

To be held in conjunction with:

The 14th International Conference on Automated Planning and Scheduling (ICAPS)
Whisler Canada, June, 2004

Overview :: Scope :: Submission :: Format :: Dates :: PC
Accepted Papers :: Agenda :: Working Notes

Overview
The topic of this workshop is on the general question of how to integrate planning capabilities into scheduling algorithms and frameworks. It has been recognized for some time that classical planning and scheduling models are at opposite ends of a spectrum, with most interesting real-world problems falling somewhere in the middle and requiring characteristics of both. Real "planning" problems tend to require the ability to handle metric quantities, overlapping actions with finite durations, and very often some notion of a resource model. Similarly, most real-world scheduling problems are not "pure" scheduling problems - i.e., concerned strictly with allocating resources to pre-specified activities over time. Even in venerable scheduling domains such as manufacturing, it is frequently necessary to solve something that looks very much like a planning problem, ranging in scope from simple selection among alternative processes (e.g., heterogeneous resource capabilities) to the synthesis of complex networks of resource configuration and support activities. Historically, scheduling research has addressed such planning issues via specialized, problem-specific model and algorithm extensions.

In recent years, the AI planning community has focused increasingly on extending classical planning formalisms to incorporate notions of resources and time. Recently published work, as well as the results achieved in the most recent International Planning Competition (IPC) at AIPS-02, have demonstrated considerable progress on incorporating metric quantities and durative actions into the classical planning framework. These extensions increase the relevance of classical planning techniques to scheduling problems. However, it is only a starting point. Classical planning focuses on individual actions, rather than organizing or synchronizing with operations in the larger environment, and on discrete state changes, rather than multiple, interacting asynchronous processes. This means that augmenting planning systems with models that include durative actions and resource capacity constraints is unlikely, by itself, to translate into an effective solution for problems in which resource allocation is central. On the other hand, the techniques typically used within schedulers to solve embedded planning problems in practice tend to be problem-specific, and are difficult to extend and transfer to new contexts. AI planning technologies offer clear potential for more general solutions.

Scope
The central theme of the workshop is that planning techniques are necessary to the solution of these problems, but must be integrated into scheduling algorithms and frameworks. To this end, the workshop seeks to bring together researchers interested in the intersection of scheduling and planning technologies to share perspectives, techniques and results on how to better solve scheduling problems with embedded planning sub-problems. Topics of interest include:

Frameworks for integrating causal reasoning into resource allocation and scheduling algorithms

Descriptions of scheduling problems requiring embedded planning capabilities

Descriptions of algorithms and implementation of features and components which add planning capabilities to the scheduling framework

Algorithms for partial order scheduling and their advantages and disadvantages in comparison to temporal planning frameworks

Techniques for reasoning about context-dependent tasks and resource setup and reconfiguration activities (e.g., ensuring the proper state of resources for correct schedule execution)

Proposals for the generation of an appropriate set of benchmark problems, similar to the current IPC domains

Arguments to the contrary (e.g., proposals for extending classical planning to address problems in which resources are primary).

Submission Instructions
Participation in the workshop will be by invitation only, and prospective participants are requested to submit one of the following:

Full Paper - Technical papers are invited that address one or more of the workshop topics indicated above. Papers can be up to 8 pages in length. The first page of the paper should include the title, a brief abstract, and author names, affiliations, postal addresses, electronic mail addresses, and telephone and fax numbers.

Statement of Interest - Although first preference will be given to full paper submissions, we anticipate room for some number of additional attendees and request that other individuals interested in attending the workshop submit a one-page statement of interest.

Invitations will be based on submissions, and on expected participation in workshop discussions.

Accepted full papers will appear in the workshop proceedings. One desired outcome of the workshop is to produce a journal special issue on aspects of integrating planning into scheduling. Authors of accepted papers will be invited to submit expanded versions of their workshop papers for consideration in this special issue.

Authors are encouraged to submit papers electronically in postscript or PDF format. Papers should be formatted using the ICAPS conference style (see ICAPS 04 conference call).

Please send your submissions by email to mark.boddy@adventiumlabs.org no later than February 17, 2004 using the subject line "WIPIS-04 Workshop Submission". Confidentiality of submissions will be maintained during the review process. All submitted materials for rejected papers will be kept confidential in perpetuity. All submitted materials for accepted papers will be kept confidential until the date of the workshop, June 4, 2004. Submissions should not include information that will be confidential or proprietary at the time of publication.

Workshop Format
The workshop will be structured to allow ample time for discussion and interactions. The workshop will last one full day, with an agenda including the following:

An invited talk from a senior member of the scheduling community, intended to give a scheduling perspective on embedded planning problems and current approaches.

Selected presentations of papers accepted by the program committee. To foster interaction and comparisons, paper presentations will be coupled with commentaries aimed at raising different, possibly opposing viewpoints.

One or more panels, each addressing a particular issue relevant to the workshop topic, to be determined once we have seen the submissions.

Important Dates

Deadline for submission of papers and position statements: February 17, 2004

Notification of acceptance/rejection: March 16, 2004

Deadline for receipt of camera-ready copy: March 26, 2004

Program Committee

Pauline Berry, SRI International

Mark Boddy, Adventium Labs (Co-Chair)

Amedeo Cesta, ISTC-CNR (Co-Chair)

Maria Fox, University of Strathclyde

Jeremy Frank, NASA Ames

Subbarao Kambhampati, Arizona State University

Philippe Laborie, ILOG

Stephen F. Smith, Carnegie Mellon University (Co-Chair)

Jean Paul Watson, Sandia National Laboratories

List of Accepted Papers

Integrating Planning into Production Scheduling: A Formal View
Roman Barták

Compiling Planning into Scheduling: A Sketch
Tania Bedrax-Weiss, James M. Crawford and David E. Smith

Integrated Planning and Scheduling for Petroleum Refinery Operations
Mark S. Boddy and Daniel P. Johnson

Biasing the Structure of Scheduling Problems Through Classical Planners
Amedeo Cesta, Federico Pecora and Riccardo Rasconi

Planning - Scheduling Connections through Exogenous Events
Minh B. Do, Subbarao Kambhampati and Terry Zimmerman

Extended Critical Paths in Temporal Planning
Stefan Edelkamp

CRIKEY - A Temporal Planner Looking at the Integration of Scheduling and Planning
Keith Halsey, Derek Long and Maria Fox

Using Constraint Programming to Solve a Project Scheduling Problem with Skilled Labor
Haitao Li, Jose Dula, Karen Lewis and Keith Womer

On-line Planning and Scheduling in a High-speed Manufacturing Domain
Wheeler Ruml and Markus P. J. Fromherz

Planning with Disjunctive Temporal Constraints
Peter J. Schwartz and Martha E. Pollack

Closed-Loop Online Scheduling with Timing Constraints and Quality Profiles on Multiprocessor Architectures
Thomas Schwarzfischer

Planning Tactics within Scheduling Problems
Stephen F. Smith and Terry L. Zimmerman

Over-Subscription in Planning: a Partial Satisfaction Problem
Menkes van den Briel, Romeo Sanchez and Subbarao Kambhampati

Branching and Pruning: An Optimal Temporal POCL Planner based on Constraint Programming
Vincent Vidal and Héctor Geffner

Agenda (preliminary)

8:30 - 8:40	Introductory remarks
8:40 - 9:30	Invited speaker
	Kenneth McKay
	Department of Management Sciences - University of Waterloo
9:30 - 10:30	CSP Compilation
	Bedrax-Weiss, Vidal
	Discussant: Maria Fox
10:30 - 11:00	Break
11:00 - 12:20	Integration and Applications
	Barták, Boddy, Smith
	Discussant: Rao Kambhampati
12:20 - 1:50	Lunch
1:50 - 3:30	Temporal Planning
	Edelkamp, Hasley, Cesta, Schwartz
	Discussant: Jeremy Frank
3:30 - 4:00	Break
4:00 - 5:00	On-line Aspects
	Ruml, Schwarzfischer
	Discussant: Jean-Paul Watson
5:00 - 6:00	Final planel: Planning into Scheduling or Scheduling into Planning?
	Panel participants include: Haitao Li, Minh B. Do, Menkes van den Briel, Jean-Paul Watson
	Moderator: Pauline Berry

Working Notes

You can download the working notes here: [PDF] (3.8MB)

Overview :: Scope :: Submission :: Format :: Dates :: PC
Accepted Papers :: Agenda :: Working Notes