Constraint networks on timelines for planning and scheduling

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