Home

Call for Paper

Program Committee

Schedule

Links

 

Constraint Satisfaction Techniques for

Planning and Scheduling Problems

ICAPS 2006 Workshop
June 6-10, 2006

Cumbria, UK



Schedule (proceedings)

 

8:55-9:00   Presentation of the workshop  

09:00-09:30

Distributed Constraint Satisfaction Problems to Model Railway Scheduling Problems

M. Abril, M. A. Salido, F. Barber, L. Ingolotti, P. Tormos and A. Lova

 

 

Railway Scheduling is considered to be a difficult and time-consuming task. This is due to real railway networks can be modelled as Constraint Satisfaction Problems (CSPs), but they require a huge number of variables and constraints. The general CSP is known to be

NP-complete; however, distributed models may reduce the exponential complexity by dividing the problem into a set of subproblems. In this work, we present several proposals to distribute the railway scheduling problem into a set of sub-problems as independent as possible. The first technique carries out a partition over the constraint network, meanwhile the second distributes the problem by trains and the third technique divides the problem by means of contiguous stations.

09:30-10:00

A Filtering and Decomposition Approach To Optimal Sequential Planning

Stphane Grandcolas and Cyril Pain-Barre

 

 

This paper presents the FDP planning system based on the paradigm of planning as constraint satisfaction. FDP integrates consistency rules and filtering and decomposition mechanisms suitable for planning, rather than transform the planning problem into a CSP and make use of an external solver. FDP works directly on a structure related to Graphplan’s planning graph. Given a fixed bound on the length of the plan, the graph is incrementally built. Each time the graph is extended, a sequential plan is searched. In the search for a plan different strategies can be employed. Currently, FDP uses a forward-search procedure based on problem decomposition with action sets partitioning. FDP produces optimal sequential plans. Various techniques are also used to avoid useless processings, in particular to discard redundant sequences of actions and dead-end states. Empirical evaluation shows that FDP is competitive on many problems, especially compared to other optimal equential planners.

 

10:00-10:30

On State Management in Plan-Space Planning from CP Perspective

Pavel Surynek

 

 

In this paper we address the problem of encoding of planspace planning problems as a CSP. We propose a constraint model for expressing plan-space partial plans. As an enrichment of the notion of partial plans we propose a world state management within the partial plan. We incorporate the world state management into our CSP model too. Next we propose a specialized algorithm for solving the CSP model. The algorithm builds the constraint model dynamically as conflicts are resolved in the model. The performed preliminary experiments showed the usefulness of state management in the constraint model. The usage of state management allows the additional search space pruning compared to the model without states.

 

10:30-11:00 Coffee Break  

11:00-11:30

Interleaving Planning and Scheduling: a Collaborative Approach

Antonio Garrido and Eva Onainda

 

 

This paper proposes an approach to interleave planning and scheduling when dealing with real-world problems in a collaborative way. Hence, the paper analyses some challenging points for this collaboration, such as modelling the problem in a joint way, introducing the integrated architecture and, particularly, the definition of planning and scheduling conflicts and the way they are solved when both processes work together. We also include an example to illustrate the interaction of both processes.

 

11:30-12:00

Scheduling with uncertain durations: generating Beta-robust schedules using constraint programming

Christine Wei Wu, Kenneth N. Brown and J. Christopher Beck

 

Many real-world scheduling problems are subject to change, and scheduling solutions should be robust to those changes. We consider a single-machine scheduling problem where the processing time of each activity is characterized by a normally-distributed random variable, and we attempt to minimize flowtime. We develop an initial constraint model for generating the b-robust schedule - the schedule that has highest probability of producing a flowtime less than a stated bound. Experiments with this initial model show that a constraint-based approach is feasible, but that better propagation methods will be required.

12:00-12:30

Fix the Schedule or Solve Again? Comparing Constraint-Based Approaches to Schedule Execution

Riccardo Rasconi, Nicola Policella and Amedeo Cesta

 

 

This paper discusses alternative approaches to the execution, monitoring and repairing of pre-defined schedules enforced in a constraint-based framework. After presenting a platform able to perform reproducible experiments, we try to shed light on a set of basic trade-offs which focus on two aspects: (a) the type of initial solution generated from an offline problem solving phase, which represents a baseline for execution. In the attempt to increase proactive robustness, we analyze two alternatives to the classical fixed time schedule – flexible schedules containing a single point solution and partial order schedules. (b) The re-scheduling policy to react to unexpected events: we distinguish between the incremental modification of the initial schedule vs. the retraction of previously made decisions, followed by a new resolution. An interesting set of results is presented then analyzed. Part of the outcome represents a direct confirmation of theoretical expectations from previous analysis; yet, the presence of counterintuitive insights in the results opens the way for further investigation and new perspectives.

 

12:30-14:00 Lunch  

 

14:00-14:30

Factored Planning: How, When, and When Not

Ronen I. Brafman and Carmel Domshlak

 

Automated domain factoring, and planning methods that utilize them, have long been of interest to planning researchers. Recent work in this area yielded new theoretical insight and algorithms, but left many questions open: How to decompose a domain into factors? How to work with these factors? And whether and when decomposition-based methods are useful? This paper provides theoretical analysis that answers many of these questions: it proposes a novel approach to factored planning; proves its theoretical superiority over previous methods; provides insight into how to factor domains; and uses its novel complexity results to analyze when factored planning is likely to perform well, and when not. It also establishes the key role played by the domain’s causal graph in the complexity analysis of planning algorithms.

 

 

14:30-15:00

Reverse Combinatorial Auctions for Resource Allocation in the Rescue Scenario

Silvia Surez and Beatriz López

 

In a disaster environment no single agent knows the disaster situation completely. So, rescue agents share their information in order to identify rescue tasks that are then allocated. In this paper we model the allocation problem as a reverse combinatorial auction and we apply some existing algorithms to solve it. Our results have been compared with the RoboCup classification of 2005.

15:00-15:30

The Aspect of Quality in Scheduling Painting Tasks for an Automatic Robotic Spray System

Ewa Kolakowska and Ole Madsen

 

 

Paint planning is one of the key issues in fully automatic robotic spray painting systems. Generation of the precise spray painting paths is no longer sufficient to cope with high demands concerning optimization of both the lead-time and painting quality. In this context it is the sequence of the painting tasks that affects the efficiency of painting process. This paper presents a novel idea of improving the painting process by design of a scheduler that captures the aspect of quality. The proposed scheduler is based on the new concept of building a Product Process Structure Tree. It represents all possible solutions, constrained by quality requirements that are defined by process technical rules. By means of the Product Process Structure Tree the scheduling problem can be formulated as the constraint satisfaction problem. It is the first time the constrain satisfaction techniques are applied in the field of automatic spray painting.

 

   

 






Home | Outline | Call for Paper | Program Committee | Schedule | Links