Efficient Multi-Objective Planning with Weighted Maximization Using Large Neighbourhood Search

Krishna Kalavadia; Shamak Dutta; Yash Vardhan Pant; Stephen L. Smith

cs.ROApr 6, 2026

Efficient Multi-Objective Planning with Weighted Maximization Using Large Neighbourhood Search

Authors: Krishna Kalavadia, Shamak Dutta, Yash Vardhan Pant, Stephen L. Smith

Organizations: Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Canada

Abstract

Autonomous navigation often requires the simultaneous 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 alternative, 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 maximum 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.

Figures & tables

Fig. 1 : Solving multi-objective path planning problems via scalarization. An external decision maker specifies objective preferences as weights $w_{1},w_{2}$ . The path planner solves the scalarized problem and returns a path for the robot to execute. The WS cannot return the solution matching the desired objective preferences because it lies in the non-convex region of the Pareto front.

Fig. 2 : An example of the changing geometry of the Pareto front depending on the subproblem considered. The global Pareto front corresponds to optimizing over $\mathcal{P}_{s,g}$ . The local Pareto front corresponds to the problem of optimizing over $\mathcal{P}_{v_{i},v_{j}}$ .

Panel of Figure 3 — Fig. 3 : Solution sets obtained when optimizing two objectives: path length and obstacle closeness. The upper row shows the solution sets found by the WS, the middle row shows the solutions found by the WM, and the bottom row shows the solutions found by the proposed WM-LNS solver. The left column shows the paths found, and the right column shows the corresponding objective values. Note that the WM-LNS plots include suboptimal solutions for illustration; however, Table I reports only Pareto-optimal solutions.

Instance	Method	Coverage $\uparrow$	# Solutions $\uparrow$
Two Obj.	WS	0.68	15
	WM	0.77	69
	WM-poly	0.76	58
	WM-beam (Ours)	0.77	65
	WM-LNS (Ours)	0.77	52
Three Obj.	WS	0.77	37

TABLE I : Solution diversity across two and three objectives.

Panel of Figure 5 — Fig. 4 : Performance of WM-LNS over two instances. Left plots show the computation time ratio over WS, and right plots show the percentage error from the optimal WM solution.

Panel of Figure 6 — Fig. 5 : Test maps used in our experiments. Left: Map 1 - Maze (Two Objectives). Right: Map 2 - Cluttered Boxes (Three Objectives). Red regions correspond to high-risk zones, and green regions correspond to low-risk zones. The paths illustrate solutions for balanced preferences, where weights are chosen such that the weighted objective values are approximately equal.

Panel of Figure 7 — Fig. 6 : Manipulator planning results. The left plot shows the computation time ratio over WS, and the right plot shows the percentage error from the optimal WM solution.

Fig. 7 : Sample results for multi-objective planning in a kitchen environment. The paths illustrate solutions for balanced preferences, where weights are chosen such that the weighted objective values are approximately equal. WM and WM-LNS paths are shown in green (identical), while the WS path is blue.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Hyperparameter	Setting
Max num. iterations	{75, 400}
Non-improving Limit	{25, 50}
Min. Removed Vertices	$0.05\times\text{Path length}$
Max. Removed Vertices	$0.95\times\text{Path length}$
Cooling Rate $c$	0.985
Start temp control $p\%$	50%

Appendix

TABLE II : WM–LNS Hyperparameters

Multi-Objective Motion Planning

Multi-objective motion planning balances competing goals such as safety, travel time, energy use, comfort, and information gathering when choosing motions.

See all 18 papers

Approximate Multi-Objective Search Under Rulebooks
Aug 5, 2026Omar Muhammetkulyyev, Oren Salzman, Tichakorn WongpiromsarnTree Search Multi-Objective Optimization
Iowa State University, Ames IA 50010, USA · Technion - Israel Institute of Technology, Haifa 3200003, Israel
Decomposability-Guided Cooperative Coevolution for Large-Scale Itinerary Planning
Jun 6, 2025Ziyu Zhang, Peilan Xu, Yuetong Sun +2Travel Planning Traveling Salesperson Problem
School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing 210044, China. · Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China. · School of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), Shenzhen 518055, Guangdong, China. +1
Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints
Mar 30, 2026Viraj Parimi, Brian C. WilliamsMulti-Agent Path Finding Multi-Robot Task Allocation
Massachusetts Institute of Technology

Aug 5, 2026J/K move · Enter open · S save

Approximate Multi-Objective Search Under Rulebooks

Omar Muhammetkulyyev, Oren Salzman, Tichakorn Wongpiromsarn

Iowa State University, Ames IA 50010, USA · Technion - Israel Institute of Technology, Haifa 3200003, Israel

Tree Search Multi-Objective Optimization

Open paper AskPDF arXiv

Robotic planning often involves multiple objectives with complex priority relationships, such as safety, efficiency, and regulatory compliance. Rulebooks formalize these relationships, allowing partial ordering of objectives that generalizes both Pareto and lexicographic dominance. Computing the full set of rulebook-optimal solutions, however, is computationally expensive. To address this challenge, we introduce the concept of epsilon-rule-dominance, a principled notion of approximate dominance under rulebooks, and propose RApex, a best-first search algorithm that efficiently computes a compact set of epsilon-approximate rulebook-optimal solutions. RApex leverages dimensionality reduction, a technique used to speed up existing multi-objective search algorithms, while respecting rule hierarchies by maintaining separate closed sets and performing dominance checks over truncated and residual rule sets. We provide a formal analysis of RA*pex, proving that every rulebook-optimal solution is epsilon-rule-dominated (a generalization of approximate dominance we introduce) by at least one solution in the returned set. Empirical results demonstrate that our approach achieves computation times over two orders of magnitude faster than existing methods.

Abstract

Multi-Objective Motion Planning

Explore similar work

Approximate Multi-Objective Search Under Rulebooks

Decomposability-Guided Cooperative Coevolution for Large-Scale Itinerary Planning

Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints