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.
The Challenge of Bi-Objective Search
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:
- 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.
- Bound Pruning: The algorithm immediately discards any partial path that exceeds either of the two user-defined bounds, drastically reducing the search space.
- 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.
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 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