Multiquery motion planning in uncertain spaces: Incremental adaptive randomized roadmaps

Khaksar, Weria ; Uddin, Md Zia ; Torresen, Jim

International Journal of Applied Mathematics and Computer Science, Tome 29 (2019) no. 4, pp. 641-654.

Résumé

Sampling-based motion planning is a powerful tool in solving the motion planning problem for a variety of different robotic platforms. As its application domains grow, more complicated planning problems arise that challenge the functionality of these planners. One of the main challenges in the implementation of a sampling-based planner is its weak performance when reacting to uncertainty in robot motion, obstacles motion, and sensing noise. In this paper, a multi-query sampling-based planner is presented based on the optimal probabilistic roadmaps algorithm that employs a hybrid sample classification and graph adjustment strategy to handle diverse types of planning uncertainty such as sensing noise, unknown static and dynamic obstacles and an inaccurate environment map in a discrete-time system. The proposed method starts by storing the collision-free generated samples in a matrix-grid structure. Using the resulting grid structure makes it computationally cheap to search and find samples in a specific region. As soon as the robot senses an obstacle during the execution of the initial plan, the occupied grid cells are detected, relevant samples are selected, and in-collision vertices are removed within the vision range of the robot. Furthermore, a second layer of nodes connected to the current direct neighbors are checked against collision, which gives the planner more time to react to uncertainty before getting too close to an obstacle. The simulation results for problems with various sources of uncertainty show a significant improvement compared with similar algorithms in terms of the failure rate, the processing time and the minimum distance from obstacles. The planner is also successfully implemented and tested on a TurtleBot in four different scenarios with uncertainty.

Détail

Keywords: motion planning, roadmap, sampling based planner, obstacle avoidance
Mots-clés : planowanie ruchu, mapa drogowa, unikanie przeszkód

Bibliographie

[1] Achtelik, M.W., Weiss, S., Chli, M. and Siegwart, R. (2013). Rapidly-exploring random belief trees for motion planning under uncertainty, IEEE International Conference on Robotics and Automation, ICRA 2013, Karlsruhe, Germany, pp. 3926–3932, DOI: 10.1109/ICRA.2013.6631130.

[2] Agha-Mohammadi, A.A. and Chakravorty, S.A.N.M. (2014). FIRM: Sampling-based feedback motion-planning under motion uncertainty and imperfect measurements, International Journal of Robotics Research 33(2): 268–304, DOI: 10.1177/0278364913501564.

[3] Aoude, G.S., Luders, B.D., Joseph, J.M., Roy, N. and How, J.P. (2013). Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns, Autonomous Robots 35(1): 51–76, DOI: 10.1007/s10514-013-9334-3.

[4] Axelrod, B., Kaelbling, L.P. and Lozano-Perez, T. (2018). Provably safe robot navigation with obstacle uncertainty, International Journal of Robotics Research 37(13-14): 1760–1774, DOI: 10.1177/0278364918778338.

[5] Belghith, K., Kabanza, F. and Hartman, L. (2013). Randomized path planning with preferences in highly complex dynamic environments, Robotica 31(8): 1195–1208, DOI: 10.1017/S0263574713000428.

[6] Bry, A. and Roy, N. (2011). Rapidly-exploring random belief trees for motion planning under uncertainty, IEEE International Conference on Robotics and Automation, ICRA 2011, Shanghai, China, pp. 723–730, DOI: 10.1109/ICRA.2011.5980508.

[7] Burns, B. and Brock, O. (2007). Sampling-based motion planning with sensing uncertainty, IEEE International Conference on Robotics and Automation, ICRA 2007, Rome, Italy, pp. 3313–3318, DOI: 10.1109/ROBOT.2007.363984.

[8] Canny, J. (1988). The Complexity of Robot Motion Planning, MIT Press, Cambridge, MA.

[9] Choset, H.M., Hutchinson, S., Lynch, K.M., Kantor, G., Burgard, W., Kavraki, L.E. and Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementations, MIT Press, Cambridge, MA.

[10] Elbanhawi, M. and Simic, M. (2014). Sampling-based robot motion planning: A review, IEEE Access 2: 56–77, DOI: 10.1109/ACCESS.2014.2302442.

[11] González, D., Pérez, J., Milanés, V. and Nashashibi, F. (2016). A review of motion planning techniques for automated vehicles, IEEE Transactions on Intelligent Transportation Systems 17(4): 1135–1145, DOI: 10.1109/TITS.2015.2498841.

[12] Ha, J.S., Choi, H.L. and Jeon, J.H. (2018). Iterative methods for efficient sampling-based optimal motion planning of nonlinear systems, International Journal of Applied Mathematics and Computer Science 28(1): 155–168, DOI: 10.2478/amcs-2018-0012.

[13] Hsu, D., Kindel, R., Latombe, J.C. and Rock, S. (2002). Randomized kinodynamic motion planning with moving obstacles, International Journal of Robotics Research 21(3): 233–255, DOI: 10.1177/027836402320556421.

[14] Jafarzadeh, H. and Fleming, C.H. (2018). An exact geometry-based algorithm for path planning, International Journal of Applied Mathematics and Computer Science 28(3): 493–504, DOI: 10.2478/amcs-2018-0038.

[15] Jaillet, L., Hoffman, J., Van den Berg, J., Abbeel, P., Porta, J.M. and Goldberg, K. (2011). EG-RRT: Environment-guided random trees for kinodynamic motion planning with uncertainty and obstacles, IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2011, San Francisco, CA, USA, pp. 2646–2652, DOI: 10.1109/IROS.2011.6094802.

