Graph neural network based method for robot path planning

Abstract

Sampling-based path planning is widely used in robotics, particularly in high-dimensional state spaces. In the path planning process, collision detection is the most time-consuming operation. Therefore, we propose a learning-based path planning method that reduces the number of collision checks. We develop an efficient neural network model based on graph neural networks. The model outputs weights for each neighbor based on the obstacle, searched path, and random geometric graph, which are used to guide the planner in avoiding obstacles. We evaluate the efficiency of the proposed path planning method through simulated random worlds and real-world experiments. The results demonstrate that the proposed method significantly reduces the number of collision checks and improves the path planning speed in high-dimensional environments.

Keywords

Graph Neural Network (GNN) / Collision detection / Sampling-based path planning

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgments

This work is suported by Shenzhen Science and Technology Program, China (RCBS20221008093305007 and 20231115141459001), and Young Elite Scientists Sponsorship Program by CAST (2023QNRC001), China.

References

[1] Edsger W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1959) 269-271.

[2] Peter E. Hart, Nils J. Nilsson, Bertram Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cybern. 4 (2) (1968) 100-107.

[3] Chelsea C. White,Dynamic programming, in: Saul I. Gass, Michael C. Fu (Eds.), Encyclopedia of Operations Research and Management Science, Springer US, Boston, MA, 2013, pp. 453-455.

[4] L.E. Kavraki, P. Svestka, J.-C. Latombe, M.H. Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Trans. Robot. Autom. 12 (4) (1996) 566-580.

[5] S.M. LaValle, J.J. Kuffner, Randomized kinodynamic planning, in: Proceed-ings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C), vol. 1, 1999, pp. 473-479.

[6] David Hsu, Robert Kindel, Jean Claude Latombe, Stephen Rock, Randomized kinodynamic motion planning with moving obstacles, Int. J. Robot. Res. 21 (3) (2002).

[7] Lucas Janson, Edward Schmerling, Ashley Clark, Marco Pavone, Fast march-ing tree: A fast marching sampling-based method for optimal motion planning in many dimensions, Int. J. Robot. Res. 34 (7) (2015) 883-921.

[8] Jonathan D. Gammell, Siddhartha S. Srinivasa, Timothy D. Barfoot, Batch Informed Trees (BIT*): Sampling-based optimal planning via the heuristi-cally guided search of implicit random geometric graphs, in: 2015 IEEE International Conference on Robotics and Automation, ICRA, 2015, pp. 3067-3074.

[9] V. Boor, M.H. Overmars, A.F. van der Stappen,The Gaussian sampling strategy for probabilistic roadmap planners, in:Proceedings 1999 IEEE In-ternational Conference on Robotics and Automation (Cat. No.99CH36288C), vol. 2, 1999, pp. 1018-1023 vol.2.

[10] Tianyi Zhang, Jiankun Wang, Max Q.-H. Meng, Generative adversarial network based heuristics for sampling-based path planning, IEEE/CAA J. Autom. Sin. 9 (1) (2022) 64-74.

[11] R. Bohlin, L.E. Kavraki,Path planning using lazy PRM, in:Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), vol. 1, 2000, pp. 521-528.

[12] Chenming Li, Fei Meng, Han Ma, Jiankun Wang, Max Q.-H. Meng, Relevant region sampling strategy with adaptive heuristic for asymptotically optimal path planning, Biomim. Intell. Robotics 3 (3) (2023) 100113.

[13] Brian Ichter, James Harrison, Marco Pavone, Learning sampling distribu-tions for robot motion planning, in: 2018 IEEE International Conference on Robotics and Automation, ICRA, 2018, pp. 7087-7094.

[14] Kihyuk Sohn, Honglak Lee, Xinchen Yan, Learning structured output repre-sentation using deep conditional generative models, in: Advances in Neural Information Processing Systems, vol. 28, 2015.

[15] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair,Aaron Courville, Y. Bengio, Generative adversarial networks, Adv. Neural Inf. Process. Syst. 3 (2014).

[16] Zhiyong Liu, Fei Lan, Haibo Yang, Partition heuristic RRT algorithm of path planning based on Q-learning, in: 2019 IEEE 4th Advanced Information Technology, Electronic and Automation Control Conference, IAEAC, 2019.

