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

In the last decades, there has been an increasing interest in the connection between planning and constraint program-ming. 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 schedul-ing 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 experimen-tal 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