Path Planning using a One-shot-sampling Skeleton Map

Authors

Keywords:

Motion planning, map-based navigation, mobile robots, denoising auto-encoder, deep learning

Abstract

Path planning algorithms fundamentally aim to compute collision-free paths, with many works focusing on finding the optimal distance path. However, for several applications, a more suitable approach is to balance response time, path safety, and path length. In this context, a skeleton map is a useful tool in graph-based schemes, as it provides an intrinsic representation of the free workspace. However, standard skeletonization algorithms are computationally expensive, as they are primarly oriented towards image processing tasks. We propose an efficient path-planning methodology that finds safe paths within an acceptable processing time. This methodology leverages a Deep Denoising Autoencoder (DDAE) based on the U-Net architecture to compute a skeletonized version of the navigation map, which we refer to as SkelUnet. The SkelUnet network facilitates exploration of the entire workspace through one-shot sampling (OSS), as opposed to the iterative or probabilistic sampling used by previous algorithms. SkelUnet is trained and tested on a dataset consisting of 12,500 two-dimensional dungeon maps. The motion planning methodology is evaluated in a simulation environment with an Unmanned Aerial Vehicle (UAV) in 250 previously unseen maps and assessed using several navigation metrics to quantify the navigability of the computed paths. The results demonstrate that using SkelUnet to construct the roadmap offers significant advantages, such as connecting all regions of free workspace, providing safer paths, and reducing processing time. These characteristics make this method particularly suitable for mobile robots in structured environments.

Downloads

Download data is not yet available.

Author Biographies

Gabriel O. Flores-Aquino, Centro de Investigación en Matemáticas (CIMAT)

Gabriel O. Flores-Aquino received the B.Sc. degree in Mechatronics Engineering in 2017 from the Professional School of Engineering and Advanced Technologies of the National Polytechnic Institute of Mexico (UPIITA-IPN). He received the M.Sc. degree in 2019 and the Ph.D. degree in 2023, both in Advanced Technology from the National Polytechnic Institute in Mexico. He is currently a postdoctoral researcher at the Mathematical Research Center (CIMAT), Guanajuato, Mexico. His research interests include mobile robotics, motion planning, pursuit-evasion problems, and artificial intelligence.

Octavio Gutierrez-Frias, Instituto Politécnico Nacional (IPN)

Octavio Gutierrez-Frias was born in Mexico City. He received a B.S. degree in Mechatronics from the Professional School of Engineering and Advanced Technologies of the National Polytechnic Institute of Mexico (UPIITA-IPN) in 2003. He received an M.Sc. degree in Computing Engineering from the Computing Research Center of the National Polytechnic Institute in 2006. In 2009, he received a Ph.D. in Computer Sciences at the CIC-IPN. Since 2012, he has been with the Graduate Section at UPIITA-IPN. His research focuses on nonlinear systems control, underactuated systems, robotics, and automation.

Juan Irving Vasquez, Instituto Politécnico Nacional (IPN)

Juan Irving Vasquez-Gomez received the B.S. degree in Computer Science from the Tehuacan Institute of Technology, Mexico, in 2006, and the M.Sc. and Ph.D. degrees from the National Institute for Astrophysics, Optics, and Electronics (INAOE), Mexico, in 2009 and 2014, respectively. From 2016 to 2021, he was a Researcher with the National Council of Science and Technology (CONACYT), Mexico. Since 2021, he has been a Full-Time Professor at the Instituto Politécnico Nacional (IPN), Mexico. His research interests include robotics, motion planning, and view planning, with applications in object reconstruction, inspection, and surveillance.

References

P. I. Corke, W. Jachimczyk, and R. Pillat, Robotics, Vision and Control: Fundamental Algorithms in MATLAB. Springer, 2011, vol. 73. DOI: https://doi.org/10.1007/978-3-031-07262-8.

T. Huang, K. Fan, and W. Sun, “Density gradient-RRT: An improved rapidly exploring random tree algorithm for UAV path planning,” Expert Systems with Applications, vol. 252, p. 124121, 2024. DOI: https://doi.org/10.1016/j.eswa.2024.124121.

J.-C. Latombe, Robot Motion Planning. New York: Springer, 1991. DOI: https://doi.org/10.1007/978-1-4615-4022-9.

H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki, and S. Thrun, Principles of Robot Motion. London, England: MIT Press, 2005. DOI: https://doi.org/10.1017/S0263574706212803.

S. Song, H. Bae, and J. Park, “Disco-U-Net based autoencoder architecture with dual input streams for skeleton image drawing,” in Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) Workshops, Oct. 2021, pp. 2128–2135. DOI: https://doi.org/10.1109/ICCVW54120.2021.00241.

R. Szeliski, Computer Vision: Algorithms and Applications. Springer Nature, 2022. DOI: https://doi.org/10.1007/978-3-030-34372-9.

P. K. Saha, G. Borgefors, and G. S. di Baja, “Skeletonization and its applications – a review,” in Skeletonization, pp. 3–42, 2017. DOI: https://doi.org/10.1016/B978-0-08-101291-8.00002-X.

P. Maragos and R. Schafer, “Morphological skeleton representation and coding of binary images,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 34, no. 5, pp. 1228–1244, 1986. DOI: https://doi.org/10.1109/TASSP.1986.1164959.

T. Y. Zhang and C. Y. Suen, “A fast parallel algorithm for thinning digital patterns,” Communications of the ACM, vol. 27, no. 3, pp. 236–239, 1984. DOI: https://doi.org/10.1145/357994.358023.

I. Demir et al., “Skelneton 2019: Dataset and challenge on deep learning for geometric shape understanding,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, June 2019. DOI: https://doi.org/10.48550/arXiv.1903.09233.

