Iterative methods for efficient sampling-based optimal motion planning of nonlinear systems

Ha, J. S. ; Choi, H. L. ; Jeon, J. H.

International Journal of Applied Mathematics and Computer Science, Tome 28 (2018) no. 1, pp. 155-168.

Résumé

This paper extends the RRT* algorithm, a recently developed but widely used sampling based optimal motion planner, in order to effectively handle nonlinear kinodynamic constraints. Nonlinearity in kinodynamic differential constraints often leads to difficulties in choosing an appropriate distance metric and in computing optimized trajectory segments in tree construction. To tackle these two difficulties, this work adopts the affine quadratic regulator-based pseudo-metric as the distance measure and utilizes iterative two-point boundary value problem solvers to compute the optimized segments. The proposed extension then preserves the inherent asymptotic optimality of the RRT* framework, while efficiently handling a variety of kinodynamic constraints. Three numerical case studies validate the applicability of the proposed method.

Détail

Keywords: optimal motion planning, sampling based algorithm, nonlinear dynamics
Mots-clés : planowanie ruchu, algorytm próbkowania, dynamika nieliniowa

Bibliographie

[1] Arslan, O. and Tsiotras, P. (2013). Use of relaxation methods in sampling-based algorithms for optimal motion planning, IEEE International Conference on Robotics and Automation, Karlsruhe, Germany, pp. 2421–2428.

[2] García-Rodríguez, R., Segovia-Palacios, V., Parra-Vega, V. and Villalva-Lucio, M. (2016). Dynamic optimal grasping of a circular object with gravity using robotic soft-fingertips, International Journal of Applied Mathematics and Computer Science 26(2): 309–323, DOI: 10.1515/amcs-2016-0022.

[3] Glassman, E. and Tedrake, R. (2010). A quadratic regulator-based heuristic for rapidly exploring state space, IEEE International Conference on Robotics and Automation, Anchorage, AK, USA, pp. 5021–5028.

[4] Goretkin, G., Perez, A., Platt, R. and Konidaris, G. (2013). Optimal sampling-based planning for linear-quadratic kinodynamic systems, IEEE International Conference on Robotics and Automation, Karlsruhe, Germany, pp. 2429–2436.

[5] Ha, J.-S., Lee, J.-J. and Choi, H.-L. (2013). A successive approximation-based approach for optimal kinodynamic motion planning with nonlinear differential constraints, IEEE Conference on Decision and Control, Florence, Italy, pp. 3623–3628.

[6] Huynh, V.A., Karaman, S. and Frazzoli, E. (2012). An incremental sampling-based algorithm for stochastic optimal control, IEEE International Conference on Robotics and Automation, Minneapolis, MN, USA, pp. 2865–2872.

[7] Huynh, V.A., Kogan, L. and Frazzoli, E. (2014). A Martingale approach and time-consistent sampling-based algorithms for risk management in stochastic optimal control, IEEE Conference on Decision and Control, Los Angeles, CA, USA, pp. 1858–1865.

[8] Janson, L., Schmerling, E., Clark, A. and Pavone, M. (2015). Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions, The International Journal of Robotics Research 34(7): 883–921.

[9] Jeon, J., Karaman, S. and Frazzoli, E. (2011). Anytime computation of time-optimal off-road vehicle maneuvers using the RRT*, IEEE Conference on Decision and Control, Orlando, FL, USA, pp. 3276–3282.

[10] Jeon, J., Karaman, S. and Frazzoli, E. (2015). Optimal sampling-based feedback motion trees among obstacles for controllable linear systems with linear constraints, IEEE International Conference on Robotics and Automation, Seattle, WA, USA, pp. 4195–4201.

[11] Karaman, S. and Frazzoli, E. (2010). Optimal kinodynamic motion planning using incremental sampling-based methods, IEEE Conference on Decision and Control, Atlanta, GA, USA, pp. 7681–7687.

[12] Karaman, S. and Frazzoli, E. (2011a). Incremental sampling-based algorithms for a class of pursuit-evasion games, in D. Hsu et al. (Eds.), Algorithmic Foundations of Robotics IX, Springer, Berlin/Heidelberg, pp. 71–87.

[13] Karaman, S. and Frazzoli, E. (2011b). Sampling-based algorithms for optimal motion planning, International Journal of Robotics Research 30(7): 846–894.

[14] Karaman, S. and Frazzoli, E. (2013). Sampling-based optimal motion planning for non-holonomic dynamical systems, IEEE International Conference on Robotics and Automation, Karlsruhe, Germany, pp. 5041–5047.

[15] Karaman, S., Walter, M.R., Perez, A., Frazzoli, E. and Teller, S. (2011). Anytime motion planning using the RRT*, IEEE International Conference on Robotics and Automation, Shanghai, China, pp. 1478–1483.

[16] Kirk, D.E. (2012). Optimal Control Theory: An Introduction, Courier Corporation, Dover Publications, Inc. Mineola, NY.

[17] Klaučo, M., Blažek, S. and Kvasnica, M. (2016). An optimal path planning problem for heterogeneous multi-vehicle systems, International Journal of Applied Mathematics and Computer Science 26(2): 297–308, DOI: 10.1515/amcs-2016-0021.

[18] LaValle, S.M. (1998). Rapidly-exploring random trees: A new tool for path planning, Technical Report 98-11, Iowa State University, Ames, IO.

[19] LaValle, S.M. (2011). Motion planning, IEEE Robotics Automation Magazine 18(1): 79–89.

[20] Lewis, F.L., Vrabie, D. and Syrmos, V.L. (1995). Optimal Control, John Wiley Sons, New York, NY.

[21] Pepy, R., Kieffer, M. and Walter, E. (2009). Reliable robust path planning with application to mobile robots, International Journal of Applied Mathematics and Computer Science 19(3): 413–424, DOI: 10.2478/v10006-009-0034-2.

[22] Perez, A., Platt, R., Konidaris, G., Kaelbling, L. and Lozano-Perez, T. (2012). LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics, IEEE International Conference on Robotics and Automation, Minneapolis, MN, USA, pp. 2537–2542.

[23] Rodríguez-Liñán, M.C., Mendoza, M., Bonilla, I. and Chávez-Olivares, C.A. (2017). Saturating stiffness control of robot manipulators with bounded inputs, International Journal of Applied Mathematics and Computer Science 27(1): 79–90, DOI: 10.1515/amcs-2017-0006.

[24] Szynkiewicz, W. and Błaszczyk, J. (2011). Optimization-based approach to path planning for closed chain robot systems, International Journal of Applied Mathematics and Computer Science 21(4): 659–670, DOI: 10.2478/v10006-011-0052-8.

[25] Tang, G. (2005). Suboptimal control for nonlinear systems: A successive approximation approach, Systems Control Letters 54(5): 429–434.

[26] Tedrake, R. (2009). Underactuated robotics: Learning, planning, and control for efficient and agile machines, Course Notes for MIT 6.832, MIT, Cambridge, MA, http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-832-underactuated-robotics-spring-2009/.

[27] Webb, D.J. and van den Berg, J. (2013). Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics, 2013 IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany, pp. 5054–5061.