Bounded-Curvature Shortest Paths through a Sequence of Points

Abstract : We consider the problem of computing shortest paths having curvature at most one almost everywhere and visiting a sequence of $n$ points in the plane in a given order. This problem arises naturally in path planning for point car-like robots in the presence of polygonal obstacles, and is also a sub-problem of the Dubins Traveling Salesman Problem. This problem reduces to minimizing the function $F:\R^n\rightarrow\R$ that maps $(\theta_1,\ldots,\theta_n)$ to the length of a shortest curvature-constrained path that visits the points $p_1, \ldots, p_n$ in order and whose tangent in $p_i$ makes an angle $\theta_i$ with the $x$-axis. We show that when consecutive points are distance at least $4$ apart, all minima of $F$ are realized over at most $2^k$ disjoint convex polyhedra over which $F$ is strictly convex; each polyhedron is defined by $4n-1$ linear inequalities and $k$ denotes, informally, the number of $p_i$ such that the angle $\angle(p_{i-1},p_i,p_{i+1})$ is small. A curvature-constrained shortest path visiting a sequence points can therefore be approximated by standard convex optimization methods, which presents an interesting alternative to the known polynomial-time algorithms that can only compute a multiplicative constant factor approximation. Our technique also opens new perspectives for bounded-curvature path planning among polygonal obstacles. In particular, we show that, under certain conditions, if the sequence of points where a shortest path touches the obstacles is known then ``connecting the dots'' reduces to a family of convex optimization problems.
Document type :
Reports
[Research Report] RR-7465, INRIA. 2010, pp.53
Liste complète des métadonnées

https://hal.inria.fr/inria-00539957
Contributor : Xavier Goaoc <>
Submitted on : Monday, November 29, 2010 - 11:51:57 AM
Last modification on : Tuesday, October 25, 2016 - 5:01:53 PM
Document(s) archivé(s) le : Saturday, December 3, 2016 - 2:53:34 AM

File

RR-7465.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00539957, version 1

Collections

Citation

Xavier Goaoc, Hyo-Sil Kim, Sylvain Lazard. Bounded-Curvature Shortest Paths through a Sequence of Points. [Research Report] RR-7465, INRIA. 2010, pp.53. 〈inria-00539957〉

Share

Metrics

Record views

411

Document downloads

213