Hybrid metaheuristic approach for robot path planning in dynamic environment

Lina Basem Amar, Wesam M Jasim /Article Link

Recently robots have gained great attention due to their ability to operate in dynamic and complex environments with moving obstacles. The path planning of a moving robot in a dynamic environment is to find the shortest and safe possible path from the starting point towards the desired target point. A dynamic environment is a robot's environment that consists of some static and moving obstacles. Therefore, this problem can be considered as an optimization problem and thus it is solved via optimization algorithms. In this paper, three approaches for determining the optimal pathway of a robot in a dynamic environment were proposed. These approaches are; the particle swarming optimization (PSO), ant colony optimization (ACO), and hybrid PSO and ACO. These used to carry out the path planning tasks effectively. A set of certain constraints must be met simultaneously to achieve the goals; the shortest path, the least time, and free from collisions. The results are calculated for the two algorithms separately and then that of the hybrid algorithm is calculated. The effectiveness and superiority of the hybrid algorithm were verified on both PSO and ACO algorithms.

Key Words— dynamic environment; ACO algorithm; colony optimization .

REFERENCES

[1] A. Q. Faridi, S. Sharma, A. Shukla, R. Tiwari, and J. Dhar, “Multi-robot multi-target dynamic path planning using artificial bee colony and evolutionary programming in unknown environment,” Intelligent Service Robotics, vol. 11, no. 2, pp. 171-186, 2018, doi: 10.1007/s11370-017-0244-7.

[2] T. T. Mac, C. Copot, D. T. Tran, and R. De Keyser, “Heuristic approaches in robot path planning: A survey,” Robotics and Autonomous Systems, vol. 86, pp. 13-28, 2016, doi: 10.1016/j.robot.2016.08.001.

[3] A. A. Baker and Y. Y. Ghadi, “Autonomous system to control a mobile robot,” Bulletin of Electrical Engineering and Informatics, vol. 9, no. 4, pp. 1711-1717, 2020, doi: 10.11591/eei.v9i4.2380.

[4] W. S. Pambudi, E. Alfianto, A. Rachman, and D. P. Hapsari, “Simulation design of trajectory planning robot manipulator,” Bulletin of Electrical Engineering and Informatics, vol. 8, no. 1, pp. 196-205, 2019, doi: 10.11591/eei.v8i1.1179.

[5] M. Sood and V. K. Panchal, “Meta-heuristic techniques for path planning: Recent trends and advancements,” International Journal of Intelligent Systems Technologies and Applications, vol. 19, no. 1, pp. 36-77, 2020, doi: 10.1504/IJISTA.2020.105177.

[6] Klan?ar, G., Zdešar, A., Blaži?, S., & Škrjanc, I, “path planning. Wheeled Mobile Robotics, ” 419–481,2017, doi:10.1016/b978-0-12-804204-5.00008-

[7] B. B. K. Ayawli, X. Mei, M. Shen, A. Y. Appiah, and F. Kyeremeh, “Mobile Robot Path Planning in Dynamic Environment Using Voronoi Diagram and Computation Geometry Technique,” IEEE Access, vol. 7, pp. 86026- 86040, 2019, doi: 10.1109/ACCESS.2019.2925623.

[8] C. O. Yinka-Banjo and U. H. Agwogie, “Swarm intelligence optimization techniques in mobile path planning-A review,” International Journal of Engineering Research in Africa, vol. 37, pp. 62-71, 2018, doi: 10.4028/www.scientific.net/JERA.37.62.

[9] J. Park and U. Huh, “Path Planning for Autonomous Mobile Robot Based on Safe Space,” vol. 11, no. 5, pp. 1441- 1448, 2016, doi: 10.5370/JEET.2016.11.5.1441.

[10] A. Koubaa, et al., “Introduction to mobile robot path planning,” Stud. Comput. Intell Robot Path Planning and Cooperation, vol. 772, pp. 3-12, 2018, doi: 10.1007/978-3-319-77042-0_1.

[11] D. M. Connell and H. M. La, “Dynamic Path Planning and Replanning for Mobile Robot Team Using RRT,” PhD Thesis, University of Nevada, Reno, May 2017.

