Abstract
When mobile robot used in large-scale dynamic environments, it face more challenging problems in real-time path planning and collision-free path tracking. This paper presents a new hybrid path planning method that combines A* algorithm with adaptive window approach to conduct global path planning, real-time tracking and obstacles avoidance for mobile robot in large-scale dynamic environments. Firstly, a safe A* algorithm is designed to simplify the calculation of risk cost function and distance cost. Secondly, key path points are extracted from the planned path which generated by the safe A* to reduce the number of the grid nodes for smooth path tracking. Finally, the real-time motion planning based on adaptive window approach is adopted to achieve the simultaneous path tracking and obstacle avoidance (SPTaOA) together the switching of the key path points. The simulation and practical experiments are conducted to verify the feasibility and performance of the proposed method. The results show that the proposed hybrid path planning method, used for global path planning, tracking and obstacles avoidance, can meet the application needs of mobile robots in complex dynamic environments.
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.
References
Lim, Z.W., Hsu, D., Lee, W.S.: Adaptive informative path planning in metric spaces[J]. Int. J. Robot. Res. 35, 283–300 (2015)
Jie, J., Khajepour, A., Melek, W.W., et al.: Path planning and tracking for vehicle collision avoidance based on model predictive control with multiconstraints[J]. IEEE Trans. Veh. Technol. 66(2), 952–964 (2017)
Bhattacharya, S., Ghrist, R., Kumar, V.: Persistent homology for path planning in uncertain environments[J]. IEEE Trans. Robot. 31(3), 578–590 (2017)
Murillo, M., Sánchez, G., Genzelis, L., et al.: A real-time path-planning algorithm based on receding horizon techniques[J]. J. Intell. Robot. Syst. 91, 445–457 (2018)
Low, E.S., Ong, P., Cheah, K.C.: Solving the optimal path planning of a mobile robot using improved Q-learning [J]. Robot. Auton. Syst. 115, 143–161 (2019)
Mac, T.T., Copot, C., Tran, D.T., et al.: Heuristic approaches in robot path planning: a survey[J]. Robot. Auton. Syst. 86, 13–28 (2016)
Kala, R., Shukla, A., Tiwari, R.: Fusion of probabilistic a* algorithm and fuzzy inference system for robotic path planning[J]. Artif. Intell. Rev. 33(4), 307–327 (2010)
Persson, S.M., Sharf, I.: Sampling-based a* algorithm for robot path-planning[J]. Int. J. Robot. Res. 33(13), 1683–1708 (2014)
Chen, W., Zhang, T., Zou, Y.: Mobile robot path planning based on social interaction space in social environment[J]. Int. J. Adv. Robot. Syst. 15(3), 1–10 (2018)
Zhang, H.M., Li, M.L., Yang, L.: Safe path planning of Mobile robot based on improved a* algorithm in complex terrains[J]. Algorithms. 11(4), 44–62 (2018)
Bayili, S., Polat, F.: Limited-damage a*: a path search algorithm that considers damage as a feasibility criterion[J]. Knowl.-Based Syst. 24(4), 501–512 (2011)
Park, J.H, No, J.H., Huh, U.Y.: Safe global path planning of Mobile robots based on modified A* algorithm[M]// the 8th international conference on robotic, vision, Signal Processing & Power Applications, pp. 99–105. Springer Singapore (2014)
Aine, S., Swaminathan, S., Narayanan, V., et al.: Multi-Heuristic A*[J]. Int. J. Robot. Res. 35(1–3), 224–243 (2016)
Likhachev, M., Koenig, S.: A generalized framework for lifelong planning a* search[C]// fifteenth international conference on international conference on automated planning and scheduling, pp. 99–108. AAAI Press (2008)
Likhachev, M., Ferguson, D., Gordon, G.: Anytime search in dynamic graphs[J]. Artif. Intell. 172(14), 1613–1643 (2008)
Toll, W.V., Geraerts, R.: Dynamically pruned A* for re-planning in navigation meshes[C]// IEEE/RSJ international conference on Intelligent Robots & Systems. IEEE (2015)
Dakulovi, M., Petrovi, et al.: Two-way D* algorithm for path planning and replanning[J]. Robot. Auton. Syst. 59(5), 329–342 (2011)
Ammar, A., Bennaceur, H., Châari, I., et al.: Relaxed Dijkstra and a* with linear complexity for robot path planning problems in large-scale grid environments.[J]. Soft. Comput. 20(10), 4149–4171 (2016)
Montiel, O., Sepúlveda, R., Orozco-Rosas, U.: Optimal path planning generation for Mobile robots using parallel evolutionary artificial potential field[J]. J. Intell. Robot. Syst. 79(2), 237–257 (2015)
Moon, C.B., Chung, W.: Kinodynamic planner dual-tree RRT (DT-RRT) for two-wheeled Mobile robots using the rapidly exploring random tree[J]. IEEE Trans. Ind. Electron. 62(2), 1080–1090 (2015)
Zaid, T., Qureshi, A.H., Yasar, A., et al.: Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments[J]. Robot. Auton. Syst. 108, 13–27 (2018)
Taheri, E., Ferdowsi, M.H., Danesh, M.: Fuzzy Greedy RRT Path Planning Algorithm in a Complex Configuration Space[J]. Int. J. Control. Autom. Syst. 16(6), 3026–3035 (2018)
Aykut, Z., Volkan, S.: Follow the gap with dynamic window approach[J]. Int. J. Semant. Comput. 12(01), 43–57 (2018)
Fox, D., Burgard, W., Thrun, S.: The dynamic window approach to collision avoidance[J]. IEEE Rob. Auto. Mag. 4(1), 23–33 (2002)
Seder, M., Petrovic, I.: Dynamic window based approach to mobile robot motion control in the presence of moving obstacles[C]// IEEE international conference on robotics and automation, pp. 1986–1991. IEEE (2007)
Li, G.Y., Wu, Y.Y., Wei, W.: Guided dynamic window approach to collision avoidance in troublesome scenarios [C].China: Proceedings of the 7th World Congress on Intelligent Control and Automation (2008)
Zhong X., Peng X., Miao M.: Planning of robot paths through environment modelling and adaptive window [J]. J. Huazhong Univ. of Sci. and Tech. (Natural Science Edition). 38(6), 107–111 (2010)
Chen, Y., Wang, X., Hong, S., et al.: Motion planning implemented in ROS for mobile robot[C]// Control and decision conference, pp. 7149–7154. IEEE (2017)
Lu, M.C., Hsu, C.C., Chen, Y.J., et al.: Hybrid path planning incorporating global and local search for Mobile robot[J]. IEEE. 7429, 668–671 (2012)
Imran, M., Kunwar, F.: A Hybrid Path Planning Technique Developed by Integrating Global and Local Path Planner[C]// 2016 International Conference on Intelligent Systems Engineering (ICISE). IEEE (2016)
Cheng, C., Xiaoyang, H., Jiansheng, L., et al.: Global Dynamic Path Planning Based on Fusion of Improved A* Algorithm and Dynamic Window Approach [J]. J. Xi'an Jiaotong Univ. 51(11), 137–143 (2017)
Acknowledgments
This work was supported in part by the National Natural Science Foundation of China (NO. 61703356, 61305117), Industry-University Cooperation Project (IUCP) of Fujian Province (NO. 2017H6021), Fundamental Research Funds for the Central Universities(NO. 20720190129).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhong, X., Tian, J., Hu, H. et al. 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). https://doi.org/10.1007/s10846-019-01112-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-019-01112-z