Cover
Vol. 12 No. 2 (2017)

Published: January 31, 2017

Pages: 221-234

Original Article

An algorithm for Path planning with polygon obstacles avoidance based on the virtual circle tangents

Zahraa Y. Ibrahim 1 Abdulmuttalib T. Rashid Ali F. Marhoon
1Electrical Engineering Department University of Basrah Basrah, Iraq
History
  • Received: November 30, 2016
  • Available Online: January 31, 2017
DOI

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

Abstract

In this paper, a new algorithm called the virtual circle tangents is introduced for mobile robot navigation in an environment with polygonal shape obstacles. The algorithm relies on representing the polygonal shape obstacles by virtual circles, and then all the possible trajectories from source to target is constructed by computing the visible tangents between the robot and the virtual circle obstacles. A new method for searching the shortest path from source to target is suggested. Two states of the simulation are suggested, the first one is the off-line state and the other is the on-line state. The introduced method is compared with two other algorithms to study its performance.

Keywords

References

  1. S. M. LaValle, *Planning Algorithms*, University of Illinois, 2006.
  2. B. Coppin, *Artificial Intelligence Illuminated*, 2004.
  3. J. Kaur, V. K. Banga, and G. Singh, “Robotic Path Planning Using the Intelligent Control,” International Conference on Advances in Electrical and Electronics Engineering (ICAEE), 2011.
  4. P. Raja and S. Pugazhenthi, “Optimal path planning of mobile robots: A review,” International Journal of Physical Sciences, vol. 7, no. 9, pp. 1314–1320, 2012.
  5. Y. Koren and J. Borenstein, “Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation,” IEEE Conference on Robotics and Automation, Sacramento, pp. 1398–1404, 1991.
  6. M. Hamani and A. Hassam, “Mobile Robot Navigation in Unknown Environment Using Improved APF Method,” 13th International Arab Conference on Information Technology (ACIT), 2012.
  7. S. Weijun, M. Rui, and Y. Chongchong, “A Study on Soccer Robot Path Planning with Fuzzy Artificial Potential Field,” Proceedings of the 2010 International Conference on Computing, Control and Industrial Engineering (CCIE), vol. 1, pp. 386–390, 2010.
  8. J. Gue, Y. Gao, and G. Cui, “Path planning of mobile robot based on improved potential field,” Information Technology Journal, vol. 12, no. 11, 2013.
  9. X. Yun and K. Tan, “A Wall-Following Method for Escaping Local Minima in Potential Field Based Motion Planning,” ICAR, Monterey, CA, 1997.
  10. G. Li, Y. Tamura, A. Yamash, and H. Asama, “Effective improved artificial potential field-based regression search method for autonomous mobile robot path planning,” International Journal of Mechatronics and Automation, vol. 3, no. 3, 2013.
  11. P. Bhattacharya and M. L. Gavrilova, “Voronoi diagram in optimal path planning,” 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD), 2007.
  12. S. Mohammadi and N. Hazar, “A Voronoi-based reactive approach for mobile robot navigation,” CSICC, CCIS 6, pp. 901–904, 2008.
  13. A. Sahraei, M. T. Manzuri, M. Tajfard, and S. Khoshbakht, “Obstacle avoidance using a near optimal trajectory for omni-directional mobile robots,” 12th International CSI Computer Conference (CSICC), Tehran, 2007.
  14. J. W. Choi, R. E. Curry, and G. H. Elkaim, “Real-time obstacle avoiding path planning for mobile robots,” AIAA Guidance, Navigation, and Control Conference (GNC), Toronto, Canada, 2010.
  15. T. Lozano-Perez, “Automatic Planning of Manipulator Transfer Movements,” IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-11, no. 10, 1981.
  16. T. Lozano-Perez and M. A. Wesley, “An algorithm for planning collision-free paths among polyhedral obstacles,” Communications of the ACM, vol. 22, no. 10, 1979.
  17. K. Nawade, V. Aditya, A. Shrivastava, and B. K. Rout, “Geometrical approach to online trajectory generation, obstacle avoidance and footstep planning for a humanoid robot,” 15th IEEE-RAS International Conference on Humanoid Robots, Seoul, 2015.
  18. Y.-H. Liu and S. Arimoto, “Proposal of tangent graph and extended tangent graph for path planning of mobile robots,” IEEE International Conference on Robotics and Automation, Sacramento, 1991.
  19. C. Alexopoulos and P. M. Griffin, “Path planning for a mobile robot,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 22, no. 2, 1992.
  20. D. Hearn and M. P. Baker, *Computer Graphics C*, 1996.
  21. L. Moroz, J. L. Cieślinski, M. Stakhiv, and V. Maksymovych, “A Comparison of Standard One-Step DDA Circular Interpolators with a New Cheap Two-Step Algorithm,” Modelling and Simulation in Engineering, Hindawi, 2014.
  22. J. L. Cieślinski and L. V. Moroz, “Fast exact digital differential analyzer for circle generation,” 2013.
  23. E. Welzl, “Smallest enclosing disks (balls and ellipsoids),” in *New Results and New Trends in Computer Science*, pp. 359–370, 1991.
  24. V. J. Lumelsky and T. Skewis, “Incorporating range sensing in the robot navigation function,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 20, no. 5, pp. 1058–1068, 1990.
  25. I. Kamon and E. Rivlin, “A new range-sensor-based global algorithm for mobile robots,” IEEE International Conference on Robotics and Automation, Minneapolis, 1996.