Journal of Computer Science

Traversal Algorithm for Complete Coverage

Kavitha Thiayagarajan and Coimbatore Ganeshsankar Balaji

DOI : 10.3844/jcssp.2012.2032.2041

Journal of Computer Science

Volume 8, Issue 12

Pages 2032-2041


There are many applications which require complete coverage and obstacle avoidance. The classical A* algorithm provides the user a shortest path by avoiding the obstacle. As well, the Dijkstra’s algorithm finds the shortest path between the source and destination. But in many applications we require complete coverage of the proposed area with obstacle avoidance. There are LSP, LSSP, BSA, spiral-STC and Complete Coverage D* algorithms which do not realize complete (100%) coverage. The complete coverage using a critical point algorithm assures complete coverage, but it is not well suited for applications like mine detection. Also for covering the missed region it keeps the obstacle as a critical point which is not advisable in critical applications where obstacle may be a dangerous one. To overcome this and to achieve the complete coverage we propose a novel graph traversal algorithm Traversal Algorithm for Complete Coverage (TRACC). Here the area to be scanned is decomposed into a finite number of cells. The traversal is done through all the cells after making sure the next cell has no obstacle. TRACC assures thorough coverage of the proposed area and ensuring that all the obstacles are avoided. Hence the TRACC always have the safer path while covering the entire area. It also reports the obstacle placed or blocked cell.


© 2012 Kavitha Thiayagarajan and Coimbatore Ganeshsankar Balaji. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.