We introduce the notion of low-discrepancy curves and use it to solve the problem of optimally covering space. In doing so, we extend the notion of low-discrepancy sequences in such a way that sufficiently smooth curv...
详细信息
ISBN:
(纸本)9783540684046
We introduce the notion of low-discrepancy curves and use it to solve the problem of optimally covering space. In doing so, we extend the notion of low-discrepancy sequences in such a way that sufficiently smooth curves with low discrepancy properties can be defined and generated. Based on a class of curves that cover the unit square in an efficient way, we define induced low discrepancy curves in Riemannian spaces. This allows us to efficiently cover an arbitrarily chosen abstract surface that admits a diffeomorphism to the unit square. We demonstrate the application of these ideas by presenting concrete examples of low-discrepancy curves on some surfaces that are of interest in robotics.
We quantitatively analyze the performance of exact and approximate nearest-neighbors algorithms on increasingly high-dimensional problems in the context of sampling-based motion planning. We study the impact of the di...
详细信息
ISBN:
(纸本)9783540684046
We quantitatively analyze the performance of exact and approximate nearest-neighbors algorithms on increasingly high-dimensional problems in the context of sampling-based motion planning. We study the impact of the dimension, number of samples, distance metrics, and sampling schemes on the efficiency and accuracy of nearest-neighbors algorithms. Efficiency measures computation time and accuracy indicates similarity between exact and approximate nearest neighbors. Our analysis indicates that after a critical dimension, which varies between 15 and 30, exact nearest-neighbors algorithms examine almost all the samples. As a result, exact nearest-neighbors algorithms become impractical for sampling-based motion planners when a considerably large number of samples needs to be generated. The impracticality of exact nearest-neighbors algorithms motivates the use of approximate algorithms, which trade off accuracy for efficiency. We propose a simple algorithm, termed Distance-based Projection onto Euclidean Space (DPES), which computes approximate nearest neighbors by using a distance-based projection of high-dimensional metric spaces onto low-dimensional Euclidean spaces. Our results indicate DPES achieves high efficiency and only a negligible loss in accuracy.
This paper describes an intuitive geometric algorithm for the localization of mobile nodes in networks of sensors and robots using range-only or angle-only measurements. The algorithm is a minimalistic approach to loc...
详细信息
ISBN:
(纸本)9783540684046
This paper describes an intuitive geometric algorithm for the localization of mobile nodes in networks of sensors and robots using range-only or angle-only measurements. The algorithm is a minimalistic approach to localization and tracking when dead reckoning is too inaccurate to be useful. The only knowledge required about the mobile node is its maximum speed. Geometric regions are formed and grown to account for the motion of the mobile node. New measurements introduce new constraints which are propagated back in time to refine previous localization regions. The mobile robots are passive listeners while the sensor nodes actively broadcast making the algorithm scalable to many mobile nodes while maintaining the privacy of individual nodes. We prove that the localization regions found are optimal-that is, they are the smallest regions which must contain the mobile node at that time. We prove that each new measurement requires quadratic time in the number of measurements to update the system, however, we demonstrate experimentally that this call be reduced to constant time.
We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the sno...
详细信息
ISBN:
(纸本)9783540684046
We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a snowblower passes over each region along the tour, it displaces snow into a nearby region. The constraint is that if the snow is piled too high, then the snowblower cannot clear the pile. We give all algorithmic study of the SBP. We show that in general, the problem is NP-complete, and we present polynomial-time approximation algorithms for removing snow tinder various assumptions about the operation of the snowblower. Most commercially available snowblowers allow the user to control the direction in which the snow is thrown. We differentiate between the cases in which the snow can be thrown ill any direction, in any direction except backwards, and only to the right. For all cases, we give constant-factor approximation algorithms;the constants increase as the throw direction becomes more restricted. Our results are also applicable to robotic vacuuming (or lawnmowing) with bounded capacity dust bin and to some versions of material-handling problems, in which the goal is to rearrange cartons on the floor of a warehouse.
The International Symposium on Experimental robotics (ISER) is a series of bi-annual meetings which are organized in a rotating fashion around North America, Europe and Asia/Oceania. The goal of ISER is to provide a f...
ISBN:
(数字)9783540774570
ISBN:
(纸本)9783540774563
The International Symposium on Experimental robotics (ISER) is a series of bi-annual meetings which are organized in a rotating fashion around North America, Europe and Asia/Oceania. The goal of ISER is to provide a forum for research in robotics that focuses on novelty of theoretical contributions validated by experimental results. The meetings are conceived to bring together, in a small group setting, researchers from around the world who are in the forefront of experimental robotics research. This unique reference presents the latest advances across the various fields of robotics, with ideas that are not only conceived conceptually but also explored experimentally. It collects contributions on the current developments and new directions in the field of experimental robotics, which are based on the papers presented at the 10th ISER held in Rio de Janeiro, July 2006.
Automatic motion planning has applications ranging from traditional robotics to computer-aided design to computational biology and chemistry. While randomized planners, such as probabilistic roadmap methods (PRMS) or ...
详细信息
ISBN:
(纸本)9783540684046
Automatic motion planning has applications ranging from traditional robotics to computer-aided design to computational biology and chemistry. While randomized planners, such as probabilistic roadmap methods (PRMS) or rapidly-exploring random trees (RRT), have been highly successful in solving many high degree of freedom problems, there are still many scenarios in which we need better methods, e.g., problems involving narrow passages or which contain multiple regions that are best suited to different planners. In this work, we present RESAMPL, a motion planning strategy that uses local region information to make intelligent decisions about how and where to sample, which samples to connect together, and to find paths through the environment. Briefly, RESAMPL classifies regions based on the entropy of the samples in it, and their uses these classifications to further refine the sampling. Regions are placed in a region graph that encodes relationships between regions, e.g., edges correspond to overlapping regions. The strategy for connecting samples is guided by the region graph, and can be exploited in both multi-query and single-query scenarios. Our experimental results comparing RESAMPL to previous multi-query and single-query methods show that RFSAMPL is generally significantly faster and also usually requires fewer samples to solve the problem.
In this paper, we generate gaits for mixed systems, that is, dynamic systems that are subject to a set of non-holonomic constraints. What is unique about mixed systems is that when we express their dynamics in body co...
详细信息
ISBN:
(纸本)9783540684046
In this paper, we generate gaits for mixed systems, that is, dynamic systems that are subject to a set of non-holonomic constraints. What is unique about mixed systems is that when we express their dynamics in body coordinates, the motion of these system can be attributed to two decoupled terms: the geometric and dynamic phase shifts. In our prior work, we analyzed systems whose dynamic phase shift was null by definition. Purely mechanical and principally kinematic systems are two classes of mechanical systems that have this property. We generated gaits for these two classes of systems by intuitively evaluating their geometric phase shift and relating it to a volume integral tinder well-defined height functions. One of the contributions of this paper is to present a similar intuitive approach for computing the dynamic phase shift. We achieve this, by introducing a new scaled momentum variable that not only simplifies the momentum evolution equation but also allows us to introduce a new set of well-defined gamma functions which enable LIS to intuitively evaluate the dynamic phase shift. More specifically, by analyzing these novel gamma functions in a similar way to how we analyzed height functions, and by analyzing the sign-definiteness of the scaled momentum variable, we are able to ensure that the dynamic phase shift is non-zero solely along the desired fiber direction. Finally, we also introduce a novel mechanical system, the variable inertia snakeboard, which is a generalization of the original snakeboard that was previously studied in the literature. Not only does this general system help us identify regions of the base space where we can not define a certain type of gaits, but also it helps us verify the generality and applicability of our gait generation approach.
Grasping and manipulation skills are at the core of the development of modern robotic systems. With the introduction of robotics in new applications involving unstructured environments (e.g. space, undersea, surgery),...
ISBN:
(数字)9783540774594
ISBN:
(纸本)9783540774587
Grasping and manipulation skills are at the core of the development of modern robotic systems. With the introduction of robotics in new applications involving unstructured environments (e.g. space, undersea, surgery), intelligent manipulation and grasping has become a crucial research area. The authors have developed an internationally recognized expertise in this area. Additionally, they designed and built several prototypes which attracted the attention of the scientific community. Their work was reported in several publications which appeared in the most renowned journals and conferences. The purpose of this book is to summarize years of research and to present, in an attractive format, the expertise developed by the authors on a new technology for graspingnamely under actuationwhich has achieved great success both in theory and in practice. This book is not intended to be used as a textbook but could be used as a reference at the post-graduate level.
This paper presents a method of computing efficient and natural-looking motions for humanoid robots walking on varied terrain. It uses a small set of high-quality motion primitives (such as a fixed gait on flat ground...
详细信息
ISBN:
(纸本)9783540684046
This paper presents a method of computing efficient and natural-looking motions for humanoid robots walking on varied terrain. It uses a small set of high-quality motion primitives (such as a fixed gait on flat ground) that have been generated offline. But rather than restrict motion to these primitives, it uses them to derive a sampling strategy for a probabilistic, sample-based planner. Results in simulation on several different terrains demonstrate a reduction in planning time and a, marked increase in motion quality.
暂无评论