Specialized algorithms

Now upper bounds are summarized for some narrower problems, which can be solved more efficiently than the general problem. All of the problems involve either two or three degrees of freedom. Therefore, we expect that the bounds are much lower than those for the general problem. In many cases, the Davenport-Schinzel sequences of Section 6.5.2 arise. Most of the bounds presented here are based on algorithms that are not practical to implement; they mainly serve to indicate the best asymptotic performance that can be obtained for a problem. Most of the bounds mentioned here are included in [865].

Consider the problem from Section 6.2, in which the robot translates in ${\cal W}= {\mathbb{R}}^2$ and ${\cal C}_{obs}$ is polygonal. Suppose that ${\cal A}$ is a convex polygon that has $k$ edges and ${\cal O}$ is the union of $m$ disjoint, convex polygons with disjoint interiors, and their total number of edges is $n$. In this case, the boundary of ${\cal C}_{free}$ (computed by Minkowski difference; see Section 4.3.2) has at most $6m-12$ nonreflex vertices (interior angles less than $\pi$) and $n+km$ reflex vertices (interior angles greater than $\pi$). The free space, ${\cal C}_{free}$, can be decomposed and searched in time $O((n+km)\lg^2 n)$ [518,865]. Using randomized algorithms, the bound reduces to $O((n+km)\cdot 2^{\alpha(n)}\lg n)$ randomized expected time. Now suppose that ${\cal A}$ is a single nonconvex polygonal region described by $k$ edges and that ${\cal O}$ is a similar polygonal region described by $n$ edges. The Minkowski difference could yield as many as $\Omega(k^2 n^2)$ edges for ${\cal C}_{obs}$. This can be avoided if the search is performed within a single connected component of ${\cal C}_{free}$. Based on analysis that uses Davenport-Schinzel sequences, it can be shown that the worst connected component may have complexity $\Theta(k n \alpha(k))$, and the planning problem can be solved in time $O(k n \lg^2 n)$ deterministically or for a randomized algorithm, $O(kn \cdot 2^{\alpha(n)}\lg n)$ randomized expected time is needed. More generally, if ${\cal C}_{obs}$ consists of $n$ algebraic curves in ${\mathbb{R}}^2$, each with degree no more than $d$, then the motion planning problem for translation only can be solved deterministically in time $O(\lambda_{s+2}(n) \lg^2 n)$, or with a randomized algorithm in $O(\lambda_{s+2}(n) \lg n)$ randomized expected time. In these expressions, $\lambda_{s+2}(n)$ is the bound (6.37) obtained from the $(n,s+2)$ Davenport-Schinzel sequence, and $s \leq d^2$.

For the case of the line-segment robot of Section 6.3.4 in an obstacle region described with $n$ edges, an $O(n^5)$-time algorithm was given. This is not the best possible running time for solving the line-segment problem, but the method is easier to understand than others that are more efficient. In [748], a roadmap algorithm based on retraction is given that solves the problem in $O(n^2 \lg n \lg^*n)$ time, in which $\lg^*n$ is the number of times that $\lg$ has to be iterated on $n$ to yield a result less than or equal to $1$ (i.e., it is a very small, insignificant term; for practical purposes, you can imagine that the running time is $O(n^2 \lg n)$). The tightest known upper bound is $O(n^2 \lg n)$ [625]. It is established in [517] that there exist examples for which the solution path requires $\Omega(n^2)$ length to encode. For the case of a line segment moving in ${\mathbb{R}}^3$ among polyhedral obstacles with a total of $n$ vertices, a complete algorithm that runs in time $O(n^4 + \epsilon)$ for any $\epsilon > 0$ was given in [547]. In [517] it was established that solution paths of complexity $\Omega(n^4)$ exist.

Now consider the case for which ${\cal C}= SE(2)$, ${\cal A}$ is a convex polygon with $k$ edges, and ${\cal O}$ is a polygonal region described by $n$ edges. The boundary of ${\cal C}_{free}$ has no more than $O(kn\lambda_6(kn))$ edges and can be computed to solve the motion planning problem in time $O(kn\lambda_6(kn)\lg kn)$ [10,11]. An algorithm that runs in time $O(k^4n\lambda_3(n)\lg n)$ and provides better clearance between the robot and obstacles is given in [205]. In [55] (some details also appear in [588]), an algorithm is presented, and even implemented, that solves the more general case in which ${\cal A}$ is nonconvex in time $O(k^3n^3 \lg(kn))$. The number of faces of ${\cal C}_{obs}$ could be as high as $\Omega(k^3n^3)$ for this problem. By explicitly representing and searching only one connected component, the best-known upper bound for the problem is $O((kn)^{2 + \epsilon})$, in which $\epsilon > 0$ may be chosen arbitrarily small [428].

In the final case, suppose that ${\cal A}$ translates in ${\cal W}= {\mathbb{R}}^3$ to yield ${\cal C}= {\mathbb{R}}^3$. For a polyhedron or polyhedral region, let its complexity be the total number of faces, edges, and vertices. If ${\cal A}$ is a polyhedron with complexity $k$, and ${\cal O}$ is a polyhedral region with complexity $n$, then the boundary of ${\cal C}_{free}$ is a polyhedral surface of complexity $\Theta(k^3n^3)$. As for other problems, if the search is restricted to a single component, then the complexity is reduced. The motion planning problem in this case can be solved in time $O((kn)^{2 + \epsilon})$ [42]. If ${\cal A}$ is convex and there are $m$ convex obstacles, then the best-known bound is $O(kmn \lg^2m)$ time. More generally, if ${\cal C}_{obs}$ is bounded by $n$ algebraic patches of constant maximum degree, then a vertical decomposition method solves the motion planning problem within a single connected component of ${\cal C}_{free}$ in time $O(n^{2+\epsilon})$.