An Axiomatic Approach to Robustness in Search Problems with Multiple Scenarios

Patrice Perny, Olivier SpanjaardUAI 2003

TL;DR

This paper introduces a formal framework for defining and finding "robust" solutions in search problems where costs vary across different scenarios. They propose the Lorenz dominance relation as a robust preference criterion and develop an A*-like algorithm to efficiently find these robust paths in state-space graphs.

What Problem Does This Paper Address?

Many real-world decision-making problems, such as path planning or resource allocation, involve uncertainty. The cost of actions or paths isn't fixed but can depend on various "scenarios" or states of the world. Traditional search algorithms, like A*, typically assume a single, fixed cost for each action. This assumption breaks down when costs are uncertain or scenario-dependent.

While existing work addresses multi-criteria decision-making and uncertainty separately, this paper focuses on a specific type of uncertainty: scenarios. The authors highlight that simple scalarization of costs (e.g., averaging) or even Pareto dominance can lead to unsatisfactory results when robustness is the primary concern. For instance, a path that is optimal in one scenario might be disastrous in another. The core problem is how to define and find solutions that are "good enough" across a range of possible futures, rather than just optimizing for a single, potentially unrealistic, scenario.

Methods

The paper proposes an axiomatic approach to define robustness. They introduce the Lorenz dominance relation as a key criterion for comparing cost vectors across scenarios. This relation is derived from axioms that capture both cost minimization and a notion of "fairness" or equity in cost distribution across scenarios, inspired by concepts like the Pigou-Dalton transfer.

To find robust solutions in state-space graphs, they adapt the well-known A search algorithm. Their modified algorithm, which they call a "sophistication of A", operates on labels (representing paths to nodes) rather than just nodes. Key algorithmic features include:

  • Heuristics: An admissible set of heuristic costs is used, similar to standard A*.
  • Priority Rule: Labels are prioritized based on a lexicographic ordering of their Lorenz vectors, aiming to explore potentially robust paths first.
  • Pruning Rules: Two crucial pruning rules are introduced:
  • Pruning subpaths whose evaluation is L-dominated by an already found robust solution.
  • Pruning subpaths that are P-dominated (Pareto-dominated) by another subpath at the same node.

These rules are designed to efficiently cut down the search space while ensuring that only L-non-dominated solutions are found.

Datasets

Not discussed in the paper. The paper uses a synthetic state-space graph example (Figure 1) to illustrate its concepts and algorithms.

Key Insights and Ideas

  • Robustness as a Formal Preference: The paper moves beyond intuitive notions of robustness to a mathematically grounded definition using axiomatic principles and the Lorenz dominance relation.
  • Lorenz Dominance as a Robustness Criterion: Lorenz dominance offers a principled way to compare solutions when costs vary across scenarios, balancing individual scenario costs with their distribution. It's more discerning than Pareto dominance and less pessimistic than minimax.
  • Axiomatic Foundation for Refinement: The paper provides an axiomatic justification for refining robustness criteria, showing how linear functions on Lorenz vectors (related to Ordered Weighted Averages) can capture preferences that are consistent with Lorenz dominance.
  • Algorithmic Adaptation of A*: The adaptation of A* to handle Lorenz dominance is a significant contribution, demonstrating how established search techniques can be extended to more complex preference structures. The label expansion strategy is key to managing the search space.
  • Computational Complexity: The paper highlights that finding L-non-dominated paths can be computationally intractable in the worst case, and deciding if a path L-dominates another is NP-complete, underscoring the need for efficient search algorithms.

Key Results

  • Formal Definition of Robustness: The paper establishes an axiomatic framework for robustness, leading to the Lorenz dominance relation.
  • Efficient Search Algorithm: An A*-like algorithm is presented that efficiently finds the set of L-non-dominated paths in state-space graphs.
  • Complexity Analysis: The paper proves that finding L-non-dominated paths is intractable in the worst case and that the decision problem is NP-complete.
  • Illustrative Example: The algorithm's behavior is demonstrated on a small example graph, showing how pruning rules effectively reduce the search space.

Limitations and Future Work

  • Parameter Elicitation: The paper acknowledges that determining the specific parameters for the linear function (related to Ordered Weighted Averages) that refines Lorenz dominance requires elicitation methods, which are not detailed.
  • Likelihood of Scenarios: The current framework assumes scenarios are equally likely. Future work could investigate how to incorporate known probabilities of scenarios, potentially using concepts like second-order stochastic dominance.
  • Extension to Other Domains: The authors suggest that the concept of robust solutions and L-dominance could be valuable in other AI domains like planning, constraint satisfaction, and game search, as well as in Operations Research.
  • Computational Intractability: While the algorithm is efficient for many cases, the worst-case intractability of finding L-non-dominated paths remains a challenge.

Summary updated

BibTeX
@inproceedings{perny2003axiomatic,
  author = {Patrice Perny and Olivier Spanjaard},
  title = {{An Axiomatic Approach to Robustness in Search Problems with Multiple Scenarios}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2003},
}
Figure