Complete Path Planning That Simultaneously Optimizes Length and Clearance
Basak Sakcak, Steven M. LaValle
Abstract
This paper considers a fundamental, optimal path planning problem that requires simultaneously minimizing path length and maximizing obstacle clearance. We show that in even simple planar settings with point and disc obstacles, the set of alternative solutions such that no one is clearly better than another (the set of Pareto-optimal solutions) is uncountably infinite. In spite of this difficulty, we introduce a complete, efficient algorithm that computes the Pareto front and a data structure that finitely represents the complete set of all Pareto- optimal paths. Particular optimal paths can then be selected from the computed data structure during execution, based on any additional conditions or considerations.
BibTeX
@inproceedings{icra2021_completepathplan,
title = {Complete Path Planning That Simultaneously Optimizes Length and Clearance},
author = {Basak Sakcak and Steven M. LaValle},
booktitle = {ICRA 2021},
year = {2021}
}