Max Is More than Min: Solving Maximization Problems with Heuristic Search

Roni Stern, Scott Kiesel, Rami Puzis, Ariel Felner, Wheeler RumlIJCAI 2015

Introduction

In the field of heuristic search, the prevailing assumption has long been that finding the "best" path is synonymous with finding the "shortest" one. Decades of research have been dedicated to perfecting minimization (MIN) problems. However, research presented at IJCAI 2015 challenges this paradigm by exploring maximization (MAX) problems—scenarios where the objective is to find the path that yields the highest total reward.

The Challenge of Maximization

While finding the shortest path between two points is a well-understood polynomial-time problem, many real-world applications—such as multi-robot patrolling, VLSI design, and maximal coverage in sensor networks—require finding the longest simple path or the path with maximum reward. These MAX problems are typically NP-Hard.

The fundamental difficulty lies in the loss of "optimal substructure." In MIN problems, any segment of an optimal path is itself an optimal path between its endpoints. In MAX problems, this property fails. Consequently, the greedy logic underpinning algorithms like Dijkstra’s cannot be applied directly to maximization without significant modification.

Redefining Search for MAX Problems

The authors identify "search space monotonicity" as the critical differentiator. A search space is monotone if a path's value never improves upon its prefixes. While MIN problems are naturally monotone (costs accumulate), MAX problems are not, as partial paths have lower rewards than the full paths they lead to. This lack of monotonicity breaks standard stopping conditions.

Figure 1: Examples where standard minimization approaches fail in a maximization context. (a) Dijkstra's Algorithm (DA) fails to find the optimal path if it stops at the first goal encounter. (b) Bidirectional Search (BDS) fails because the optimal path is not a simple concatenation of optimal subpaths. (c) An illustration of the $h_{CC}$ heuristic.

To address this, the authors propose several algorithmic adaptations:

  • MAX-Dijkstra: To guarantee optimality, the algorithm must expand nodes with the highest $g$-value and continue searching until the OPEN list is entirely exhausted, rather than stopping at the first goal.
  • MAX-A*: This version expands states based on the highest $f(n) = g(n) + h(n)$. The search only halts when the highest $f$-value in OPEN is no longer greater than the best solution found so far.
  • Weighted A (WA) Symmetry: Interestingly, while setting the weight $w=0$ in MIN search yields Dijkstra, doing so in MAX search results in Depth-First Search (DFS).

Empirical Evaluation and Results

The researchers tested these algorithms on various Longest Simple Path Problem (LPP) instances, including uniform grids, "Life Grids" with varying terrain rewards, and massive US road networks.

Figure 6: CPU Time vs. Suboptimality for various search algorithms. Note that EES performs significantly worse in the MAX setting compared to traditional MIN benchmarks.

Key findings from the experiments include:

  • Optimality and Pruning: Depth-First Branch and Bound (DFBnB) and A* showed similar performance for optimal search. However, DFBnB often had a slight edge due to lower overhead from not managing an OPEN list. The use of admissible heuristics like "Connected Components" ($h_{CC}$) proved essential for making large-scale problems tractable.
  • Satisficing Search: For instances where a "good enough" solution is needed quickly, "Speedy Search"—which prioritizes nodes based on a distance-to-goal heuristic ($d$) rather than reward—outperformed reward-based heuristics. On road networks, Speedy Search achieved a 100% success rate within five minutes, whereas standard DFS and Greedy Best-First Search struggled.
  • The Failure of Focal Search: Advanced algorithms like Explicit Estimation Search (EES) performed poorly. The results suggest that focal search methods require distance-to-goal heuristics specifically tailored for maximization to be effective.

Conclusion and Future Directions

This research highlights that maximization is fundamentally different from minimization in heuristic search. While pruning with admissible heuristics allows for solving previously intractable problems, there is still much to explore. Future work could address duplicate detection in DFBnB for non-LPP domains and the development of better distance heuristics for focal search in MAX contexts. Furthermore, extending these findings to non-additive reward structures remains a significant open challenge.

Summary updated

BibTeX
@inproceedings{stern2015max,
  author = {Roni Stern and Scott Kiesel and Rami Puzis and Ariel Felner and Wheeler Ruml},
  title = {{Max Is More than Min: Solving Maximization Problems with Heuristic Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure