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:
- The need for a intelligent sampling strategy to avoid redundant exploration
- Avoiding expensive collision checking module
- Efficient ways of implementing the so called “local steering” problem connecting any two vertices in the connectivity graph.
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
- Arslan, O., Berntorp, K., and Tsiotras, P.,"Sampling-based Algorithms for Optimal Motion Planning Using Closed-loop Prediction,'' International Conference on Robotics and Automation, Singapore, May. 12-14, 2017, pp. 4991-4996, doi: 10.1109/ICRA.2017.7989581
- Hauer, F., and Tsiotras, P., "Deformable Rapidly-Exploring Random Trees,'' Robotics: Science and Systems, Cambridge, MA, July 12-16, 2017.
Movies
- Anthropomorthic robot motion planning (6dof)
- Anthropomorthic robot motion planning (12dof)
- Manipulator planning using DRRT
- Implementation of CL-RRT# on Mars Rover at JPL
