Generating Qualitatively Different Plans through Metatheoretic Biases

AAAI 1999

TL;DR

This paper introduces a novel method for automatically generating a diverse set of qualitatively different plans by leveraging a domain's "metatheory" to create targeted biases. This approach moves beyond simple randomization, ensuring that generated plan variations are semantically meaningful and useful for users exploring complex decision spaces.

What Problem Does This Paper Address?

Automated planning systems are powerful tools for assisting humans in complex decision-making, particularly in domains with vast solution spaces like air campaign or travel planning. While current planners can generate many plans, these often differ only superficially (e.g., slight variations in length) or require extensive user intervention to guide the search towards distinct outcomes. The core challenge is to automatically produce a small set of qualitatively different plans that offer users meaningful choices, helping them understand the spectrum of possibilities and make informed decisions. Simply randomizing choices doesn't guarantee meaningful differences, and relying on user-defined evaluation functions for hill-climbing is often impractical due to the difficulty of eliciting and formalizing subjective preferences.

Methods

The paper proposes a bias-driven planning approach that leverages a domain metatheory. This metatheory provides an abstract characterization of the planning domain, highlighting key semantic differences in operators, variables, and individuals.

  1. Metatheory Construction: The metatheory defines roles, features (distinguishing attributes of operators), and measures (rankings of features or instances based on criteria like "affordability" or "time-efficiency").
  2. Bias Generation: Biases are created by selecting specific measures from the metatheory and defining intervals within their domains. These biases are designed to steer the planner towards solutions with particular characteristics.
  3. Region Creation: The system partitions the domains of selected measures into intervals and groups these intervals into "regions." Each region represents a specific combination of biases, aiming to direct the planner to a distinct section of the plan space.
  4. Bias Enforcement: Biases are enforced heuristically by ordering planning decisions (operator selection and instance selection) based on scoring functions that reflect how well a choice satisfies the current region's biases. This is not a hard constraint but a preference, ensuring that plans are still possible but are guided towards desired attributes.

Datasets

The evaluation was performed in a simulated travel domain. This domain involved selecting itineraries, schedules, accommodations, modes of travel, and carriers for business and leisure trips. No specific public dataset was introduced; rather, a custom domain was constructed for experimental purposes.

Key Insights and Ideas

  • Metatheory as a Semantic Compass: The domain metatheory is crucial for abstracting away from low-level planning details and focusing on semantically meaningful differences that users care about.
  • Biases for Targeted Exploration: By translating metatheoretic concepts into biases, planners can be directed to explore specific "regions" of the solution space, guaranteeing qualitative differences by design.
  • Heuristic Enforcement is Sufficient: Imposing preferences rather than hard constraints on planning decisions is effective for guiding the search without overly restricting the possibility of finding solutions.
  • Dispersion and Proximity as Coverage Metrics: The paper formalizes "qualitative difference" using dispersion (how spread out plans are) and proximity (how close the set is to all possible solutions), providing a quantitative way to evaluate plan set quality.

Key Results

Experiments in the travel domain showed that the bias-driven approach significantly outperformed simple randomization in generating plan sets with:

  • Higher Dispersion: Plans were more spread out in the evaluation space, offering a wider range of options.
  • Lower Proximity: The generated plan sets were closer to covering the entire solution space.
  • Reduced Variance: The bias-driven methods produced much more consistent results (lower standard deviation) compared to randomization, meaning users were less likely to receive poor quality plans.

These improvements were most pronounced for smaller plan set sizes (n=2 to n=6).

Limitations and Future Work

  • Bias Region Creation Strategies: The paper notes that various strategies exist for partitioning and grouping measure intervals into regions. While the random assignment strategy used worked well, exploring other methods (e.g., dynamic feedback among regions) could lead to further improvements.
  • Leveraging Metatheory Further: Additional aspects of the domain metatheory, such as roles, could be incorporated into the biasing algorithm.
  • Explanatory Capabilities: The paper suggests that the metatheory could be used to generate concise summaries of plan differences, making it easier for users to understand why plans are different.
  • Measure-Measure and Measure-Evaluation Correlations: While the current method uses random selection to avoid issues with correlations, future work could explore more sophisticated biasing methods that leverage known correlations among measures or between measures and evaluation criteria.

Summary updated

BibTeX
@inproceedings{1999generating,
  title = {{Generating Qualitatively Different Plans through Metatheoretic Biases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure