Complete Path Planning That Simultaneously Optimizes Length and Clearance

Basak Sakcak; Steven M. LaValle

doi:10.1109/ICRA48506.2021.9561784

Complete Path Planning That Simultaneously Optimizes Length and Clearance

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	2021 IEEE International Conference on Robotics and Automation, ICRA 2021
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2407-2413
Number of pages	7
ISBN (Electronic)	9781728190778
DOIs	https://doi.org/10.1109/ICRA48506.2021.9561784
State	Published - 2021
Externally published	Yes
Event	2021 IEEE International Conference on Robotics and Automation, ICRA 2021 - Xi'an, China Duration: May 30 2021 → Jun 5 2021

Publication series

Name	Proceedings - IEEE International Conference on Robotics and Automation
Volume	2021-May
ISSN (Print)	1050-4729

Conference

Conference	2021 IEEE International Conference on Robotics and Automation, ICRA 2021
Country/Territory	China
City	Xi'an
Period	5/30/21 → 6/5/21

ASJC Scopus subject areas

Software
Control and Systems Engineering
Artificial Intelligence
Electrical and Electronic Engineering

Online availability

10.1109/ICRA48506.2021.9561784

Library availability

Discover UIUC Full Text

Cite this

Sakcak, B., & LaValle, S. M. (2021). Complete Path Planning That Simultaneously Optimizes Length and Clearance. In 2021 IEEE International Conference on Robotics and Automation, ICRA 2021 (pp. 2407-2413). (Proceedings - IEEE International Conference on Robotics and Automation; Vol. 2021-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICRA48506.2021.9561784

Complete Path Planning That Simultaneously Optimizes Length and Clearance. / Sakcak, Basak; LaValle, Steven M.
2021 IEEE International Conference on Robotics and Automation, ICRA 2021. Institute of Electrical and Electronics Engineers Inc., 2021. p. 2407-2413 (Proceedings - IEEE International Conference on Robotics and Automation; Vol. 2021-May).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sakcak, B & LaValle, SM 2021, Complete Path Planning That Simultaneously Optimizes Length and Clearance. in 2021 IEEE International Conference on Robotics and Automation, ICRA 2021. Proceedings - IEEE International Conference on Robotics and Automation, vol. 2021-May, Institute of Electrical and Electronics Engineers Inc., pp. 2407-2413, 2021 IEEE International Conference on Robotics and Automation, ICRA 2021, Xi'an, China, 5/30/21. https://doi.org/10.1109/ICRA48506.2021.9561784

@inproceedings{e941a1e68ab7483c8a418cb772ba08e6,

title = "Complete Path Planning That Simultaneously Optimizes Length and Clearance",

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.",

author = "Basak Sakcak and LaValle, {Steven M.}",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE; 2021 IEEE International Conference on Robotics and Automation, ICRA 2021 ; Conference date: 30-05-2021 Through 05-06-2021",

year = "2021",

doi = "10.1109/ICRA48506.2021.9561784",

language = "English (US)",

series = "Proceedings - IEEE International Conference on Robotics and Automation",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2407--2413",

booktitle = "2021 IEEE International Conference on Robotics and Automation, ICRA 2021",

address = "United States",

}

TY - GEN

T1 - Complete Path Planning That Simultaneously Optimizes Length and Clearance

AU - Sakcak, Basak

AU - LaValle, Steven M.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85125485978&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85125485978&partnerID=8YFLogxK

U2 - 10.1109/ICRA48506.2021.9561784

DO - 10.1109/ICRA48506.2021.9561784

M3 - Conference contribution

AN - SCOPUS:85125485978

T3 - Proceedings - IEEE International Conference on Robotics and Automation

SP - 2407

EP - 2413

BT - 2021 IEEE International Conference on Robotics and Automation, ICRA 2021

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2021 IEEE International Conference on Robotics and Automation, ICRA 2021

Y2 - 30 May 2021 through 5 June 2021

ER -

Complete Path Planning That Simultaneously Optimizes Length and Clearance

Abstract

Publication series

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this