[12] G. Li and W. Chou, “Path planning for mobile robot using self-adaptive learning particle swarm optimization,” Science China Information Sciences, vol. 61, no. 5, pp. 1-18, May 2018, doi: 10.1007/s11432-016-9115-2.

[13] M. Elhoseny, A. Shehab, and X. Yuan, “Optimizing robot path in dynamic environments using Genetic Algorithm and Bezier Curve,” Journal of Intelligent and Fuzzy Systems, vol. 33, no. 4, pp. 2305-2316, 2017, doi: 10.3233/JIFS-17348.

[14] F. Cherni, C. Rekik, and N. Derbel, “Mobile robot navigation based on tangent circle algorithm Faten Cherni,” International Journal of Computer Applications in Technology,” vol. 59, no. 1, pp. 31-42, December 2018, doi: 10.1504/IJCAT.2019.097114.

[15] S. N. Annual, et al., “Ga-based optimisation of a lidar feedback autonomous mobile robot navigation system,” Bulletin of Electrical Engineering and Informatics, vol. 7, no. 3, pp. 433-441, 2018, doi: 10.11591/eei.v7i3.1275.

[16] B. K. Patle, A. Pandey, A. Jagadeesh, and D. R. Parhi, “Path planning in uncertain environment by using firefly algorithm,” Defence technology, vol. 14, no. 6, pp. 691-701, 2018, doi: 10.1016/j.dt.2018.06.004.

[17] A. S. H. H. V. Injarapu and S. K. Gawre, "A survey of autonomous mobile robot path planning approaches," 2017 International Conference on Recent Innovations in Signal processing and Embedded Systems (RISE), 2017, pp. 624-628, doi: 10.1109/RISE.2017.8378228.

[18] Q. M. Nguyen, L. N. M. Tran, and T. C. Phung, "A Study on Building Optimal Path Planning Algorithms for Mobile Robot," 2018 4th International Conference on Green Technology and Sustainable Development (GTSD), 2018, pp. 341-346, doi: 10.1109/GTSD.2018.8595558.

[19] L. M. R. Rere, B. A. Wardijono, and Y. I. Chandra, “A comparison study of three single-solution based metaheuristic optimisation for stacked auto encoder A comparison study of three single-solution based metaheuristic optimisation for stacked auto encoder,” Journal of Physics: Conference Series, vol. 1192, no. 1, p. 012066, March 2019, doi: 10.1088/1742-6596/1192/1/012066.

[20] S. Muthuraman and V. P. Venkatesan, "A Comprehensive Study on Hybrid Meta-Heuristic Approaches Used for Solving Combinatorial Optimization Problems," 2017 World Congress on Computing and Communication Technologies (WCCCT), 2017, pp. 185-190, doi: 10.1109/WCCCT.2016.53.

[21] M. Usman, “The Effect of the Implementation of a Swarm Intelligence Algorithm on the Efficiency of the Cosmos Open Source Managed Operating System,” Doctoral dissertation, Northcentral University, 2018.

[22] P. K. Das, H. S. Behera, S. Das, H. K. Tripathy, B. K. Panigrahi, and S. K. Pradhan, “A hybrid improved PSO-DV algorithm for multi-robot path planning in a clutter environment,” Neurocomputing, vol. 207, pp. 735-753, 2016, doi: 10.1016/j.neucom.2016.05.057.

[23] M. Cao, Y. Yang, and L. Wang, “Application of improved ant colony algorithm in the path planning problem of mobile robot,” Proceedings of the 2019 3rd High Performance Computing and Cluster Technologies Conference, pp. 11-15, 2019, doi: 10.1145/3341069.3341073.

[24] X. Dai, S. Long, Z. Zhang, and D. Gong, “Mobile robot path planning based on ant colony algorithm with a∗ heuristic method,” Frontiers in neurorobotics, vol. 13, p. 15, April, 2019, doi: 10.3389/fnbot.2019.00015.

[25] H. Haghighi, S. H. Sadati, S. M. M. Dehghan, and J. Karimi, “Hybrid form of particle swarm optimization and genetic algorithm for optimal path planning in coverage mission by cooperated unmanned aerial vehicles,” Journal of Aerospace Technology and Management, vol. 12, no. 1, pp. 1-13, 2020, doi: 10.5028/jatm.v12.1169.