Path Planning under Time-Dependent Uncertainty

Michael P. Wellman, Matthew Ford, Kenneth LarsonUAI 1995 · OpenReview

TL;DR

This paper tackles the challenge of finding optimal paths in networks where travel times are uncertain and can change based on departure time. They introduce a "stochastic consistency" condition that allows for a generalized dynamic programming approach, leading to a new algorithm called PFS-Dominance that efficiently finds optimal paths by pruning dominated alternatives.

What Problem Does This Paper Address?

Traditional shortest path algorithms, like Dijkstra's, rely on two key assumptions: path costs are additive (the total cost is the sum of individual edge costs), and edge costs are deterministic (known with certainty). These assumptions break down in real-world scenarios like transportation networks where travel times vary with the time of day (e.g., rush hour traffic, bus schedules) and are inherently uncertain. When these assumptions are violated, standard algorithms can produce suboptimal or incorrect paths. The paper specifically addresses the problem of time-dependent, uncertain edge costs, where the cost of traversing an edge depends on when you start, and the actual cost is a random variable. This time-dependency can break the "optimality principle" that underpins standard dynamic programming, meaning the best path to a destination might not be composed of the best paths to intermediate nodes.

Methods

The core of the paper's contribution lies in defining a new condition called stochastic consistency. This condition, expressed as Pr(s + cij(s) ≤ z) ≥ Pr(t + cij(t) ≤ z) for s < t, essentially states that leaving later on an edge cannot increase the probability of arriving by any given time z. This is a weaker condition than deterministic consistency and is crucial because it allows for a generalized dynamic programming approach.

Based on this, they propose PFS-Dominance, a modified version of priority-first search (PFS). Instead of storing only the single "best" path to each node, PFS-Dominance maintains a set of undominated paths. A path is considered dominated if another path to the same node offers a better outcome across all possible scenarios (according to stochastic dominance). By pruning these dominated paths, the algorithm significantly reduces the search space while still guaranteeing optimality under the stochastic consistency condition. The algorithm uses a priority queue and a closed list to manage these undominated paths.

Datasets

The paper introduces a stochastic bus network model for empirical evaluation. This model simulates a transportation network where edges represent bus routes, and travel times for each bus follow an exponential distribution. The parameters of these distributions (minimum arrival time, average delay) are used to define the stochastic nature of the travel times. They generated a series of these bus networks in an n x n grid format for testing.

Key Insights and Ideas

  • Stochastic Consistency is Key: The paper identifies a surprisingly weak condition (stochastic consistency) that is sufficient to salvage dynamic programming for time-dependent, uncertain path planning. This is a significant theoretical contribution.
  • Stochastic Dominance as a Pruning Tool: The paper demonstrates that stochastic dominance is not just a way to compare outcomes but a powerful pruning criterion for search algorithms in this context. It allows for significant computational savings without sacrificing optimality.
  • Time-Dependent Uncertainty is Pervasive: The bus network example vividly illustrates how seemingly small variations in schedules and travel times can fundamentally alter optimal path choices, highlighting the practical importance of their work.
  • Adaptive Planning Outperforms Open-Loop: The introduction of an "Adaptive-Path" algorithm shows that for complex, uncertain environments, a closed-loop policy (making decisions as you go) generally outperforms a pre-computed open-loop path.

Key Results

  • The PFS-Dominance algorithm is proven to produce optimal paths under the stochastic consistency condition.
  • Empirical results on the stochastic bus network model show that PFS-Dominance explores significantly fewer paths than a non-pruning search, allowing it to solve problems of much larger sizes (up to n=17 for grid size).
  • A comparison with a standard shortest-path algorithm (using expected values) and the proposed PFS-Dominance algorithm, as well as an adaptive planning algorithm, on a 10x10 bus network with deadline utilities, showed that:
  • Adaptive planning performed best.
  • PFS-Dominance performed better than the expected-value shortest-path algorithm.
  • The expected-value algorithm, while computationally efficient, produced suboptimal results.

Limitations and Future Work

  • Computational Complexity: While PFS-Dominance is more efficient than exhaustive search, maintaining sets of undominated paths can still lead to significant complexity, especially if the network is not "stochastically consistent" or if many paths are not dominated.
  • Generalization of Pruning: The authors suggest that more aggressive pruning criteria might be possible, but stochastic dominance is identified as the "right" criterion for stochastically consistent networks. Exploring other pruning methods that might offer a trade-off between optimality and efficiency is a future direction.
  • Space-Limited Versions: Developing space-limited versions of the algorithm using recent AI techniques is mentioned as a future refinement.
  • Reformulating Problems: The paper speculates on the possibility of reformulating problems with uncertain state transitions into path planning problems with uncertain edge costs, which could leverage their methods.
  • Heuristic Search: Extending the concepts to heuristic search frameworks (like A*) by incorporating heuristic estimates of remaining distance is an active area of research for the authors.

Summary updated

Abstract

Standard algorithms for finding the shortest path in a graph require that the cost of a path be additive in edge costs, and typically assume that costs are deterministic. We consider the problem of uncertain edge costs, with potential probabilistic dependencies among the costs. Although these dependencies violate the standard dynamic-programming decomposition, we identify a weaker stochastic consistency condition that justifies a generalized dynamic-programming approach based on stochastic dominance. We present a revised path-planning algorithm and prove that it produces optimal paths under time-dependent uncertain costs. We test the algorithm by applying it to a model of stochastic bus networks, and present empirical performance results comparing it to some alternatives. Finally, we consider extensions of these concepts to a more general class of problems of heuristic search under uncertainty.
BibTeX
@inproceedings{wellman1995path,
  author = {Michael P. Wellman and Matthew Ford and Kenneth Larson},
  title = {{Path Planning under Time-Dependent Uncertainty}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1995},
  url = {https://openreview.net/forum?id=_FOPGxWg_n},
}
Figure