Date of Award
1-13-2016
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
clustering, path finding, path planning
Supervisor
Goodwin, Scott
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Abstract
Finding the shortest path between two points on a given grid map is called path finding. Many algorithms have been devised, but the most widely used and efficient is A*. Theta* is an any-angle algorithm that finds shorter and more realistic paths when compared with A*. Theta* is an any angle path planning algorithm which works by utilizing line of sight checks during the search to find shorter paths due to which the algorithms takes considerable amount of time to find the goal as the map size increases. To solve this problem C – Theta* is proposed, It utilizes the concept of clustering to improve the search performance by implementing on-demand line of sight checks, this improves the time taken by C – Theta* to find the goal by at least 20% when compared with Theta* and the paths plotted are as short as Theta* and no longer than A* algorithms.
Recommended Citation
Mendonca, Pramod, "C – THETA* : PATH PLANNING ON GRIDS" (2016). Electronic Theses and Dissertations. 5654.
https://scholar.uwindsor.ca/etd/5654