Home | People | Research | Publications | Software | Links | News | Contact   

Incremental Sampling-Based Algorithms and Stochastic Optimal Control on Random Graphs

Motion planning and trajectory generation problems are at the at the core of all autonomous and robotic systems. Although – at least in theory – such problems can be solved using optimal control or dynamic programming, the computational complexity for realizing these solutions is still prohibitive for many real-life problems, especially for high-dimensional systems. Recently, randomized algorithms have been proposed, which promise to remedy the “curse of dimensionality” associated with more traditional, deterministic methods.

In recent years, sampling-based motion planning algorithms (SBMPs) have become popular due to their ability to handle higher dimensions and kino-dynamic constraints. Incremental sampling based algorithms, in particular, Rapidly-exploring Random Trees (RRT), RRT* avoid apriori discretization of the search space and build a connectivity graph online by generating random samples from the search space. However, these randomized methods are hindered by three computational bottlenecks, namely:

In this research, we propose ideas from classical heuristics, dynamic programming and machine learning to address these issues.

Exploration: Exploration problem (where to sample) is crucial for speedy convergence. An efficient sampling strategy must first find an initial (sub-optimal) solution quickly and then focus search in the regions that can potentially improve the current solution. Past collision data can be used to learn the topology of, and avoid generating samples in the obstacle space. Recently proposed non-parametric informed sampler (NP-Informed sampler) presents an approach to achieve these objectives.

Exploitation: Objective of the exploitation module is the process(rewire) graph to improve the current solution. The recently proposed RRT# algorithm implements global rewiring of the graph using Value Iteration. This ensures each vertex is optimally connected at the end of every iteration and results in faster convergence to the optimal solution.

RACECAR robot: RACECAR robot is a 1/10 scale car equipped with powerful sensors and NVIDIA Jetson processor, ideal for validating motion planning algorithms developed in this research. The algorithms developed are put to test in various simulation environments and on actual hardware.

Sponsors

This project is sponsored by NSF.

Selected Publications

Movies


   

Home | People | Research | Publications | Software | Links | News | Contact