C-Theta*: Cluster Based Path-Planning on Grids

Path planning is used to solve the problem of moving an agent towards a destination. Theta* is a well know any angle path planning algorithm which works by utilizing line of sight checks during the search. To find shorter paths that are not constraint to grid edges, there is a compromise in the time taken to reach the destination which makes Theta* undesirable as the grid map size increases. To solve this problem and enhance the search performance we propose a method which divides a map into high and low density regions using an unsupervised clustering algorithm based on the number of blocked nodes on a grid map. After comparing the proposed model with theta* the results show the time taken to find the shortest path to be reduced significantly in comparison with Theta* while the path length will remain as short as Theta.