An algorithm for computing a convex and simple path of bounded curvature in a simple polygon

Jean-Daniel Boissonnat 1 Subir Kumar Ghosh 2 Telikepalli Kavitha 2 Sylvain Lazard 3
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
3 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we study the collision-free path planning problem for a point robot, whose path is of {\em bounded curvature} (i.e., constrained to have curvature at most 1), moving in the plane inside an $n$-sided simple polygon $P$. Given two points $s$ and $t$ inside $P$ and two directions of travel, one at $s$ and one at $t$, the problem is to compute a convex and simple path of bounded curvature inside $P$ from $s$ to $t$ consisting of straight-line segments and circular arcs such that (i) the radius of each circular arc is at least 1, (ii) each segment on the path is the tangent between the two consecutive circular arcs on the path, (iii) the given initial direction at $s$ is tangent to the path at $s$ and (iv) the given final direction at $t$ is tangent to the path at $t$. We propose an $O(n^4)$ time algorithm for this problem. Using the notion of complete visibility, $P$ is pruned to another polygon $P'$ such that any convex and simple path from $s$ to $t$ inside $P$ also remains inside $P'$. Then our algorithm constructs the locus of center of a circle of unit radius translating along the boundary of $P'$ and using this locus, the algorithm constructs a convex and simple path of bounded curvature. Our algorithm is based on the relationship between the Euclidean shortest path, link paths and paths of bounded curvature, and uses several properties derived here on convex and simple paths of bounded curvature. We also show that the path computed by our algorithm can be transformed in $O(n)$ time to a {\it minimal} convex and simple path of bounded curvature. Using this transformation and two necessary conditions proposed here for the shortest convex and simple path of bounded curvature, a {\it minimal} bounded curvature path is located in $O(n^4)$ time whose length, except in special situations involving arcs of length greater than $\pi$, is at most twice the length of a shortest convex and simple path of bounded curvature.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2002, 34 (2), pp.109-156. 〈10.1007/s00453-002-0950-0〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00100533
Contributeur : Sylvain Lazard <>
Soumis le : mardi 26 septembre 2006 - 14:46:31
Dernière modification le : samedi 27 janvier 2018 - 01:31:23

Lien texte intégral

Identifiants

Collections

Citation

Jean-Daniel Boissonnat, Subir Kumar Ghosh, Telikepalli Kavitha, Sylvain Lazard. An algorithm for computing a convex and simple path of bounded curvature in a simple polygon. Algorithmica, Springer Verlag, 2002, 34 (2), pp.109-156. 〈10.1007/s00453-002-0950-0〉. 〈inria-00100533〉

Partager

Métriques

Consultations de la notice

377