Research Article
BibTex RIS Cite

PRM Path Smoothening by Circular Arc Fillet Method for Mobile Robot Navigation

Year 2024, Volume: 16 Issue: 1, 1 - 19, 31.01.2024

Meral Kılıçarslan Ouach , Tolga Eren , Evrencan Özcan

https://doi.org/10.29137/umagd.1278980

Abstract

The problem of motion planning and navigation for mobile robots in complex environments has been a central issue in robotics. Navigating these environments requires sophisticated algorithms that handle obstacles and provide smooth, efficient paths. The Probabilistic Roadmap (PRM) method is a widespread technique in robotics for constructing paths for mobile robot navigation. In this study, we propose a novel path-smoothing method using arc fillets for path planning, building on PRM's foundation in the presence of obstacles. Our method operates in two primary stages to improve path efficiency and quality. The first stage generates the shortest path between the initial and goal states in an obstacle-rich environment using PRM, constructing a straight-line, collision-free route. The second stage smooths corners caused by nodes with arc fillets, ensuring smooth turns and minimizing abrupt changes in direction, resulting in more natural and efficient robot motion. We conducted simulations and tests using various PRM features to evaluate the proposed method. The results indicate that the built route offers a smooth turning motion and quicker, more compact movement while evading obstacles. This study contributes to mobile robot navigation by offering a practical approach to improving pathway quality in challenging environments.

Keywords

Probabilistic Roadmap Method (PRM) planner Path smoothening Arc fillet method

