CABINS: A Framework of Knowledge Acquisition and Iterative Revision for Schedule Improvement and Reactive Repair

Kazuo Miyashita and Katia Sycara
tech. report CMU-RI-TR-94-34, Robotics Institute, Carnegie Mellon University, October, 1994


Download
  • Adobe portable document format (pdf) (2MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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 a case-based learning method for acquiring context-dependent user optimization preferences and tradeoffs and using them to incrementally improve schedule quality in predictive scheduling and reactive schedule management in response to unexpected execution events. The approach, implemented in the CABINS system, uses acquired user preferences to dynamically modify search control 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, 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 search control bias. There is no a priori characterization of the amount of modification that may be required by repair actions. 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.

Notes
Sponsor: DARPA
Grant ID: F30602-91-C-0016
Number of pages: 43

Text Reference
Kazuo Miyashita and Katia Sycara, "CABINS: A Framework of Knowledge Acquisition and Iterative Revision for Schedule Improvement and Reactive Repair," tech. report CMU-RI-TR-94-34, Robotics Institute, Carnegie Mellon University, October, 1994

BibTeX Reference
@techreport{Sycara_1994_353,
   author = "Kazuo Miyashita and Katia Sycara",
   title = "CABINS: A Framework of Knowledge Acquisition and Iterative Revision for Schedule Improvement and Reactive Repair",
   booktitle = "",
   institution = "Robotics Institute",
   month = "October",
   year = "1994",
   number= "CMU-RI-TR-94-34",
   address= "Pittsburgh, PA",
}