11502954
Motion generation for formations of robots: A geometric approach
Develops a method for generating smooth trajectories for mobile robots in formation. The problem of trajectory generation is cast in terms of designing optimal curves on the Euclidean group, SE(3). Specifically, the method generates the trajectory that minimizes the total energy associated with the translations and rotations of the robots, while maintaining a rigid formation. When the mobile robots are nonholonomic, trajectories that allow rigid formations to be maintained must satisfy appropriate constraints. An efficient non-iterative algorithm to obtain near-optimal trajectories is described. Finally, the approach is illustrated with examples involving formations of aircrafts.
15738427
A potential field based approach to multi-robot manipulation
We describe a framework for controlling and coordinating a group of robots for cooperative manipulation tasks. The framework enables a decentralized approach to planning and control. It allows the robots to approach the object, organize themselves into a formation that will trap the object, and then transport the object to the desired destination. Our controllers and planners are derived from simple potential fields and the hierarchical composition of potential fields. We show how these potential field based controllers and planners benefit complex group interactions, specifically for manipulating and transporting objects in the plane. Theoretically, we show how we can derive results on formation stability with potential field based controllers in many cases. Simulation results demonstrate successful application to a wide range of examples without showing sensitivity to parameters. Because the framework is decentralized at both trajectory generation level and the estimation and control agent level, our framework can potentially scale to groups of tens and hundreds of robots.
6879835
Calibrating an air-ground control system from motion correspondences
In this paper we consider the problem of controlling the motion of a vehicle moving on a ground plane based on aerial imagery. In the course of this work we propose a novel analysis of the relationship between the velocity of the vehicle on the ground plane and the velocity of its projection in the image. We show that this relationship provides information about a subset of the parameters of the homography relating the ground plane to the aerial image plane and describe how we can recover this relationship from available measurements.
29516211
Control of Contact Interactions with Acatastatic Nonholonomic Constraints
A robot arm performs many tasks by interacting with objects or other robots in the environment. It is important for the robot arm to be able to exhibit controlled interactions with the objects and other robots. The contact motion between the robot arm and an object can be rolling, sliding, or separation. In this article, we address the problem of maintaining rolling contact between the robot arm and an external moving object. We assume that a nominal model of the motion of the moving object is available. The dynamic system that characterizes the motion of the robot arm and the moving object in this case is acatastatic and nonholonomic. We have designed a nonlinear feedback for the control of such a system that successfully maintains rolling contact. Simulation results are presented to demonstrate the effectiveness of the system.
5542960
Metrics for analysis and optimization of grasps and fixtures
We develop two quality measures for the analysis and optimization of grasps and fixtures. The first metric is a measure of stability and is obtained by analyzing the effect of small perturbations in the position of the grasped object or small disturbance forces on the grasped object The second metric is a measure of robustness to errors in the positions of the fixture elements. In addition, we explore the effect that the stiffness of the fixture elements has on these two quality measures and propose a design optimization approach to maximize stability and robustness to errors.
7023425
A Paradigm for Dynamic Coordination of Multiple Robots
In this paper, we present a paradigm for coordinating multiple robots in the execution of cooperative tasks. The basic idea in the paper is to assign to each robot in the team, a role that determines its actions during the cooperation. The robots dynamically assume and exchange roles in a synchronized manner in order to perform the task successfully, adapting to unexpected events in the environment. We model this mechanism using a hybrid systems framework and apply it in different cooperative tasks: cooperative manipulation and cooperative search and transportation. Simulations and real experiments demonstrating the effectiveness of the proposed paradigm are presented.
2804750
A Timeout-Based Mobile Transaction Commitment Protocol
We investigate transaction commit in Mobile Database Systems (MDS) and develop a commitment protocol based on "timeout" approach. Timeout approach is universally used to reach a decision as a last option in all message oriented systems. With this approach we have minimized the use of wireless message cost in commiting transactions.
18650185
Minimization, Learning, and Conformance Testing of Boolean Programs
Boolean programs with recursion are convenient abstractions of sequential imperative programs, and can be represented as recursive state machines (RSMs) or pushdown automata. Motivated by the special structure of RSMs, we define a notion of modular visibly pushdown automata (modular VPA) and show that for the class of languages accepted by such automata, unique minimal modular VPA exist. This yields an efficient approximate minimization theorem that minimizes RSMs to within a factor of k of the minimal RSM, where k is the maximum number of parameters in any module. Using the congruence defined for minimization, we show an active learning algorithm (with a minimally adequate teacher) for context free languages in terms of modular VPAs. We also present an algorithm that constructs complete test suites for Boolean program specifications. Finally, we apply our results on learning and test generation to perform model checking of black-box Boolean programs.
47278894
Equilibria in Topology Control Games for Ad Hoc Networks
We study topology control problems in ad hoc networks where network nodes get to choose their power levels in order to ensure desired connectivity properties. Unlike most other work on this topic, we assume that the network nodes are owned by different entities, whose only goal is to maximize their own utility that they get out of the network without considering the overall performance of the network. Game theory is the appropriate tool to study such selfish nodes: we define several topology control games in which the nodes need to choose power levels in order to connect to other nodes in the network to reach their communication partners while at the same time minimizing their costs. We study Nash equilibria and show that—among the games we define—these can only be guaranteed to exist if each network node is required to be connected to all other nodes (we call this the Strong Connectivity Game). For a variation called Connectivity Game, where each node is only required to be connected (possibly via intermediate nodes) to a given set of nodes, we show that Nash equilibria do not necessarily exist. We further study how to find Nash equilibria with incentive-compatible algorithms and compare the cost of Nash equilibria to the cost of a social optimum, which is a radius assignment that minimizes the total cost in a network where nodes cooperate. We also study variations of the games; one where nodes not only have to be connected, but k-connected, and one that we call the Reachability Game, where nodes have to reach as many other nodes as possible, while keeping costs low. We extend our study of the Strong Connectivity Game and the Connectivity Game to wireless networks with directional antennas and wireline networks, where nodes need to choose neighbors to which they will pay a link. Our work is a first step towards game-theoretic analyses of topology control in wireless and wireline networks.
11125586
The Behavior of Database Concurrency Control Mechanisms under Bursty Arrivals
The robustness and sensitivity of four two-phase databases concurrency control mechanisms are studied under a dynamically changing workload due to the bursty arrival of transactions. The concurrency control mechanisms are studied under closely controlled conditions in which the only variable is the coefficient of variance of the arrival rate distribution. This paper shows that bursty traffic does impact the performance of the concurrency control mechanisms at both high and low loads, and that the degree of this impact is different for the different mechanisms investigated. We also show that the behavior of some CCMs change significantly under such environment.
5564142
Provable algorithms for parallel generalized sweep scheduling
Abstract We present provably efficient parallel algorithms for sweep scheduling, which is a commonly used technique in radiation transport problems, and involves inverting an operator by iteratively sweeping across a mesh from multiple directions. Each sweep involves solving the operator locally at each cell. However, each direction induces a partial order in which this computation can proceed. On a distributed computing system, the goal is to schedule the computation, so that the length of the schedule is minimized. Due to efficiency and coupling considerations, we have an additional constraint, namely, a mesh cell must be processed on the same processor along each direction. Problems similar in nature to sweep scheduling arise in several other applications, and here we formulate a combinatorial generalization of this problem that captures the sweep scheduling constraints,and call it the generalized sweep scheduling problem. Several heuristics have been proposed for this problem; see [S. Pautz, An algorithm for parallel S n sweeps on unstructured meshes, Nucl. Sci. Eng. 140 (2002) 111–136; S. Plimpton, B. Hendrickson, S. Burns, W. McLendon, Parallel algorithms for radiation transport on unstructured grids, Super Comput. (2001)] and the references therein; but none of these have provable worst case performance guarantees. Here we present a simple, almost linear time randomized algorithm for the generalized sweep scheduling problem that (provably) gives a schedule of length at most O ( log 2 n ) times the optimal schedule for instances with n cells, when the communication cost is not considered, and a slight variant, which coupled with a much more careful analysis, gives a schedule of (expected) length O ( log m log log log m ) times the optimal schedule for m processors. These are the first such provable guarantees for this problem. The algorithm can be extended with an additional multiplicative factor in the case when we have inter-processor communication latency, in the models of Rayward-Smith [UET scheduling with inter-processor communication delays, Discrete Appl. Math. 18 (1) (1987) 55–71] and Hwang et al. [Scheduling precedence graphs in systems with inter-processor communication times, SIAM J. Comput. 18(2) (1989) 244–257]. Our algorithms are extremely simple, and use no geometric information about the mesh; therefore, these techniques are likely to be applicable in more general settings. We also design a priority based list schedule using these ideas, with the same theoretical guarantee, but much better performance in practice; combining this algorithm with a simple block decomposition also lowers the overall communication cost significantly. Finally, we perform a detailed experimental analysis of our algorithm. Our results indicate that the algorithm compares favorably with the length of the schedule produced by other natural and efficient parallel algorithms proposed in the literature [S. Pautz, An Algorithm for parallel S n sweeps on unstructured meshes, Nucl. Sci. Eng. 140 (2002) 111–136; S. Plimpton, B. Hendrickson, S. Burns, W. McLendon, Parallel algorithms for radiation transport on unstructured grids, Super Comput. (2001)].