[16] Jaillet, L. and Simeon, T. (2004). A PRM-based motion planner for dynamically changing environments, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2004, Sendai, Japan, pp. 1606–1611, DOI: 10.1109/IROS.2004.1389625.

[17] Jaillet, L. and Siméon, T. (2008). Path deformation roadmaps: Compact graphs with useful cycles for motion planning, The International Journal of Robotics Research 27(11).

[18] Janson, L., Ichter, B. and Pavone, M. (2018). Deterministic sampling-based motion planning: Optimality, complexity, and performance, International Journal of Robotics Research 37(1): 46–61, DOI: 10.1177/0278364917714338.

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

[20] Kavraki, L.E., Svestka, P., Latombe, J.C. and Overmars, M.H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Transactions on Robots and Automation 12(4): 566–580, DOI: 10.1109/70.508439.

[21] Khaksar, W., Tang, S.H., Ismail, N. and Arrifin, M. (2012). A review on robot motion planning approaches, Pertanika Journal of Science Technology 20(1): 15–29.

[22] Khaksar, W., Tang, S.H., Khaksar, M. and Motlagh, O. (2013). A low dispersion probabilistic roadmaps (LD-PRM) algorithm for fast and efficient sampling-based motion planning, International Journal of Advanced Robotic Systems 10(11): 1–10, DOI: 10.5772/56973.

[23] Kingston, Z., Moll, M. and Kavraki, L.E. (2018). Sampling-based methods for motion planning with constraints, Annual Review of Control, Robotics, and Autonomous Systems 1: 159–185, DOI: 10.1146/annurev-control-060117-105226.

[24] 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.

[25] Kurniawati, H., Bandyopadhyay, T. and Patrikalakis, N.M. (2012). Global motion planning under uncertain motion, sensing, and environment map, Autonomous Robots 33(3): 255–272, DOI: 10.1007/s10514-012-9307-y.

[26] LaValle, S.M. and Kuffner, J.J. (2001). Randomized kinodynamic planning, The International Journal of Robotics Research 25(5): 378–400, DOI: 10.1177/02783640122067453.

[27] Leven, P. and Hutchinson, S. (2011). A framework for real-time path planning in changing environments, The International Journal of Robotics Research 21(12): 999–1030, DOI: 10.1177/0278364902021012001.

[28] Li, D., Li, Q., Cheng, N. and Song, J. (2014). Sampling-based real-time motion planning under state uncertainty for autonomous micro-aerial vehicles in GPS-denied environments, Sensors 14(11): 21791–21825, DOI: 10.3390/s141121791.

[29] Liu, W. and Ang, M.H. (2014). Incremental sampling-based algorithm for risk-aware planning under motion uncertainty, IEEE International Conference on Robotics and Automation, ICRA 2014, Hong Kong, China, pp. 2051–2058, DOI: 10.1109/ICRA.2014.6907131.

[30] Luders, B.D. and How, J.P. (2014). An optimizing sampling-based motion planner with guaranteed robustness to bounded uncertainty, American Control Conference, ACC 2014, Portland, OR, USA, pp. 771–777, DOI: 10.1109/ACC.2014.6859383.

[31] Luna, R., Şucan, I.A., Moll, M. and Kavraki, L.E. (2013). Anytime solution optimization for sampling-based motion planning, IEEE International Conference on Robotics and Automation, ICRA 2013, Karlsruhe, Germany, pp. 5068–5074, DOI: 10.1109/ICRA.2013.6631301.

[32] Otte,M. and Frazzoli, E. (2016). RRTX: Asymptotically optimal single-query sampling-based motion planning with quick replanning, International Journal of Robotics Research 35(7): 797–822, DOI: 10.1177/0278364915594679.

[33] Pilania, V. and Gupta, K. (2017). Localization aware sampling and connection strategies for incremental motion planning under uncertainty, Autonomous Robots 41(1): 111–132, DOI: 10.1007/s10514-015-9536-y.

[34] Pilania, V. and Gupta, K. (2018). Mobile manipulator planning under uncertainty in unknown environments under uncertainty, International Journal of Robotics Research 37(2–3): 316–339, DOI: 10.1177/0278364918754677.

[35] Przybylski, M. and Putz, B. (2017). D* Extra Lite: A dynamic A* with searchtree cutting and frontiergap repairing, International Journal of Applied Mathematics and Computer Science 27(2): 273–290, DOI: 10.1515/amcs-2017-0020.

[36] Shan, T. and Englot, B. (2017). Belief roadmap search: Advances in optimal and efficient planning under uncertainty, IEEE International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, BC, Canada, pp. 5318–5325, DOI: 10.1109/IROS.2017.8206425.

[37] Summers, T. (2018). Distributionally robust sampling-based motion planning under uncertainty, IEEE International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, BC, Canada, pp. 6518–6523, DOI: 10.1109/IROS.2018.8593893.

[38] Sun, W., Patil, S. and Alterovitz, R. (2015). High-frequency replanning under uncertainty using parallel sampling-based motion planning, IEEE Transactions on Robotics 31(1): 104–116, DOI: 10.1109/TRO.2014.2380273.

[39] Vasquez-Gomez, J.I., Sucar, L.E. and Murrieta-Cid, R. (2017). View/state planning for three-dimensional object reconstruction under uncertainty, Autonomous Robots 41(1): 89–109, DOI: 10.1007/s10514-015-9531-3.