Robot trajectories comparison: a statistical approach

The task of planning a collision-free trajectory from a start to a goal position is fundamental for an autonomous mobile robot. Although path planning has been extensively investigated since the beginning of robotics, there is no agreement on how to measure the performance of a motion algorithm. This paper presents a new approach to perform robot trajectories comparison that could be applied to any kind of trajectories and in both simulated and real environments. Given an initial set of features, it automatically selects the most significant ones and performs a statistical comparison using them. Additionally, a graphical data visualization named polygraph which helps to better understand the obtained results is provided. The proposed method has been applied, as an example, to compare two different motion planners, FM(2) and WaveFront, using different environments, robots, and local planners.

Sparsification of motion-planning roadmaps by edge contraction

Roadmaps constructed by the recently introduced PRM* algorithm for asymptotically-optimal motion planning encode high-quality paths yet can be extremely dense. We consider the problem of [Formula: see text] the roadmap, i.e. reducing its size, while minimizing the degradation of the quality of paths that can be extracted from the resulting roadmap. We present a simple, effective sparsifying algorithm, called [Formula: see text][Formula: see text] (RSEC). The primitive operation used by RSEC is [Formula: see text]—the contraction of a roadmap edge ( v′, v″) to a new vertex [Formula: see text] and the connection of the new vertex [Formula: see text] to the neighboring vertices of the contracted edge’s vertices (i.e. to all neighbors of [Formula: see text] and [Formula: see text]). For certain scenarios, we compress more than 97% of the edges and vertices of a given roadmap at the cost of degradation of average shortest path length by at most 4%.

Multi-agent plan reconfiguration under local LTL specifications

We propose a cooperative motion and task planning scheme for multi-agent systems where the agents have independently assigned local tasks, specified as linear temporal logic formulas. These tasks contain hard and soft sub-specifications. A least-violating initial plan is synthesized first for the potentially infeasible task and the partially-known workspace. This discrete plan is then implemented by the potential-field-based navigation controllers. While the system runs, each agent updates its knowledge about the workspace via its sensing capability and shares this knowledge with its neighbouring agents. Based on the knowledge update, each agent verifies and revises its motion plan in real time. It is ensured that the hard specification is always fulfilled for safety and the satisfaction for the soft specification is improved gradually. The design is distributed as only local interactions are assumed. The overall framework is demonstrated by a case study and an experiment.

Randomized path planning on vector fields

Given a vector field defined on a robot’s configuration space, in which the vector field represents the system drift, e.g. a wind velocity field, water current flow, or gradient field for some potential function, we present a randomized path planning algorithm for reaching a desired goal configuration. Taking the premise that moving against the vector field requires greater control effort, and that minimizing the control effort is both physically meaningful and desirable, we propose an integral functional for control effort, called the upstream criterion, that measures the extent to which a path goes against the given vector field. The integrand of the upstream criterion is then used to construct a rapidly exploring random tree (RRT) in the configuration space, in a way such that random nodes are generated with an a priori specified bias that favors directions indicated by the vector field. The resulting planning algorithm produces better quality paths while preserving many of the desirable features of RRT-based planning, e.g. the Voronoi bias property, computational efficiency, algorithmic simplicity, and straightforward extension to constrained and nonholonomic problems. Extensive numerical experiments demonstrate the advantages of our algorithm vis-à-vis existing optimality criterion-based planning algorithms.

Sampling-based A* algorithm for robot path-planning

This paper presents a generalization of the classic A* algorithm to the domain of sampling-based motion planning. The root assumptions of the A* algorithm are examined and reformulated in a manner that enables a direct use of the search strategy as the driving force behind the generation of new samples in a motion graph. Formal analysis is presented to show probabilistic completeness and convergence of the method. This leads to a highly exploitative method which does not sacrifice entropy. Many improvements are presented to this versatile method, most notably, an optimal connection strategy, a bias towards the goal region via an Anytime A* heuristic, and balancing of exploration and exploitation on a simulated annealing schedule. Empirical results are presented to assess the proposed method both qualitatively and quantitatively in the context of high-dimensional planning problems. The potential of the proposed methods is apparent, both in terms of reliability and quality of solutions found.

Needle Steering in 3-D Via Rapid Replanning

Steerable needles have the potential to improve the effectiveness of needle-based clinical procedures such as biopsy and drug delivery by improving targeting accuracy and reaching previously inaccessible targets that are behind sensitive or impenetrable anatomical regions. We present a new needle steering system capable of automatically reaching targets in 3-D environments while avoiding obstacles and compensating for real-world uncertainties. Given a specification of anatomical obstacles and a clinical target (e.g., from preoperative medical images), our system plans and controls needle motion in a closed-loop fashion under sensory feedback to optimize a clinical metric. We unify planning and control using a new fast algorithm that continuously replans the needle motion. Our rapid replanning approach is enabled by an efficient sampling-based rapidly exploring random tree (RRT) planner that achieves orders-of-magnitude reduction in computation time compared with prior 3-D approaches by incorporating variable curvature kinematics and a novel distance metric for planning. Our system uses an electromagnetic tracking system to sense the state of the needle tip during the procedure. We experimentally evaluate our needle steering system using tissue phantoms and animal tissue ex vivo. We demonstrate that our rapid replanning strategy successfully guides the needle around obstacles to desired 3-D targets with an average error of less than 3 mm.

Receding horizon temporal logic control in dynamic environments

We present a receding horizon method for controlling an autonomous vehicle that must satisfy a rich mission specification over service requests occurring at the regions of a partitioned environment. The overall mission specification consists of a temporal logic statement over a set of static, a priori known requests, a regular expression over a set of dynamic requests that can be sensed only locally, and a servicing priority order over these dynamic requests. Our approach is based on two main steps. First, we construct an abstraction for the motion of the vehicle in the environment by using input–output linearization and assignment of vector fields to the regions in the partition. Second, a receding horizon controller computes local plans within the sensing range of the vehicle such that both local and global mission specifications are satisfied. We implement and evaluate our method through experiments and simulations consisting of a quadrotor performing a persistent surveillance task over a planar grid environment.

Motion Planning of a Humanoid Robot in a Complex Environment Using RRT and Spatiotemporal Post-Processing Techniques

This paper presents a motion planning method which provides a complete whole body trajectory of a humanoid robot traveling in a complex environment with various life items, steps, slopes, gates, walls, etc. A two-stage planning scheme is employed to simplify the problem of discontinuously changing dynamical constraints, where a sequence of double-support postures is planned in the first stage, and a continuous and smooth trajectory interpolates it in the second stage. RRT is utilized in the both stages in order to exploit the whole body with a large degree-of-freedom and perform in such a three-dimensionally intricate field. An inevitable issue of that random-sampling-based approach is that the searched trajectory is necessarily jaggy and detouring. The proposed method includes effective post-processing techniques for each stage, which are mandatory in practice. In the first stage, a necessary condition is that any pair of adjacent postures has to share one supporting foot as the pivot. A key idea is to insert intermediate postures between a pair of non-adjacent milestones with a cross-combination of the support feet to bypass and average a sequence of double-support transitions. The optimal sequence of the possible transitions is found by applying Dijkstra's method. In the second stage, an idea of the center of mass (COM)-enforcement to artificially constrain the trajectory of COM on one based on the mass-concentrated approximation is proposed, expecting that a solution can be found on this manifold. A continuous and smooth trajectory which satisfies the geometric constraint is planned by RRT and NURBS interpolation, and then, the temporal property of the trajectory is adjusted based on the dynamic programming to satisfy the dynamical constraint without breaking the geometric constraint. The performance was examined in a mock field of a living room. Comparing with a naive method only with RRT-connect, it substantially shortened the total travel distance in many cases. It also succeeded to plan dynamically feasible walking trajectories on that complex terrain.

Sampling-based robotic information gathering algorithms

We propose three sampling-based motion planning algorithms for generating informative mobile robot trajectories. The goal is to find a trajectory that maximizes an information quality metric (e.g. variance reduction, information gain, or mutual information) and also falls within a pre-specified budget constraint (e.g. fuel, energy, or time). Prior algorithms have employed combinatorial optimization techniques to solve these problems, but existing techniques are typically restricted to discrete domains and often scale poorly in the size of the problem. Our proposed rapidly exploring information gathering (RIG) algorithms combine ideas from sampling-based motion planning with branch and bound techniques to achieve efficient information gathering in continuous space with motion constraints. We provide analysis of the asymptotic optimality of our algorithms, and we present several conservative pruning strategies for modular, submodular, and time-varying information objectives. We demonstrate that our proposed techniques find optimal solutions more quickly than existing combinatorial solvers, and we provide a proof-of-concept field implementation on an autonomous surface vehicle performing a wireless signal strength monitoring task in a lake.

Convex optimization of nonlinear feedback controllers via occupation measures

The construction of feedback control laws for underactuated nonlinear robotic systems with input saturation limits is crucial for dynamic robotic tasks such as walking, running, or flying. Existing techniques for feedback control design are either restricted to linear systems, rely on discretizations of the state space, or require solving a nonconvex optimization problem that requires feasible initialization. This paper presents a method for designing feedback controllers for polynomial systems that maximize the size of the time-limited backwards reachable set (BRS). In contrast to traditional approaches based on Lyapunov’s criteria for stability, we rely on the notion of occupation measures to pose this problem as an infinite-dimensional linear program which can then be approximated in finite dimension via semidefinite programs (SDPs). The solution to each SDP yields a polynomial control policy and an outer approximation of the largest achievable BRS which is well suited for use in a trajectory library or feedback motion planning algorithm. We demonstrate the efficacy and scalability of our approach on six nonlinear systems. Comparisons to an infinite-horizon linear quadratic regulator approach and an approach relying on Lyapunov’s criteria for stability are also included in order to illustrate the improved performance of the presented technique.

Motion planning with sequential convex optimization and convex collision checking

We present a new optimization-based approach for robotic motion planning among obstacles. Like CHOMP (Covariant Hamiltonian Optimization for Motion Planning), our algorithm can be used to find collision-free trajectories from naïve, straight-line initializations that might be in collision. At the core of our approach are (a) a sequential convex optimization procedure, which penalizes collisions with a hinge loss and increases the penalty coefficients in an outer loop as necessary, and (b) an efficient formulation of the no-collisions constraint that directly considers continuous-time safety Our algorithm is implemented in a software package called TrajOpt.

We report results from a series of experiments comparing TrajOpt with CHOMP and randomized planners from OMPL, with regard to planning time and path quality. We consider motion planning for 7 DOF robot arms, 18 DOF full-body robots, statically stable walking motion for the 34 DOF Atlas humanoid robot, and physical experiments with the 18 DOF PR2. We also apply TrajOpt to plan curvature-constrained steerable needle trajectories in the SE(3) configuration space and multiple non-intersecting curved channels within 3D-printed implants for intracavitary brachytherapy. Details, videos, and source code are freely available at: http://rll.berkeley.edu/trajopt/ijrr .

Interactive-rate Motion Planning for Concentric Tube Robots

Concentric tube robots may enable new, safer minimally invasive surgical procedures by moving along curved paths to reach difficult-to-reach sites in a patient's anatomy. Operating these devices is challenging due to their complex, unintuitive kinematics and the need to avoid sensitive structures in the anatomy. In this paper, we present a motion planning method that computes collision-free motion plans for concentric tube robots at interactive rates. Our method's high speed enables a user to continuously and freely move the robot's tip while the motion planner ensures that the robot's shaft does not collide with any anatomical obstacles. Our approach uses a highly accurate mechanical model of tube interactions, which is important since small movements of the tip position may require large changes in the shape of the device's shaft. Our motion planner achieves its high speed and accuracy by combining offline precomputation of a collision-free roadmap with online position control. We demonstrate our interactive planner in a simulated neurosurgical scenario where a user guides the robot's tip through the environment while the robot automatically avoids collisions with the anatomical obstacles.

