Warning:
This page is provided for historical and archival purposes only. While the seminar dates are correct, we offer no guarantee of informational accuracy or link validity. Contact information for the speakers, hosts and seminar committee are certainly out of date.

RI Seminar -- Katia Sycara

• WHEN: Friday, March 18, 1994; 3:30 pm - 5:00 pm Refreshments will be served starting at 3:15 pm
• WHERE: ADAMSON WING Auditorium in Baker Hall
• SPEAKER: Katia Sycara,

          The Robotics Institute
          Carnegie Mellon University
         

• TITLE: CABINS : A Framework of Knowledge Acquisition and Iterative Revision for Schedule Optimization and Reactive Repair

ABSTRACT

Practical scheduling problems generally require allocation of resources in the presence of a large, diverse and typically conflicting set of constraints and optimization criteria. The ill-structuredness of both the solution space and the desired objectives make scheduling problems difficult to formalize. This paper describes an incremental repair method for improving schedule quality in scheduling and reactive schedule management in response to unexpected execution events. The approach, implemented in the CABINS system, uses case-based learning to incrementally acquire the repair control model that biases the search procedure of a constraint-based scheduler. CABINS records situation-dependent tradeoffs about repair actions and schedule quality to guide schedule improvement. During iterative repair, cases are exploited for: (1) repair action selection, (2) evaluation of intermediate repair results and (3) recovery from revision failures. The method allows the system to dynamically switch between repair heuristic actions (tactics), each of which operates with respect to a particular local view of the problem and offers selective repair advantages. Application of a repair action tunes the search procedure to the characteristics of the local repair problem. This is achieved by dynamic modification of the bias of contention metrics. Because both scheduling and schedule repair are NP-hard, there is no a priori characterization of the amount of modification that may be required. However, initial experimental results show that the approach is able to (a) capture and effectively utilize user scheduling preferences that were not present in the scheduling model, (b) produce schedules with high quality, without unduly sacrificing efficiency in predictive schedule generation and reactive response to unpredictable execution events along a variety of criteria that have been recognized as important in real operating environments.

Host:           Yangsheng Xu (xu@cs.cmu.edu)
Appointment:    Lalit Katragadda (lalit@cs.cmu.edu)