Cover
Vol. 16 No. 2 (2016)

Published: November 30, 2016

Pages: 48-60

Original Article

Prediction-Based Path Planning with Obstacle Avoidance in Dynamic Target Environment

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

https://doi.org/10.33971/bjes.16.2.5

Abstract

In this paper, a new algorithm for mobile robot navigation and polygonal obstacles avoidance in dynamic target environment is introduced. In the dynamic target path planning the agent (robot) trying to reach a moving target in minimum path cost. The introduced algorithm which called Prediction-based path planning with obstacle avoidance in dynamic target environ- ment planning a path to a moving target by predicting the next target location, then computing a path from the robot current lo- cation to the predicted target location representing each visible obstacle by the smallest circle that enclosing the polygon obstacle, then determine the visible tangents between the robot and the cir- cular obstacle that intersect its shortest path and compute the shortest path. Three target movement scenarios were suggested and tested in different environment conditions. The results show that the target was reached in all scenarios and under all environ- ment conditions with good path cost.

Keywords

References

  1. J.F. Canny, J.M. Malik, D.D. Edwards"Artificial In- telligence A Modern Approach",1995.
  2. S. Koenig, and M. Likhachev,” Fast Replanning for Navigation in Unknown Terrain”, IEEE TRANSAC- TIONS ON ROBOTICS, VOL. 21, NO. 3, JUNE 2005.
  3. A.Stentz,” The Focussed D* Algorithm for Real-Time Replanning”, International Joint Conference on Artificial Intelligence, August 1995.
  4. A.T. Rashid, A. A. Ali, M. Frasca, and L. Fortuna,” Path planning with obstacle avoidance based on shortest distance algorithm”, Robotics and Autonomous Systems, Vol. 61, No. 12, p.p. 1440-1449, 2013.
  5. C.Undeger, and F.polat,” Real-Time Edge Follow: A Real-Time Path Search Approach”, IEEE Transactions on Systems Man and Cybernetics Part C, October 2007
  6. T.Ishida, and R.E. Korf,”Moving-Target Search: A real-Time Search for Changing Goals”,IEEE TRANSAC- TION ON PATTERN ANALYSIS AND MACHINE IN- TALIGENT ,Vol.17,NO.16,JUNE 1995
  7. T.Uras, S.Koenig, and C.Hern´andez” Subgoal Graphs for Optimal Pathfinding in Eight-Neighbor Grids”, Pro- ceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, 2013
  8. D.Nussbaum, and A.Yörüçkü,” Moving Target Search with Subgoal Graphs”, Proceedings of the Eighth Interna- tional Symposium on Combinatorial Search (SoCS-2015).
  9. C.Hern´andez,and J.A. Baier,” Fast Subgoaling for Pathfinding via Real-Time Search”, Association for the Advancement of Artificial Intelligence,2011.
  10. Y.Björnsson, Ramon Lawrence,and V. Bulitko,” Case-Based Subgoaling in Real-Time Heuristic Search for Video Game Pathfinding”, Journal of Artificial Intelli- gence Research,September 2010.
  11. D.Hearn, M.P.Baker,Computer Graphics C (1996).
  12. L.Moroz, J.L. CieVliNski, M.Stakhiv and V.Maksymovych, “A Comparison of Standard One-Step DDA Circular Interpolators with a New Cheap Two-Step Algorithm”, Hindawi Publishing Corporation Modelling and Simulation in Engineering, 2014.
  13. ] J.L. Cie´sli´nski and L.V.Moroz, "Fast exact digital differential analyzer for circle generation", 2013.
  14. E.Welzl, "Smallest enclosing disks (balls and ellip- soids)", APPEARED IN”New Results and New Trends in Computer Science 555, p.p. 359-370, 1991.