Cache-Aware Asymptotically-Optimal Sampling-Based Motion Planning

We present CARRT* (Cache-Aware Rapidly Exploring Random Tree*), an asymptotically optimal sampling-based motion planner that significantly reduces motion planning computation time by effectively utilizing the cache memory hierarchy of modern central processing units (CPUs). CARRT* can account for the CPU's cache size in a manner that keeps its working dataset in the cache. The motion planner progressively subdivides the robot's configuration space into smaller regions as the number of configuration samples rises. By focusing configuration exploration in a region for periods of time, nearest neighbor searching is accelerated since the working dataset is small enough to fit in the cache. CARRT* also rewires the motion planning graph in a manner that complements the cache-aware subdivision strategy to more quickly refine the motion planning graph toward optimality. We demonstrate the performance benefit of our cache-aware motion planning approach for scenarios involving a point robot as well as the Rethink Robotics Baxter robot.

Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey

We review a range of techniques related to navigation of unmanned vehicles through unknown environments with obstacles, especially those that rigorously ensure collision avoidance (given certain assumptions about the system). This topic continues to be an active area of research, and we highlight some directions in which available approaches may be improved. The paper discusses models of the sensors and vehicle kinematics, assumptions about the environment, and performance criteria. Methods applicable to stationary obstacles, moving obstacles and multiple vehicles scenarios are all reviewed. In preference to global approaches based on full knowledge of the environment, particular attention is given to reactive methods based on local sensory data, with a special focus on recently proposed navigation laws based on model predictive and sliding mode control.

Sparse roadmap spanners for asymptotically near-optimal motion planning

Asymptotically optimal planners, such as PRM*, guarantee that solutions approach optimal as the number of iterations increases. Roadmaps with this property, however, may grow too large for storing on resource-constrained robots and for achieving efficient online query resolution. By relaxing optimality, asymptotically near-optimal planners produce sparser graphs by not including all edges. The idea stems from graph spanners, which produce sparse subgraphs that guarantee near-optimality. Existing asymptotically optimal and near-optimal planners, however, include all sampled configurations as roadmap nodes, meaning only infinite-size graphs have the desired properties. To address this limitation, this work describes SPARS, an algorithm that returns a sparse roadmap spanner. The method provides the following properties: (a) probabilistic completeness, (b) asymptotic near-optimality and (c) the probability of adding nodes to the spanner converges to zero as iterations increase. The last point suggests that finite-size data structures with asymptotic near-optimality in continuous spaces may indeed exist. The approach builds simultaneously a dense graph similar to PRM* and its roadmap spanner, meaning that upon construction an infinite-size graph is still needed asymptotically. An extension of SPARS is also presented, termed SPARS2, which removes the dependency on building a dense graph for constructing the sparse roadmap spanner and for which it is shown that the same desirable properties hold. Simulations for rigid-body motion planning show that algorithms for constructing sparse roadmap spanners indeed provide small data structures and result in faster query resolution. The rate of node addition is shown to decrease over time and practically the quality of solutions is considerably better than the theoretical bounds. Upon construction, the memory requirements of SPARS2 are significantly smaller but there is a small sacrifice in the size of the final spanner relative to SPARS.

Cellular Automata Based Real-Time Path-Planning for Mobile Robots

Intelligent mobile robotic agents demand optimal motion planners with minimal query time. Most contemporary algorithms lack one of these two required aspects. This paper proposes an efficient path-planning scheme based on cellular automata (CA) that generates optimal paths in the minimum time. A Cellular automaton is evolved over the entire search space and subsequently used for the determination of the shortest path. This approach generates a parent-child relationship for each cell in order to minimize the search time. Performance comparisons with A*, Dijkstra's, D* and MPCNN have proven it to be time-efficient. Analysis, simulation and experimental results have proven it to be a robust and complete path-planning scheme. Also it has demonstrated to be time-efficient in both static and dynamic environments.

