This paper describes a test-bed for planar micro and mesoscale manipulation tasks and a framework for planning based on quasi-static models of mechanical systems with intermittent frictional contacts. We show how planar peg-in-the-hole assembly tasks can be designed using randomized motion planning techniques with Mason's models for quasi-static manipulation. Simulation and experimental results are presented in support of our methodology. We develop this further into a systematic approach to incorporating uncertainty into planning manipulation tasks with frictional contacts. We again consider the canonical problem of assembling a peg into a hole at the mesoscale using probes with minimal actuation but with visual feedback from an optical microscope. We consider three sources of uncertainty. First, because of errors in sensing position and orientation of the parts to be assembled, we must consider uncertainty in the sensed configuration of the system. Second, there is uncertainty because of errors in actuation. Third, there are geometric and physical parameters characterizing the environment that are unknown. We discuss the synthesis of robust planning primitives using a single degree-of-freedom probe and the automated generation of plans for mesoscale manipulation. We show simulation and experimental results of our work.

Manipulation and assembly tasks are typically characterized by many nominally rigid bodies coming into frictional contacts, possibly involving impacts. Manipulation tasks are difficult to model because uncertainties associated with friction and assembly tasks are particularly hard to analyze because of the interplay between process tolerance and geometric uncertainties due to manufacturing errors. Manipulation at the meso (hundred microns to millimeters) and micro (several microns to tens of microns) scale is even harder for several reasons. It is difficult to measure forces at the micro-netwon level reliably using off-the-shelf force sensors and good force-feedback control schemes have not proved successful. It is hard to manufacture general-purpose end effectors at this scale and it is even more difficult to grasp and manipulate parts at the micro and meso level than it is at the macro level. Finally, the lack of good models of the mechanics of contact interactions at this scale means that model-based approaches to planning and control are difficult.

In this paper, we present a scalable, decentralized task allocation algorithm for a group of unknown number of unmanned aerial vehicles (UAVs), which are equipped with GPS receivers, synchronized clocks and radars with a finite, but known operating distance to identify neighbors. The algorithm assigns subgroups of UAVs, whose initial positions are randomly scattered in a bounded space, to a finite set of independent tasks. The key features of the proposed algorithm are: (1) the algorithm does not require any communication between the UAVs; (2) the task allocation is achieved in finite time. The analysis and results in the simplified 2D simulation environment respectively prove and verify the correctness of the proposed algorithm.

In this paper, we study the time-optimal trajectory planning of a sensor attached to an unmanned aerial vehicle (UAV) to provide complete 3-dimensional coverage with applications to urban environments with 2.5-dimensional features. The basic approach is to approximate the features of interest with a set of non planar coverage surfaces and to design a motion plan that guarantees the coverage surface is swept completely with a conical-field-of-view sensor. We establish a lower bound on time for a UAV to achieve complete coverage and derive the analytical coverage plan whose duration is a constant times this lower bound. Our hardware-in-the-loop simulation results verify the effectiveness of the proposed algorithm.

Sampling-based nonholonomic and kinodynamic planning iteratively constructs solutions with sampled controls. A constructed trajectory is returned as an acceptable solution if its ldquogaps,rdquo including discontinuities within the trajectory and mismatches between the terminal and goal states, are within a given gap tolerance. For a given coarseness in the sampling of the control space, finding a trajectory with a small gap tolerance might be either impossible or extremely expensive. In this paper, we propose an efficient trajectory perturbation method, which complements existing steering and perturbation methods, enabling these sampling-based algorithms to quickly obtain solutions by reducing large gaps in constructed trajectories. Our method uses system symmetry, e.g., invariance of dynamics with respect to certain state transformations, to achieve efficient gap reduction by evaluating trajectory final state with a constant-time operation, and, naturally, generating the admissible perturbed trajectories. Simulation results demonstrate dramatic performance improvement for unidirectional, bidirectional, and PRM-based sampling-based algorithms with the proposed enhancement with respect to their basic counterparts on different systems: one with the second-order dynamics, one with nonholonomic constraints, and one with two different modes.

Classical path planning does not address many of the challenges of robotic systems subject to differential constraints. While there have been many recent efforts to develop motion planning algorithms for systems with differential constraints (MPD), very little has been said about the existence of exact algorithms. In other words, the decidability of MPD problems is still an open question. In this paper, we propose a partial answer to this question limiting ourselves to special cases where the trajectory functions of the systems under the finite-dimensional piecewise-continuous controls have a closed-form polynomial formulation. We define an abstract formulation for the MPD problem based on the concept of a control space. We provide an incremental decision algorithm to answer the decidability question and present sufficient conditions for problems to which this algorithm can be applied. Decidability results for several non trivial MPD problems are presented. For example, we show that the question of existence of a trajectory for a Dubin's car with a polygonal rigid body between two specified positions and orientations in a polygonal environment with a fixed and finite number of discontinuities in curvature is decidable.

