Nearest neighbor searching is a fundamental building block of most sampling-based motion planners. We present a novel method for fast exact nearest neighbor searching in SE(3)-the 6 dimensional space that represents r...
详细信息
ISBN:
(纸本)9783319165950;9783319165943
Nearest neighbor searching is a fundamental building block of most sampling-based motion planners. We present a novel method for fast exact nearest neighbor searching in SE(3)-the 6 dimensional space that represents rotations and translations in 3 dimensions. SE(3) is commonly used when planning the motions of rigid body robots. Our approach starts by projecting a 4-dimensional cube onto the 3-sphere that is created by the unit quaternion representation of rotations in the rotational group SO(3). We then use 4 kd-trees to efficiently partition the projected faces (and their negatives). We propose efficient methods to handle the recursion pruning checks that arise with this kd-tree splitting approach, discuss splitting strategies that support dynamic data sets, and extend this approach to SE(3) by incorporating translations. We integrate our approach into RRT and RRT* and demonstrate the fast performance and efficient scaling of our nearest neighbor search as the tree size increases.
We introduce a novel optimization-based motion planner, Stochastic Extended LQR (SELQR), which computes a trajectory and associated linear control policy with the objective of minimizing the expected value of a user-d...
详细信息
ISBN:
(纸本)9783319165950;9783319165943
We introduce a novel optimization-based motion planner, Stochastic Extended LQR (SELQR), which computes a trajectory and associated linear control policy with the objective of minimizing the expected value of a user-defined cost function. SELQR applies to robotic systems that have stochastic non-linear dynamics with motion uncertainty modeled by Gaussian distributions that can be state-and control-dependent. In each iteration, SELQR uses a combination of forward and backward value iteration to estimate the cost-to-come and the cost-to-go for each state along a trajectory. SELQR then locally optimizes each state along the trajectory at each iteration to minimize the expected total cost, which results in smoothed states that are used for dynamics linearization and cost function quadratization. SELQR progressively improves the approximation of the expected total cost, resulting in higher quality plans. For applications with imperfect sensing, we extend SELQR to plan in the robot's belief space. We show that our iterative approach achieves fast and reliable convergence to high-quality plans in multiple simulated scenarios involving a car-like robot, a quadrotor, and a medical steerable needle performing a liver biopsy procedure.
Motion vectors (MVs) characterize the movement of pixel blocks in video streams and are readily available. MVs not only allow us to avoid expensive feature transform and correspondence computations but also provide th...
详细信息
ISBN:
(纸本)9783319165950;9783319165943
Motion vectors (MVs) characterize the movement of pixel blocks in video streams and are readily available. MVs not only allow us to avoid expensive feature transform and correspondence computations but also provide the motion information for both the environment and moving obstacles. This enables us to develop a new framework that is capable of simultaneous localization, scene mapping, and moving obstacle tracking. This method first extracts planes from MVs and their corresponding pixel macro blocks (MBs) using properties of plane-induced homographies. We then classify MBs as stationary or moving using geometric constraints on MVs. Planes are labeled as part of the stationary scene or moving obstacles using MB voting. Therefore, we can establish planes as observations for extended Kalman filters (EKFs) for both the stationary scene and moving objects. We have implemented the proposed method. The results show that the proposed method can establish plane-based rectilinear scene structure and detect moving objects while achieving similar localization accuracy of 1-Point EKF. More specifically, the system detects moving obstacles at a true positive rate of 96.6% with a relative absolution trajectory error of no more than 2.53%.
Disaster recovery robots must operate in unstructured environments where wheeled or tracked motion may not be feasible or where it may be subject to extreme slip. Many industrial disaster scenarios also preclude relia...
详细信息
ISBN:
(纸本)9783319074887;9783319074870
Disaster recovery robots must operate in unstructured environments where wheeled or tracked motion may not be feasible or where it may be subject to extreme slip. Many industrial disaster scenarios also preclude reliance on GNSS or other external signals as robots are deployed indoors or underground. Two of the candidates for precise positioning in these scenarios are visual odometry and inertial navigation. This paper presents some practical experience in the design and analysis of a combined visual and inertial odometry system for the Carnegie Mellon University Highly Intelligent Mobile Platform (CHIMP);a humanoid robot competing in the DARPA robotics Challenge.
The optimal trajectory with respect to some metric may require very many switches between controls, or even infinitely many, a phenomenon called chattering;this can be problematic for existing motion planning algorith...
详细信息
ISBN:
(纸本)9783319165950;9783319165943
The optimal trajectory with respect to some metric may require very many switches between controls, or even infinitely many, a phenomenon called chattering;this can be problematic for existing motion planning algorithms that plan using a finite set of motion primitives. One remedy is to add some penalty for switching between controls. This paper explores the implications of this switching cost for optimal trajectories, using rigid bodies in the plane (which have been studied extensively in the cost-free-switch model) as an example system. Blatt's Indifference Principle (BIP) is used to derive necessary conditions on optimal trajectories;Lipschitzian optimization techniques together with an A* search yield an algorithm for finding trajectories that can arbitrarily approximate the optimal trajectories.
Mapping a rivers course and width provides valuable information to help understand the ecology, topology and health of a particular environment. Such maps can also be useful to determine whether specific surface vesse...
详细信息
ISBN:
(纸本)9783319074887;9783319074870
Mapping a rivers course and width provides valuable information to help understand the ecology, topology and health of a particular environment. Such maps can also be useful to determine whether specific surface vessels can traverse the rivers. While rivers can be mapped from satellite imagery, the presence of vegetation, sometimes so thick that the canopy completely occludes the river, complicates the process of mapping. Here we propose the use of a micro air vehicle flying under the canopy to create accurate maps of the environment. We study and present a system that can autonomously explore rivers without any prior information, and demonstrate an algorithm that can guide the vehicle based upon local sensors mounted on board the flying vehicle that can perceive the river, bank and obstacles. Our field experiments demonstrate what we believe is the first autonomous exploration of rivers by an autonomous vehicle. We show the 3D maps produced by our system over runs of 100-450 meters in length and compare guidance decisions made by our system to those made by a human piloting a boat carrying our system over multiple kilometers.
This paper addresses a team of cooperating vehicles performing autonomous deliveries in urban environments. The cooperating team comprises two vehicles with complementary capabilities, a truck restricted to travel alo...
详细信息
ISBN:
(纸本)9783319165950;9783319165943
This paper addresses a team of cooperating vehicles performing autonomous deliveries in urban environments. The cooperating team comprises two vehicles with complementary capabilities, a truck restricted to travel along a street network, and a quadrotor micro-aerial vehicle of capacity one that can be deployed from the truck to perform deliveries. The problem is formulated as an optimal path planning problem on a graph and the goal is to find the shortest cooperative route enabling the quadrotor to deliver items at all requested locations. The problem is shown to be NP-hard using a reduction from the Travelling Salesman Problem and an algorithmic solution is proposed using a graph transformation to the Generalized Travelling Salesman Problem, which can be solved using existing methods. Simulation results compare the performance of the presented algorithms and demonstrate examples of delivery route computations over real urban street maps.
This paper presents a controlled tying approach for knots using fixtures and simple pulling motions applied to the ends of string. Each fixture is specific to a particular knot;the paper gives a design process that al...
详细信息
ISBN:
(纸本)9783319165950;9783319165943
This paper presents a controlled tying approach for knots using fixtures and simple pulling motions applied to the ends of string. Each fixture is specific to a particular knot;the paper gives a design process that allows a suitable fixture to be designed for an input knot. Knot tying is separated into two phases. In the first phase, a fixture is used to loosely arrange the string around a set of rods, with the required topology of the given knot. In the second phase, the string is pulled taut and slid along the rods (the tightening fixture) in a direction such that the cross-sections of the rods get closer together, allowing controlled tightening. Successful tying is shown for two interesting cases: a "double coin" knot design, and the top of a shoelace knot.
This carefully edited volume is the outcome of the eleventh edition of the Workshop on Algorithmic Foundations of robotics (WAFR), which is the premier venue showcasing cutting edge research in algorithmic robotics. T...
详细信息
ISBN:
(数字)9783319165950
ISBN:
(纸本)9783319165943;9783319165950
This carefully edited volume is the outcome of the eleventh edition of the Workshop on Algorithmic Foundations of robotics (WAFR), which is the premier venue showcasing cutting edge research in algorithmic robotics. The eleventh WAFR, which was held August 3-5, 2014 at Boazii University in Istanbul, Turkey continued this tradition. This volume contains extended versions of the 42 papers presented at WAFR. These contributions highlight the cutting edge research in classical robotics problems (e.g. manipulation, motion, path, multi-robot and kinodynamic planning), geometric and topological computation in robotics as well novel applications such as informative path planning, active sensing and surgical planning. This book - rich by topics and authoritative contributors - is a unique reference on the current developments and new directions in the field of algorithmic foundations.
This paper presents a polynomial time approximation algorithm for Multi-Robot Routing. The Multi-Robot Routing problem seeks to plan paths for a team of robots to visit a large number of interchangeable goal locations...
详细信息
ISBN:
(纸本)9783319165950;9783319165943
This paper presents a polynomial time approximation algorithm for Multi-Robot Routing. The Multi-Robot Routing problem seeks to plan paths for a team of robots to visit a large number of interchangeable goal locations as quickly as possible. As a result of providing a constant factor bound on the suboptimality of the total distance any robot travels, the total completion time, or makespan, for robots to visit every goal vertex using this plan is no more than 5 times the optimal completion time. This result is significant because it provides a rigorous guarantee on time optimality, important in applications in which teams of robots carry out time-critical missions. These applications include autonomous exploration, surveillance, first response, and search and rescue.
暂无评论