FIRM: Sampling-based feedback motion-planning under motion uncertainty and imperfect measurements

In this paper we present feedback-based information roadmap (FIRM), a multi-query approach for planning under uncertainty which is a belief-space variant of probabilistic roadmap methods. The crucial feature of FIRM is that the costs associated with the edges are independent of each other, and in this sense it is the first method that generates a graph in belief space that preserves the optimal substructure property. From a practical point of view, FIRM is a robust and reliable planning framework. It is robust since the solution is a feedback and there is no need for expensive replanning. It is reliable because accurate collision probabilities can be computed along the edges. In addition, FIRM is a scalable framework, where the complexity of planning with FIRM is a constant multiplier of the complexity of planning with PRM. In this paper, FIRM is introduced as an abstract framework. As a concrete instantiation of FIRM, we adopt stationary linear quadratic Gaussian (SLQG) controllers as belief stabilizers and introduce the so-called SLQG-FIRM. In SLQG-FIRM we focus on kinematic systems and then extend to dynamical systems by sampling in the equilibrium space. We investigate the performance of SLQG-FIRM in different scenarios.

k-color multi-robot motion planning

We present a simple and natural extension of the multi-robot motion planning problem where the robots are partitioned into groups (colors), such that in each group the robots are interchangeable. Every robot is no longer required to move to a specific target, but rather to some target placement that is assigned to its group. We call this problem k- color multi-robot motion planning and provide a sampling-based algorithm specifically designed for solving it. At the heart of the algorithm is a novel technique where the k-color problem is reduced to several discrete multi-robot motion planning problems. These reductions amplify basic samples into massive collections of free placements and paths for the robots. We demonstrate the performance of the algorithm by an implementation for the case of disc robots and polygonal robots translating in the plane. We show that the algorithm successfully and efficiently copes with a variety of challenging scenarios, involving many robots, while a simplified version of this algorithm, that can be viewed as an extension of a prevalent sampling-based algorithm for the k-color case, fails even on simple scenarios. Interestingly, our algorithm outperforms a well established implementation of PRM for the standard multi-robot problem, in which each robot has a distinct color.

Three-dimensional coverage planning for an underwater inspection robot

To support autonomous, in-water inspection of a ship hull, we propose and implement new techniques for coverage path planning over complex 3D structures. Our main contribution is a comprehensive methodology for sampling-based design of inspection routes, including an algorithm for planning, an algorithm for smoothing, and an analysis of probabilistic completeness. The latter two outcomes are the first of their kind in the area of coverage planning. Our algorithms give high-quality solutions over expansive structures, and we demonstrate this with experiments in the laboratory and on a 75 m Coast Guard cutter.

CHOMP: Covariant Hamiltonian optimization for motion planning

In this paper, we present CHOMP (covariant Hamiltonian optimization for motion planning), a method for trajectory optimization invariant to reparametrization. CHOMP uses functional gradient techniques to iteratively improve the quality of an initial trajectory, optimizing a functional that trades off between a smoothness and an obstacle avoidance component. CHOMP can be used to locally optimize feasible trajectories, as well as to solve motion planning queries, converging to low-cost trajectories even when initialized with infeasible ones. It uses Hamiltonian Monte Carlo to alleviate the problem of convergence to high-cost local minima (and for probabilistic completeness), and is capable of respecting hard constraints along the trajectory. We present extensive experiments with CHOMP on manipulation and locomotion tasks, using seven-degree-of-freedom manipulators and a rough-terrain quadruped robot.

Online obstacle avoidance at high speeds

