C – THETA* : PATH PLANNING ON GRIDS

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