HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Path Planning with Objectives Minimum Length and Maximum Clearance

Abstract : In this paper, we study the problem of bi-objective path planning with the objectives minimizing the length and maximizing the clearance of the path, that is, maximizing the minimum distance between the path and the obstacles. The goal is to find Pareto optimal paths. We consider the case that the first objective is measured using the Manhattan metric and the second one using the Euclidean metric, and propose an $$O(n^3 \log n)$$ time algorithm, where n is the total number of vertices of the obstacles. Also, we state that the algorithm results in a ($$\sqrt{2}, 1$$)-approximation solution when both the objectives are measured using the Euclidean metric.
Document type :
Conference papers
Complete list of metadata

Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, March 10, 2021 - 4:05:14 PM
Last modification on : Wednesday, March 10, 2021 - 4:10:30 PM
Long-term archiving on: : Friday, June 11, 2021 - 7:06:48 PM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2023-01-01

Please log in to resquest access to the document


Distributed under a Creative Commons Attribution 4.0 International License



Mansoor Davoodi, Arman Rouhani, Maryam Sanisales. Path Planning with Objectives Minimum Length and Maximum Clearance. 3rd International Conference on Topics in Theoretical Computer Science (TTCS), Jul 2020, Tehran, Iran. pp.101-115, ⟨10.1007/978-3-030-57852-7_8⟩. ⟨hal-03165382⟩



Record views