References

  • Aria, M. (2020). New sampling based planning algorithm for local path planning for autonomous vehicles. Journal of Engineering Science and Technology, 15, 66–76.
  • Ayawli, B. B. K., Appiah, A. Y., Nti, I. K., Kyeremeh, F., & Ayawli, E. I. (2021). Path planning for mobile robots using Morphological Dilation Voronoi Diagram Roadmap algorithm. Scientific African, 12, e00745.https://doi.org/10.1016/j.sciaf.2021.e00745
  • Bohlin, R., & Kavraki, L. E. (2000). Path planning using Lazy PRM. Proceedings-IEEE International Conference on Robotics and Automation, 1, 521–528. https://doi.org/10.1109/ROBOT.2000.844107
  • Canny, J. (1988). The complexity of robot motion planning. MIT Press.
  • Cheok, K. C., Iyengar, K., & Oweis, S. (2019). Smooth trajectory planning for autonomous leader-follower robots. Proceedings of 34th International Conference on Computers and Their Applications, CATA 2019, 58, 301–309. https://doi.org/10.29007/n6kt
  • Choset, H. M. (2005). Principles of robot motion : theory, algorithms, and implementation. MIT Press.
  • Contreras-Cruz, M. A., Ayala-Ramirez, V., & Hernandez-Belmonte, U. H. (2015). Mobile robot path planning using artificial bee colony and evolutionary programming. Applied Soft Computing, 30, 319–328. https://doi.org/https://doi.org/10.1016/j.asoc.2015.01.067
  • Davoodi, M., Panahi, F., Mohades, A., & Hashemi, S. N. (2015). Clear and smooth path planning. Applied Soft Computing, 32, 568–579. https://doi.org/https://doi.org/10.1016/j.asoc.2015.04.017
  • Elhoseny, M., Tharwat, A., & Hassanien, A. E. (2018). Bezier Curve Based Path Planning in a Dynamic Field using Modified Genetic Algorithm. Journal of Computational Science, 25, 339–350. https://doi.org/https://doi.org/10.1016/j.jocs.2017.08.004
  • Gang, L., & Wang, J. (2016). PRM Path planning optimization algorithm research. WSEAS Trans. Syst. Control, 11, 81–85.
  • Hamdy A. Taha. (1997). Operations research: An introduction. Computers & Mathematics with Applications, 33(5), 132. https://doi.org/https://doi.org/10.1016/S0898-1221(97)82948-3
  • Han, J., & Seo, Y. (2017). Mobile robot path planning with surrounding point set and path improvement. Applied Soft Computing Journal, 57, 35–47. https://doi.org/10.1016/j.asoc.2017.03.035
  • Huh, U.-Y., & Chang, S.-R. (2014). A G(2) Continuous Path-smoothing Algorithm Using Modified Quadratic Polynomial Interpolation. International Journal Of Advanced Robotic Systems, 11. https://doi.org/10.5772/57340
  • Janjoš, F., Reichart, R., & Niermeyer, P. (2017). Smooth Path-Generation Around Obstacles Using Quartic Splines and RRTs. IFAC-PapersOnLine, 50(1), 9108–9113. https://doi.org/10.1016/j.ifacol.2017.08.1708
  • Ju, M.-Y., & Cheng, C.-W. (2011). Smooth Path Planning Using Genetic Algorithms. 2011 9th World Congress On Intelligent Control And Automation (Wcica 2011), 1103–1107.
  • Kapitanyuk, Y. A., & Chepinsky, S. A. (2013). Control of mobile robot following a piecewise-smooth path. Gyroscopy and Navigation, 4(4), 198–203. https://doi.org/10.1134/S207510871304007X
  • Ladd, A. M., & Kavraki, L. E. (2004). Measure theoretic analysis of probabilistic path planning. IEEE Transactions on Robotics and Automation, 20(2), 229–242. https://doi.org/10.1109/TRA.2004.824649
  • Latombe , J.-C. (1991). Robot Motion Planning. https://public.ebookcentral.proquest.com/choice/publicfullrecord.aspx?p=3080882 LaValle , ProQuest (Firm), S. M. (2006). Planning algorithms. Cambridge University Press.
  • Miller, R. D. (1992). IV.5 - Joining Two Lines With A Circular Arc Fillet. In D. Kirk (Ed.), Graphics Gems III (IBM Version) (pp. 193–198). Morgan Kaufmann. https://doi.org/https://doi.org/10.1016/B978-0-08-050755-2.50044-0
  • Mohanta, J. C., & Keshari, A. (2019). A knowledge based fuzzy-probabilistic roadmap method for mobile robot navigation. Applied Soft Computing, 79, 391–409. https://doi.org/https://doi.org/10.1016/j.asoc.2019.03.055
  • Nasrollahy, A. Z., & Javadi, H. H. S. (2009). Using Particle Swarm Optimization for Robot Path Planning in Dynamic Environments with Moving Obstacles and Target. 2009 Third UKSim European Symposium on Computer Modeling and Simulation, 60–65. https://doi.org/10.1109/EMS.2009.67
  • Nazarahari, M., Khanmirza, E., & Doostie, S. (2019). Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm. Expert Systems with Applications, 115, 106–120. https://doi.org/https://doi.org/10.1016/j.eswa.2018.08.008
  • Ouach, M. K., Eren, T., & Özcan, E. (2022). PRM path smoothening by circular arc fillet method for mobile robot navigation. Arxiv.Org.
  • Raja, P., & Pugazhenthi, S. (2012). Optimal path planning of mobile robots: A review. International Journal of Physical Sciences, 7(9), 1314–1320.
  • Ravankar, A., Ravankar, A. A., Kobayashi, Y., & Emaru, T. (2016). SHP: Smooth Hypocycloidal Paths with Collision-free and Decoupled Multi-robot Path Planning. Internatıonal Journal Of Advanced Robotıc Systems, 13. https://doi.org/10.5772/63458
  • Sánchez, G., & Latombe, J.-C. (2002). On delaying collision checking in PRM planning: Application to multi-robot coordination. International Journal of Robotics Research, 21(1), 5–26. https://doi.org/10.1177/027836402320556458
  • Simba, K. R., Uchiyama, N., Aldibaja, M., & Sano, S. (2015). Vision-based smooth obstacle avoidance motion trajectory generation for autonomous mobile robots using Bézier curves. Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science, 231(3), 541–554. https://doi.org/10.1177/0954406215616986
  • Song, B., Wang, Z., & Sheng, L. (2016). A new genetic algorithm approach to smooth path planning for mobile robots. Assembly Automation, 36(2), 138–145. https://doi.org/10.1108/AA-11-2015-094
  • Song, B., Wang, Z., & Zou, L. (2021). An improved PSO algorithm for smooth path planning of mobile robots using continuous high-degree Bezier curve. Applied Soft Computing, 100, 106960. https://doi.org/https://doi.org/10.1016/j.asoc.2020.106960
  • Song, B., Wang, Z., Zou, L., Xu, L., & Alsaadi, F. E. (2019). A new approach to smooth global path planning of mobile robots with kinematic constraints. International Journal of Machine Learning and Cybernetics, 10(1), 107–119. https://doi.org/10.1007/s13042-017-0703-7
  • Su, K.-H., & Phan, T.-P. (2014). Robot Path Planning and Smoothing Based on Fuzzy Inference. 2014 IEEE International Conference On System Science And Engineering (ICSSE), 64–68.
  • Sudhakara, P., Ganapathy, V., & Sundaran, K. (2017). Probabilistic roadmaps-spline based trajectory planning for wheeled mobile robot. 2017 International Conference on Energy, Communication, Data Analytics and Soft Computing (ICECDS), 3579–3583. https://doi.org/10.1109/ICECDS.2017.8390129
  • Sugihara, K., & Smith, J. (1997). Genetic algorithms for adaptive motion planning of an autonomous mobile robot. Proceedings 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation CIRA’97. “Towards New Computational Principles for Robotics and Automation,” 138–143. https://doi.org/10.1109/CIRA.1997.613850
  • Sun, Y., Zhang, C., Sun, P., & Liu, C. (2020). Safe and Smooth Motion Planning for Mecanum-Wheeled Robot Using Improved RRT and Cubic Spline. Arabian Journal for Science and Engineering, 45(4), 3075–3090. https://doi.org/10.1007/s13369-019-04283-x
  • Tharwat, A., Elhoseny, M., Hassanien, A. E., Gabel, T., & Kumar, A. (2019). Intelligent Bézier curve-based path planning model using Chaotic Particle Swarm Optimization algorithm. Cluster Computing, 22(s2), 4745–4766. https://doi.org/10.1007/s10586-018-2360-3
  • Wang, K., Dang, S., He, F., & Cheng, P. (2017). A Path Planning Method for Indoor Robots Based on Partial a Global A-Star Algorithm. 130(Fmsmt), 395–398. https://doi.org/10.2991/fmsmt-17.2017.83
  • Yang, C.-Y., Yang, J.-S., & Lian, F.-L. (2012). Safe And Smooth: Mobile Agent Trajectory Smoothing By Svm. International Journal Of Innovative Computing Information And Control, 8(7B), 4959–4978.
  • Yang, K., Jung, D., & Sukkarieh, S. (2013). Continuous curvature path-smoothing algorithm using cubic Bezier spiral curves for non-holonomic robots. Advanced Robotics, 27(4), 247–258. https://doi.org/10.1080/01691864.2013.755246

