Search

Article dans revue scientifique avec comité de lecture.; International audience; 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.

Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let $\poly$ be a convex polygon with n vertices. We study the collision-free, optimal path-planning problem for B moving between two configurations inside $\poly$. (A configuration specifies both a location and a direction of travel.) We present an O(n2 log n) time algorithm for determining whether a collision-free path exists for B between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvature-constrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. For example, we prove that any such shortest path is comprised of at most eight segments, each of which is a circular arc of unit radius or a straight-line segment. Some of the properties are quite general and shed some light on curvature-constrained shortest paths amid obstacles.