This paper presents a method of computing free motions of a planar assembly of rigid bodies connected by loose joints. Joints are modeled using local distance constraints, which are then linearized with respect to configuration space velocities, yielding a linear programming formulation that allows analysis of systems with thousands of rigid bodies. Potential applications include analysis of collections of modular robots, structural stability perturbation analysis, tolerance analysis for mechanical systems, and formation control of mobile robots.

Discrete graphs are commonly used to approximately represent configuration spaces used in robot motion planning. This paper explores a representation in which the costs of crossing local regions of the configuration space are represented using piecewise linear regression (PLR). We explore a few simple motion planning problems, and show that for these problems, the memory required to store the representation compares favorably to that required for standard discrete vertex-and-edge models, while preserving the quality of paths returned from searches.

We present a new way of constructing sparse roadmaps using point clouds that approximates and measures the underlying topology of the Cfreespace. The main advantage of the constructed roadmap is its homotopy equivalence to the η-offset of the Cfreespace. Though only used to plan paths as a regular roadmap in this work, because the roadmap preserves the topology of the underlying sampled space, the information can be used to plan paths beyond the simple connection of graph vertices. To construct the roadmap, we first sample the configuration space so that the resulting graph is a n-skeleton graph that constructs a Vietoris-Rips (VR) complex. Then, we perform a series of topological collapses to remove vertices from the graph while still preserving its topological properties. The resulting roadmaps are used to plan paths for different robots and the experimental results show that the proposed topological approach is faster and more feasible in complex high-dimensional spaces.

This paper investigates the connection between the kinematics of robots arms and the shortest paths for mobile robots. Lagrange multipliers are used to show that the shortest paths are equivalent to arms in configurations that balance an external force, while applying equal torques and forces at each joint. Analysis of the arm Jacobian yields a further geometric interpretations of optimal paths, constraining the locations of rotation centers and the directions of translations that may occur along optimal paths.

Simply pulling on the ends of string is sufficient to tighten simple knots such as the overhand knot, but many knots used for decoration or binding need to be tightened at particular locations along the string. For example, a shoelace knot should have equally-sized bows, as should a decorative cloverleaf knot. Knots tied in sounding lines (historically used to measure depth in the ocean) must be placed at precise distances apart. Precise control of tying also allows tangling to be avoided in complex knots. This paper explores an approach to tying knots precisely, so that friction locks occur at specified locations along the string. First, the knot is laid out on a fixture using an arm and a specialized gripper; then, the fixture contracts as string is pulled to tighten the knot. This is the first work we know of in robotic manipulation focused on precise knot tightening (rather than loose arrangement), and presents tying of a fairly complex decorative knot, the Ruyi knot, as a proof of concept. The fixtures are each specific to particular knots, but are designed automatically using the algorithm presented.

String stretched tightly along a sequence of fixed grasp points takes the shape of a polygonal arc. In this work, we investigate how many points are necessary and sufficient to grasp and tie arbitrary knots while maintaining tension, so that the string remains polygonal. This approach allows reasoning that is entirely geometric, which does not rely on potentially inaccurate dynamic models of the string or detailed knowledge of physical characteristics of the string. Algorithms are proposed to determine the contact locations, and generate the motions needed to tie arbitrary knots. This work shows that a number of grasp points that is linear in the number of crossings in a knot diagram is sufficient to immobilize string in a polygonal shape with the topology of an arbitrary knot, or to fold or unfold the knot from a straight configuration.

This paper presents a fast tight-tolerance threading technique for string and rope. Instead of relying on simulations of these deformable objects to plan a path or compute control actions, we control the movement of the string with a virtual magnetic vector field emanating from the narrow openings we wish to thread through. We compute an approximate Jacobian to move the tip of the string through the vector field and propose a method to promote alignment of the head of the string to the opening. We also propose a method for re-grasping the string based on the relationship between the string's configuration, the orientation of the opening, and direction of gravity. This re-grasping method in conjunction with our controller can be used to thread the string through a sequence of openings. We evaluated our method in simulation (with simulated sensor noise) and on the Da Vinci surgical robot. Our results suggest that our method is quite robust to errors in sensing, and is capable of real-world threading tasks with the da Vinci robot, where the diameter of the string (3.5mm) and opening (4.9mm) differ by only 1.4 mm.