This paper presents an efficient algorithm for online avoidance of static obstacles that accounts for robot dynamics and actuator constraints. The robot trajectory (path and speed) is generated incrementally by avoiding obstacles optimally one at a time, thus reducing the original problem from one that avoids m obstacles to m simpler problems that avoid one obstacle each. The computational complexity of this planner is therefore linear in the number of obstacles, instead of the typical exponential complexity of traditional geometric planners. This approach is quite general and applicable to any cost function and to any robot dynamics; it is treated here for minimum time motions, a planar point mass robot, and circular obstacles. Numerical experiments demonstrate the algorithm for very cluttered environments (70 obstacles) and narrow passages. Upper and lower bounds on the motion time and on the path length were derived as functions of the Euclidean distance between the end points and the average obstacle size. Comparing a kinematic version of this algorithm to the RRT and RRT* planners showed significant advantages over both planners. The algorithm was demonstrated on an experimental mobile robot moving at high speeds in a known environment.

A snake-based scheme for path planning and control with constraints by distributed visual sensors

This paper proposes a robot navigation scheme using wireless visual sensors deployed in an environment. Different from the conventional autonomous robot approaches, the scheme intends to relieve massive on-board information processing required by a robot to its environment so that a robot or a vehicle with less intelligence can exhibit sophisticated mobility. A three-state snake mechanism is developed for coordinating a series of sensors to form a reference path. Wireless visual sensors communicate internal forces with each other along the reference snake for dynamic adjustment, react to repulsive forces from obstacles, and activate a state change in the snake body from a flexible state to a rigid or even to a broken state due to kinematic or environmental constraints. A control snake is further proposed as a tracker of the reference path, taking into account the robot's non-holonomic constraint and limited steering power. A predictive control algorithm is developed to have an optimal velocity profile under robot dynamic constraints for the snake tracking. They together form a unified solution for robot navigation by distributed sensors to deal with the kinematic and dynamic constraints of a robot and to react to dynamic changes in advance. Simulations and experiments demonstrate the capability of a wireless sensor network to carry out low-level control activities for a vehicle.

Dynamic walking and whole-body motion planning for humanoid robots: an integrated approach

This paper presents a general method for planning collision-free whole-body walking motions for humanoid robots. First, we present a randomized algorithm for constrained motion planning, that is used to generate collision-free statically balanced paths solving manipulation tasks. Then, we show that dynamic walking makes humanoid robots small-space controllable. Such a property allows to easily transform collision-free statically balanced paths into collision-free dynamically balanced trajectories. It leads to a sound algorithm which has been applied and evaluated on several problems where whole-body planning and walk are needed, and the results have been validated on a real HRP-2 robot.

Integrated task and motion planning in belief space

We describe an integrated strategy for planning, perception, state estimation and action in complex mobile manipulation domains based on planning in the belief space of probability distributions over states using hierarchical goal regression (pre-image back-chaining). We develop a vocabulary of logical expressions that describe sets of belief states, which are goals and subgoals in the planning process. We show that a relatively small set of symbolic operators can give rise to task-oriented perception in support of the manipulation goals. An implementation of this method is demonstrated in simulation and on a real PR2 robot, showing robust, flexible solution of mobile manipulation problems with multiple objects and substantial uncertainty.

Safety-oriented path planning for articulated robots

This work presents an approach to motion planning for robotic manipulators that aims at improving path quality in terms of safety. Safety is explicitly assessed using the quantity calleddanger field. The measure of safety can easily be embedded into a heuristic function that guides the exploration of the free configuration space. As a result, the resulting path is likely to have substantially higher safety margin when compared to one obtained by regular planning algorithms. To this end, four planning algorithms have been proposed. The first planner is based on volume trees comprised of bubbles of free configuration space, while the remaining ones represent modifications of classical sampling-based algorithms. Several numerical case studies are carried out to validate and compare the performance of the presented algorithms with respect to classical planners. The results indicate significantly lower danger metric for paths obtained by safety-oriented planners even with some decrease in running time.

Conditional Density Growth (CDG) model: a simplified model of RRT coverage for kinematic systems

