A Polynomial-Time Algorithm for Computing a Shortest Path of Bounded Curvature Amidst Moderate Obstacles

Jean-Daniel Boissonnat 1 Sylvain Lazard
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane. More precisely, given prescribed initial and final configurations (i.e. positions and orientations) and a set of obstacles in the plane, we want to compute a shortest $C¨$ path joining those two configurations, avoiding the obstacles, and with the further constraint that, on each $C©$ piece, the radius of curvature is at least 1. In this paper, we consider the case of moderate obstacles (as introduced by Agarwal et al.) and present a polynomial-time exact algorithm to solve this problem.
Document type :
Reports
Complete list of metadatas

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/inria-00073803
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 1:47:01 PM
Last modification on : Saturday, January 27, 2018 - 1:31:28 AM
Long-term archiving on : Sunday, April 4, 2010 - 11:58:50 PM

Identifiers

  • HAL Id : inria-00073803, version 1

Collections

Citation

Jean-Daniel Boissonnat, Sylvain Lazard. A Polynomial-Time Algorithm for Computing a Shortest Path of Bounded Curvature Amidst Moderate Obstacles. RR-2887, INRIA. 1996. ⟨inria-00073803⟩

Share

Metrics

Record views

231

Files downloads

206