Introduction
In many real-world pathfinding scenarios, such as robot routing or logistics, we must balance multiple conflicting objectives—minimizing travel time, fuel cost, and risk simultaneously. The set of all optimal trade-offs is known as the Pareto frontier. However, computing the exact Pareto frontier is often computationally intractable, as its size can grow exponentially with the number of objectives and the search space.
This paper introduces Anytime Apex (A-Apex), the first anytime multi-objective search algorithm designed to handle an arbitrary number of objectives. A-A*pex provides high-quality approximate solutions quickly and improves them over time, making it ideal for time-sensitive applications where a "good enough" set of trade-offs is needed immediately.
Methodology
A-Apex builds upon the state-of-the-art approximate search algorithm Apex**. It operates by running multiple search iterations, each with a progressively smaller approximation factor ($\epsilon$). In early iterations, the algorithm is "loose," merging similar paths to find a rough frontier quickly. As time permits, it tightens the requirements to refine the solutions.
Search Strategies
The authors explored three strategies for managing search effort across iterations:
- Restart: The search starts from scratch whenever $\epsilon$ decreases.
- Reuse: The algorithm tracks paths pruned in previous iterations (because they were redundant for a coarse approximation) and "resurrects" them when a finer approximation is required.
- Hybrid: This variant combines both approaches, using restarts for early, coarse iterations and switching to reuse for final polishing phases. The hybrid strategy was found to be the most efficient, balancing overhead and search effort.
Experimental Evaluation
The researchers evaluated A-Apex against exact algorithms like BOA and LTMOA* using two primary benchmarks:
- Synthetic Grids: 48x48 grids with up to six objectives.
- NY Road Network: A real-world dataset of New York with approximately 264,000 states and 730,000 edges, tested with 2 to 5 objectives.
Key Results
A-Apex demonstrates significant improvements in "speed to quality" compared to traditional exact algorithms. While exact algorithms often focus on finding perfect solutions in one corner of the trade-off space first, A-Apex provides global coverage of the frontier from the start.
Performance on Real-World Data
In road network tests, A-Apex achieved an Area Under the Curve (AUC) for approximation error that was up to 100x smaller* than the baselines. It can find a "1% approximate frontier" (where every optimal solution is within 1% of a found solution) orders of magnitude faster than exact algorithms can find the true frontier.
Conclusion and Future Work
A-A*pex represents a major step forward in multi-objective search, offering a practical solution for high-dimensional trade-off problems. While it requires some parameter tuning (such as the decay factor for $\epsilon$) and carries a memory overhead for storing pruned paths, its ability to provide rapid, high-quality approximations makes it highly suitable for real-time systems. Future work may involve automated parameter tuning and applications to complex robotic configuration spaces.
Summary updated