[17] Ian Baldwin, Paul Newman,Non-parametric learning for natural plan generation, in: Intelligent Robots and Systems, 2010.

[18] Run Yang, Jingru Li, Zhikun Jia, Sen Wang, Huan Yao, Erbao Dong, EPL-PRM: Equipotential line sampling strategy for probabilistic roadmap planners in narrow passages, Biomim. Intell. Robotics 3 (3) (2023) 100112.

[19] Nika Haghtalab, Simon Mackenzie, Ariel D. Procaccia, Oren Salzman, Siddhartha S. Srinivasa,The provable virtue of laziness in motion planning, in:International Conference on Automated Planning and Scheduling, 2017.

[20] DasNikhil, YipMichael, Learning-based proxy collision detection for robot motion planning applications, IEEE Trans. Robot. (2020).

[21] J. Chase Kew, Brian Ichter, Maryam Bandari, Tsang Wei Edward Lee, Aleksandra Faust, Neural collision clearance estimator for batched motion planning, 2019.

[22] Binghong Chen, Bo Dai, Qinjie Lin, Guo Ye, Han Liu, Le Song,Learning to plan in high dimensions via neural exploration-exploitation trees, in: 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, OpenReview.net, 2020.

[23] Brian Ichter, Marco Pavone, Robot motion planning in learned latent spaces, IEEE Robot. Autom. Lett. 4 (3) (2019) 2407-2414.

[24] Jiankun Wang, Wenzheng Chi, Chenming Li, Chaoqun Wang, Max Q.-H. Meng, Neural RRT*: Learning-based optimal path planning, IEEE Trans. Autom. Sci. Eng. 17 (4) (2020) 1748-1758.

[25] Tingjun Lei, Timothy Sellers, Chaomin Luo, Daniel W. Carruth, Zhuming Bi, Graph-based robot optimal path planning with bio-inspired algorithms, Biomim. Intell. Robotics 3 (3) (2023) 100119.

[26] Thomas N. Kipf, Max Welling, Semi-supervised classification with graph convolutional networks, 2016.

[27] Alex Fout, Jonathon Byrd, Basir Shariat, Asa Ben-Hur,Protein interface prediction using graph convolutional networks, in: Neural Information Processing Systems, 2017.

[28] Zhouxia Wang, Tianshui Chen, Jimmy Ren, Weihao Yu, Hui Cheng, Liang Lin, Deep reasoning with knowledge graph for social relationship understanding, 2018.

[29] Chenning Yu, Sicun Gao,Reducing collision checking for sampling-based motion planning using graph neural networks, in:Conference on Neural Information Processing Systems, NeurIPS.

[30] Qingbiao Li, Fernando Gama, Alejandro Ribeiro, Amanda Prorok, Graph neural networks for decentralized multi-robot path planning, in: 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, 2020, pp. 11785-11792.

[31] Alejandro Ribeiro, Arbaaz Khan, Vijay Kumar, Anthony G Francis, Graph neural networks for motion planning, 2020.

[32] Oktay Arslan, Karl Berntorp, Panagiotis Tsiotras, Sampling-based algorithms for optimal motion planning using closed-loop prediction, in: 2017 IEEE International Conference on Robotics and Automation, ICRA, 2017, pp. 4991-4996.

[33] Feng Xue, Panganamala Ramana Kumar, The number of neighbors needed for connectivity of wireless networks, Wirel. Netw. 10 (2004) 169-181.

[34] Edgar N. Gilbert, Random plane networks, J. Soc. Ind. Appl. Math. 9 (1961) 533-543.

[35] Jimmy Lei Ba, Jamie Ryan Kiros, Geoffrey E. Hinton, Layer normalization, 2016.

[36] Sepp Hochreiter, Jürgen Schmidhuber, Long short-term memory, Neural Comput. 9 (8) (1997) 1735-1780.

[37] Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, Illia Polosukhin,Attention is all you need, in: Neural Information Processing Systems, 2017.

[38] Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, Bin Luo, Semi-supervised learning with graph learning-convolutional networks, in: 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR, 2019, pp. 11305-11312.

[39] Zhiyuan Liu, Jie Zhou, Graph attention networks, in: Introduction to Graph Neural Networks, Springer International Publishing, Cham, 2020, pp. 39-41.