NUDGE, a Knowledge-Based Scheduling Program

Abstract

Traditional scheduling algorithms (using the techniques of PERT charts, decision analysis or operations research) require well-defined, quantitative, complete sets of constraints. They are insufficient for scheduling situations where the problem description is ill-defined, involving incomplete, possibly inconsistent and generally qualitative constraints. The NUDGE program uses an extensive knowledge base to debug scheduling requests by supplying typical values for qualitative constraints, supplying missing details and resolving minor inconsistencies. The result is that an informal request is converted to a complete description suitable for a traditional scheduler. To implement the NUDGE program, a knowledge representation language-FRL-0- based on a few powerful generalizations of the traditional property list representation has been developed. The NUDGE knowledge base defined in FRL-0 consists of a hierarchical set of concepts that provide generic deseriptions of the typical activities, agents, plans and purposes of the domain to be scheduled. Currently, this domain is the management and coordination of personnel engaged in a group project. NUDGE constitutes an experiment in knowledge-based, rather than power-based AI programs. It also provides an example of an intelligent support system, in which an AI program serves as an aid to a decision maker. Finally, NUDGE has served an experimental vehicle for testing advanced representation techniques.