Design-to-Criteria Scheduling

We have developed a new domain independent flexible computation approach to task scheduling called Design-to-Criteria. The four most distinguishing features of Design-to-Criteria are its first class treatment of uncertainty about actions (modeled as probability distributions), the ability to reason about the utility attribute trade-offs of different solutions based on different goal criteria, the ability use these utility attribute trade-offs to focus every step of the scheduling process, and the ability to do these activities from a satisficing perspective. Satisficing with respect to the scheduling process itself enables the scheduler to produce results when computational combinatorics prevent an optimal solution. Satisficing with respect to meeting the criteria enables the scheduler to produce a result that adheres to the spirit of the goal when the criteria cannot be satisfied perfectly due to environmental and resource constraints.

In plain-speak, Design-to-Criteria real-time scheduling is about coping with high-order complexity while custom tailoring a way to achieve a high-level task to fit a particular client's quality, cost, duration, and uncertainty criteria or needs. To ground further discussion consider the simple information gathering task structure shown below, along with four satisficing schedules produced by the scheduler. The task structure, written in the TAEMS language, models multiple different approaches for gathering information about WordPerfect via the WWW. Each different approach has different cost, quality, duration, and certainty trade-offs. The four schedules shown below are produced to meet four different sets of goal criteria. Schedule A is constructed for a client interested in a fast, free, solution with any non-zero quality. Schedule B suits a client who wants a timely and free solution, but wants less uncertainty about the expected quality of the results. Schedule C is constructed for a user interested in a good quality, free, solution that can be obtained while she goes for a cup of coffee. Schedule D is generated to meet the criteria of a fourth individual who is willing to pay and wait for a high-quality response.


Information Gathering TAEMS Task Structure


Four Satisficing Schedules

The Design-to-Criteria satisficing dualism translates into four different techniques that reduce the search space and make the scheduling problem tractable:

  • Criteria-Directed-Focusing - Client goal criteria is leveraged to focus all processing activities on producing solutions and partial solutions that are most likely to meet the goal criteria. This is achieved by creating and identifying partial solutions that seem likely to meet the criteria and concentrating further development on these classes of partial solutions, pruning or ignoring other partial solutions that are deemed least probable to lead to ``good'' solutions.
  • Approximation - Schedule approximations provide an inexpensive, but coarse, overview of the exponential ($\omega(2^m)$ and $o(m^m)$) schedule solution space. The approximation space is used in conjunction with criteria directed focusing to build schedules from approximations that are most likely to lead to good schedules.
  • Heuristic Decision Making - A set of heuristics is used to cope with the combinatorics of the traditional action sequencing problem. The heuristics take into consideration task interactions, resource limits, individual action deadlines, task deadlines, commitments made with other problem solving agents, and other constraints. The heuristic algorithm reduces the $O(n!)$ action ordering problem to low-order polynomial levels in the worst case.
  • Heuristic Error Correction - The use of approximation and heuristic decision making has a price -- it is possible for task interactions to be ``abstracted-out'' resulting in the creation of schedules that are missing important components. A set of critic heuristics examine schedules that do not meet expectations and suggest improvements that are then considered by the focusing mechanism.
The client goal criteria that focuses all processing criteria is generated by clients, agents or users, using a new specification metaphor called sliders. Using the sliders clients describe the relative importance of quality, cost, and duration with respect to four classes of concerns, where each class of concerns is arranged as a bank of quality, cost, and duration sliders. The banks are:

  • Raw-goodness - this bank relates the importance of raw quality to raw duration and raw cost. Setting the quality slider to 50% and duration and cost to 25% says that in this category, quality is twice as important as duration and cost and that solutions should be more quality-centric. (The mapping of sliders to utility is found in the papers below.)
  • Limits/Thresholds - this bank contains one slider for each dimension, quality, cost, and duration, and allows users to specify desired limits or thresholds for each dimension and then to relate the importance of each dimension relative to the others. For example, setting the quality slider to 50% and giving it a limit of 5, and setting the duration slider to 50% and giving it a threshold of 200, says that solutions whose quality is over 5 and whose durations is less than 200 are preferred (and that the two thresholds are equally important.)
  • Raw-uncertainty - like the raw-goodness bank, this bank relates the importance of reducing uncertainty in quality, cost, and duration.
  • Uncertainty Thresholds - like the limits/thresholds bank, this bank relates the importance of obtaining a particular level of certainty about particular dimensions.
  • Meta Bank - the meta bank contains one slider for each of the above slider banks and is used to relate the importance of each class above to each other. For example, setting the raw-goodness slider to 50% and the uncertainty thresholds slider to 50% says that raw goodness and the uncertainty thresholds are equally important.
