Research Article Open Access

Traversal Algorithm for Complete Coverage

Kavitha Thiayagarajan1 and Coimbatore Ganeshsankar Balaji1
  • 1 SASTRA University, India
Journal of Computer Science
Volume 8 No. 12, 2012, 2032-2041

DOI: https://doi.org/10.3844/jcssp.2012.2032.2041

Submitted On: 12 July 2012 Published On: 15 December 2012

How to Cite: Thiayagarajan, K. & Balaji, C. G. (2012). Traversal Algorithm for Complete Coverage. Journal of Computer Science, 8(12), 2032-2041. https://doi.org/10.3844/jcssp.2012.2032.2041

Abstract

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.

  • 1,137 Views
  • 2,612 Downloads
  • 1 Citations

Download

Keywords

  • Complete
  • Area Coverage
  • Traversal Algorithm
  • Path Planning
  • Demining Algorithm