Sampling of Pareto-Optimal Trajectories Using Progressive Objective Evaluation in Multi-Objective Motion Planning
Jeongseok Lee, Daqing Yi, Siddhartha S. Srinivasa
Abstract
In this paper, we introduce a Markov chain Monte Carlo (MCMC)method to solve multi-objective motion-planning problems. We formulate the problem of finding Pareto-optimal trajectories as a problem of sampling trajectories from a Pareto-optimal set. We define an implicit uniform distribution over the Pareto-frontier using a dominance function and then sample in the space of trajectories. The nature of MCMC guarantees the convergence to the Pareto-frontier, while the uniform distribution ensures the diversity of the trajectories. We also propose progressive objective evaluation to increase efficiency in problems with expensive-to-evaluate objective functions. This enables determination of dominance relationship between trajectories before they are entirely evaluated. We finally analyze the effectiveness of the framework and its applications in robotics.
BibTeX
@inproceedings{iros2018_samplingofpareto,
title = {Sampling of Pareto-Optimal Trajectories Using Progressive Objective Evaluation in Multi-Objective Motion Planning},
author = {Jeongseok Lee and Daqing Yi and Siddhartha S. Srinivasa},
booktitle = {IROS 2018},
year = {2018}
}