Consider an example. Say the quality slider of the raw-goodness bank is set to 100% and the duration slider of the uncertainty-thresholds bank is set to 100% and given a value of 80%; and that the meta sliders for raw-goodness and uncertainty-thresholds are both set to 50%. This says that until duration certainty crosses the 80% mark, certainty about duration and raw-quality are equally important. After duration crosses the 80% mark, it is no longer used to differentiate one possible solution from another -- quality alone takes this role.

Design-to-Criteria is related to Design-to-Time, but differs in its ubiquitous use of the goal criteria to focus processing and its ubiquitous integration of uncertainty modeling.

Related project pages:

Related Publications

Sims, Mark; Mostafa, Hala; Horling, Bryan; Zhang, Haizheng; Lesser, Victor; Corkill, Dan. Lateral and Hierarchical Partial Centralization for Distributed Coordination and Scheduling of Complex Hierarchical Task Networks. AAAI 2006 Spring Symposium on Distributed Plan and Schedule Management. 2006.

Horling, Bryan; Lesser, Victor; Vincent, Regis and Wagner, Thomas. The Soft Real-Time Agent Control Architecture. Autonomous Agents and Multi-Agent Systems, Volume 12, Number 1, Springer Science+Business Media , pp. 35-92. 2006. An earlier version is available as UMass Computer Science Technical Report 2002-14.

Wagner, Tom; Horling, Bryan; Lesser, Victor; Phelps, John; and Guralnik, Valerie. The Struggle for Reuse: Pros and Cons of Generalization in Taems and its Impact on Technology Transition. Proceedings of the ISCA 12th International Conference on Intelligent and Adaptive Systems and Software Engineering (IASSE-2003). 2003.

Horling, Bryan; Lesser, Victor; Vincent, Regis and Wagner, Thomas. The Soft Real-Time Agent Control Architecture. Proceedings of the AAAI/KDD/UAI-2002 Joint Workshop on Real-Time Decision Support and Diagnosis Systems. 2002. Also available as UMass Computer Science Tech Report 02-14.

Horling, Bryan; Lesser, Victor; Vincent, Regis; and Wagner, Tom. The Soft Real-Time Agent Control Architecture. UMass Computer Science Technical Report 2002-14, Number 02-14, University of Massachusetts. 2002. See also this paper.

Vincent, Regis, Horling, Bryan, Lesser, Victor and Wagner, Thomas. Implementing Soft Real-Time Agent Control. Proceedings of the 5th International Conference on Autonomous Agents, ACM Press, pp. 355-362. 2001.

Wagner, Thomas, and Horling, Bryan. The Struggle for Reuse and Domain Independence: Research with TAEMS, DTC and JAF. Proceedings of the 2nd Workshop on Infrastructure for Agents, MAS, and Scalable MAS (Agents 2001), AAAI. 2001.

Wagner, Thomas; Benyo, Brett; Lesser, Victor; Xuan, Ping. Investigating Interactions Between Agent Conversations and Agent Control Components. Issues in Agent Communication, Lecture Notes in Artificial Intelligence, Frank Dignum and Mark Greaves, ed., Berlin: Springer-Verlag, pp. 314-331. 2000. Also available as UMASS Computer Science Technical Report #99-07.

Raja, Anita, Wagner, Thomas and Lesser, Victor. Reasoning about Uncertainty in Design-to-Criteria Scheduling. Proceedings of AAAI 2000 Spring Symposium on Real-Time Autonomous Systems, AAAI, pp. 76-83. 2000.

Wagner, Thomas and Lesser, Victor. Design-to-Criteria Scheduling: Real-Time Agent Control. Proceedings of AAAI 2000 Spring Symposium on Real-Time Autonomous Systems, A version also available as UMASS CS Tech Report 99-58, pp. 89-96. 2000.

Wagner, Thomas and Lesser, Victor. Toward Generalized Organizationally Contexted Agent Control. Proceedings of the AAAI-99 Workshop on Reasoning in Context, a version also available as UMASS CS Tech Report TR99-18, AAAI Press, pp. 101-105. 1999.

Wagner, Thomas; Shapiro, Jonathan; Xuan, Ping; Lesser, Victor. Multi-Level Conflict in Multi-Agent Systems. Proceedings of the AAAI-99 Workshop on Negotiation in MAS , AAAI Press, pp. 50-55. 1999. Also available as UMASS CS Tech Report 99-17

Wagner, Thomas A., Garvey, Alan J. and Lesser, Victor R.. Criteria Directed Task Scheduling. Journal for Approximate Reasoning (Special Issue on Scheduling), Volume 19, Elsevier Science Inc., pp. 91-118. 1998. A version is also available as UMass Computer Science Technical Report 1997-59.

Garvey, A., Lesser, V.. Design-to-time Scheduling and Anytime Algorithms. SIGART Bulletin, Volume 7, Number 3. 1996.