Search for Choquet-optimal paths under uncertainty

Lucie Galand, Patrice PernyUAI 2007

TL;DR

This paper introduces a novel approach to path planning under uncertainty by leveraging the Choquet Expected Utility (CEU) framework. They propose two heuristic search algorithms to efficiently find "robust" paths that perform well across a range of possible scenarios, addressing limitations of traditional expected utility models.

What Problem Does This Paper Address?

Path planning in AI often deals with imperfect knowledge of the environment. While standard approaches like Markov Decision Processes (MDPs) handle uncertainty in transitions and states, this paper focuses on a different kind of uncertainty: uncertainty in the costs of those transitions. Specifically, the costs might vary depending on different "scenarios" (e.g., traffic conditions in a city, market fluctuations). Traditional methods like expected utility assume known probabilities for these scenarios, which isn't always realistic. The paper addresses situations where these probabilities are unknown or where decision-makers exhibit "uncertainty aversion" – a preference for more predictable outcomes even if they might be slightly worse on average. This is exemplified by the Ellsberg's urn paradox, where standard expected utility models fail to capture natural preferences. The goal is to find "Choquet-optimal" paths, which are robust across these uncertain scenarios.

Methods

The core of the paper lies in applying the Choquet Expected Disutility (CED) criterion for path planning. CED uses a "capacity" function to represent beliefs about scenarios, which is more flexible than probability distributions as it doesn't require additivity. The paper proposes two algorithms to find CED-optimal paths:

  • Multiobjective Search (Algorithm 2): This approach adapts multiobjective search algorithms (like MOA*) to the CED problem. It treats each scenario as a separate objective and searches for non-dominated paths in the multi-dimensional cost space. Two pruning rules are introduced to focus the search on CED-optimal paths and improve efficiency.
  • Ranking Approach (Algorithm 3): This method uses a scalarization of the problem by employing a linear aggregation of costs based on a probability distribution derived from the capacity (e.g., Shapley values or maximum entropy probabilities). Paths are then ranked based on this scalarized cost, and the search stops once a path is found that is guaranteed to be CED-optimal.

Datasets

Not discussed in the paper. The experiments were conducted on synthetically generated graphs with varying sizes and arc densities, with scenario costs randomly drawn.

Key Insights and Ideas

  • CEU for Robust Path Planning: The paper demonstrates that the CEU framework, particularly CED, is a powerful tool for modeling robust path planning under scenario-based uncertainty, especially when decision-makers are uncertainty-averse.
  • Beyond Expected Utility: CEU offers a more descriptive model than standard expected utility when scenario probabilities are unknown or when preferences exhibit non-additive beliefs.
  • Violation of Bellman Principle: The CED criterion can lead to preference reversals, meaning a sub-optimal path in terms of CED might be part of a globally optimal path. This breaks the standard Bellman principle used in many shortest-path algorithms, necessitating new search strategies.
  • Heuristic Lower Bounds: Using probability distributions derived from the capacity (like Shapley values or maximum entropy) provides effective optimistic heuristics for guiding the search.

Key Results

The paper presents numerical experiments comparing the two proposed algorithms (Algorithm 2 and 3) on path-planning problems of varying sizes. The results show that both algorithms are practically efficient. While Algorithm 3 (ranking approach) was slightly faster in some cases, the difference was not significant. The experiments also suggest that using probabilities derived from maximal entropy or Shapley values provides a slightly better lower bound for the CED criterion compared to other probability distributions.

Limitations and Future Work

  • Complexity: The paper acknowledges that the general -OPT problem is NP-hard, meaning worst-case performance can be poor.
  • Dynamic Decision Making: The authors suggest exploring the use of the Choquet integral in dynamic decision-making problems (e.g., decision trees, Markov Decision Processes), noting that dynamic inconsistencies induced by the Choquet integral need to be addressed.
  • Multiobjective Planning: Extending the Choquet integral to multiobjective planning problems is another promising avenue, potentially allowing for the characterization of "fine compromise" solution paths.
  • Real-world Applications: While the paper demonstrates practical efficiency on synthetic data, further validation on real-world path-planning scenarios would be valuable.

Summary updated

BibTeX
@inproceedings{galand2007search,
  author = {Lucie Galand and Patrice Perny},
  title = {{Search for Choquet-optimal paths under uncertainty}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2007},
}
Figure