This paper presents a distributed control algorithm for multi-target surveillance by multiple robots. Robots equipped with sensors and communication devices discover and track as many evasive targets as possible in an open region. The algorithm utilizes information from sensors, communication, and a mechanism to predict the minimum time before a robot loses a target. Workload is shared locally between robots using a greedy assignment of targets. Across long distances robots cooperate through explicit communication. The approach is coined Behavioral Cooperative Multi-robot Observation of Multiple Moving Targets. A formal representation of the proposed algorithm as well as proofs of performance guarantee are provided. Extensive simulations confirm the theoretical results in practice.
Bar-Shalom, Y. and Fortmann, T.E. (1987). Tracking and data association. Academic Press Professional, San Diego, CA.
2.
Chin, W.P. and Ntafos, S. (1991). Shoretest watchman routes in simple polygons. Discrete and Computational Geometry, 6(1): 9—31.
3.
Cortés, J., Martínez, S., and Bullo, F. (2006). Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions. IEEE Transactions on Automatic Control2004, 51(8): 1289—1298.
4.
Cortés, J., Martínez, S., Karatas, T., and Bullo, F. (2004). Coverage control for mobile sensing netorks. IEEE Transactions on Robotics and Automation, 20(2): 243—255.
5.
Gerkey, B., Thrun, S., and Gordon, G. (2006). Visibility-based pursuit-evasion with limited field of view. International Journal of Robotics Research , 25(4): 299—316.
6.
Gerkey, B., Vaughan, R., and Howard, A. (2003). The player/stage project: Tools for multi-robot and distributed sensor systems. Proceedings of IEEE International Conference on Robotics and Automation, pp 317—323.
7.
González-Baños, H.H., Guibas, L., Latombe, J.-C., LaValle, S.M., Lin, D., Motwani, R., and Tomasi, C. (1998). Motion planning with visibility constraints: Building autonomous observers. In Proceedings of the Eighth International Symposium on Robotics Research (eds Y. Shirai and S. Hirose), pp. 95—101, Springer-Verlag, Berlin.
8.
Guibas, L., Latombe, J.-C., LaValle, S.M., Lin, D., and Motwani, R. (1999). A visibility-based pursuit-evasion problem. International Journal of Computational Geometry and Applications, 9(4/5): 471—494.
9.
Jadbabaie, A., Lin, J. and Morse A.S. (2003). Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6): 988—1001.
10.
Jung, B. and Sukhatme, G. (2002). Tracking targets using multiple mobile robots: the effect of environment occlusion. Autonomous Robots,13(2): 191—205.
11.
Jung, B. and Sukhatme, G. (2006). Cooperative multirobot target tracking. In Proceedings of the 8th International Symposium on Distributed Autonomous Systems (eds M. Gini and R. Voyles), pp. 81—90, Springer-Verlag .
12.
Kolling, A. (2006). Multirobot cooperation for surveillance of multiple moving targets — an improved behavioral approach and its formalization . Master's thesis, International University Bremen, Germany.
13.
Kolling, A. and Carpin, S. (2006). Multirobot cooperation for surveillance of multiple moving targets — a new behavioral approach. Proceeding of the IEEE International Conference on Robotics and Automation , pp. 1311—1316
14.
LaValle, S.M., Lin, D., Guibas, L., Latombe, J.-C., and Motwani, R. (1997). Finding an unpredictable target in a workspace with obstacles. Proceedings IEEE International Conference on Robotics and Automation, pp. 737—742.
15.
Martínez, S. and Bullo, F. (2006). Optimal sensor placement and motion coordination for target tracking. Automatica,42(4): 661—668.
16.
Mills, D.L. (1995). Improved algorithms for synchronizing computer network clocks. IEEE Transactions on Networking,3(3): 245—254.
17.
Oh, S., Russell, S., and Sastry, S. (2004). Markov chain monte carlo data association for general multiple-target tracking problems. Proceedings of the 43rd IEEE Conference on Decision and Control, pp. 735—742.
18.
Parker, L.E. (2002). Distributed algorithms for multi-robot observation of multiple moving targets. Autonomous Robots,12(3): 231—255.
19.
Parker, L.E. (1998). Alliance: An architecture for fault-tolerant multi-robot cooperation. IEEE Transactions on Robotics and Automation , 14(2): 220—240.
Sachs, S., Rajko, S., and LaValle, S.M. (2004). Visibility-based pursuit-evasion in an unknown planar environment. International Journal of Robotics Research , 23(1): 3—26.
22.
Saptharishi, M., Spence Oliver, C., Dihel, C.P., Bhat, K.S., Dolan, J.M., Trebi-Ollennu, A., and Kohsla, P.K. (2002). Distributed surveillance and reconnaisance using multiple autonomous atvs: Cyberscout. IEEE Transactions on Robotics and Automation, 18(5): 826—836.
23.
Schenato, L., Oh, S., Sastry, S., and Bose, P. (2005). Swarm coordination for pursuit evasion games using sensor networks. Proceedings of the IEEE International Conference on Robotics and Automation, pp. 2493—2498.
24.
Shermer, T.C. (1992). Recent results in art galleries. Proceedings of the IEEE, 80(9): 1384—1399.
25.
Suzuki, I. and M. Yamashita, M. (1992). Searching for a mobile intruder in a polygonal region. SIAM Journal of Computing , 21(5): 863—888.
26.
Werger, B.B. and Mataric, M.J. (2000). Broadcast of local eligibility for multi-target observation. In Distributed Autonomous Robotics Systems 4 (eds Parker et al.), pp. 347— 358, Springer.
