16866072
Metrics and Connections for Rigid-Body Kinematics
The set of rigid-body motions forms a Lie group called SE(3), the special Euclidean group in three dimensions. In this paper, we investigate possilble choices of Riemannian metrics and affine connections on SE(3) for applications to kinematic analysis and robot-trajectory planning. In the first part of the paper, we study metrics whose geodesics are screw motions. We prove that no Riemannian metrics call have such geodesics, and we show that the metrics whose geodesics are screw motions form a two-parameter family of semi-Riemannan metrics. In the second part of the paper, we investigate affine connections which through the covariant derivative give the correct expression for the acceleration of a rigid body. We prove that there is a unique symmetric connection with this property. Furthermore, we show that there is a family of Riemannian metrics that are compatible with such a connection. These metrics are products of the bi-invariant metric on the group of rotations and a positive-definite constant metric on the group of translations.
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.
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.
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.
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.
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.
39362526
Main memory database recovery algorithms and their performance
In main memory systems recovery becomes more complex mainly due to the volatility of main memory and the elimination of the separation of data storage (disk) and data processing locations (main memory). In a disk based database system, it is the disk copy that represents the stable database restored after a system failure; but in MDBSs, the main memory copy of the database must be recovered. The paper discusses the recovery issues in MDBSs and presents a somewhat detailed performance study of two recovery algorithms, one using a shadow approach and the other update-in-place.<<ETX>>
7638167
Congruences for Visibly Pushdown Languages
We study congruences on words in order to characterize the class of visibly pushdown languages (Vpl), a subclass of context-free languages. For any language L, we define a natural congruence on words that resembles the syntactic congruence for regular languages, such that this congruence is of finite index if, and only if, L is a Vpl. We then study the problem of finding canonical minimal deterministic automata for Vpls. Though Vpls in general do not have unique minimal automata, we consider a subclass of VPAs called k-module single-entry VPAs that correspond to programs with recursive procedures without input parameters, and show that the class of well-matched Vpls do indeed have unique minimal k-module single-entry automata. We also give a polynomial time algorithm that minimizes such k-module single-entry VPAs.
16578484
On the Complexity of Error Explanation
When a system fails to satisfy its specification, the model checker produces an error trace (or counter-example) that demonstrates an undesirable behavior, which is then used in debugging the system. Error explanation is the task of discovering errors in the system or the reasons why the system exhibits the error trace. While there has been considerable recent interest in automating this task and developing tools based on different heuristics, there has been very little effort in characterizing the computational complexity of the problem of error explanation. 
 
In this paper, we study the complexity of two popular heuristics used in error explanation. The first approach tries to compute the smallest number of system changes that need to be made in order to ensure that the given counter-example is no longer exhibited, with the intuition being that these changes are the errors that need fixing. The second approach relies on the observation that differences between correct and faulty runs of a system shed considerable light on the sources of errors. In this approach, one tries to compute the correct trace of the system that is closest to the counter-example. We consider three commonly used abstractions to model programs and systems, namely, finite state Mealy machines, extended finite state machines and pushdown automata. We show that the first approach of trying to find the fewest program changes is NP-complete no matter which of the three formal models is used to represent the system. Moreover we show that no polynomial factor approximation algorithm for computing the smallest set of changes is possible, unless P = NP. For the second approach, we present a polynomial time algorithm that finds the closest correct trace, when the program is represented by a Mealy machine or a pushdown automata. When the program is represented by an extended finite state machine, the problem is once again NP-complete, and no polynomial factor approximation algorithm is likely.
5797236
Strong edge coloring for channel assignment in wireless radio networks
We give efficient sequential and distributed approximation algorithms for strong edge coloring graphs modeling wireless networks. Strong edge coloring is equivalent to computing a conflict-free assignment of channels or frequencies to pairwise links between transceivers in the network
5622554
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 all network nodes are required to be connected to all other nodes (we call this the Strong Connectivity Game). We give asymptotically tight bounds for the worst case quality of a Nash equilibrium in the Strong Connectivity Game and we improve these bounds for randomly distributed nodes. We then study the computational complexity of finding Nash equilibria and show that a polynomial-time algorithm finds Nash equilibria whose costs are at most a factor 2 off the minimum cost possible; 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 answering the question, if a Nash equilibrium exists, is NP-hard, if the network graph satisfies the triangle inequality. For a second game called Reachability Game, where each node tries to reach as many other nodes as possible, while minimizing its radius, we show that 1+o(1)-approximate Nash equilibria exist for randomly distributed nodes. Our work is a first step towards game-theoretic analyses of ad hoc networks.