Bounded-Cost Bi-Objective Heuristic Search

Shawn Skyler, Dor Atzmon, Ariel Felner, Oren Salzman, Han Zhang, Sven Koenig, William Yeoh, Carlos Hernández Ulloa

In multi-objective pathfinding, finding the complete set of Pareto-optimal solutions is often computationally prohibitive. This paper introduces Bounded-Cost Bi-Objective Search (BC-BOS), a framework designed to find a single Pareto-optimal path that satisfies user-defined cost constraints for two objectives. By leveraging normalization and novel node ordering strategies, the proposed BCP-BOA* algorithm achieves significant speedups over traditional methods.

Standard pathfinding algorithms typically optimize for a single metric, such as distance. However, real-world navigation often involves trade-offs—for instance, choosing between the fastest route (time) and the cheapest route (tolls). This is the domain of Bi-Objective Search (BOS).

Traditionally, BOS algorithms aim to find the Pareto-Optimal Frontier (POF), which is the set of all paths where improving one objective necessarily degrades the other. While comprehensive, finding the full POF is often exponentially complex. In many practical scenarios, a user doesn't need every possible trade-off; they simply need one path that fits their specific budget, such as "under 40 minutes and less than $15."

Methodology: BCP-BOA*

The authors propose BCP-BOA, an evolution of the state-of-the-art Bi-Objective A algorithm. Its efficiency stems from three primary mechanisms:

  1. Normalization: Since objectives often use different scales (e.g., meters vs. seconds), costs are mapped into a uniform $[0, 1]$ range to allow for mathematical comparison.
  2. Bound Pruning: The algorithm immediately discards any partial path that exceeds either of the two user-defined bounds, drastically reducing the search space.
  3. Node Ordering Functions: The search's efficiency depends on the order in which nodes are expanded. The authors explored several strategies, including lexicographic (Lex1/Lex2), minimum, maximum, and average normalized costs.
Overview of normalization, the budget rectangle, and various node ordering functions used in BCP-BOA*.

Key Insights: The Budget Rectangle

A central concept in this framework is the "Budget Rectangle." By defining two bounds ($b_1, b_2$), the user creates a target region in the cost-space. A solution exists only if the POF intersects this rectangle.

The "Budget Rectangle" defined by normalized bounds in the cost space.

The researchers discovered that the choice of ordering function significantly impacts performance based on the shape of this rectangle. Their "Selective Lex" strategy—which dynamically chooses between Lex1 and Lex2 based on the relative tightness of the bounds—proved to be the most robust and consistent performer.

Experimental Results and Performance

Evaluations were conducted using the BAY road map benchmark (San Francisco Bay Area), with travel time and distance as the two objectives. The results were striking:

  • Massive Speedups: BCP-BOA is significantly faster than the original BOA because it stops as soon as a single valid path is found.
  • Efficiency Gains: In challenging test cases where bounds were far from the start, the best ordering function reduced node expansions by a factor of over 400 compared to a full POF search.
  • Selective Lex Dominance: Selective Lex was almost always the top performer across various scenarios, making it the recommended choice for practical applications.

Conclusion

BC-BOS offers a practical and highly efficient alternative to full Pareto-optimal search when specific constraints are known. By focusing on finding a single valid solution within a "budget rectangle," BCP-BOA* enables real-time multi-objective pathfinding that was previously computationally out of reach. Future work may extend these techniques to more than two objectives or explore relaxing the Pareto-optimality requirement to find "good enough" paths even faster.

Summary updated

Abstract

There are many settings that extend the basic shortest path search problem. In Bounded-Cost Search, we are given a constant bound and the task is to find a solution within the bound. In Bi-Objective Search, each edge is associated with two costs (objectives) and the task is to minimize both objectives. In this paper, we combine both these settings into a new setting of Bounded-Cost Bi-Objective Search. We are given two bounds, one for each objective and the task is to find a solution within these bounds. We provide a scheme for normalizing the two objectives. We then introduce several algorithms for this new setting and compare them experimentally.
BibTeX
@inproceedings{skyler2022bounded,
  author = {Shawn Skyler and Dor Atzmon and Ariel Felner and Oren Salzman and Han Zhang and Sven Koenig and William Yeoh and Carlos Hernández Ulloa},
  title = {{Bounded-Cost Bi-Objective Heuristic Search}},
  booktitle = {SOCS},
  year = {2022},
  doi = {10.1609/socs.v15i1.21774},
}
Figure