Publication - Modeling Uncertainty and its Implications to Design-to-Criteria Scheduling

Authors: Wagner, Thomas; Raja, Anita; and Lesser, Victor
Title: Modeling Uncertainty and its Implications to Design-to-Criteria Scheduling
Abstract: Open environments are characterized by their uncertainty and non-determinism. Agents need to adapt their task processing to available resources, deadlines, the goal criteria specified by the clients as well their current problem solving context in order to survive in these environments. If there were no resource constraints, then an optimal Markov Decision Process based policy would obviously be the best way to make scheduling decisions. However in real agent systems, these scheduling decisions have to be made in real-time making the off-line policy computationally infeasible in open environments. Design-to-Criteria scheduling is the soft real-time process of custom building a schedule to meet dynamic client goal criteria (including real-time deadlines), using a task model that describes alternate ways to achieve tasks and subtasks. Recent advances in Design-to-Criteria include the addition of uncertainty to the TÆMS computational task models analyzed by the scheduler and the incorporation of uncertainty in the scheduling process. Design-to-Criteria uses a heuristic approach for on-line scheduling of medium granularity tasks. It approximates the analysis used to generate an optimal policy by heuristically reasoning about the implications of uncertainty in task execution. Design-to-Criteria is related to Design-to-Time and flexible computation methodologies. The addition of uncertainty has also spawned a post-scheduling contingency analysis step that can be employed in deadline critical situations where the added computational cost is worth the expense. We describe the uncertainty representation and how it improves task models and the scheduling process, and provide empirical examples of uncertainty reduction in action. We also evaluate the performance of our heuristic-based approach using the performance of the policy generated by an optimal controller as the benchmark.
Keywords: Contingency, Scheduling
Publication: UMASS Technical Report TR 1998-51, Num: TR 1998-51
Publisher: University of Massachusetts
Date: December 1999
Sources: PDF: /Documents/wagner99modeling.pdf
Reference: Wagner, Thomas; Raja, Anita; and Lesser, Victor. Modeling Uncertainty and its Implications to Design-to-Criteria Scheduling. UMASS Technical Report TR 1998-51, Number TR 1998-51, University of Massachusetts. December 1999.
bibtex: 
@techreport{wagner-121,
  author    = "Thomas Wagner and Anita Raja and Victor Lesser",
  title     = "{Modeling Uncertainty and its Implications to
               Design-to-Criteria Scheduling}",
  number    = "TR 1998-51",
  institution = "University of Massachusetts",
  type      = "Computer Science Technical Report",
  month     = "December",
  year      = "1999",
  url       = "http://mas.cs.umass.edu/paper/121",
}