D. Perille, A. Truong, X. Xiao, and P. Stone, “Benchmarking metric ground navigation,” in 2020 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR), 2020, pp. 116–121. DOI: https://doi.org/10.1109/SSRR50563.2020.9292572.

D.-H. Yang and S.-K. Hong, “A roadmap construction algorithm for mobile robot path planning using skeleton maps,” Advanced Robotics, vol. 21, no. 1–2, pp. 51–63, 2007. DOI: https://doi.org/10.1163/156855307779293724.

Y. Dong, E. Camci, and E. Kayacan, “Faster RRT-based nonholonomic path planning in 2D building environments using skeleton-constrained path biasing,” Journal of Intelligent & Robotic Systems, vol. 89, pp. 387–401, 2018. DOI: https://doi.org/10.1007/s10846-017-0567-9.

S. M. LaValle and J. J. Kuffner Jr., “Randomized kinodynamic planning,” The International Journal of Robotics Research, vol. 20, no. 5, pp. 378–400, 2001. DOI: https://doi.org/10.1177/02783640122067453.

N. Bourbakis et al., “Path planning in a 2-D known space using neural networks and skeletonization,” in 1997 IEEE International Conference on Systems, Man, and Cybernetics, vol. 3, pp. 2001–2005, 1997. DOI: https://doi.org/10.1109/ICSMC.1997.635147.

J. Wang et al., “Neural RRT*: Learning-based optimal path planning,” IEEE Transactions on Automation Science and Engineering, vol. 17, no. 4, pp. 1748–1758, 2020. DOI: https://doi.org/10.1109/TASE.2020.2976560.

H. Ryu and Y. Park, “Improved informed RRT* using gridmap skeletonization for mobile robot path planning,” International Journal of Precision Engineering and Manufacturing, vol. 20, pp. 2033–2039, 2019. DOI: https://doi.org/10.1007/s40684-019-00075-8.

F. Zou et al., “Generating critical nodes for sub-path planning with a deep neural network based on ResNet50,” in Proceedings of the 2022 International Conference on Autonomous Unmanned Systems (ICAUS 2022), Singapore: Springer Nature, 2023, pp. 811–822. DOI: https://doi.org/10.1007/978-981-99-0479-2_74.

M. Ramana, S. A. Varma, and M. Kothari, “Motion planning for a fixed-wing UAV in urban environments,” IFAC-PapersOnLine, vol. 49, no. 1, pp. 419–424, 2016. DOI: https://doi.org/10.1016/j.ifacol.2016.03.090.

V. Zinage and S. Ghosh, “An efficient motion planning algorithm for UAVs in obstacle-cluttered environment,” in 2019 American Control Conference (ACC), 2019, pp. 2271–2276. DOI: https://doi.org/10.23919/ACC.2019.8814609.

M. C. G. Pawan Kumar, K. Pal, and A. Choudhary, “Rapid A*: A robust path planning scheme for UAVs,” International Journal of Intelligent Robotics and Applications, 2023. DOI: https://doi.org/10.1007/s41315-023-00294-y.

O. Ronneberger, P. Fischer, and T. Brox, “U-Net: Convolutional networks for biomedical image segmentation,” in Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015, Cham: Springer International Publishing, 2015, pp. 234–241. DOI: https://doi.org/10.1007/978-3-319-24574-4_28.

Y. Bengio, A. Courville, and P. Vincent, “Representation learning: A review and new perspectives,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 8, pp. 1798–1828, 2013. DOI: https://doi.org/10.1109/TPAMI.2013.50.

I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning. London, England: MIT Press, 2017. DOI: https://doi.org/10.1007/s10710-017-9314-z.

V. Dumoulin and F. Visin, “A guide to convolution arithmetic for deep learning,” arXiv preprint arXiv:1603.07285, 2016. DOI: https://doi.org/10.48550/arXiv.1603.07285.

G. O. Flores-Aquino, J. D. Díaz-Ortega, R. López-Muñoz, O. O. Gutiérrez-Frías, and J. I. Vásquez-Gómez, “2D grid map generation for deep-learning-based navigation approaches,” in 2021 IEEE International Conference on Mechatronics, Electronics and Automotive Engineering (ICMEAE), 2021. DOI: https://doi.org/10.48550/arXiv.2110.13242.

A. P. Schoellig, C. Wiltsche, and R. D’Andrea, “Feed-forward parameter identification for precise periodic quadrocopter motions,” in 2012 American Control Conference (ACC), IEEE, 2012, pp. 4313–4318. DOI: https://doi.org/10.1109/ACC.2012.6315248.

S. A. Wilmarth, N. M. Amato, and P. F. Stiller, “MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space,” in Proceedings of the 1999 IEEE International Conference on Robotics and Automation, vol. 2, IEEE, 1999, pp. 1024–1031. DOI: https://doi.org/10.1109/ROBOT.1999.772448.

H. I. Choi, S. W. Choi, and H. P. Moon, “Mathematical theory of medial axis transform,” Pacific Journal of Mathematics, vol. 181, no. 1, pp. 57–88, 1997. DOI: http://doi.org/10.2140/pjm.1997.181.57.

Downloads

Published

2026-02-27

How to Cite

Flores-Aquino, G. O., Gutierrez-Frias, O., & Vasquez, J. I. (2026). Path Planning using a One-shot-sampling Skeleton Map . IEEE Latin America Transactions, 24(3), 260–268. Retrieved from https://latamt.ieeer9.org/index.php/transactions/article/view/10253

Issue

Vol. 24 No. 3 (2026): Ordinary Issue

Section

Computing