It has been shown before that the Rapidly Exploring Random Tree (RRT) algorithm is probabilistically and resolution complete; and that the probability of finding a particular solution path can be related to the number of nodes. However, little analysis exists on the rate at which the tree covers the configuration space. In this paper, we present a stochastic difference equation which models how the tree covers the configuration space as a function of the number of nodes in the tree. Using two simplifying assumptions, appropriate for holonomic, kinematic systems in expansive configuration spaces, we derive closed-form solutions for the expected value and variance of configuration space coverage, which only depend on two easily computable parameters. Using a grid-based coverage measurement, we present experimental evidence supporting this model across a range of dimensions, obstacle densities, and parameter choices. Collecting data from 1000 RRTs, we provide evidence that configuration space coverage concentrates tightly around the expected coverage predicted by the model; and the results of the Chi-squared test suggest that the distribution of coverage across these runs is highly Gaussian. Together these results enable one to predict the expected coverage, along with a confidence interval, after a certain number of nodes have been added to the tree. We also applied the model to an example with extremely narrow passages and to a system with non-holonomic kinematics. The expected value prediction is still qualitatively accurate; but the rate constant is reduced and the variance is higher. Overall, in addition to its theoretical value, the model may find future application as an online measure of search-progress and problem difficulty, useful for adaptive variants of the basic RRT algorithm.

RRT*-SMART: A Rapid Convergence Implementation of RRT*

Many sampling based algorithms have been introduced recently. Among them Rapidly Exploring Random Tree (RRT) is one of the quickest and the most efficient obstacle free path finding algorithm. Although it ensures probabilistic completeness, it cannot guarantee finding the most optimal path. Rapidly Exploring Random Tree Star (RRT*), a recently proposed extension of RRT, claims to achieve convergence towards the optimal solution thus ensuring asymptotic optimality along with probabilistic completeness. However, it has been proven to take an infinite time to do so and with a slow convergence rate. In this paper an extension of RRT*, called as RRT*-Smart, has been prposed to overcome the limitaions of RRT*. The goal of the proposecd method is to accelerate the rate of convergence, in order to reach an optimum or near optimum solution at a much faster rate, thus reducing the execution time. The novel approach of the proposed algorithm makes use of two new techniques in RRT*–Path Optimization and Intelligent Sampling. Simulation results presented in various obstacle cluttered environments along with statistical and mathematical analysis confirm the efficiency of the proposed RRT*-Smart algorithm.

A Low Dispersion Probabilistic Roadmaps (LD-PRM) Algorithm for Fast and Efficient Sampling-Based Motion Planning

In this paper, we propose a new learning strategy for a probabilistic roadmap (PRM) algorithm. The proposed strategy is based on reducing the dispersion of the generated set of samples. We defined a forbidden range around each selected sample and ignored this region in further sampling. The resultant planner, called low dispersion-PRM, is an effective multi-query sampling-based planner that is able to solve motion planning queries with smaller graphs. Simulation results indicated that the proposed planner improved the performance of the original PRM and other low-dispersion variants of PRM. Furthermore, the proposed planner is able to solve difficult motion planning instances, including narrow passages and bug traps, which represent particularly difficult tasks for classic sampling-based algorithms. For measuring the uniformity of the generated samples, a new algorithm was created to measure the dispersion of a set of samples based on a predetermined resolution.

Advanced perception, navigation and planning for autonomous in-water ship hull inspection

Inspection of ship hulls and marine structures using autonomous underwater vehicles has emerged as a unique and challenging application of robotics. The problem poses rich questions in physical design and operation, perception and navigation, and planning, driven by difficulties arising from the acoustic environment, poor water quality and the highly complex structures to be inspected. In this paper, we develop and apply algorithms for the central navigation and planning problems on ship hulls. These divide into two classes, suitable for the open, forward parts of a typical monohull, and for the complex areas around the shafting, propellers and rudders. On the open hull, we have integrated acoustic and visual mapping processes to achieve closed-loop control relative to features such as weld-lines and biofouling. In the complex area, we implemented new large-scale planning routines so as to achieve full imaging coverage of all the structures, at a high resolution. We demonstrate our approaches in recent operations on naval ships.

