¹Faculty of Information Technology, Duy Tan University, Danang, Vietnam.
²Institute of Engineering and Technology, Vinh University, Vietnam.
³Biomedical Engineering Department, International University-Vietnam National University, Ho Chi Minh, Vietnam.
⁴School of EEECS, Queen’s University Belfast, Belfast, UK.
⁵Department of Automotive Engineering, Vietnam Maritime University, Vietnam.

---

Abstract—Path planning for 2D grid maps has been studied for a long time, however the substantial leaps have just been achieved with recent series of Theta* variations, which allow the found path more efficient and realistic. Since the search is on grid, optimality is not guaranteed by incremental searching methods including Dijkstra, A*, Theta* and their variations like A*-PS, Lazy-Theta*, etc. In this paper, we present several attempts of improving sub-optimal path planning techniques in 2D grid maps. The combination of these attempts has reached results that are asymptotic to the optimal solution in terms of path length. The runtime for this method is much lower compared to that of the brute-force A* on Visibility Graphs.

Index Terms—Path planning, grid map, 2D map, incremental search.

[PDF]

Cite: Viet-Hung Dang, Hoang Huu Viet, Nguyen Duc Thang, Ngo Anh Vien, Le Anh Tuan, "Improving Path Planning Methods in 2D Grid Maps," Journal of Computers vol. 15, no. 1, pp. 1-9, 2020.

Copyright © 2020 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).