This paper presents a definition of convexity useful for describing local optimality in configuration spaces, proves that finding convex regions is relatively easy, and presents an algorithm for approximating the free configuration space using a set of such convex regions. The paper examines simple but interesting systems: serial planar arms with revolute joints, and a Reeds-Shepp car. The paper experimentally explores an approach for finding good (although not necessarily optimal) trajectories using the derived data structure.

This paper presents a controlled tying approach for knots using fixtures and simple pulling motions applied to the ends of string. Each fixture is specific to a particular knot; the paper gives a design process that allows a suitable fixture to be designed for an input knot. Knot tying is separated into two phases. In the first phase, a fixture is used to loosely arrange the string around a set of rods, with the required topology of the given knot. In the second phase, the string is pulled taut around the tightening fixtures. Two tightening fixture designs are presented. The first design is a fixture with no moving parts; tilted rods whose cross-sections get closer near the tips, guiding string in a controlled fashion as string slides up the rods during tightening. The second design is a collection of straight rods that can move passively along predefined paths during tightening. Successful tying is shown for three interesting cases: a “cloverleaf knot” design, a “double coin” knot design, and the top of a shoelace knot.

Analytical results describing the optimal trajectories for general classes of robot systems have proven elusive, in part because the optimal trajectories for a complex system may not exist, or may be computed only numerically from differential equations. This paper studies a simpler optimization problem: finding an optimal sequence and optimal durations of motion primitives (simple preprogrammed actions) to reach a goal. By adding a fixed cost for each switch between primitives, we ensure that optimal trajectories exist and are well-behaved. To demonstrate this approach, we prove some general results that geometrically characterize time-optimal trajectories for rigid bodies in the plane with costly switches (allowing comparison with previous analysis of optimal motion using Pontryagin's Maximum Principle), and also present a complete analytical solution for a problem of moving a heavy park bench by rotating the bench around each end point in sequence.

Sampling-based probabilistic roadmap algorithms such as PRM and PRM* have been shown to be effective at solving certain motion planning problems, but the large graphs generated to express the connectivity and a metric on the configuration space may require much storage space and be expensive to search. Recent work by Marble and Bekris [14], [19] applied spanner algorithms to PRM* these algorithms prune some edges in a dense graph, while guaranteeably maintaining an approximation to the metric. In this paper, we apply (and improve) a state-of-the-art streaming spanner algorithm to prune PRM* roadmaps. The algorithm we present has the main advantage of computational speed; when applied to PRM*, the processing time per vertex is independent of the number of sampled vertices, n, as compared to O(nlog2nloglogn) in [19]. In practice, the algorithm we present prunes a graph with about 20 million edges in less than 20 seconds on a modern desktop computer; compared to the time required for generating such a roadmap, this additional processing time is essentially trivial. In fact, because the combination of this algorithm with PRM* avoids the need for many collision detections, the combination runs several times faster than PRM*alone.

We present the first analytical solution method for finding a time-optimal trajectory between any given pair of configurations for a three-wheeled omni-directional vehicle in an obstacle-free plane. The mathematical model of the vehicle bounds the velocities of the wheels independently. The timeoptimal trajectories can be divided into two categories: singular and generic. An analytical solution method has previously been presented for singular trajectories; this paper completes the work and presents the solution for generic trajectories. The speed and precision of the algorithm allow dense sampling of the configuration space, to determine how the time and structure of time-optimal trajectories change across configurations. Simulation results show that time-optimal trajectories tend to be ten to twenty percent faster than a simple but practical driving strategy: turn until the fastest translation direction faces the goal, drive to the goal, and turn to the current angle.

This paper presents first attempts at a method for searching for time-optimal trajectories for a general model of mobile robots that includes Dubins and Reeds-Shepp cars, differential-drive robots, and omnidirectional robots as special cases. The paper takes as a starting point recent results by the authors that describe necessary conditions on the trajectories, based on Pontryagin's Maximum Principle. These necessary conditions reduce the problem of finding an optimal trajectory between start and goal to a few one-dimensional search problems. This search is not formally guaranteed to find a near-optimal trajectory if the sampling of the search space is not fine enough, but comparison to existing analytical results for specific systems, and a complete numerical search over trajectories with only a few control switches, demonstrates effectiveness of the method.