University of Oulu

B. Sakcak and S. M. LaValle, "Complete Path Planning That Simultaneously Optimizes Length and Clearance," 2021 IEEE International Conference on Robotics and Automation (ICRA), 2021, pp. 10100-10106, doi: 10.1109/ICRA48506.2021.9561784

Complete path planning that simultaneously optimizes length and clearance

Saved in:
Author: Sakcak, Basak1; LaValle, Steven M.1
Organizations: 1Center of Ubiquitous Computing, Faculty of Information Technology and Electrical Engineering, University of Oulu, Finland
Format: article
Version: accepted version
Access: open
Online Access: PDF Full Text (PDF, 0.3 MB)
Persistent link:
Language: English
Published: Institute of Electrical and Electronics Engineers, 2021
Publish Date: 2021-11-11


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.

see all

Series: IEEE International Conference on Robotics and Automation
ISSN: 2152-4092
ISSN-E: 2379-9552
ISSN-L: 2152-4092
ISBN: 978-1-7281-9077-8
ISBN Print: 978-1-7281-9078-5
Pages: 10100 - 10106
DOI: 10.1109/ICRA48506.2021.9561784
Host publication: 2021 IEEE International Conference on Robotics and Automation (ICRA)
Conference: IEEE International Conference on Robotics and Automation
Type of Publication: A4 Article in conference proceedings
Field of Science: 113 Computer and information sciences
213 Electronic, automation and communications engineering, electronics
Funding: This work was supported by Academy of Finland project PERCEPT, 322637.
Academy of Finland Grant Number: 322637
Detailed Information: 322637 (Academy of Finland Funding decision)
Copyright information: © 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.