Efficient Constraint Generation for Stochastic Shortest Path Problems

Johannes Schmalz, Felipe W. TrevizanAAAI 2024 · DOI

TL;DR

This paper introduces CG-iLAO, a novel algorithm for solving Stochastic Shortest Path Problems (SSPs) that significantly improves efficiency by intelligently ignoring "inactive" actions. By connecting planning to linear programming techniques, CG-iLAO avoids computing costs for actions that won't contribute to the optimal solution, leading to substantial speedups over existing state-of-the-art methods.

What Problem Does This Paper Address?

Solving Stochastic Shortest Path Problems (SSPs) involves finding an optimal policy (a sequence of actions) that minimizes expected costs in an environment with probabilistic outcomes. Existing algorithms like LRTDP and iLAO build upon Bellman backups, a core dynamic programming technique. However, a fundamental limitation is that these algorithms must compute the expected cost-to-go for every* applicable action in a state, even if many of those actions are clearly suboptimal. This leads to wasted computation, especially in complex problems where the same suboptimal actions are evaluated repeatedly. While techniques like action elimination exist to prune useless actions, they often rely on domain-independent upper bounds, which are hard to compute efficiently, limiting their practical use in general planning. This paper addresses the need for a method that can efficiently prune suboptimal actions without requiring complex upper bounds.

Methods

The core contribution is a new algorithm, CG-iLAO, which extends the iLAO algorithm by incorporating an efficient "separation oracle" for constraint generation. The authors frame SSP solving as a linear programming (LP) problem. They then leverage the concepts of variable and constraint generation from operations research to optimize this LP.

Here's a breakdown of the key ideas:

  • Constraint Generation Analogy: The paper draws a parallel between heuristic search algorithms for SSPs and techniques used to solve large LPs. Variable generation involves adding new decision variables to an LP, while constraint generation involves adding new constraints.
  • Partial SSPs as Relaxed LPs: Algorithms like iLAO* incrementally build a "partial SSP," which the authors interpret as solving a relaxed version of the full LP.
  • Efficient Separation Oracle: The novelty lies in CG-iLAO's separation oracle. Instead of blindly adding all applicable actions (as in iLAO), CG-iLAO* intelligently identifies and adds only those actions (constraints) that are "violated" – meaning they could potentially improve the current solution. This is achieved by tracking changes in the value function and identifying potential constraint violations.
  • Ignoring Inactive Actions: An "inactive action" is defined as one whose expected cost-to-go is higher than the current estimated value of the state. CG-iLAO* effectively ignores these actions, meaning their costs-to-go are not computed during Bellman backups. This is the primary source of computational savings.
  • CG-iLAO* Algorithm: The algorithm iteratively expands a partial SSP, performs backups, and then uses its separation oracle (through CG-BACKUPS and FIX-CONSTRS functions) to identify and fix violated constraints by adding necessary actions. This process continues until the solution is sufficiently accurate (e-consistent).

Datasets

The paper evaluates CG-iLAO* on several standard benchmark domains for planning under uncertainty:

  • Triangle Tire World (TW): Extended with a "head-start" feature to create more varied problem instances.
  • Probabilistic Blocks World (BW): A probabilistic version of the classic Blocks World.
  • Exploding Blocks World (ExBW): A variation where actions can cause explosions, potentially making goals unreachable.
  • Probabilistic PARC Printer (PARC): A domain modeling a modular printer with probabilistic jamming. Both repairable (PARC-R) and non-repairable (PARC-N) versions are used.

No new benchmarks were introduced; instead, existing ones were used to compare against state-of-the-art methods.

Key Insights and Ideas

  • SSP Solving as LP Optimization: The paper provides a powerful new perspective by framing SSP solving as an LP problem solvable with variable and constraint generation. This connection unlocks new algorithmic possibilities.
  • The Power of Ignoring: The core insight is that explicitly identifying and ignoring "inactive" actions, rather than just pruning states, leads to significant computational gains. This is achieved by a more intelligent separation oracle.
  • Heuristic Quality Matters: The performance benefits of CG-iLAO over iLAO are amplified when using more informative heuristics. This suggests that better heuristics allow CG-iLAO* to more effectively identify and ignore inactive actions.
  • Value Function Can Decrease: Unlike most traditional Bellman backup algorithms (which guarantee non-decreasing value functions with monotonic heuristics), CG-iLAO* can exhibit a decreasing value function. This is a consequence of its more aggressive pruning and constraint fixing mechanism, but the authors prove it still leads to an optimal and e-consistent solution.

Key Results

  • Significant Speedups: CG-iLAO consistently outperforms iLAO and LRTDP in terms of speed. For example, it solves problems up to 8x faster than LRTDP and 3x faster than iLAO* on average.
  • Improved Coverage: CG-iLAO* achieves higher coverage (solves more instances within the time limit) across various domains and heuristics, particularly when using the hroc heuristic.
  • Reduced Action Consideration: CG-iLAO considers significantly fewer actions than iLAO. For instance, it only considers 43-65% of iLAO*'s actions in its partial SSP.
  • Q-Value Savings Outweigh Overhead: While CG-iLAO* incurs some overhead for its separation oracle, the savings from ignoring inactive actions are substantial, leading to fewer Q-value computations overall for a given level of performance.

Limitations and Future Work

  • Heuristic Dependence: While CG-iLAO* benefits greatly from good heuristics, its performance gains might be less pronounced with very weak heuristics.
  • Future Work: The authors suggest extending CG-iLAO* to more complex models, such as those with imprecise parameters (e.g., MDPs with minimax semantics) or Probabilistic Linear Temporal Logic (PLTL) constraints. They also believe the approach could be applicable to model checking and probabilistic reachability problems.

Summary updated

BibTeX
@inproceedings{schmalz2024efficient,
  author = {Johannes Schmalz and Felipe W. Trevizan},
  title = {{Efficient Constraint Generation for Stochastic Shortest Path Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.30005},
}
Figure