Cover
Vol. 17 No. 1 (2021)

Published: June 30, 2021

Pages: 136-145

Original Article

Path Planning and Obstacles Avoidance in Dynamic Workspace Using Polygon Shape Tangents Algorithm

Duaa Ahmed Ramadhan 1 Auday Al-Mayyahi Mofeed Turky Rashid
1Electrical Engineering Department, University of Basrah, Basrah, Iraq
History
  • Received: April 5, 2021
  • Revised: May 17, 2021
  • Accepted: May 18, 2021
  • Available Online: May 20, 2021
DOI

https://doi.org/10.37917/ijeee.17.1.16

Abstract

This paper presents the design of a path planning system in an environment that contains a set of static and dynamic polygon obstacles localized randomly. In this paper, an algorithm so-called (Polygon shape tangents algorithm) is proposed to move a mobile robot from a source point to a destination point with no collision with surrounding obstacles using the visibility binary tree algorithm. The methodology of this algorithm is based on predicting the steps of a robot trajectory from the source to the destination point. The polygon shapes tangent algorithm is compared with the virtual circles' tangents algorithm for different numbers of static and dynamic polygon obstacles for the time of arrival and the length of the path to the target. The obtained result shows that the used algorithm has better performance than the other algorithms and gets less time of arrival and shortest path with free collision.

Keywords

References

  1. Z. Y. Ibrahim, A. T. Rashid, and A. F. Marhoon, “Prediction-Based Path Planning with Obstacle Avoidance in Dynamic Target Environment,” Basrah J. Eng. Sci., vol. 16, no. 2, pp. 48–60, 2016.
  2. B. Bonet and H. Geffner, “Planning as heuristic search,” Artif. Intell., vol. 129, no. 1–2, pp. 5–33, 2001.
  3. J. van den Berg, R. Shah, A. Huang, and K. Goldberg, “ANA*: Anytime Nonparametric A*,” in Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011, vol. 25, no. 1, pp. 105–111.
  4. P.-Y. P. Ting-Kai Wang, Quan Dang, “Path Planning Approach in Unknown Environment,” Int. J. Autom. Comput., vol. 7, no. 3, pp. 310–316, 2010.
  5. Enric Galceran and M. Carreras, “A survey on coverage path planning for robotics,” Rob. Auton. Syst., vol. 61, no. 12, pp. 1258–1276, 2013.
  6. M. K. JHA, G. A. KARRI, and M.-W. KANG, “A military path planning algorithm using visualization and dynamic GIS,” in Proceedings of the 4th WSEAS international conference on Computer engineering and applications, Cambridge, Stevens Point, Wisconsin, 2010, pp. 188–193.
  7. K. F, T. SH, K. W, Z. N, and A. SA, “A Review on Motion Planning and Obstacle Avoidance Approaches in Dynamic Environments,” Adv. Robot. Autom., vol. 4, no. 2, 2015.
  8. A. A.Ali, A. T. Rashid, M. Frasca, and L. Fortuna, “An algorithm for multi-robot collision-free navigation based on shortest distance,” Robotics and Autonomous Systems, vol. 75, Part B, pp. 119-128, 2016.
  9. Z. Y. Ibrahim, A. T. Rashid, and A. F. Marhoon, “Path planning algorithm for mobile robot navigation in a dynamic environment based on motion prediction and tangency graph,” IEEE First International Conference on Recent Trends of Engineering Science and Sustainability, January 2018.
  10. C. Undeger and F. Polat, “Real-time edge follow A real- time path search approach,” IEEE Trans. Syst. Man, Cybern. Part C (Applications Rev., vol. 37, no. 5, pp. 860–872, 2007.
  11. M. S. Alam, M. U. Rafique, and M. U. Khan, “Mobile Robot Path Planning in Static Environments using Particle Swarm Optimization,” Int. J. Comput. Sci. Electron. Eng., vol. 3, no. 3, pp. 253–257, 2015.
  12. S. Koenig and M. Likhachev, “Fast replanning for navigation in unknown terrain,” IEEE Trans. Robot., vol. 21, no. 3, pp. 354–363, 2005.
  13. A. Stentz, “The Focussed D* Algorithm for Real-Time Replanning,” Int. Jt. Conf. Artif. Intell., vol. 95, pp. 1652–1659, 1995.
  14. A. T. Rashid, A. A. Ali, M. Frasca, and L. Fortuna, “Path planning with obstacle avoidance based on visibility binary tree algorithm,” Rob. Auton. Syst., vol. 61, no. 12, pp. 1440–1449, 2013.
  15. [Z. Y. Ibrahim, A. T. Rashid, and A. F. Marhoon, “An algorithm for Path planning with polygon obstacles avoidance based on the virtual circle tangents,” Iraqi J. Electr. Electron. Eng., vol. 12, no. 2, 2016.
  16. I. S. A. Al-Forati and A. Rashid, “Design and Implementation an Indoor Robot Localization System Using Minimum Bounded Circle Algorithm,” in 2019 8th International Conference on Modeling Simulation and Applied Optimization (ICMSAO), 2019, pp. 1–6.
  17. A. T. Rashid, A. A. Ali, M. Frasca, and L. Fortuna, “Multi-robot collision-free navigation based on reciprocal orientation,” Rob. Auton. Syst., vol. 60, no. 10, pp. 1221–230, 2012.
  18. A. A. Aldair and A. Al-Mayyahi, “Maze Maneuvering and Colored Object Tracking for Differential Drive Mobile Robot,” Iraqi J. Electr. Electron. Eng., vol. 15, no. 1, pp. 47–52, 2019.
  19. B. N. Abdul Samed, A. A. Aldair, and A. Al-Mayyahi, “Robust Trajectory Tracking Control and Obstacles Avoidance Algorithm for Quadrotor Unmanned Aerial Vehicle,” J. Electr. Eng. Technol., vol. 15, no. 2, pp. 855– 868, 2020.
  20. A. Al-Mayyahi and W. Wang, “Fuzzy inference approach for autonomous ground vehicle navigation in a dynamic environment,” in 2014 IEEE International Conference on Control System, Computing and Engineering (ICCSCE 2014), 2014, pp. 29–34.