Complex Goal Criteria and Its Application in Design-to-Criteria Scheduling

AAAI 1997

TL;DR

This paper introduces "Design-to-Criteria" (DTC) scheduling, a novel AI approach that allows complex, multi-dimensional client goals to dynamically guide the scheduling process. By using an expressive "slider" metaphor for clients to define their priorities (quality, cost, duration, and their uncertainties), DTC focuses computational effort on generating truly satisficing schedules, rather than just optimal ones, especially in computationally intractable domains.

What Problem Does This Paper Address?

Real-time AI systems often face complex problems where simply optimizing for a single metric like "time" or "quality" isn't enough. Clients have nuanced, multi-faceted needs that can change dynamically. Traditional scheduling approaches struggle to incorporate these complex, multi-dimensional goals, especially when dealing with the combinatorial explosion of possible solutions. This paper addresses the challenge of building AI schedulers that can understand and dynamically adapt to diverse and complex client objectives, producing schedules that are "good enough" (satisficing) according to these criteria, even when perfect optimization is impossible.

Methods

The core of the paper is the Design-to-Criteria (DTC) scheduling framework. Key innovations include:

  • Client Criteria Specification Metaphor (Sliders): Clients define their goals using "importance sliders" that represent the relative weight of different attributes (quality, cost, duration) and their uncertainties. These sliders can also incorporate thresholds and limits. This metaphor is designed to be intuitive for users.
  • Principled Evaluation Model: A new, inexpensive evaluation mechanism is introduced. This model assesses potential schedules or partial solutions based on the client's criteria, focusing on "relativity" and "proportionality." This means the "goodness" of a solution is judged relative to other possibilities and weighted according to the client's specified importance.
  • Ubiquitous Satisficing: Satisficing is applied at multiple levels:
  • Process Satisficing: The scheduler prunes the search space of possible solutions early on, avoiding computationally expensive exploration of paths unlikely to meet the criteria.
  • Criteria Satisficing: The scheduler aims to produce solutions that best meet the spirit of the client's goals, even if perfect satisfaction is impossible due to environmental or resource constraints.
  • TÆMS Framework: The problem domain is modeled using the Task Analysis, Environment Modeling, and Simulation (TÆMS) framework, which describes task structures and primitive actions with statistical characteristics (quality, cost, duration).

Datasets

Not discussed in the paper. The paper uses a hypothetical "Information Gathering Task Structure" to illustrate its concepts, with generated schedules and alternatives shown in figures.

Key Insights and Ideas

  • Client-centric scheduling is crucial: The "goodness" of a schedule is entirely dependent on the client's specific, often complex, objectives.
  • Beyond optimality: Satisficing is key: In many real-world AI problems, finding a "good enough" solution that meets dynamic, multi-dimensional criteria is more practical and valuable than striving for a computationally infeasible optimal solution.
  • Expressive criteria specification matters: A user-friendly way for clients to articulate their needs (like the slider metaphor) is essential for effective AI scheduling.
  • Dynamic criteria drive focused computation: By continuously evaluating potential solutions against dynamic client criteria, the scheduler can intelligently prune the search space and focus its computational resources where they matter most.
  • Relativity and proportionality are foundational: The evaluation mechanism's reliance on these principles ensures that comparisons between solutions are fair and weighted appropriately according to client priorities.

Key Results

The paper demonstrates the effectiveness of its approach through an empirical example involving a complex task structure with a vast number of alternatives and schedules.

  • Client A (focused on raw quality): The selected schedule returned the highest expected quality, as predicted.
  • Client B (focused on quality and duration equally): The selected schedule achieved a good trade-off, returning lower quality but also lower duration than Client A's schedule, which aligns with their criteria.
  • The figures show how the alternatives and selected schedules differ significantly based on the clients' criteria, illustrating the system's ability to tailor solutions.

Limitations and Future Work

  • Limitations: The paper acknowledges that while the system aims for satisficing, there might be cases where no generated schedule satisfactorily meets the client's ideal needs, even if it's the best among the options. The current model doesn't explicitly handle hard constraints, suggesting negotiation as a solution.
  • Future Work: The authors highlight interactive negotiation as a critical next step. This would allow for dynamic refinement of criteria during the scheduling process, enabling the scheduler to adjust its intermediate processing and better align with the client's evolving expectations. This negotiation could occur during alternative generation or even as schedules are being produced.

Summary updated

BibTeX
@inproceedings{1997complex,
  title = {{Complex Goal Criteria and Its Application in Design-to-Criteria Scheduling}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1997},
}

Loading related content...

Figure