This Article Abstract Free Full Text (Free PDF) Free Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Kolling, A. Articles by Carpin, S. Search for Related Content Social Bookmarking                         What's this?

Cooperative Observation of Multiple Moving Targets: an algorithm and its formalization

School of Engineering University of California 5200 North Lake Rd Merced,CA, 95344 - USA, akolling{at}ucmerced.edu

Stefano Carpin

School of Engineering University of California 5200 North Lake Rd Merced,CA, 95344 - USA, scarpin{at}ucmerced.edu

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.

Key Words: behavior-based systems • distributed robot systems • surveillance systems

References

• Bar-Shalom, Y. and Fortmann, T.E. (1987). Tracking and data association. Academic Press Professional, San Diego, CA.
• Chin, W.P. and Ntafos, S. (1991). Shoretest watchman routes in simple polygons. Discrete and Computational Geometry, 6(1): 9—31.[CrossRef]
• 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 Control 2004, 51(8): 1289—1298.[CrossRef]
• 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.[CrossRef][Web of Science]
• 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.[Abstract/Free Full Text]
• 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.
• 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.
• 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.[CrossRef]
• 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.[CrossRef][Web of Science]
• Jung, B. and Sukhatme, G. (2002). Tracking targets using multiple mobile robots: the effect of environment occlusion. Autonomous Robots, 13(2): 191—205.[CrossRef][Web of Science]
• 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.
• 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.
• 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
• 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.
• Martínez, S. and Bullo, F. (2006). Optimal sensor placement and motion coordination for target tracking. Automatica, 42(4): 661—668.[CrossRef][Web of Science]
• Mills, D.L. (1995). Improved algorithms for synchronizing computer network clocks. IEEE Transactions on Networking, 3(3): 245—254.[CrossRef]
• 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.
• Parker, L.E. (2002). Distributed algorithms for multi-robot observation of multiple moving targets. Autonomous Robots, 12(3): 231—255.[CrossRef][Web of Science]
• Parker, L.E. (1998). Alliance: An architecture for fault-tolerant multi-robot cooperation. IEEE Transactions on Robotics and Automation, 14(2): 220—240.[CrossRef][Web of Science]
• Player/stage project. (2005). http://playerstage.sourceforge.net
• 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.[Abstract]
• 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.[CrossRef][Web of Science]
• 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.
• Shermer, T.C. (1992). Recent results in art galleries. Proceedings of the IEEE, 80(9): 1384—1399.[CrossRef][Web of Science]
• Suzuki, I. and M. Yamashita, M. (1992). Searching for a mobile intruder in a polygonal region. SIAM Journal of Computing, 21(5): 863—888.[CrossRef]
• 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.

The International Journal of Robotics Research, Vol. 26, No. 9, 935-953 (2007)
DOI: 10.1177/0278364907080424


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?

This Article Abstract Free Full Text (Free PDF) Free Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Kolling, A. Articles by Carpin, S. Search for Related Content Social Bookmarking                         What's this?