A framework and analysis for cooperative search using UAV swarms

ABSTRACT

We design and analyze the performance of cooperative search strategies for unmanned aerial vehicles (UAVs) searching for moving, possibly evading, targets in a hazardous environment. Rather than engaging in independent sensing missions, the sensing agents (UAVs with sensors) "work together" by arranging themselves into a flight configuration that optimizes their integrated sensing capability. If a UAV is shot down by enemy fire, the team adapts by reconfiguring its topology to optimally continue the mission with the surviving assets. We presetn a cooperative search methodology that integrates the multiple agents into an advantageous formation that distinctively enhances the sensing and detection operations of the system while minimizing the transmission of excessive control information for adaptation of the team's topology. After analyzing our strategy to determine the performance tradeoff between search time and number of UAVs employed, we present an algorithm that selects the minimum number of UAVs to deploy in order to meet a targeted search time within probabilistic guarantees.

REFERENCES

• 1: Ablavsky, V. and Snorrason, M. Optimal Search For a Moving Target: A Geometric Approach. In Proceedings of the AIAA Guidance, Navigation and Control Conference (Denver, CO, August 14--17). American Institute of Aeronautics and Astronautics, Virginia, 2000.
• 2: Benkoski, S., Monticino, M., and Weisinger, J. A Survey of the Search Theory Literature. Naval Research Logistics 38, 4 (August 1991), 469--494.
• 3: 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]
• 4: Hert, S., Tiwari, S. and Lumelsky, V. A Terrain-Covering Algorithm for an AUV. Autonomous Robots 3, 2 (1996), 91--119.
• 5: Koopman, B. O. The Theory of Search II, Target Detection. Operations Research 4, 5 (October 1956), 503--531.
• 6: Kurabayashi, J., Ota, J., Arai, T. And Yoshida, E. Cooperative Sweeping by Multiple Mobile Robots. In Proceedings of the IEEE International Conference on Robotics and Automation, (Minneapolis, MN, April 22--28). IEEE Computer Society Press, 1996, 1744--1749.
• 7: Lumelsky, V. J., Mukhopadhyay, S. and Sun, K. Dynamic Path Planning in Sensor-Based Terrain Acquisition. IEEE Transactions on Robotics and Automation, 6, 4, (August 1990), 462--472.
• 8: Passino, K., Polycarpou, M., Jacques, D., Pachter, M., Liu, Y., Yang, Y., Flint, M. and Baum, M. Cooperative Control for Autononous Air Vehicles. In Cooperative Control and Optimization, R. Murphey and P. Pardalos, editors. Kluwer Academic Publishers, Boston, 2002.
• 9: Polycarpou, M., Yang, Y. and Passino, K. A Cooperative Search Framework for Distributed Agents. In Proceedings of the 2001 IEEE International Symposium on Intelligent Control (Mexico City, Mexico, September 5--7). IEEE, New Jersey, 2001, 1--6.
• 10: Stone, L.D. Theory of Optimal Search. Academic Press, New York, 1975.
• 11: Shannon V. Spires , Steven Y. Goldsmith, Exhaustive Geographic Search with Mobile Robots Along Space-Filling Curves, Proceedings of the First International Workshop on Collective Robotics, p.1-12, July 04-05, 1998

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Military

General Terms:
Design, Performance, Reliability

Keywords:
UAV swarms, adaptive systems, cooperative robots, path and motion planning