We present a sample-based replanning strategy for driving partially-observable, high-dimensional robotic systems to a desired goal. At each time step, it uses forward simulation of randomly-sampled open-loop controls ...
详细信息
ISBN:
(纸本)9783642174513
We present a sample-based replanning strategy for driving partially-observable, high-dimensional robotic systems to a desired goal. At each time step, it uses forward simulation of randomly-sampled open-loop controls to construct a belief-space search tree rooted at its current belief state. Then, it executes the action at the root that leads to the best node in the tree. As a node quality metric we use Monte Carlo simulation to estimate the likelihood of success under the QMDP belief-space feedback policy, which encourages the robot to take information-gathering actions as needed to reach the goal. The technique is demonstrated on target-finding and localization examples in up to 5D state spacess.
In this paper we examine some of the current trends in building robots capable of self-assembly, self-reconfiguration, and self-organization, and we describe two new approaches to creating programmable matter. We expl...
详细信息
ISBN:
(纸本)9783642147432
In this paper we examine some of the current trends in building robots capable of self-assembly, self-reconfiguration, and self-organization, and we describe two new approaches to creating programmable matter. We explain the notion of building robot shapes by self-dissasembly, the process of "sculpting" a desired shape from a connected block of robotic modules by removing units, and discuss lessons learned with a robot system capable of self-disassembly. We also describe the notion of incorporating passive components such as rigid bars in the body of a modular robot and lessons learned from the development;of a first system prototype.
In this paper we propose novel algorithms for reconfiguring modular robots that are composed of n atoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or...
详细信息
ISBN:
(纸本)9783642003110
In this paper we propose novel algorithms for reconfiguring modular robots that are composed of n atoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or detach from faces of neighboring atoms. For universal reconfiguration, atoms must be arranged in 2 x 2 x 2 modules. We respect certain physical constraints: each atom reaches at most unit velocity and (via expansion) can displace at most one other atom. We require that one of the atoms can store a map of the target configuration. Our algorithms involve a total of O(n(2)) such atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n(2)) parallel steps [8, 10, 4] or do not respect the constraints mentioned above [1]. In fact, in the setting considered, our algorithms are optimal, in the sense that certain reconfigurations require Omega(n) parallel steps. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configurations.
Computing the Minkowski sum of two polyhedra exactly has been shown difficult. Despite its fundamental role in many geometric problems in robotics, to the best of our knowledge, no 3-d Minkowski sum software for gener...
详细信息
ISBN:
(纸本)9783642003110
Computing the Minkowski sum of two polyhedra exactly has been shown difficult. Despite its fundamental role in many geometric problems in robotics, to the best of our knowledge, no 3-d Minkowski sum software for general polyhedra is available to the public. One of the main reasons is the difficulty of implementing the existing methods. There are two main approaches for computing Minkowski sums: divide-and-conquer and convolution. The first approach decomposes the input polyhedra into convex pieces, computes the Minkowski sums between a pair of convex pieces, and unites all the pairwise Minkowski sums. Although conceptually simple, the major problems of this approach include: (1) The size of the decomposition and the pairwise Minkowski sums can be extremely large and (2) robustly computing the union of a large number of components can be very tricky. On the other hand, convolving two polyhedra can be done more efficiently. The resulting convolution is a superset of the Minkowski sum boundary. For non-convex inputs, filtering or trimming is needed. This usually involves computing (1) the arrangement of the convolution and its substructures and (2) the winding numbers for the arrangement subdivisions. Both computations are difficult to implement robustly in 3-d. In this paper we present a new approach that is simple to implement and can efficiently generate accurate Minkowski sum boundary. Our method is convolution based but it avoids computing the 3-d arrangement and the winding numbers. The premise of our method is to reduce the trimming problem to the problems of computing 2-d arrangements and collision detection, which are much better understood in the literature. To maintain the simplicity, we intentionally sacrifice the exactness. While our Method generates exact solutions in most cases, it does not produce low dimensional boundaries, e.g., boundaries enclosing zero volume. We classify our method as 'nearly exact' to distinguish it from the exact and approximate
The problem of generating uniform deterministic samples over the rotation group, SO(3), is fundamental to computational biology, chemistry, physics, and numerous branches of computer science. We present the best-known...
详细信息
ISBN:
(纸本)9783642003110
The problem of generating uniform deterministic samples over the rotation group, SO(3), is fundamental to computational biology, chemistry, physics, and numerous branches of computer science. We present the best-known method to date for constructing incremental, deterministic grids on SO(3);it provides: (1) the lowest metric distortion for grid neighbor edges, (2) optimal dispersion-reduction with each additional sample, (3) explicit neighborhood structure, and (4) equivolumetric partition of SO(3) by the grid cells. We also demonstrate the use of the sequence on motion planning problems.
While spatial sampling of points has already received much attention, the motion planning problem can also be viewed as a process which samples the function space of paths. We define a search space to be a set of cand...
详细信息
ISBN:
(纸本)9783642147432
While spatial sampling of points has already received much attention, the motion planning problem can also be viewed as a process which samples the function space of paths. We define a search space to be a set of candidate paths and consider the problem of designing a search space which is most likely to produce a solution given a probabilistic representation of all possible environments. We introduce the concept of relative completeness which is the prior probability, before the environment, is specified, of producing a solution path in a bounded amount of computation. We show how this probability is related to the mutual separation of the set of paths searched. The problem of producing an optimal set can be related to the maximum k-facility dispersion problem which is known to be NP-hard. We propose a greedy algorithm for producing a good set of paths and demonstrate that it produces results with both low dispersion and high prior probability of success.
We consider the inverse problem of discovering the location of a source from very sparse point measurements in a bounded domain that contains impenetrable (and possibly unknown) obstacles. We present an adaptive algor...
详细信息
ISBN:
(纸本)9783642003110
We consider the inverse problem of discovering the location of a source from very sparse point measurements in a bounded domain that contains impenetrable (and possibly unknown) obstacles. We present an adaptive algorithm for determining the measurement locations, and ultimately, the source locations. Specifically, we investigate source discovery for the Laplace operator, though the approach can be applied to more general linear partial differential operators. We propose a strategy for the case when the obstacles are unknown and the environment has to be mapped out using a range sensor concurrently with source discovery.
This paper studies modeling of tangential compliance as two rigid bodies collide in the space. Stronge's spring-based contact structure [13, pp. 95-96] is extended to three dimensions. Slip or stick is indicated b...
详细信息
ISBN:
(纸本)9783642174513
This paper studies modeling of tangential compliance as two rigid bodies collide in the space. Stronge's spring-based contact structure [13, pp. 95-96] is extended to three dimensions. Slip or stick is indicated by the tangential motion of a massless particle connected to the contact point (viewed as an infinitesimal region) on one body via three orthogonal springs. We show that the effect of tangential compliance can be analyzed using normal impulse rather than time, contrary to a previous claim by Stronge. This is primarily due to the ability of updating the elastic energies of the three springs without knowledge of their stiffnesses or length changes. The change rates, nevertheless, are computable. So are sliding velocity and tangential impulse. The latter is then integrated into impact equations and contact kinematics, making the whole system driven by normal impulse alone. Examples include a ball and a pencil bouncing on a table, and a masse billiard shot. The theory has potential impact on impulsive robotic manipulation in which the ability to deal with friction and compliance is vital for skillful maneuvers.
We propose data structures for answering a geodesic-distance query between two query points in a two-dimensional or three-dimensional dynamic environment, in which obstacles are deforming continuously. Each obstacle i...
详细信息
ISBN:
(纸本)9783642003110
We propose data structures for answering a geodesic-distance query between two query points in a two-dimensional or three-dimensional dynamic environment, in which obstacles are deforming continuously. Each obstacle in the environment is modeled as the convex hull of a continuously deforming point cloud. The key to our approach is to avoid maintaining the convex hull of each point cloud explicitly but still able to retain sufficient geometric information to estimate geodesic distances in the free space.
We describe the architecture, algorithms, and experimental testbed for the deployment of large numbers of cooperating robots, and applications to tasks like manipulation and transportation. The coordination between ro...
详细信息
ISBN:
(纸本)9783642147432
We describe the architecture, algorithms, and experimental testbed for the deployment of large numbers of cooperating robots, and applications to tasks like manipulation and transportation. The coordination between robots is completely decentralized to enable scaling up to large numbers of robots. There is no labeling or identification of robots and all robots (and their software) are identical allowing robustness to failures, ease of programming, and modularity enabling the addition or deletion of robots from the team. Our approach requires minimal communication and sensing and the proposed controllers are based only on local information. Moreover, our architecture facilitates asymmetric communication from one or more supervisory agents that can broadcast information to all robots and close the loop by acquiring abstract, high level information related to the supervised robots. We discuss the hardware and software implementation, the architecture, and present recent experimental results.
暂无评论