9625755 Ginsberg, Matthew L. University of Oregon, Eugene Postdoc: Planning and Scheduling as Constraint Satisfaction Investigating Fundamental Similarities and Differences This award supports CES Associate David Joslin. Although planning and scheduling are closely related fields, the latter has enjoyed far greater success in recent years. Research in the field of scheduling has benefited greatly from treating scheduling problems as constraint satisfaction problems (CSPs); the application of CSP techniques to planning has been more limited, and has tended to be ad hoc. The Descartes algorithm, introduced by Joslin in 1995, has demonstrated that planning problems can be transformed into dynamic CSPs, allowing CSP techniques to be applied uniformly to all decisions. The CSP formulation also makes it possible to leverage successful scheduling algorithms in the solution of planning problems. The focus of this research is on understanding when and why CSP-based scheduling techniques are (or are not) effective when applied to planning problems. In the first phase, an efficient scheduling algorithm is integrated with the Descartes planning algorithm. The resulting hybrid system is experimentally evaluated on both planning and scheduling problems. In the second phase, differences between planning and scheduling are characterized in terms of a common CSP representation, and these differences are exploited to improve the performance of the planning system. ***
