Abstract
Optimal path planning refers to choosing a collision-free, shortest, and smooth path, which is achieved by proposing a new technique, Optimized A* (OA*). The proposed OA* is the hybrid version of three techniques that are ABA* (Adaptive Bidirectional A*), VTM (Vector triangulation method), and PSF (Path smoothing filter which is the modification of Bezier curve technique). The conventional A* only deal with the heuristic values of concerned nodes, but the proposed ABA* algorithm also considers the occupied cells/ obstacles present near the starting and goal nodes in the grid cells to select the shortest path from start to destination. Due to the involvement of the occupied cells, the execution time, path curves, and the number of operations is primarily reduced because occupied nodes are considered as closed nodes, and its heuristic calculation is not considered in the conventional method. The trajectory generated by the proposed ABA* technique is also further made smoother by implementing a path smoothing filter that is the combination of VTM and modified Bezier curve technique based on selecting optimal control point for the collision free trajectory. While implementing the proposed OA* makes the path trajectory become smoother by reducing the number of sharp turns by 85.36% w.r.t traditional ACO, 73.91% w.r.t improved ACO, and 64.70% w.r.t hybrid solution of ACO+ A*. Due to the reduction in the number of sharp turns in the path trajectory, the acceleration of the mobile robot is increased by 52.96% w.r.t traditional ACO, 28.63% w.r.t improved ACO, and 19.96% w.r.t hybrid solution of ACO+ A*.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Code Availability
The code used in this study is available upon request.
References
Dai, X., Long, S., Zhang, Z., Gong, D.: Mobile robot path planning based on ant colony algorithm with A* heuristic method. Front. Neurorobot. 13, 15 (2019)
Galceran, E., Carreras, M.: A survey on coverage path planning for robotics. Robot. Auton. Syst. 61(12), 1258–1276 (2013)
Urcola, P., Lázaro, M.T., Castellanos, J.A., Montano, L.: Cooperative minimum expected length planning for robot formations in stochastic maps. Robot. Auton. Syst. 87, 38–50 (2017)
Tahir, Z., et al.: Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments. Robot. Auton. Syst. 108, 13–27 (2018)
Krishnan, J., Rajeev, U.P., Jayabalan, J., Sheela, D.S.: Optimal motion planning based on path length minimisation. Robot. Auton. Syst. 94, 245–263 (2017)
Guo, H., Mao, Z., Ding, W., Liu, P.: Optimal search path planning for unmanned surface vehicle based on an improved genetic algorithm. Comput. Electr. Eng. 79, 106467 (2019)
Duchoň, F., Babinec, A., Kajan, M., Beňo, P., Florek, M., Fico, T., Jurišica, L.: Path planning with modified a star algorithm for a mobile robot. Proc. Eng. 96, 59–69 (2014)
Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)
Sântejudean, T., Buşoniu, L.: Online learning control for path-aware global optimization with nonlinear mobile robots. Control Eng. Pract. 126, 105228 (2022)
Mansouri, S.S., Kanellakis, C., Fresk, E., Kominiak, D., Nikolakopoulos, G.: Cooperative coverage path planning for visual inspection. Control Eng. Pract. 74, 118–131 (2018)
Mac, T.T., Copot, C., Tran, D.T., De Keyser, R.: Heuristic approaches in robot path planning: a survey. Robot. Auton. Syst. 86, 13–28 (2016)
Zhao, J., Cheng, D., Hao, C.: An improved ant colony algorithm for solving the path planning problem of the omnidirectional mobile vehicle. Math. Probl. Eng. 2016(1) (2016). https://doi.org/10.1155/2016/7672839
Singh, R., Nagla, K.S.: Comparative analysis of range sensors for robust autonomous navigation–a review. Sens. Rev. 40(1), 17–41 (2019)
Singh, R., Nagla, K.S.: Improved 2D laser grid mapping by solving mirror reflection uncertainty in SLAM. Int. J. Intell. Unmanned Syst. 6(2), 93–114 (2018). https://doi.org/10.1108/IJIUS-01-2018-0003
Singh, Ravinder: Optimized trajectory planning for the time efficient navigation of mobile robot in constrained environment. Int. J. Mach. Learn. Cybernet. 14(4), 1079–1103 (2023)
Song, B., Wang, Z., Zou, L.: An improved PSO algorithm for smooth path planning of mobile robots using continuous high-degree Bezier curve. Appl. Soft Comput. 100, 106960 (2021)
Lai, X., Li, J., Chambers, J.: Enhanced center constraint weighted a* algorithm for path planning of petrochemical inspection robot. J. Intell. Robot. Syst. 102, 1–15 (2021)
Candeloro, M., Lekkas, A.M., Sørensen, A.J.: A Voronoi-diagram-based dynamic path-planning system for underactuated marine vessels. Control Eng. Pract. 61, 41–54 (2017)
Shao, Shikai, Peng, Yu., He, Chenglong, Yun, Du.: Efficient path planning for UAV formation via comprehensively improved particle swarm optimization. ISA transactions 97, 415–430 (2020)
Wang, W., Zuo, L., Xu, X.: A learning based multi-RRT approach for robot path planning in narrow passages. J. Intelli. Robot. Syst. 90, 81–100 (2018)
Montiel, O., Sepúlveda, R., Orozco-Rosas, U.: Optimal path planning generation for mobile robots using parallel evolutionary artificial potential field. J. Intell. Robot. Syst. 79, 237–257 (2015)
Kumar, S., Sikander, A.: A modified probabilistic roadmap algorithm for efficient mobile robot path planning. Engineering Optimization, 55(9), 1616–1634 (2023). https://doi.org/10.1080/0305215X.2022.2104840
Zhong, X., Tian, J., Hu, H., Peng, X.: Hybrid path planning based on safe A* algorithm and adaptive window approach for mobile robot in large-scale dynamic environment. J. Intell. Robot. Syst. 99, 65–77 (2020)
Singh, R.: Trajectory optimization with hybrid probabilistic roadmap approach to achieve time efficient navigation of unmanned vehicles in unstructured environment. Robot. Intell. Automa. 44(1), 164–89 (2024). https://doi.org/10.1108/RIA-08-2023-0107
Tang, B., Hirota, K., Wu, X., Dai, Y., Jia, Z.: Path planning based on improved hybrid A* algorithm. J. Adv. Comput. Intell. Intell. Inform. 25(1), 64–72 (2021)
Wang, X., Liu, Z., Liu, J.: Mobile robot path planning based on an improved A* algorithm. In: International Conference On Computer Graphics, Artificial Intelligence, and Data Processing (ICCAID 2022), vol. 12604, pp. 1093–1098. SPIE (2023)
Mandloi, D., Arya, R., Verma, A.K.: Unmanned aerial vehicle path planning based on A* algorithm and its variants in 3d environment. Int. J. Syst. Assur. Eng. Manag. 12, 990–1000 (2021)
Singh, R.K., Nagla, K.S.: Reduction in trajectory error by generating smoother trajectory for the time-efficient navigation of mobile robot. MAPAN (2024). https://doi.org/10.1007/s12647-024-00752-3
Funding
No funding/grant to be informed.
Author information
Authors and Affiliations
Contributions
All the authors contribute equally to problem identification, analysis, experimental setup, result analysis and implementation.
Corresponding author
Ethics declarations
Ethics Approval
Not applicable.
Consent to Participate
Not applicable.
Consent for Publication
All authors comply with the consent to publish.
Competing Interests
Not applicable.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/.
About this article
Cite this article
Singh, R. A Hybrid Path Planning Technique for the Time-Efficient Navigation of Unmanned Vehicles in an Unconstrained Environment. J Intell Robot Syst 110, 119 (2024). https://doi.org/10.1007/s10846-024-02150-y
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10846-024-02150-y