Error-Bounded Approximation of Pareto Fronts in Robot Planning Problems

Conference paper (2023)

Authors

Alexander Botros University of Waterloo
Armin Sadeghi University of Waterloo
N. Wilde Learning & Autonomous Control - Mechanical, Maritime and Materials Engineering
J. Alonso-Mora Learning & Autonomous Control - Mechanical, Maritime and Materials Engineering
Stephen L. Smith University of Waterloo
Research Group
Learning & Autonomous Control (Mechanical, Maritime and Materials Engineering) (TU Delft)
Copyright: © 2023 Alexander Botros, Armin Sadeghi, N. Wilde, J. Alonso-Mora, Stephen L. Smith
DOI: https://doi.org/10.1007/978-3-031-21090-7_30
Planning Multi-objective optimization Human-robot interaction
More Info
expand_more

Published Date

2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Mechanical, Maritime and Materials Engineering

Department

Cognitive Robotics

Research Group

Learning & Autonomous Control

Abstract

Many problems in robotics seek to simultaneously optimize several competing objectives under constraints. A conventional approach to solving such multi-objective optimization problems is to create a single cost function comprised of the weighted sum of the individual objectives. Solutions to this scalarized optimization problem are Pareto optimal solutions to the original multi-objective problem. However, finding an accurate representation of a Pareto front remains an important challenge. Using uniformly spaced weight vectors is often inefficient and does not provide error bounds. Thus, we address the problem of computing a finite set of weight vectors such that for any other weight vector, there exists an element in the set whose error compared to optimal is minimized. To this end, we prove fundamental properties of the optimal cost as a function of the weight vector, including its continuity and concavity. Using these, we propose an algorithm that greedily adds the weight vector least-represented by the current set, and provide bounds on the error. Finally, we illustrate that the proposed approach significantly outperforms uniformly distributed weights for different robot planning problems with varying numbers of objective functions.