MKIDS

Management of Knowledge Intensive Dynamic Systems

ICLL was one of nine research organizations participating in this combined NSF / DoD program investigating how information technology can help streamline processes for organizations that must respond rapidly to incoming knowledge, dynamic situations, and uncertainty. http://nlp.syrres.com/mkids/index.htm

Problem
Knowledge-intensive dynamic systems (KIDS) present complex scheduling and coordination problems. KIDS refer generally to large-scale, multi-actor systems that plan and execute production processes with the following characteristics: (1) they principally involve the collection, manipulation and management of knowledge products, (2) they exhibit perpetual novelty in process structure, and (3) they are unpredictable in their outcomes and require continual dynamic adjustment and revision. The establishment of a schedule is crucial to effective management and control of KIDS; it is the means by which global coordination of executing agents (actors) is achieved and maintained. Attention must be paid to the cost of continual solution change and to maintaining continuity in currently executing processes, as evolving requirements, changing priorities and new resource availability constraints continually force changes to previously planned tasks and resource assignments. Like many other practical domains, KIDS are further complicated by the presence of multiple performance objectives, the need to optimize under complex (and often idiosyncratic) constraints and the need for flexible human decision-making involvement.

The ICLL Approach
Previous ICLL research has focused on the development of methods that overcome limitations of classical scheduling models and most current scheduling tools, which are conceived and designed as batch-oriented, black box solution generators. This has led to a framework for dynamic scheduling based on incremental, constraint-based search procedures and heuristics. These procedures permit flexible, controlled management of schedules in response to execution dynamics over time, under quite general assumptions regarding the representation and incorporation of various domain constraints. Our MKIDS research extended this approach to the management of knowledge-intensive dynamic systems. Specifically, we developed and experimentally validated techniques relating to:

  • Representation of task cost and task quality. We investigated various metrics for characterizing task cost and task quality. One meaningful surrogate for task cost is task duration; the longer the duration the higher the cost. With regard to task quality, a measure relating to percentage of success appears useful as one baseline surrogate; another might summarize some amount of product obtained in relation to some target quantity.
  • Scheduling (and rescheduling) to maximize task quality. We focused on incremental scheduling strategies and heuristics that aim at maximizing the quality of task outcomes. One aspect of this is the trade-off of process quality estimates against cost (i.e., time constraints) and the relative priorities of competing tasks. This might, for example, lead to adopting a faster but potentially lower quality alternative to meet an important deadline. Another aspect is associated with the skills (or expertise) of assigned resources (e.g., an experienced reporter will get better information than a novice). This aspect led to scheduling search procedures and heuristics for optimizing the ?fit? of available resource skills to pending tasks.

Platform
The above techniques were implemented in a system called INCA which is based on the COMIREM scheduling platform. Core resource management services provided by COMIREM leverage an underlying model of planning and scheduling as an incremental change process, thereby providing direct support for incremental, mixed-initiative solution development and management. INCA (like COMIREM) is based on a flexible-times scheduling paradigm that employs a simple temporal problem (STP) network; resources are assigned (and re-assigned) via a least-commitment, constraint-posting scheduling procedure.

Recent Publications

  • T. Zimmerman, A. Gallagher, and.S.F. Smith, Incremental Scheduling to Maximize Quality in a Dynamic Environment, Proceedings International Conference on Planning & Scheduling, June 2006.
  • S.F. Smith, and T. Zimmerman, ?Planning Tactics in Scheduling Problems?, Proceedings ICAPS-04 Workshop on Integrating Planning into Scheduling, Whistler CA, June 2004.
    http://pst.ip.rm.cnr.it/wipis-at-icaps-04/WIPIS-ICAPS04-Notes.pdf
  • S.F. Smith, and T. Zimmerman, Towards Integrated Planning and Scheduling: Resource Abstraction in the Planning Graph, Proceedings AAAI-05 Workshop on Integrating Planning into Scheduling, Pittsburgh, PA, July 2005.
  • X. Wang and S.F. Smith, ?Generating Schedules to Maximize Quality?, Technical Report CMU-RI-TR-04-25, CMU Robotics Institute, June 2004.
    http://www.ri.cmu.edu/pubs/pub_4663.html
  • N. Policella, S.F. Smith, A. Cesta and A. Oddi, ?Generating Robust Schedules through Temporal Flexibility?, Proc. 14th Int. Conf. on Automated Planning and Scheduling, Whistler CA, June 2004.
    http://www2.cs.cmu.edu/afs/cs/project/ozone/www/PCP/publications/ICAPS04Robust.html
  • N. Policella, A. Oddi, S.F. Smith and A. Cesta, ?Generating Robust Partial Order Schedules?, Proc. 10th Int. Conf. on Principles and Practice for Constraint Programming, Toronto CA, September 2004.
    http://www2.cs.cmu.edu/afs/cs/project/ozone/www/PCP/publications/RobustCP.pdf
Researchers