作者:
Karaman, SertacFrazzoli, EmilioMIT
Dept Elect Engn & Comp Sci Informat & Decis Syst Lab Cambridge MA 02139 USA MIT
Dept Aeronaut & Astronaut Informat & Decis Syst Lab Cambridge MA 02139 USA
Pursuit-evasion games have been used for modeling various forms of conflict arising between two agents modeled as dynamical systems. Although analytical solutions of some simple pursuit-evasion games are known, most i...
详细信息
ISBN:
(纸本)9783642174513
Pursuit-evasion games have been used for modeling various forms of conflict arising between two agents modeled as dynamical systems. Although analytical solutions of some simple pursuit-evasion games are known, most interesting instances can only be solved using numerical methods requiring significant offline computation. In this paper, a novel incremental sampling-based algorithm is presented to compute optimal open-loop solutions for the evader, assuming worst-case behavior for the pursuer. It is shown that the algorithm has probabilistic completeness and soundness guarantees. As opposed to many other numerical methods tailored to solve pursuit-evasion games, incremental sampling-based algorithms offer anytime properties, which allow their real-time implementations in online settings.
In this paper, we propose an object usual places extraction system that is based on mobile robot patrolling a smart space referred to as a "Robotic Room". The system monitors the user's daily life, and b...
详细信息
ISBN:
(纸本)9783642147432
In this paper, we propose an object usual places extraction system that is based on mobile robot patrolling a smart space referred to as a "Robotic Room". The system monitors the user's daily life, and based on this observation it searches for objects efficiently by narrowing the range of places that the object is likely to be located. In addition, when the robot is not performing other tasks, it moves to the neiborhood of these locations, searches for objects and determines their positions. Finally, the system uses the long-term measurement data to statistically determine the usual places where objects are located. Experimental results demonstrate that the system locates objects in a reasonably fast time and automatically extracts the usual locations of objects from the log data.
This paper models a multibody collision in the impulse space as a state transition diagram, where each state represents a phase during which impacts are "active" at only a subset of the contact points. A sta...
详细信息
ISBN:
(纸本)9783642003110
This paper models a multibody collision in the impulse space as a state transition diagram, where each state represents a phase during which impacts are "active" at only a subset of the contact points. A state transition happens whenever an active impact finishes restitution, or an inactive impact gets reactivated, depending on whether the two involved bodies are instantaneously penetrating into each other or not. The elastic energy due to an impact is not only affected by the impulse at the corresponding contact point, but also by other impulses exerted on the two involved bodies during the impact. Consequently, Poisson's impulse-based law of restitution could result in negative energy. A new law governing the loss of elastic energy during restitution is introduced. Convergence of the impulse sequence generated by the state transition diagram is established. The collision outcome depends on the ratios of the contact stiffnesses rather than on their individual values. The collision model is then applied in an analysis of billiard shooting in which the cue stick impacts the cue ball, which in turn impacts the pool table. The system is driven by the normal impulses at the two contacts with the tangential impulses determined via a contact mode analysis.
We address the problem of propagating a piece of information among robots scattered in an environment. Initially, a single robot has the information. This robot searches for other robots to pass it along. When a robot...
详细信息
ISBN:
(纸本)9783642003110
We address the problem of propagating a piece of information among robots scattered in an environment. Initially, a single robot has the information. This robot searches for other robots to pass it along. When a robot is discovered, it can participate in the process by searching for other robots. Since our motivation for studying this problem is to form an ad-hoc network, we call it the Network Formation Problem. In this paper, we study the case where the environment is a rectangle and the robots' locations are unknown but chosen uniformly at random. We present an efficient network formation algorithm, Stripes, and show that its expected performance is within a logarithmic factor of the optimal performance. We also compare Stripes with an intuitive network formation algorithm in simulations. The feasibility of Stripes is demonstrated with a proof-of-concept implementation.
Developing robust and automated protein structure determination algorithms using nuclear magnetic resonance (NMR) data is an important goal in computational structural biology. Algorithms based on global orientational...
详细信息
ISBN:
(纸本)9783642174513
Developing robust and automated protein structure determination algorithms using nuclear magnetic resonance (NMR) data is an important goal in computational structural biology. Algorithms based on global orientational restraints from residual dipolar couplings (RDCs) promise to be quicker and more accurate than approaches that use only distance restraints. Recent development of analytic expressions for the roots of RDC equations together with protein kinematics has enabled exact, linear-time algorithms, highly desirable over earlier stochastic methods. In addition to providing guarantees on the number and quality of solutions, exact algorithms require a minimal amount of NMR data, thereby reducing the number of NMR experiments. Implementations of these methods determine the solution structures by explicitly computing the intersections of algebraic curves representing discrete RDC values. However, if additional RDC data can be measured, the algebraic curves no longer generically intersect. We address this situation in the paper and show that globally optimal structures can still be computed analytically as points closest to all of the algebraic curves representing the RDCs. We present new algorithms that expand the types and number of RDCs from which analytic solutions are computed. We evaluate the performance of our algorithms on NMR data for four proteins: human ubiquitin, DNA-damage-inducible protein I (DinI), the Z domain of staphylococcal protein A (SpA), and the third IgG-binding domain of Protein G (GB3). The results show that our algorithms are able to determine high-resolution backbone structures from a limited amount of NMR data.
This paper presents the Parameterised POMDP (PPOMDP) algorithm: a method for planning in the space of continuous parameterised functions. The novel contribution is an approach to transitioning parameterised beliefs us...
详细信息
ISBN:
(纸本)9783642147432
This paper presents the Parameterised POMDP (PPOMDP) algorithm: a method for planning in the space of continuous parameterised functions. The novel contribution is an approach to transitioning parameterised beliefs using Monte Carlo methods. By re-using prediction and observation calculations, the transition function can be computed efficiently. An analysis of scalability suggests that the approach is likely to scale to physically larger environments than algorithms which rely on an underlying discretisation. Experimental results in a simulated robot navigation problem show that the algorithm compares favourably with existing approaches.
This paper addresses theoretical foundations of motion planning with differential constraints in the presence of obstacles. We establish general conditions for the existence of resolution complete planning algorithms ...
详细信息
ISBN:
(纸本)9783642174513
This paper addresses theoretical foundations of motion planning with differential constraints in the presence of obstacles. We establish general conditions for the existence of resolution complete planning algorithms by introducing a functional analysis framework and reducing algorithm existence to a simple topological property. First, we establish metric spaces over the control function space and the trajectory space. Second, using these metrics and assuming that the control system is Lipschitz continuous, we show that the mapping between open-loop controls and corresponding trajectories is continuous. Next, we prove that the set of all paths connecting the initial state to the goal set is open. Therefore, the set of open-loop controls, corresponding to solution trajectories, must be open. This leads to a simple algorithm that searches for a solution by sampling a control space directly, without building a reachability graph. A dense sample set is given by a discrete-time model. Convergence of the algorithm is proven in the metric of a trajectory space. The results provide some insights into the design of more effective planning algorithms and motion primitives.
Neurally controlled prosthetic devices capable of environmental manipulation have much potential towards restoring the physical functionality of disabled people. However, the number of user input variables provided by...
详细信息
ISBN:
(纸本)9783642147432
Neurally controlled prosthetic devices capable of environmental manipulation have much potential towards restoring the physical functionality of disabled people. However, the number of user input variables provided by current neural decoding systems is much less than the number of control degrees-of-freedom (DOFs) of a prosthetic hand and/or arm. To address this sparse control problem, we propose the use of low-dimensional subspaces embedded within the pose space of a robotic limb. These subspaces are extracted using dimension reduction techniques to compress captured human hand motion into a (often two-dimensional) subspace that can be spanned by the output of neural decoding systems. To evaluate our approach, we explore a set of current state-of-the-art dimension reduction techniques and show results for effective control of a 13 DOF robot hand performing basic grasping tasks taking place in both static and dynamic environments.
We present a unified treatment for modeling Coulomb and viscous friction within multi-rigid body simulation using the principle of maximum dissipation. This principle is used to build two different methods-an event-dr...
详细信息
ISBN:
(纸本)9783642174513
We present a unified treatment for modeling Coulomb and viscous friction within multi-rigid body simulation using the principle of maximum dissipation. This principle is used to build two different methods-an event-driven impulse-based method and a time stepping method-for modeling contact. The same principle is used to effect joint friction in articulated mechanisms. Experiments show that the contact models are able to be solved faster and more robustly than alternative models. Experiments on the joint friction model show that it is as accurate as a standard model while permitting much larger simulation step sizes to be employed.
Reconfiguring chain-type modular robots has been considered a difficult problem scaling poorly with increasing numbers of modules. We address the reconfiguration problem for robots in 2D by presenting centralized and ...
详细信息
ISBN:
(纸本)9783642174513
Reconfiguring chain-type modular robots has been considered a difficult problem scaling poorly with increasing numbers of modules. We address the reconfiguration problem for robots in 2D by presenting centralized and decentralized algorithms based on the Carpenter's Rule Theorem [4]. The theorem guarantees the existence of instantaneous collision-free unfolding motions which monotonically increase the distance between all joint pairs until an open chain is straightened or a closed chain is convexified. The motions can be found by solving a convex program. Compared to the centralized version, the decentralized algorithm utilizes local proximity sensing and limited communications between subsets of nearby modules. Because the decentralized version reduces the number of joint pairs considered in each convex optimization, it is a practical solution for large number of modules.
暂无评论