Motion planning under differential constraints is one of the canonical problems in robotics. State-of-the-art methods evolve around kinodynamic variants of popular sampling-based algorithms, such as Rapidly-exploring Random Trees (RRTs). However, there are still challenges remaining, for example, how to include complex dynamics while guaranteeing optimality. If the open-loop dynamics are unstable, exploration by random sampling in control space becomes inefficient. We describe CL-RRT#, which leverages ideas from the RRT# algorithm and a variant of the RRT algorithm, which generates trajectories using closed-loop prediction. Planning with closed-loop prediction allows us to handle complex unstable dynamics and avoids the need to find computationally hard steering procedures. The search technique presented in the RRT# algorithm allows us to improve the solution quality by searching over alternative reference trajectories. We show the benefits of the proposed approach on an autonomous-driving scenario.

Several sampling-based algorithms have been recently proposed that ensure asymptotic optimality. The convergence of these algorithms can be improved if sampling is guided toward the most promising region of the search space where the solution is more likely to be found. In this paper we propose three sample rejection methods that leverage the classification of the samples according to their potential of being part of the optimal solution to guide the exploration of the motion planner to promising regions of the search space. These sampling strategies are a direct by-product of the exploitation phase of the algorithm, which uses a dynamic programming (DP) step while planning on random graphs as, for example, is done in the RRT# algorithm. It is shown that the proposed sampling strategies are able to compute high-quality solutions, much faster than existing algorithms. We provide numerical results and compare the performance of the proposed algorithm with the original RRT# and the RRT* algorithms.

We propose a machine learning (ML)-inspired approach to estimate the relevant region of a motion planning problem during the exploration phase of sampling-based path-planners. The algorithm guides the exploration so that it draws more samples from the relevant region as the number of iterations increases. The approach works in two steps: first, it predicts if a given sample is collision-free (classification phase) without calling the collision-checker, and it then estimates if it is a promising sample, i.e., if it has the potential to improve the current best solution (regression phase), without solving the local steering problem. The proposed exploration strategy is integrated to the RRT#algorithm. Numerical simulations demonstrate the efficiency of the proposed approach.

This paper considers optimal control of dynamical systems which are represented by nonlinear stochastic differential equations. It is well-known that the optimal control policy for this problem can be obtained as a function of a value function that satisfies a nonlinear partial differential equation, namely, the Hamilton-Jacobi-Bellman equation. This nonlinear PDE must be solved backwards in time, and this computation is intractable for large scale systems. Under certain assumptions, and after applying a logarithmic transformation, an alternative characterization of the optimal policy can be given in terms of a path integral. Path Integral (PI) based control methods have recently been shown to provide elegant solutions to a broad class of stochastic optimal control problems. One of the implementation challenges with this formalism is the computation of the expectation of a cost functional over the trajectories of the unforced dynamics. Computing such expectation over trajectories that are sampled uniformly may induce numerical instabilities due to the exponentiation of the cost. Therefore, sampling of low-cost trajectories is essential for the practical implementation of PI-based methods. In this paper, we use incremental sampling-based algorithms to sample useful trajectories from the unforced system dynamics, and make a novel connection between Rapidly-exploring Random Trees (RRTs) and information-theoretic stochastic optimal control. We show the results from the numerical implementation of the proposed approach to several examples.

Several variants of incremental sampling-based algorithms have been recently proposed in order to optimally solve motion planning problems. Popular examples include the RRT* and the PRM* algorithms. These algorithms are asymptotically optimal and thus provide high quality solutions. However, the convergence rate to the optimal solution may still be slow. Borrowing from ideas used in the well-known LPA* algorithm, in this paper we present a new incremental sampling-based motion planning algorithm based on Rapidly-exploring Random Graphs (RRG), denoted by RRT#(RRT “sharp”), which also guarantees asymptotic optimality, but, in addition, it also ensures that the constructed spanning tree rooted at the initial state contains lowest-cost path information for vertices which have the potential to be part of the optimal solution. This implies that the best possible solution is readily computed if there are some vertices in the current graph that are already in the goal region.

Auditory is a convenient and efficient way for Human-Robot Interaction, however implementing a sound source localization system based on TDOA method encounters many problems, such as noise of real environments, and resolution of nonlinear equations, switch between far field and near field and lack of microphones for geometric positioning localization method. In this paper, a new spectral weighting GCC-PHAT method is proposed to deal with noise. Furthermore, the time difference feature of sound source and its spatial distribution are analyzed. Based on prosperities of the distribution, a space grid matching (SGM) algorithm is proposed for localization step, which handles those problems that geometric positioning method faces effectively. Decision tree and valid feature detection algorithm are also proposed to reduce computational complexity and improve performance. Experiments are achieved in real environments on a mobile robot platform, in which 2016 sets of speech data are tested using four microphones in 3D space. More than 95% azimuth localization rate with error less than 5 degrees and approximate 90% horizontal distance localization rate are obtained.

In this paper we consider dynamic shortest path-planning problems on a graph with a single endpoint pair and with potentially changing edge weights over time. Several incremental algorithms exist in the literature that solve this problem, notably among them the Lifelong Planning A* (LPA*) algorithm. Although, in most cases, the LPA* algorithm requires a relatively small number of updates, in some other cases the amount of work required by the LPA* to find the optimal path can be overwhelming. To address this issue, in this paper we propose an extension of the baseline LPA* algorithm, by making efficient use of a multiscale representation of the environment.

Path-planning (equivalently, path-finding) problems are fundamental in many applications, such as transportation, VLSI design, robot navigation, and many more. In this paper, we consider dynamic shortest path-planning problems on a graph with a single endpoint pair and with potentially changing edge weights over time. Several algorithms exist in the literature that solve this problem, notably among them the Lifelong Planning algorithm. The algorithm is an incremental search algorithm that replans the path when there are changes in the environment. In numerical experiments, however, it was observed that the performance of is sensitive in the number of vertex expansions required to update the graph when an edge weight value changes or when a vertex is added or deleted. Although, in most cases, the classical requires a relatively small number of updates, in some other cases the amount of work required by the to find the optimal path can be overwhelming. To address this issue, in this paper, we propose an extension of the baseline algorithm, by making efficient use of a multiscale representation of the environment. This multiscale representation allows one to quickly localize the changed edges, and subsequently update the priority queue efficiently. This incremental multiscale ( for short) algorithm leads to an improvement both in terms of robustness and computational complexity-in the worst case-when compared to the classical . Numerical experiments validate the aforementioned claims.