05 Aug

#### Motion Planning 2: Sampling-Based Methods

Sampling-based motion planning approaches, such as Probabilistic RoadMap Method (PRM) and Rapidly-exploring Random Trees (RRT) , avoid the discretization problems of graph-based algorithms by randomly sampling the continuous domain. This scales more effectively to high-dimensional problems, but makes their search probabilistic. Thus, compared with the properties of graph-based algorithms, they are probabilistically complete, having a probability of finding a solution if one exists, that goes to one as the number of samples goes to infinity. Optimal variants, such as RRT* and PRM* are also asymptotically optimal, converging asymptotically to the optimal solution with probability one as the number of samples goes to infinity. Recently, BIT* is proposed that is able to find optimal solutions with better convergence rate against RRT* reusing previous suboptimal solutions efficiently.

The main disadvantage of sapling-based algorithms is that the obtained paths often manifest redundant and jerky motion and hence require post processing to smooth and shorten the computed trajectories, which typically takes quite time to compute. Furthermore, they suffer from finding samples that satisfy many complicated constraints, especially for very high DoF robots such as humanoid robots, in cluttered environments.

Here, I illustrate each of the concepts that constitute typical sampling-based motion planning algorithms with the need to satisfy the constraints.

• Samplers: If the environment is occupied by a number of obstacles, then it is very difficult for the samplers to find the node within the collision-free space. A planner somehow needs to find the sample configurations that satisfy constraints or guide the search towards the area where the collison-free is guaranteed.
• Metrics and nearest neighbor data structure: Normally, you can use the L_2 norm as the metric to compute the edge cost between the current node to the sampled node. However, this is very difficult under the configuration space with constraints because the typical trajectory is line anymore and it can be curved and twisted, leading to the inconvenience of using l2 norm as the metric. You can use the Riemannian metric, but the computation would be very expensive.
• Local planners: If you use the methods something like interpolation, this would not work anymore as you can imagine due to many constraints. In addition, normally, the curvature and structure of the space is unknown a priori so that it is very difficult for the planner to consider the constraints before the planner runs. Even for relatively simple robots such as wheeled robots, you need to consider good local planners to satisfy constraints like stearing constraints, energy constraints. I do recommend that you can use trajecotry optimization algorithms, which I will explain in my next blog.
• Coverge estimates: To the best of my knowledge, "no" constrained sampling-based planner has constructed a planning method that use a converge estimate in its planning process. This is one of the largest open problem in sampling-based planners.

Reference:

M. Elbanhawi and M. Simic, “Sampling-Based Robot Motion Planning: A Review,” IEEE Access, vol. 2, pp. 56–77, 2014.
@article{Elbanhawi_2014,
doi = {10.1109/access.2014.2302442},
url = {https://doi.org/10.1109%2Faccess.2014.2302442},
year = 2014,
publisher = {Institute of Electrical and Electronics Engineers ({IEEE})},
volume = {2},
pages = {56--77},
author = {Mohamed Elbanhawi and Milan Simic},
title = {Sampling-Based Robot Motion Planning: A Review},
journal = {{IEEE} Access}
}
< bib >
Z. Kingston, M. Moll, and L. E. Kavraki, “Sampling-Based Methods for Motion Planning with Constraints,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 1, no. 1, pp. 159–185, May 2018.
@article{Kingston_2018,
doi = {10.1146/annurev-control-060117-105226},
url = {https://doi.org/10.1146%2Fannurev-control-060117-105226},
year = 2018,
month = {may},
publisher = {Annual Reviews},
volume = {1},
number = {1},
pages = {159--185},
author = {Zachary Kingston and Mark Moll and Lydia E. Kavraki},
title = {Sampling-Based Methods for Motion Planning with Constraints},
journal = {Annual Review of Control, Robotics, and Autonomous Systems}
}
< bib >
J. D. Gammell, T. D. Barfoot, and S. S. Srinivasa, “Batch Informed Trees (BIT*): Informed asymptotically optimal anytime search,” The International Journal of Robotics Research, vol. 39, no. 5, pp. 543–567, Jan. 2020.
@article{Gammell_2020,
doi = {10.1177/0278364919890396},
url = {https://doi.org/10.1177%2F0278364919890396},
year = 2020,
month = {jan},
publisher = {{SAGE} Publications},
volume = {39},
number = {5},
pages = {543--567},
author = {Jonathan D Gammell and Timothy D Barfoot and Siddhartha S Srinivasa},
title = {Batch Informed Trees ({BIT}{\ast}): Informed asymptotically optimal anytime search},
journal = {The International Journal of Robotics Research}
}
< bib >