Using Constraint Networks on Timelines to Model and Solve Planning and Scheduling Problems

Cédric Pralet, Gérard Verfaillie

In the last decades, there has been an increasing interest in the connection between planning and constraint programming. Several approaches were used, leading to different forms of combination between the two domains. In this paper, we present a new framework, called Constraint Network on Timelines (CNT), to model and solve planning and scheduling problems. Basically, CNTs are a kind of dynamic CSPs, enhanced with special variables called dimension variables representing the initially unknown number of steps in a valid or optimal plan. We also present an algorithm and experimental results showing that the expressiveness of CNTs allows efficient models to be developed, and can lead to significant gains on problems taken from planning competitions.

Subjects: 1.11 Planning; 15.2 Constraint Satisfaction

Submitted: Jun 27, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.