A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-04012006-154337


Type of Document Master's Thesis
Author Datta, Soumita
Author's Email Address soumita.datta@vanderbilt.edu
URN etd-04012006-154337
Title Constraint Programming Approach to the TAEMS Scheduling Problem
Degree Master of Science
Department Computer Science
Advisory Committee
Advisor Name Title
Gabor Karsai Committee Chair
Keywords
  • Planning and Scheduling
  • Constraint Programming
  • TAEMS
Date of Defense 2006-03-24
Availability unrestricted
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.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Datta_S_5_0_Scheduling.pdf 535.39 Kb 00:02:28 00:01:16 00:01:06 00:00:33 00:00:02

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LITS.