Mobil Robot Navigasyonu için Dairesel Kavis Dolgu Yöntemiyle PRM Yol Yumuşatma

Year 2024, Volume: 16 Issue: 1, 1 - 19, 31.01.2024

Meral Kılıçarslan Ouach , Tolga Eren , Evrencan Özcan

https://doi.org/10.29137/umagd.1278980

Abstract

The problem of motion planning and navigation for mobile robots in complex environments has been a central issue in robotics. Navigating these environments requires sophisticated algorithms that handle obstacles and provide smooth, efficient paths. The Probabilistic Roadmap (PRM) method is a widespread technique in robotics for constructing paths for mobile robot navigation. In this study, we propose a novel path-smoothing method using arc fillets for path planning, building on PRM's foundation in the presence of obstacles. Our method operates in two primary stages to improve path efficiency and quality. The first stage generates the shortest path between the initial and goal states in an obstacle-rich environment using PRM, constructing a straight-line, collision-free route. The second stage smooths corners caused by nodes with arc fillets, ensuring smooth turns and minimizing abrupt changes in direction, resulting in more natural and efficient robot motion. We conducted simulations and tests using various PRM features to evaluate the proposed method. The results indicate that the built route offers a smooth turning motion and quicker, more compact movement while evading obstacles. This study contributes to mobile robot navigation by offering a practical approach to improving pathway quality in challenging environments.

Keywords

Probabilistic Roadmap Method (PRM) planner Path smoothening Arc fillet method

