Preference Propogation in Temporal/Capacity Constraint Graphs

Norman Sadeh-Koniecpol and Mark S. Fox
tech. report CMU-RI-TR-89-02, Robotics Institute, Carnegie Mellon University, January, 1989

  • Adobe portable document format (pdf) (3MB)
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.

Scheduling can be formalized as a constraint satisfaction problem (CSP). Within this framework activities in a plan are interconnected via temporal relation constraints a la Allen, thereby defining a temporal constraint graph (TCG). Additionally there are capacity constraints restricting the use of each resource to only one activity at a time. Together these constraints form a temporallcapacity constraint graph (T/CCG) . Preferences such as meeting due dates, reducing order flowtime, or selecting accurate machines are modeled as utility functions over the domain of possible start times and durations of activities and over the sets of possible resources activities can use. These preferences interact via the TCG and via the resource capacity constraints. Hence, in general, they cannot be simultaneously optimized. The objective of preference propagation techniques is to transform such local a priori preferences so as to account for their interactions.

In this paper we describe a probabilistic framework in which start time, duration and resource preferences are propagated across T/CCGs in order to focus attention in an incremental scheduler. The propagation is first performed across the TCG, thereby producing activity (a posteriori) start time and duration distributions. These distributions allow for early detection of unsolvable CSPs, and provide measures of value goodness and variable looseness for activity start times and durations. In a second phase, these distributions are combined to predict the degree of contention for each resource and the reliance of each activity on the possession of that resource.

Grant ID: #F33615-86-C-5-38
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems

Text Reference
Norman Sadeh-Koniecpol and Mark S. Fox, "Preference Propogation in Temporal/Capacity Constraint Graphs," tech. report CMU-RI-TR-89-02, Robotics Institute, Carnegie Mellon University, January, 1989

BibTeX Reference
   author = "Norman Sadeh-Koniecpol and Mark S Fox",
   title = "Preference Propogation in Temporal/Capacity Constraint Graphs",
   booktitle = "",
   institution = "Robotics Institute",
   month = "January",
   year = "1989",
   number= "CMU-RI-TR-89-02",
   address= "Pittsburgh, PA",