Efficient Multi-Objective Planning with Weighted Maximization Using Large Neighbourhood Search
Krishna Kalavadia, Shamak Dutta, Yash Vardhan Pant, Stephen L. Smith
AI summary
Problem
Weighted-sum scalarization misses critical solutions in non-convex Pareto regions, while the alternative weighted-maximization approach is NP-hard and computationally prohibitive in discrete planning domains.
Approach
An adaptive Large Neighbourhood Search framework that iteratively destroys and repairs path segments by solving efficient weighted-sum subproblems, guided by heuristic selection and simulated annealing.
Key results
- Proves NP-hardness of optimal weighted-sum approximation for weighted-maximization
- Derives a worst-case n-factor approximation bound for weighted-sum methods
- Achieves 1–2 orders of magnitude runtime reduction over existing weighted-maximization planners
- Guarantees coverage of the entire Pareto front, including non-convex regions
Why it matters
Enables real-time, comprehensive multi-objective robot navigation by making Pareto-complete planning computationally viable for autonomous systems.
Abstract
Autonomous navigation often requires the simul- taneous optimization of multiple objectives. The most common approach scalarizes these into a single cost function using a weighted sum, but this method is unable to find all possible trade-offs and can therefore miss critical solutions. An alterna- tive, the weighted maximum of objectives, can find all Pareto- optimal solutions, including those in non-convex regions of the trade-off space that weighted sum methods cannot find. However, the increased computational complexity of finding weighted maximum solutions in the discrete domain has limited its practical use. To address this challenge, we propose a novel search algorithm based on the Large Neighbourhood Search framework that efficiently solves the weighted max- imum planning problem. Through extensive simulations, we demonstrate that our algorithm achieves comparable solution quality to existing weighted maximum planners with a runtime improvement of 1-2 orders of magnitude, making it a viable option for autonomous navigation.