Foundations and Trends® in Robotics > Vol 9 > Issue 4

A Survey on the Integration of Machine Learning with Sampling-based Motion Planning

By Troy McMahon, Rutgers University, USA, tm799@rutgers.edu | Aravind Sivaramakrishnan, Rutgers University, USA, as2578@rutgers.edu | Edgar Granados, Rutgers University, USA, eg585@rutgers.edu | Kostas E. Bekris, Rutgers University, USA, kb572@rutgers.edu

 
Suggested Citation
Troy McMahon, Aravind Sivaramakrishnan, Edgar Granados and Kostas E. Bekris (2022), "A Survey on the Integration of Machine Learning with Sampling-based Motion Planning", Foundations and Trends® in Robotics: Vol. 9: No. 4, pp 266-327. http://dx.doi.org/10.1561/2300000063

Publication Date: 10 Nov 2022
© 2022 T. McMahon et al.
 
Subjects
Planning
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction
2. Sampling-based Motion Planning
3. Learning Primitives of Sampling-based Motion Planning
4. Learning-based Pipelines
5. SBMP with Learned Models
6. Discussion
References

Abstract

Sampling-based methods are widely adopted solutions for robot motion planning. The methods are straightforward to implement, effective in practice for many robotic systems. It is often possible to prove that they have desirable properties, such as probabilistic completeness and asymptotic optimality. Nevertheless, they still face challenges as the complexity of the underlying planning problem increases, especially under tight computation time constraints, which impact the quality of returned solutions or given inaccurate models. This has motivated machine learning to improve the computational efficiency and applicability of Sampling- Based Motion Planners (SBMPs). This survey reviews such integrative efforts and aims to provide a classification of the alternative directions that have been explored in the literature. It first discusses how learning has been used to enhance key components of SBMPs, such as node sampling, collision detection, distance or nearest neighbor computation, local planning, and termination conditions. Then, it highlights planners that use learning to adaptively select between different implementations of such primitives in response to the underlying problem’s features. It also covers emerging methods, which build complete machine learning pipelines that reflect the traditional structure of SBMPs. It also discusses how machine learning has been used to provide data-driven models of robots, which can then be used by a SBMP. Finally, it provides a comparative discussion of the advantages and disadvantages of the approaches covered, and insights on possible future directions of research. An online version of this survey can be found at: https://prx-kinodynamic.github.io

DOI:10.1561/2300000063
ISBN: 978-1-63828-134-4
74 pp. $60.00
Buy book (pb)
 
ISBN: 978-1-63828-135-1
74 pp. $145.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Sampling-based Motion Planning
3. Learning Primitives of Sampling-based Motion Planning
4. Learning-based Pipelines
5. SBMP with Learned Models
6. Discussion
References

A Survey on the Integration of Machine Learning with Sampling-based Motion Planning

Motion planning is the problem of finding valid paths, expressed as sequences of configurations, or trajectories, expressed as sequences of controls, which move a robot from a given start state to a desired goal state while avoiding obstacles. Sampling-based methods are widely adopted solutions for robot motion planning. The methods are straightforward to implement, and effective in practice for many robotic systems. Furthermore, they have numerous desirable properties, such as probabilistic completeness and asymptotic optimality. Nevertheless, sampling-based methods still face challenges as the complexity of the underlying planning problem increases, especially under tight computation time constraints, which impact the quality of returned solutions or given inaccurate models. This has motivated machine learning to improve the computational efficiency and applicability of Sampling-Based Motion Planners (SBMPs).

There are numerous publications on the use of machine learning algorithms to improve the efficiency of robotic systems in general. Recently, attention has focussed on the progress of deep learning methods, which has resulted in many efforts to utilize the corresponding tools in robotics. This monograph focuses specifically on integrating machine learning tools to improve the efficiency, convergence, and applicability of SBMPs. The publication covers a wide range of robotic applications, including, but not limited to, manipulation planning, and planning for systems with dynamic constraints. In particular, this manuscript first reviews the attempts to use machine learning to improve the performance of individual primitives used by SBMPs. It also studies a series of planners that use machine learning to adaptively select from a set of motion planning primitives. The monograph then proceeds to study a series of integrated architectures that learn an end-to-end mapping of sensor inputs to robot trajectories or controls. Finally, the monograph shows how SBMPs can operate over learned models of robotic system due to the presence of noise and uncertainty, and it concludes with a comparative discussion of the different approaches covered in terms of their impact on computational efficiency of the planner, quality of the computed paths as well as the usability of SBMPs. Also outlined are the broad difficulties and limitations of these methods, as well as potential directions of future work.

 
ROB-063