Narrow passages in free space pose great challenges to many sampling-based motion planners. In problems with high-dimensional configuration spaces (C-spaces), narrow passages in free space (C-free) can be hard to find and navigate and, sometimes, even counterintuitive. In this article, we present an algorithm to construct cones of available instantaneous velocities (“free velocity cones” or, briefly, “free cones”) on the boundary of C-free to facilitate finding and navigating narrow passages. This is accomplished by first developing free cones and associated measures of local C-space narrowness for a single rigid link. These results are then extended to kinematic chains (open and closed) of arbitrary degrees of freedom. It turns out that the degeneracy of the free cones dictates the existence of C-space narrow passages, and the locations and orientations of the links in the workspace relate intimately to the corresponding connected component of C-free. This observation leads us to a modified probabilistic roadmap (M-PRM) algorithm and a modified rapidly exploring random vine (M-RRV) algorithm of combining the enumeration of topological components and random sampling of the free cones. Experimental results from applying our algorithms to several challenging examples show that our new algorithms are more efficient than some variants of the PRM algorithms, and several variants of the rapidly exploring random tree (RRT) algorithms, such as RRT-CONNECT and RRV.

This article aims to extend the theory of Lie subgroups and symmetric subspaces for studying an important class of submanifolds of the special Euclidean group SE(3) whose tangent space at each point on the submanifold relates to that at the identity by an adjoint map. These submanifolds, which we call adjoint-invariant submanifolds in this article, are known in the literature as persistent submanifolds, since they are strictly related to the concept of persistent screw systems. The difference is that in this article, just as Lie subgroups and symmetric subspaces, we put forward adjoint-invariant submanifolds as independent geometric objects from mechanisms and their associated local screw systems. Adjoint invariance relaxes the strict left and right invariance of Lie subgroups and the reflective invariance of symmetric subspaces by allowing generic moving reference frame in the aforementioned adjoint map. It turns out such adjoint invariance can be studied under the framework of distributions on manifolds, which allows us to explore global geometric properties of adjoint-invariant submanifolds. We classify adjoint-invariant submanifolds into reflective-type and product-type submanifolds and derive the conditions for their adjoint invariance. We then propose geometric methods and algorithms for synthesizing the kinematic generators for reflective-type submanifolds, as demonstrated with a number of examples.

We study the motion problem for planar star-shaped manipulators. These manipulators are formed by joining k "legs" to a common point (like the thorax of an insect) and then fixing the "feet" to the ground. The result is a planar parallel manipulator with k - 1 independent closed loops. A topological analysis is used to understand the global structure of the configuration space so that planning problem can be solved exactly. The worst-case complexity of our algorithm is O(k3N3), where N is the maximum number of links in a leg. A simple example illustrating our method is given

In this paper we develop a systematic topological approach to motion planning for a planar 2-R manipulator with point obstacles. By considering components in the free space for the second joint as the first joint varies, we build a two-dimensional array representing the cells of the free space and an associated graph representing the boundaries of those cells. Using this graph, we derive a closed formula for the number of components of the free space. At the same time we solve the motion existence problem, namely, when are two arbitrary configurations in the same component? If so, we develop two explicit algorithms for constructing the path - a middle path method and a linear interpolation method. These algorithms give complete solutions to the path planning problem. Extensive examples are worked out which verify the correctness and efficiency of the resulting program. Then we briefly discuss how these methods generalize to a 3-R planar manipulator.