An algorithm for computing a convex and simple path of bounded curvature in a simple polygon
Résumé
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.