References

  • Aria, M. (2020). New sampling based planning algorithm for local path planning for autonomous vehicles. Journal of Engineering Science and Technology, 15, 66–76.
  • Ayawli, B. B. K., Appiah, A. Y., Nti, I. K., Kyeremeh, F., & Ayawli, E. I. (2021). Path planning for mobile robots using Morphological Dilation Voronoi Diagram Roadmap algorithm. Scientific African, 12, e00745.https://doi.org/10.1016/j.sciaf.2021.e00745
  • Bohlin, R., & Kavraki, L. E. (2000). Path planning using Lazy PRM. Proceedings-IEEE International Conference on Robotics and Automation, 1, 521–528. https://doi.org/10.1109/ROBOT.2000.844107
  • Canny, J. (1988). The complexity of robot motion planning. MIT Press.
  • Cheok, K. C., Iyengar, K., & Oweis, S. (2019). Smooth trajectory planning for autonomous leader-follower robots. Proceedings of 34th International Conference on Computers and Their Applications, CATA 2019, 58, 301–309. https://doi.org/10.29007/n6kt
  • Choset, H. M. (2005). Principles of robot motion : theory, algorithms, and implementation. MIT Press.
  • Contreras-Cruz, M. A., Ayala-Ramirez, V., & Hernandez-Belmonte, U. H. (2015). Mobile robot path planning using artificial bee colony and evolutionary programming. Applied Soft Computing, 30, 319–328. https://doi.org/https://doi.org/10.1016/j.asoc.2015.01.067
  • Davoodi, M., Panahi, F., Mohades, A., & Hashemi, S. N. (2015). Clear and smooth path planning. Applied Soft Computing, 32, 568–579. https://doi.org/https://doi.org/10.1016/j.asoc.2015.04.017
  • Elhoseny, M., Tharwat, A., & Hassanien, A. E. (2018). Bezier Curve Based Path Planning in a Dynamic Field using Modified Genetic Algorithm. Journal of Computational Science, 25, 339–350. https://doi.org/https://doi.org/10.1016/j.jocs.2017.08.004
  • Gang, L., & Wang, J. (2016). PRM Path planning optimization algorithm research. WSEAS Trans. Syst. Control, 11, 81–85.
  • Hamdy A. Taha. (1997). Operations research: An introduction. Computers & Mathematics with Applications, 33(5), 132. https://doi.org/https://doi.org/10.1016/S0898-1221(97)82948-3
  • Han, J., & Seo, Y. (2017). Mobile robot path planning with surrounding point set and path improvement. Applied Soft Computing Journal, 57, 35–47. https://doi.org/10.1016/j.asoc.2017.03.035
  • Huh, U.-Y., & Chang, S.-R. (2014). A G(2) Continuous Path-smoothing Algorithm Using Modified Quadratic Polynomial Interpolation. International Journal Of Advanced Robotic Systems, 11. https://doi.org/10.5772/57340
  • Janjoš, F., Reichart, R., & Niermeyer, P. (2017). Smooth Path-Generation Around Obstacles Using Quartic Splines and RRTs. IFAC-PapersOnLine, 50(1), 9108–9113. https://doi.org/10.1016/j.ifacol.2017.08.1708
  • Ju, M.-Y., & Cheng, C.-W. (2011). Smooth Path Planning Using Genetic Algorithms. 2011 9th World Congress On Intelligent Control And Automation (Wcica 2011), 1103–1107.
  • Kapitanyuk, Y. A., & Chepinsky, S. A. (2013). Control of mobile robot following a piecewise-smooth path. Gyroscopy and Navigation, 4(4), 198–203. https://doi.org/10.1134/S207510871304007X
  • Ladd, A. M., & Kavraki, L. E. (2004). Measure theoretic analysis of probabilistic path planning. IEEE Transactions on Robotics and Automation, 20(2), 229–242. https://doi.org/10.1109/TRA.2004.824649
  • Latombe , J.-C. (1991). Robot Motion Planning. https://public.ebookcentral.proquest.com/choice/publicfullrecord.aspx?p=3080882 LaValle , ProQuest (Firm), S. M. (2006). Planning algorithms. Cambridge University Press.
  • Miller, R. D. (1992). IV.5 - Joining Two Lines With A Circular Arc Fillet. In D. Kirk (Ed.), Graphics Gems III (IBM Version) (pp. 193–198). Morgan Kaufmann. https://doi.org/https://doi.org/10.1016/B978-0-08-050755-2.50044-0
  • Mohanta, J. C., & Keshari, A. (2019). A knowledge based fuzzy-probabilistic roadmap method for mobile robot navigation. Applied Soft Computing, 79, 391–409. https://doi.org/https://doi.org/10.1016/j.asoc.2019.03.055
  • Nasrollahy, A. Z., & Javadi, H. H. S. (2009). Using Particle Swarm Optimization for Robot Path Planning in Dynamic Environments with Moving Obstacles and Target. 2009 Third UKSim European Symposium on Computer Modeling and Simulation, 60–65. https://doi.org/10.1109/EMS.2009.67
  • Nazarahari, M., Khanmirza, E., & Doostie, S. (2019). Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm. Expert Systems with Applications, 115, 106–120. https://doi.org/https://doi.org/10.1016/j.eswa.2018.08.008
  • Ouach, M. K., Eren, T., & Özcan, E. (2022). PRM path smoothening by circular arc fillet method for mobile robot navigation. Arxiv.Org.
  • Raja, P., & Pugazhenthi, S. (2012). Optimal path planning of mobile robots: A review. International Journal of Physical Sciences, 7(9), 1314–1320.
  • Ravankar, A., Ravankar, A. A., Kobayashi, Y., & Emaru, T. (2016). SHP: Smooth Hypocycloidal Paths with Collision-free and Decoupled Multi-robot Path Planning. Internatıonal Journal Of Advanced Robotıc Systems, 13. https://doi.org/10.5772/63458
  • Sánchez, G., & Latombe, J.-C. (2002). On delaying collision checking in PRM planning: Application to multi-robot coordination. International Journal of Robotics Research, 21(1), 5–26. https://doi.org/10.1177/027836402320556458
  • Simba, K. R., Uchiyama, N., Aldibaja, M., & Sano, S. (2015). Vision-based smooth obstacle avoidance motion trajectory generation for autonomous mobile robots using Bézier curves. Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science, 231(3), 541–554. https://doi.org/10.1177/0954406215616986
  • Song, B., Wang, Z., & Sheng, L. (2016). A new genetic algorithm approach to smooth path planning for mobile robots. Assembly Automation, 36(2), 138–145. https://doi.org/10.1108/AA-11-2015-094
  • Song, B., Wang, Z., & Zou, L. (2021). An improved PSO algorithm for smooth path planning of mobile robots using continuous high-degree Bezier curve. Applied Soft Computing, 100, 106960. https://doi.org/https://doi.org/10.1016/j.asoc.2020.106960
  • Song, B., Wang, Z., Zou, L., Xu, L., & Alsaadi, F. E. (2019). A new approach to smooth global path planning of mobile robots with kinematic constraints. International Journal of Machine Learning and Cybernetics, 10(1), 107–119. https://doi.org/10.1007/s13042-017-0703-7
  • Su, K.-H., & Phan, T.-P. (2014). Robot Path Planning and Smoothing Based on Fuzzy Inference. 2014 IEEE International Conference On System Science And Engineering (ICSSE), 64–68.
  • Sudhakara, P., Ganapathy, V., & Sundaran, K. (2017). Probabilistic roadmaps-spline based trajectory planning for wheeled mobile robot. 2017 International Conference on Energy, Communication, Data Analytics and Soft Computing (ICECDS), 3579–3583. https://doi.org/10.1109/ICECDS.2017.8390129
  • Sugihara, K., & Smith, J. (1997). Genetic algorithms for adaptive motion planning of an autonomous mobile robot. Proceedings 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation CIRA’97. “Towards New Computational Principles for Robotics and Automation,” 138–143. https://doi.org/10.1109/CIRA.1997.613850
  • Sun, Y., Zhang, C., Sun, P., & Liu, C. (2020). Safe and Smooth Motion Planning for Mecanum-Wheeled Robot Using Improved RRT and Cubic Spline. Arabian Journal for Science and Engineering, 45(4), 3075–3090. https://doi.org/10.1007/s13369-019-04283-x
  • Tharwat, A., Elhoseny, M., Hassanien, A. E., Gabel, T., & Kumar, A. (2019). Intelligent Bézier curve-based path planning model using Chaotic Particle Swarm Optimization algorithm. Cluster Computing, 22(s2), 4745–4766. https://doi.org/10.1007/s10586-018-2360-3
  • Wang, K., Dang, S., He, F., & Cheng, P. (2017). A Path Planning Method for Indoor Robots Based on Partial a Global A-Star Algorithm. 130(Fmsmt), 395–398. https://doi.org/10.2991/fmsmt-17.2017.83
  • Yang, C.-Y., Yang, J.-S., & Lian, F.-L. (2012). Safe And Smooth: Mobile Agent Trajectory Smoothing By Svm. International Journal Of Innovative Computing Information And Control, 8(7B), 4959–4978.
  • Yang, K., Jung, D., & Sukkarieh, S. (2013). Continuous curvature path-smoothing algorithm using cubic Bezier spiral curves for non-holonomic robots. Advanced Robotics, 27(4), 247–258. https://doi.org/10.1080/01691864.2013.755246
There are 38 citations in total.

Details

Primary Language English
Subjects Electrical Engineering
Journal Section Articles
Authors

Meral Kılıçarslan Ouach 0000-0002-1086-5273

Tolga Eren 0000-0001-5577-6752

Evrencan Özcan 0000-0002-3662-6190

Publication Date January 31, 2024
Submission Date April 8, 2023
Published in Issue Year 2024 Volume: 16 Issue: 1

Cite

APA Kılıçarslan Ouach, M., Eren, T., & Özcan, E. (2024). PRM Path Smoothening by Circular Arc Fillet Method for Mobile Robot Navigation. International Journal of Engineering Research and Development, 16(1), 1-19. https://doi.org/10.29137/umagd.1278980

All Rights Reserved. Kırıkkale University, Faculty of Engineering and Natural Science.