9454097
An asynchronous integration and event detection algorithm for simulating multi-agent hybrid systems
A simulation algorithm is presented for multi-agent hybrid systems---systems consisting of many sets of nonsmooth differential equations---such as systems involving multiple rigid bodies, vehicles, or airplanes. The differential equations are partitioned into coupled subsystems, called "agents"; and the conditions which trigger the discontinuities in the derivatives, called "events", may depend on the global state vector. Such systems normally require significant computational resources to simulate because a global time step is used to ensure the discontinuity is properly handled. When the number of systems is large, forcing all system to be simulated at the same rate creates a computational bottleneck, dramatically decreasing efficiency. By using a control systems approach for selecting integration step sizes, we avoid using a global time step. Each subsystem can be simulated asynchronously when the state is away from the event. As the state approaches the event, the simulation is able to synchronize each of the local time clocks in such a way that the discontinuities are properly handled without the need for "roll back". The algorithm's operation and utility is demonstrated on an example problem inspired by autonomous highway vehicles. Using a combination of stochastic modelling and numerical experiments we show that the algorithm requires significantly less computation time when compared with traditional simulation techniques for such problems, and scales more favorably with problem size.
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.
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.
18215048
Performance of Recovery Algorithms for Centralized Database Management Systems
Database recovery is responsible for preserving the database consistency after a failure of any kind (transaction, system or media). Relevant information solely for recovery is saved in a log during normal transaction processing. To recover from a failure, basically two operations: undo and redo are applied with the help of the log on the last consistent state of the database. These two operations can be combined in four different ways to define four different types of recovery algorithms: “undo-redo,” “no undo-redo,” “undo-no redo” and “no undo-no redo.” Each of these algorithms manages log and updates to the database differently, which affect the overall performance and the availability of the database. 
 
To our knowledge, not much work has been done on the performance of recovery algorithms. There are only six reports available and these works have concentrated their studies on only a few algorithms. They have mainly used a queuing approach, which we believe is not adequate for a detailed performance study. In this paper we investigate the relative performance of these four algorithms through simulation. The purpose of conducting this study is first, to verify the findings of earlier works, and second, to obtain a detailed comparison of the behavior of all recovery algorithms. Our simulation studies show that in most cases, undo-redo and no undo-redo deliver similar but better recovery performance than undo-no redo and no undo-no redo. We observe that the recovery times increase with multiprogramming level, but generally decrease as the number of checkpoints increases. The undo-no redo algorithm results in a greater number of transaction rollbacks, which creates a larger transaction log, and thus longer recovery times. Its performance increases against undo-redo and no undo-redo as input/output performance improves. Slow input/output performance is also attributed to be the cause of the no undo-no redo algorithm's poor recovery performance.
1921533
A superior two-phase locking algorithm and its performance
Abstract Concurrent transactions, during their execution, may conflict over common data entities. Such conflicts are resolved by concurrency control mechanisms by use of operations such as transaction rollback and/or transaction blocking. There are a number of mechanisms available and each applies these operations in different ways to resolve conflicts and claims some performance advantages. In this work we have analyzed the behavior of a new deadlock-free two-phase locking mechanism, called Cautious Waiting, and have compared its performance with other well-known mechanisms. The mechanism is conceptually quite simple; therefore it is not likely to be difficult to implement. We show that this mechanism performs consistently better under a wide range of parameter values than the other mechanisms investigated here. We also show that it is more robust, in the sense that it is less sensitive to load increases and other changes in parameter settings. In contrast, we show that one of the most commonly used mechanisms is not as robust and efficient under stress situations.
213611
Covering rectilinear polygons with axis-parallel rectangles
We give an O( log n) factor approximation algorithm for covering a rectilinear polygon with holes using axis-parallel rectangles. This is the first polynomial time approximation algorithm for this problem with an o(log n) approximation factor. 1. Introduction. We consider the problem of covering rectilinear polygons with axis-parallel rectangles. Given a rectilinear polygon P with complexity n (complexity refers to the minimum of the number of vertical edges and the number of horizontal edges in the polygon), this problem requires determining the minimum number of axis-parallel rectangles whose union covers P. The polygon P may have holes in it. Applications. Cheng, Iyengar, and Kashyap (5) showed that this problem has applications to image compression. They claim that representing an image using a rectangle covering of its white pixels gives compression superior to that achieved by quadtrees. It also has applications to printing integrated circuits (9). Hardness. Much effort has gone into determining the computational complexity of this problem. In spite of this, the exact complexity of this problem has remained open for many years and continues to do so. Masek (19) showed that this problem is NP-complete. Later, Culberson and Reckhow (6) used a clever reduction from 3-SAT to show that this is the case even when P has no holes. The next natural question is whether the number of rectangles needed to cover P can be computed approximately. Berman and Dasgupta (2) showed that this problem is MaxSNP-Hard for polygons with holes, ruling out the possibility of a polynomial time approximation scheme. Approximation results. Note that the rectangle covering problem is a special case of the general set covering problem. Therefore, it admits an approximation algorithm with a performance guarantee of O(log n), using the greedy scheme due to Johnson (10) and Lovasz (16). This was the best approximation factor known for the rectangle covering problem until now. Further, it is known that the general set covering problem cannot be approximated any better, modulo constant terms, unless NP = P (17, 18). However, this proof of hardness assumes certain properties about the set system which do not hold for the rectangle covering problem. In this paper, we address the issue of whether the Ω(log n) approximation factor barrier can be broken in polynomial time for the rectangle covering problem. There seem to be only a few examples of nontrivial algorithms breaking this
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.
8261257
TCOT-A Timeout-Based Mobile Transaction Commitment Protocol
We present a transaction commit protocol, "Transaction Commit On Timeout (TCOT)," based on a "timeout" approach for Mobile Database Systems (MDS), which can be universally used to reach a final transaction termination decision (e.g., commit, abort, etc.) in any message-oriented system. Particularly suited for a wireless environment, a timeout mechanism is the only way to minimize the impact of the slow and unreliable wireless link. We compare TCOT to a modified version of 2PC to show its superiority based on commit time.