On reduced time fault tolerant paths for multiple UAVs covering a hostile terrain

ABSTRACT

We present a method for finding reduced time coverage paths of multiple UAVs (Unmanned Air Vehicles) monitoring a 3D terrain represented as height fields. A novel metric based on per time visibility is used that couples visibility gained at a terrain point with the time spent to reach the point. This coupled metric is utilized to form reduced time paths by maximizing the visibility gained per unit time at every step. We compare the results of this approach with an approach that covers the terrain based on a per distance visibility metric, which reduces the sum, over distances covered by each UAV path. The comparisons show that the current method gives substantially time reduced paths albeit with an expected increase in sum over distances of UAV paths. We also show that time taken to cover the terrain based on the current metric is far less than prevalent methods that try to decompose the terrain based on visibility followed by time or time followed by visibility in a decoupled fashion. The method is further extended to provide for fault tolerance on a hostile terrain. Each terrain point is guaranteed to be seen by at-least one UAV that has not been damaged due to any calamity, shot or otherwise.

REFERENCES

• 1: N Hazon, F Mieli and G Kaminka, "Towards Robust Online Multi-Robot Coverage", Proc ICRA, 2006, pp: 1710--1715
• 2: Howie Choset, Coverage for robotics – A survey of recent results, Annals of Mathematics and Artificial Intelligence, v.31 n.1-4, p.113-126, 2001 [doi>10.1023/A:1016639210559]
• 3: B. Yamauchi, A frontier-based approach for autonomous exploration, Proceedings of the 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation, p.146, June 10-11, 1997
• 4: M. A. Batalin and G. S. Sukhatme. Spreading out: A local approach to multi-robot coverage. In Proc. of the 6th Internat. Symposium on Distributed Autonomous Robotic Systems, page 373382, 2002
• 5: Sameera Poduri and Gaurav S. Sukhatme "Constrained Coverage for Mobile Sensor Network". IEEE ICRA (2004), 165--171
• 6: Stephan Eidenbenz, Approximation algorithms for terrain guarding, Information Processing Letters, v.82 n.2, p.99-105, 30 April 2002 [doi>10.1016/S0020-0190(01)00255-1]
• 7: Mohamed S. Marzouqi , Ray A. Jarvis, New visibility-based path-planning approach for covert robotic navigation, Robotica, v.24 n.6, p.759-773, November 2006 [doi>10.1017/S0263574706002931]
• 8: M. S. Marzouqi and R. A. Jarvis, "Covert Robotics: Covert Path Planning in Unknown Environments"
• 9: A D Tews, G Sukhatme and M Mataric, "A Multi Robot Approach to Stealth Navigation in Presence of Obsevers", Proc of ICRA, 2004
• 10: Patrick Vincent , Izhak Rubin, A framework and analysis for cooperative search using UAV swarms, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.967919]
• 11: Randal Beard, Timothy McLain: Multiple UAV Cooperative Search Under Collision Avoidance And Communication Constraints, 2003 IEEE Conference on Decision and Control
• 12: N Hazon and G Kaminka, "Redundancy, Efficiency and Robustness in Multi-Robot Coverage", Proc ICRA, 2005, pp: 735--741

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

General Terms:
Algorithms

Keywords:
coverage, formal models of multi-robot plans, surveillance