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.
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.
38254367
Parallel formulations of decision-tree classification algorithms
Classification decision tree algorithms are used extensively for data mining in many domains such as retail target marketing, fraud detection, etc. Highly parallel algorithms for constructing classification decision trees are desirable for dealing with large data sets in reasonable amount of time. Algorithms for building classification decision trees have a natural concurrency, but are difficult to parallelize due to the inherent dynamic nature of the computation. We present parallel formulations of classification decision tree learning algorithm based on induction. We describe two basic parallel formulations. One is based on Synchronous Tree Construction Approach and the other is based on Partitioned Tree Construction Approach. We discuss the advantages and disadvantages of using these methods and propose a hybrid method that employs the good features of these methods. Experimental results on an IBM SP-2 demonstrate excellent speedups and scalability.
42935672
Performance Measurement of Main Memory Database Recovery Algorithms Based on Update-in-Place and Shadow Approaches
The authors present a performance study of two main memory database recovery algorithms, one using a shadow approach and the other update-in-place. The results show that in main memory databases, shadow approach performs better than update-in-place. The authors introduce minor improvements to the shadow scheme and show that the modified algorithm does show further performance improvement. >
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.
5147118
Location dependent query processing
The advances in wireless and mobile computing allow a mobile user to perform a wide range of aplications once limited to non-mobile hard wired computing environments. As the geographical position of a mobile user is becoming more trackable, users need to pull data which are related to their location, perhaps seeking information about unfamiliar places or local lifestyle data. In these requests, a location attribute has to be identified in order to provide more efficient access to location dependent data, whose value is determined by the location to which it is related. Local yellow pages, local events, and weather information are some of the examples of these data.
In this paper, we give a formalization of location relatedness in queries. We differentiate location dependence and location awareness and provide thorough examples to support our approach.
14530470
Conformance testing in the presence of multiple faults
Conformance testing is the problem of determining if a black-box implementation I is equivalent to a specification S, where both are modeled as finite state Mealy machines. The problem involves constructing a checking sequence based on the specification, which is a sequence of inputs that detects all faulty machines. Traditionally conformance testing algorithms have assumed that the number of states in the implementation does not exceed that in the specification. This is because it is known that, in the absence of this assumption, the length of the checking sequence needs to be at least exponential in the number of extra states in the implementation [41]. However, this has limited the applicability of these techniques in practice where the implementation typically has many more states than the specification.In this paper we relax the constraints on the size of the implementation and investigate the existence of polynomial length checking sequences for implementations with extra states, under the promise that they either have multiple faults or no faults at all. We present randomized algorithms to construct checking sequences that catch faulty implementations with at most Δ extra states, having at least r faults (where Δ and r are parameters to the algorithm), and pass all correct implementations. We demonstrate the near optimality of our algorithms by presenting lower bounds for this problem. One of the main technical lemmas used in our proof is an estimate of the probability that a random walk on directed graphs will reach a large target set. We believe that this lemma will be of independent interest in the context of verifying safety properties.