Constraint Programming Approach to the TAEMS Scheduling Problem

Abstract

Planning and Scheduling are well-recognized research areas in the field of AI that address goal directed problem solving. They deal with choosing a course of action to achieve a goal contingent upon some sequencing and temporal constraints. TAEMS, (acronym for Task Analysis, Environment Modeling, and Simulation) is a modeling language for describing the task structures of agents. The TAEMS planning and scheduling problem is a particular case, where the actions that need to be scheduled to accomplish a root task are presented in a graph like structure. This problem is an NP-hard problem requiring search through a possibly exponential sized solution space. This thesis aims at generating the basic initial schedule for a TAEMS style objective task structure using constraint programming techniques. Solving this initial planning and scheduling problem using constraint programming techniques involves encoding the TAEMS problem as a Constraint Satisfaction Problem, solving the Constraint Satisfaction Problem using various solver search techniques and decoding the solution into a TAEMS plan and schedule. The advantage of using the Constraint Programming approach is that the built-in search techniques of a solver can be utilized instead of implementing hand-crafted algorithms in a high level language. The thesis explains the techniques developed and provides the results of an experimental evaluation.