In very high-dimensional$(\gg 10)$spaces, a collection of points generated uniformly at random will concentrate very tightly about its expected value - defying intuition developed in low-dimensional spaces. This paper explores the implications of this for two major classes of sample-based robot motion planning algorithms: Rapidly Exploring Random Trees (RRTs) and Probabilistic Road Maps (PRMs). First we show that the graph vertices concentrate in a thin-shelled hyper-sphere, with almost none near the origin nor at the edges of the workspace. Next we examine how varying one of the algorithms' parameters - the maximum edge length- can dramatically alter the algorithms' complexity and the connectivity of the resulting graph. Finally, we explore how the position of the initial node, often placed arbitrarily, can impact the shape of the graph. While the contributions of this paper are largely theoretical, many robotic applications of practical interest have extremely high-dimensional configuration spaces including humanoids, swarms and soft (a.k.a. continuum) robotics.

It has been shown that the Rapidly Exploring Random Tree algorithm is complete - both probabilistically and in the sense of resolution; however little analysis exists on the rate of convergence. We present a model of state space coverage as a function of the number of nodes in the tree, for holonomic systems in expansive configuration spaces. Based on two simplifying assumptions, we develop a stochastic difference equation, whose expected value exponentially converges to one as the number of nodes increases. The convergence rate is related through a closed form expression to the step size and a Lipschitz constant. Using a grid-based coverage measurement, we present experimental evidence supporting the model across a range of dimensions, obstacle densities and parameter choices.

In this paper we consider cooperative manipulation problems where a large group (swarm) of non-articulated mobile robots is trying to cooperatively control the velocity of some larger rigid body by exerting forces around its perimeter. We consider a second-order dynamic model for the object but use a simplified contact model. We seek solutions that require minimal information sharing among the swarm members. We present a velocity control law that is asymptotically stable. In the case of a constant desired velocity, it is shown that no coordination is required between the swarm members. For more complex trajectories we introduce a decentralized feed-forward component that uses an online consensus estimate of the swarm's configuration. The results are illustrated in simulation.

Assume a swarm of mobile robots is in the act of transporting a large object in the plane, by applying unilateral forces to the perimeter of that object. We address the question of where a new robot, joining the group, should establish contact with the object to maximally improve the manipulation capabilities of the swarm. Inspired by the literature on multi-fingered hands, we synthesize a grasp by incrementally optimizing a grasp quality function. We adapt the quality function in several important ways to accommodate the distributed nature of the swarm problem. We show that the objective function is quasi- concave, which has important implications for uniqueness and scalability of the solution; and present a solution methodology. We apply the resulting framework to the example of a large swarm of autonomous tug boats towing a barge, taken from our larger research program.

In this paper we present a strategy that allows a swarm of autonomous tugboats to cooperatively move a large object on the water. The two main challenges are: (1) the actuators are unidirectional and experience saturation; (2) the hydrodynamics of the system are difficult to characterize. The primary theoretical contribution of the paper addresses the first challenge. We present a tracking controller and force allocation strategy that, despite actuator limitations, result in asymptotically convergent tracking for a certain class of reference trajectories. The primary practical contribution is the introduction of a set of adaptive control laws that address the second challenge by compensating for unknown, and difficult to measure, hydrodynamic parameters. Experimental verification of the controllers is presented using a 1:36 scale model of a U.S. Navy ship, inside the Naval Academy's unique 380 ft testing tank.

Many robot systems employ logic-based or reactive controllers, making them hybrid systems (i.e., mixed discrete continuous). However, designing such control laws in a systematic manner remains a challenging task. In this paper, we apply the formal modeling paradigm to a team of mobile robots. The linear hybrid automata modeling framework is used to describe the high-level design, and the verification software HyTech is used for symbolic analysis of the description. The goal is to symbolically quantify system-level performance as a function of the design parameters, for the purpose of optimizing and synthesizing design parameters, verifying safe operation, and quantitatively exploring tradeoff issues. In order to make the analysis tractable, a series of restrictive assumptions and simplifications must be made-some dictated by the linear hybrid automata model and others necessitated by computational cost. We comment on the restrictiveness of these assumptions and the overall utility of this automated analysis approach in designing complex robotic systems

The low power requirements of many small radio modems suggest that robust operation is best attained when the transmitter/receiver pair is: (1) separated by less than some maximum distance (range); and (2) not obstructed by large dense objects (line-of-sight). Therefore to maintain a wireless link between two robots, it is desirable to comply with these two spatial constraints. Given a swarm of point robots with specified initial and final configurations and a set of desired communication links consistent with the above criteria, we explore the problem of designing inputs to achieve the final configuration while preserving the desired links for the duration of the motion. Some interesting conclusions about the feasibility of the problem are offered. An algorithm is provided and its operation is demonstrated through both simulation and experimentation on Koala robots

This paper describes the modeling language CHARON for modular design of interacting hybrid systems. The language allows specification of architectural as well as behavioral hierarchy and discrete as well as continuous activities. The modular structure of the language is not merely syntactic, but is exploited by analysis tools and is supported by a formal semantics with an accompanying compositional theory of refinement. We illustrate the benefits of CHARON in the design of embedded control software using examples from automated highways concerning vehicle coordination.

The problem of motion planning in environments with both known static obstacles and unpredictable dynamic constraints is considered. A methodology is introduced in which the motion plan for the static environment is modified on-line to accommodate the unpredictable constraints in such a way that the completeness properties of the original motion plan are preserved. At the heart of the approach is the idea that navigation functions are indeed Lyapunov functions; and that the traditional method of forcing the robot to track the negative gradient of field is not the only input which stabilizes the system. This extra freedom in selecting the input is used to accommodate the dynamic constraints. A computational method for selecting the appropriate inputs is given. The method is used to solve two sample problems. The constraints in these cases are used to model collisions with other robots and, in the second example, a team of robots traveling information. Finally, some preliminary work on extending the approach to nonholonomic systems is presented.

In this paper multirate numerical integration techniques are introduced as a tool for simulating robotic systems. In contrast with traditional simulation techniques where a single global time step is used, multirate methods seek a gain in efficiency by using larger step sizes for the slow varying components and smaller step sizes for components with rapidly changing solutions. We argue that many robotic systems inherently possess different time scales, and therefore can benefit from multirate techniques. We have developed a multirate version of the popular Adams predictor-corrector methods, which has a variety of modern features. We present results on the accuracy, stability and efficiency of the algorithm along with simulation results.

We discuss a game theoretic approach to the design of closed loop feedback laws to solve sensor based motion planning problems for mobile robots. Our approach provides a framework for dealing with environmental uncertainty, and, by explicitly accounting for the sensor dynamics, a formal way of combining exploratory and goal directed motions. We focus on methods of devising optimal feedback laws, using finite dimensional parametrizations, under the worst case uncertainty for several illustrative examples.

We propose a hierarchical structure for control of autonomous robots. We draw on ideas from the hybrid systems theory, which describe systems governed by a discrete set of continuous modes of operation and transitions between these modes. We aim to enable rapid development of test applications and to allow easy performance upgrades. Our structure is based on the creation of agents to process inputs and outputs at the highest level of abstraction in the system (the application domain). We describe our implementation of this structure in two systems: a nonholonomic car-like robot and a quadrupedal entertainment robot. Both examples demonstrate how abstraction of planning away from the implementation details of the robot enables rapid development.