University of Waterloo
Multi-Objective Robot Planning Scalarized using Weighted Maximization
Abstract
dc:description.abstractAutonomous robots often operate under multiple, potentially competing, objectives. Solving a multi-objective optimization problem generally results in a set of Pareto-optimal solutions that describe the trade-offs among objectives. A common approach to multi-objective optimization is scalarization, in which the objectives are combined using a set of preference weights specified by a Decision Maker (DM). These weights represent the relative importance of each objective. The most widely used scalarization is to take a Weighted Sum (WS) of the objectives; however, this method cannot return solutions in non-convex regions of the Pareto front. An alternative is the Weighted Maximum (WM) scalarization, which can recover Pareto-optimal solutions in both convex and non-convex regions of the Pareto front. While the WM is well-established in the optimization literature, it has seen limited adoption in robotic planning. In this thesis, we study two problems related to the WM scalarization. First, we investigate how to efficiently solve discrete, graph-based WM planning problems, where the resulting formulation is NP-hard. We develop a Large Neighbourhood Search (LNS) algorithm that solves a WM problem by solving a sequence of subproblems using the WS. Second, we investigate how to construct a representative sample of the Pareto front. We analyze the geometric properties of the WM cost function and propose a method that greedily identifies preference weights that are underrepresented in the current sample set. In this thesis, we look to bridge the gap between the theoretical benefits of the WM scalarization and its application within robotics. Together, our proposed approaches pro- vide a set of practical tools for solving complex multi-objective planning problems.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Kalavadia, Krishna
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10012/24067