Project Title:

Incremental Mixed-Initiative Planning and Scheduling Using Constraint Hierarchies

	  94-1	06.02	7828

	  Incremental Mixed-Initiative Planning and Scheduling Using 
	  Constraint Hierarchies

Abstract:

NASA is challenged by large, complex planning and scheduling 
problems. These problems require powerful problem solving 
techniques and sophisticated knowledge representation schemes. 
This research proposes to further advance the technology 
available for effectively solving large, complex planning and 
scheduling problems. Specifically, this research will focus on 
using constraint hierarchy technology, developed at the 
University of Washington, to support automated planning and 
scheduling of NASA missions, development efforts, and 
organizational tasks. This technology has been formalized through 
the development of a constraint hierarchy theory. This theory 
defines an architecture in which constraints are represented in 
a priority hierarchy. Computational mechanisms have been 
developed that perform incremental constraint satisfaction and 
automated constraint relaxation. This will be the first 
application of this promising new technology to the planning and 
scheduling domain. This technology will provide the capability 
to perform incremental, mixed initiative planning and scheduling. 
Constraint hierarchy theory concepts allow preferential 
constraints, which often influence planning and scheduling 
decisions, to be used in the automated solution of complex 
planning and scheduling problems. During Phase I of this project, 
the feasibility of applying constraint hierarchy technology to 
planning and scheduling will be verified and demonstrated.

The primary product would be a constraint-based reasoning system 
based on constraint hierarchy technology and marketed as a C++ 
class library that could be integrated into a wide range of 
applications. Another product would be an automated planning and 
scheduling engine that would be integrated into existing 
scheduling products.

Key words

Merritt Systems, Inc.
P.O. Box 542103
Merritt Island, FL 32954-2103