CarSpeak

This paper introduces CarSpeak, a communication system for autonomous driving. CarSpeak enables a car to query and access sensory information captured by other cars in a manner similar to how it accesses information from its local sensors. CarSpeak adopts a content-centric approach where information objects -- i.e., regions along the road -- are first class citizens. It names and accesses road regions using a multi-resolution system, which allows it to scale the amount of transmitted data with the available bandwidth. CarSpeak also changes the MAC protocol so that, instead of having nodes contend for the medium, contention is between road regions, and the medium share assigned to any region depends on the number of cars interested in that region.

CarSpeak is implemented in a state-of-the-art autonomous driving system and tested on indoor and outdoor hardware testbeds including an autonomous golf car and 10 iRobot Create robots. In comparison with a baseline that directly uses 802.11, CarSpeak reduces the time for navigating around obstacles by 2.4x, and reduces the probability of a collision due to limited visibility by 14x.

Learning and exploiting low-dimensional structure for efficient holonomic motion planning in high-dimensional spaces

We present a class of methods for optimal holonomic planning in high-dimensional spaces that automatically learns and leverages low-dimensional structure to efficiently find high-quality solutions. These methods are founded on the principle that problems possessing such structure are inherently simple to solve. This is demonstrated by presenting algorithms to solve these problems in time that scales with the dimension of a salient subspace, as opposed to the scaling with configuration-space dimension that would result from a naive approach. For generic problems possessing only approximate low-dimensional structure, we give iterative algorithms that are guaranteed convergence to local optima while making non-local path adjustments to escape poor local minima. We detail the theoretical underpinnings of these methods as well as give simulation and experimental results demonstrating the ability of our approach to efficiently find solutions of a quality exceeding that of known methods, and in problems of high dimensionality.

Real-time informed path sampling for motion planning search

Mobile robot motions often originate from an uninformed path-sampling process such as random or low-dispersion sampling. We demonstrate an alternative approach to path sampling that closes the loop on the expensive collision-testing process. Although all necessary information for collision testing a path is known to the planner, that information is typically stored in a relatively unavailable form in a costmap or obstacle map. By summarizing the most salient data in a more accessible form, our process delivers a denser sampling of the free path space per unit time than open-loop sampling techniques. We obtain this result by probabilistically modeling—in real time and with minimal information—the locations of obstacles and free space, based on collision-test results. We present CALM, the combined adaptive locality model, along with an algorithm to bias path sampling based on the model’s predictions. We provide experimental results in simulation for motion planning on mobile robots, demonstrating up to a 330% increase in paths surviving collision test.

Collision-free and smooth trajectory computation in cluttered environments

We present a novel trajectory computation algorithm to smooth piecewise linear collision-free trajectories computed by sample-based motion planners. Our approach uses cubic B-splines to generate trajectories that are C2 almost everywhere, except on a few isolated points. The algorithm performs local spline refinement to compute smooth, collision-free trajectories and it works well even in environments with narrow passages. We also present a fast and reliable algorithm for collision checking between a robot and the environment along the B-spline trajectories. We highlight the performance of our algorithm on complex benchmarks, including path computation for rigid and articulated models in cluttered environments.

Cross-entropy motion planning

This paper is concerned with motion planning for non-linear robotic systems operating in constrained environments. A method for computing high-quality trajectories is proposed building upon recent developments in sampling-based motion planning and stochastic optimization. The idea is to equip sampling-based methods with a probabilistic model that serves as a sampling distribution and to incrementally update the model during planning using data collected by the algorithm. At the core of the approach lies the cross-entropy method for the estimation of rare-event probabilities. The cross-entropy method is combined with recent optimal motion planning methods such as the rapidly exploring random trees (RRT*) in order to handle complex environments. The main goal is to provide a framework for consistent adaptive sampling that correlates the spatial structure of trajectories and their computed costs in order to improve the performance of existing planning methods.