The roller racer, an undulatory locomotion system, is a toy which can be propelled forward by sitting on it and only oscillating the steering handle. A nonholonomic dynamic model and controllability analysis of the roller racer was first published by Krishnaprasad and Tsakiris in 1998. The model is derived from the usual assumption that all the wheels obey sticking (non-slipping) constraints, i.e., rolling without slipping. Controllability analysis shows that under these assumptions, the roller racer cannot be stopped once started. Yet physical prototypes do not exhibit this characteristic. In this paper, a high-fidelity model of the roller racer is presented by considering the finite static friction between the wheels and the ground, i.e., slipping will occur when constraint force exceeds the maximal allowable frictional force. It is proved that the system could be stopped from any state with only the steering angle control. Furthermore, based on group symmetry and motion primitives, a planner is designed to achieve motions between any two given positions and orientations with zero velocities. Experiments also show that front wheel slipping stops the system faster than joint frictions

The TRIKKE is a three-wheeled, human-powered scooter that can be propelled by a combination of cyclic motion of its handlebar and swaying motion of the rider. This paper addresses the modeling, dynamics and control of the TRIKKE and the development of a robotic platform called the ROBOTRIKKE that is derived from similar principles. The TRIKKE can be modeled as a modified roller-racer with an unstable steering arrangement. The model of the TRIKKE reduces to the roller-racer [8] in the absence of this steering arrangement. We prove that under certain conditions on the geometric parameters of the system, the TRIKKE and roller-racer systems cannot be stopped after motion starting from rest using the steering control as the sole input. As a consequence, the ideal model is severely limited from the point of view of controllability. We demonstrate the validity of our model through comparison with experimental measurements on a small-scale robotic prototype of the TRIKKE. We present closed-loop control results for tracking (on average) a straight line trajectory using visual feedback from an overhead camera.

We present a new sampling-based algorithm for iteratively locating Voronoi vertices of a point set in the unit cube Id= [0, 1]d. The algorithm takes an input sample and executes a series of transformations, each of which projects the sample to a new face of the Voronoi cell in which it is located. After d such transformations, the sample has been transformed into a Voronoi vertex. Locating Voronoi vertices has many potential applications for motion planning, such as estimating dispersion for coverage and verification applications, and providing information useful for Voronoi-biased or multiple-tree planning. We prove theoretical results regarding our algorithm, and give experimental results comparing it to naive sampling for the problem of dispersion estimation.

Although sampling-based planning algorithms have been extensively used to approximately solve motion planning problems with differential constraints, gaps usually appear in their solution trajectories due to various factors. Higher precision may be requested, but as we show in this paper, this dramatically increases the computational cost. In practice, this could mean that a solution would not be found in a reasonable amount of time. In this paper, we substantially improve the performance of an RRT-based algorithm by planning low precision solutions, and then refining their quality by employing a gap reduction technique that exploits group symmetries of the system to avoid costly numerical integrations. This technique also allows PRMs to be extended to problems with differential constraints, even when no high-quality steering method exists.

We address the problem of eliminating gaps in paths that are constructed by some nonholonomic and kinodynamic motion planning algorithms. In many of these algorithms, control inputs at each planning step are chosen from a finite set, obtained from discretization of the available control set. While this approach is attractive for computational reasons, it can generate gaps, or discontinuities, either between path segments or between the final state and the desired goal. For the purpose of reducing gaps, the original control set and continuous time interval can be utilized, and perturbations may be applied to incrementally optimize the gap error while respecting collision constraints. By exploiting Lie group symmetries, which emerge in a broad class of robot systems, we are able to avoid costly numerical integrations that usually occur in each step of gradient-based optimization techniques. It is hoped that the approach can ultimately lead to faster planning algorithms by allowing coarser discretizations of time and the available input set, with the understanding that later refinements can be made efficiently.

Trajectory design for high-dimensional systems with nonconvex constraints has considerable success recently; however, the resolution completeness analysis for various methods is insufficient. In this paper, based on Lipschitz condition and the accessibility graph, conditions for resolution completeness are derived. By combining the systematic search with randomized technique, a randomized planner is transformed to be a deterministic resolution complete planner, which shows reliable performance in the simulation.

This paper addresses the trajectory design for generic problems that involve: (1) complicated global constraints that include nonconvex obstacles, (2) nonlinear equations of motion that involve substantial drift due to momentum, and (3) a high-dimensional state space. Our approach to these challenging problems is to develop randomized planning algorithms based on rapidly-exploring random trees (RRTs). RRTs use metric-induced heuristics to conduct a greedy exploration of the state space; however, performance substantially degrades when the chosen metric does not adequately reflect the true cost-to-go. In this paper, we present a version of the RRT that refines its exploration strategy in the presence of a poor metric. Experiments on problems in vehicle dynamics and spacecraft navigation indicate substantial performance improvement over existing techniques.