Error-Bounded Approximation of Pareto Fronts in Robot Planning Problems

Alexander Botros, Armin Sadeghi, Nils Wilde*, Javier Alonso-Mora, Stephen L. Smith

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

11 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationAlgorithmic Foundations of Robotics XV
Subtitle of host publicationProceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics
EditorsSteven M. LaValle, Jason M. O’Kane, Michael Otte, Dorsa Sadigh, Pratap Tokekar
PublisherSpringer
Pages506-522
ISBN (Electronic)978-3-031-21090-7
ISBN (Print)978-3-031-21089-1
DOIs
Publication statusPublished - 2023
Event15th Workshop on the Algorithmic Foundations of Robotics, WAFR 2022 - College Park, United States
Duration: 22 Jun 202224 Jun 2022

Publication series

NameSpringer Proceedings in Advanced Robotics
Volume25 SPAR
ISSN (Print)2511-1256
ISSN (Electronic)2511-1264

Conference

Conference15th Workshop on the Algorithmic Foundations of Robotics, WAFR 2022
Country/TerritoryUnited States
CityCollege Park
Period22/06/2224/06/22

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

  • Human-robot interaction
  • Multi-objective optimization
  • Planning

Fingerprint

Dive into the research topics of 'Error-Bounded Approximation of Pareto Fronts in Robot Planning Problems'. Together they form a unique fingerprint.

Cite this