Configurable, Mixed-Initiative Scheduling Systems

The OZONE/DITOPS Project

About

This research builds from our previous work in constraint-based scheduling and focuses on two key obstacles to the development and application of intelligent systems in large-scale planning and scheduling domains such as manufacturing management and crisis-action logisitics planning:

Current systems do not effectively support user tasks and requirements - They force users to operate on their terms, provide no guidance in understanding, diagnosing and improving results, and do not support the iterative, evolving process of problem understanding, requirements determination, conflict resolution and solution refinement that is inherent in large-scale, multi-agent problem solving.
Current application building efforts are difficult, costly and time consuming tasks. The power of knowledge-based planning and scheduling technologies, i.e., their ability to encode and productively exploit high-fidelity models of the target environment and domain-specific heuristics, is also their "Achilles' heel" from a system development perspective.

Approach

We are developing theories, techniques and software architectures that address these problems, enabling both flexible collaborative problem solving between user and system, and flexible reconfiguration of system functionality to accommodate new domains and/or domain requirements. Our approach to mixed-initiative systems properly recognizes scheduling for what it is in most practical domains: an iterative process of "getting the constraints right" in which humans always have strategic, big-picture decision-making expertise and knowledge to contribute but are unable to effectively cope with the complexity of detailed solution development. We are developing a collaborative scheduling framework based on this process viewpoint, where the user visualizes and manipulates solutions from comprehensible, aggregate perspectives, and the system incrementally manages the details of user changes in accordance with communicated goals and expectations. Our approach to scheduling system architecture builds from object technology concepts. We are developing a general "ontology" of scheduling concepts to enable application in different domains and allow integration with other, complementary problem solving and information processing services. Our broader goal is a planning and scheduling "tool box", an application construction environment which couples a system configuration infra-structure with expandable libraries of functional componentry.

Application Context and Software Technologies

The dominant application focus of this work, funded under the ARPA/Rome Laboratories Planning Initiative, is military crisis-action deployment scheduling. This has led to development of the DITOPS scheduling system. DITOPS combines the use of hierarchical domain models and solution visualizations with reactive, constraint-based scheduling techniques to provide advanced capabilities for generating, analyzing, manipulating and improving deployment schedules. At the same time, DITOPS has been designed for reconfigurability; the supporting OZONE scheduling infra-structure provides a rich class library of modeling and scheduling services that make the system readily applicable to other problem domains.

Links

DITOPS System Overview
DARPA/Rome Laboratory Planning Initiative (ARPI) home page
ARPI Phase I Technology Inventory page for DITOPS
Ditops Demo
Barrel Demo
A transportation scheduling problem that DITOPS has solved.

Recent Publications

S.F. Smith, O. Lassila and M. Becker, Configurable, Mixed-Initiative Systems for Planning and Scheduling, in Advanced Planning Technology, (ed. A. Tate), AAAI Press, Menlo Park, CA, May, 1996.

M. Becker, and S.F. Smith, "Using DITOPS as a Tool for Mixed-Initiative Schedule Improvement" (This is a TAR file with the gzipped version of the paper. The post-script file has been split into 6 parts because of its size. Download the file, 1M, untar with "tar xvf ditops-demo.tar", goto the compressed directory, "gunzip ditops-demo-ps*").

Smith, S.F. and M. Becker, "An Ontology for Constructing Scheduling Systems", to appear in Working Notes of 1997 AAAI Symposium on Ontological Engineering, Stanford, CA, March, 1997 (AAAI Press).

O. Lassila, M. Becker and S.F. Smith, "An Exploratory Prototype for Air Medical Evacuation Re-Planning", CMU Robotics Institute Technical Report CMU-RI-TR-96-03, January, 1996.

S.F. Smith, "Reactive Scheduling Systems", in Intelligent Scheduling Systems, (eds. Brown & Scherer), Kluwer Publishing, 1995.

M. Burstien, R. Shantz, M. Bienkowski, M.desJardin and S.F. Smith, "The Arpa/Rome Laboratory Common Prototyping Environment: A Framework for Software Technology Integration, Evaluation and Transition", IEEE Expert, Vol. 10, No. 1, February 1995.

S.F.Smith and O.Lassila, Toward the Development of Mixed-Initiative Scheduling systems, ARPA-Rome Laboratory Planning Initiative Workshop, Tucson (AZ), 1994.

O.Lassila and S.F.Smith, Constructing Flexible Scheduling Systems for Decision Support, Proceedings 1994 Finnish AI Symposium, Turku (Finland), August 1994.

O.Lassila and S.F.Smith, Flexible, Constraint-Based Tools for Complex Scheduling Applications, IEEE 4th Annual Dual-Use Technologies & Applications Conference, Utica (NY), 1994.

S.F. Smith, O. Lassila and M. Becker, "Configurable Planning and Scheduling Systems", AI*IA Notizie (Quarterly Publication of the Artificial Intelligence Italian Association), Special Issue on Aspects of Planning Research, Vol.9, No. 1, March, 1996, pp. 27-32.

S.F. Smith, O. Lassila and M. Becker, "A Scheduling Ontology: Informal Concept Descriptions", ICLL Working Paper, January, 1996.

S.F.Smith and O.Lassila, Configurable Systems for Reactive Production Management, IFIP Transactions B-15, Elsevier Science B.V., 1994.

S.F.Smith and K.P. Sycara, Flexible Coordination in Resource-Constrained Domains, Technical Report CMU-RI-TR-93-17, The Robotics Institute, Carnegie Mellon University, December, 1993.

Marcel Becker
Last modified: Fri Mar 10 18:12:12 EST 2000