iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s10514-015-9491-7
Multi-robot target detection and tracking: taxonomy and survey | Autonomous Robots Skip to main content
Springer Nature Link
Log in

Multi-robot target detection and tracking: taxonomy and survey

  • Published:
Autonomous Robots Aims and scope Submit manuscript

Abstract

Target detection and tracking encompasses a variety of decisional problems such as coverage, surveillance, search, patrolling, observing and pursuit-evasion along with others. These problems are studied by several communities, that tackle them using diverse formulations, hypotheses and approaches. This variety and the fact that target related robotics problems are pertinent for a large spectrum of applications has motivated a large amount of contributions, which have mostly been surveyed according to one or another viewpoint. In this article, our objective is to go beyond the frontiers of specific communities and specific problems, and to enlarge the scope of prior surveys. We define classes of missions and problems, and relate the results from various communities according to a unifying taxonomy. We review various work related to each class of problems identified in the taxonomy, highlighting the different approaches, models and results. Finally, we propose a transverse synthesis which analyses the approaches, models and lacks that are recurrent through all the tackled problems, and isolate the current main research directions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Adaptive sampling or information gathering processes consist in assessing the extend and/or distribution of spatially spread phenomena—see Hollinger and Sukhatme (2013) for instance.

  2. The Set Cover Problem (SCP) is a classical question in combinatorics: given a set of elements (called the universe) and a set S of n sets whose union equals the universe, the SCP is to identify the smallest subset of S whose union equals the universe.

  3. Gazebo is a realistic robot platform simulator (Koenig and Howard 2004).

  4. Autonomous Ground/Aerial Vehicles.

  5. Note that the article does not refer to patrolling explicitly, although it exactly embraces its scope.

  6. The graph being non-cyclic, there does not strictly exist an Hamiltonian cycle: one should “re-use” some vertices to cover the whole graph, hence the non-optimality.

  7. Autonomous surface vehicles.

  8. Mixed-initiative interactions allows users to occasionally adjust or override the automated schedule.

  9. In a CAT(k) space, k is a lower bound of the space curvature. A notable special case is k = 0: complete CAT(0) spaces are known as Hadamard spaces. Traditional Euclidian spaces are CAT(0) spaces.

  10. Such as the Multi-Autonomous Ground Robot International Challenge (MAGIC) held in 2010 (Hsieh and Lacroix 2012) or the Eurathlon series of challenges.

References

  • Acevedo, J. J., Arrue, B. C., Maza, I., & Ollero, A. (2014). A decentralized algorithm for area surveillance missions using a team of aerial robots with different sensing capabilities. In IEEE international conference on robotics and automation (ICRA) (pp. 4735–4740).

  • Agmon, N., Kraus, S., & Kaminka, G. A. (2008). Multi-robot perimeter patrol in adversarial settings. In IEEE international conference on robotics and automation (ICRA) (pp. 2339–2345). doi:10.1109/ROBOT.2008.4543563.

  • Al Marzouqi, M., & Jarvis, R. A. (2011). Robotic covert path planning: A survey. In 2011 IEEE 5th international conference on robotics, automation and mechatronics (RAM) (pp. 77–82). doi:10.1109/RAMECH.2011.6070460.

  • Alamdari, S., Fata, E., & Smith, S. L. (2013). Persistent monitoring in discrete environments: Minimizing the maximum weighted latency between observations. International Journal of Robotics Research (IJRR). doi:10.1177/0278364913504011.

  • Alexander S., Bishop R., & Ghrist R. (2010). Total curvature and simple pursuit on domains of curvature bounded above. Geometriae Dedicata (pp. 1–15). arXiv:0909.4113v1.

  • Alexander, S., Bishop, R., & Ghrist, R. (2006). Pursuit and evasion in non-convex domains of arbitrary dimensions. In Proceedings of robotics: Science and systems (RSS).

  • Alexander, S., Bishop, R., & Ghrist, R. (2009). Capture pursuit games on unbounded domains. LEnseignement Mathématique, 55, 103–125.

    Article  MathSciNet  MATH  Google Scholar 

  • Almeida, A., Ramalho, G., Santana, H., & Corruble, V. (2004). Recent advances on multi-agent patrolling. Advances in artificial intelligence. Berlin: Springer.

    Google Scholar 

  • Alspach, B. (2006). Searching and sweeping graphs: A brief survey. Le matematiche, LIX, 5–37.

    MathSciNet  Google Scholar 

  • Amigoni, F., & Basilico, N. (2010). A decision-theoretic framework to select effective observation locations in robotic search and rescue scenarios. In IEEE international conference on robotics and automation (ICRA).

  • Amigoni, F., Basilico, N., & Gatti, N. (2009). Finding the optimal strategies for robotic patrolling with adversaries in topologically-represented environments. In IEEE international conference on robotics and automation (ICRA).

  • Amigoni, F., Basilico, N., & Li, A. (2013). How much worth is coordination of mobile robots for exploration in search and rescue? RoboCup 2012: Robot Soccer World Cup XVI.

  • Annas, J., Xiao, J. (2009). Intelligent Pursuit & Evasion in an unknown environment. In IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 4899–4906).

  • Annas, J., Xiao, J. (2010). Intelligent Pursuit & Evasion in unknown environments against human players—extended abstract. In IEEE international conference on robotics and automation (ICRA).

  • Ataei, H. N., Ziarati, K., & Eghtesad, M. (2013). A BSO-Based Algorithm for Multi-robot and Multi-target Search. In: Recent trends in applied artificial intelligence (pp. 312–321).

  • Balakirsky, S. (2007). Usarsim: a robocup virtual urban search and rescue competition. In: Defense and security symposium.

  • Bandyopadhyay, T., & Ang, M. (2006). A greedy strategy for tracking a locally predictable target among obstacles. In IEEE international conference on robotics and automation (ICRA) (pp. 2342–2347). doi:10.1109/ROBOT.2006.1642052.

  • Bandyopadhyay, T., Ang, Jr M. H., & Hsu, D. (2005). Stealth tracking of an unpredictable target among obstacles. Algorithmic foundations of robotics VI (pp. 43–58).

  • Bandyopadhyay, T., Rong, N., Ang, M., Hsu, D., & Lee, W. S. (2009). Motion planning for people tracking in uncertain and dynamic environments. In IEEE international conference on robotics and automation (ICRA)

  • Bandyopadhyay, T., M. Ang, Jr., Hsu, D. (2011). Motion planning for 3D target tracking among obstacles. Robotics Research.

  • Benkoski, S. J., Monticino, M. G., & Weisinger, J. R. (1991). A survey of the search theory literature. Naval Research Logistics (NRL), 38(4), 469–494.

    Article  MATH  Google Scholar 

  • Bhattacharya, S., Candido, S., & Hutchinson, S. (2007). Motion strategies for surveillance. In Proceedings of robotics: Science and systems (RSS).

  • Bhattacharya, S., Ghrist, R., & Kumar, V. (2013). Multi-robot coverage and exploration on Riemannian manifolds with boundaries. International Journal of Robotics Research (IJRR), 33(1), 113–137. doi:10.1177/0278364913507324.

    Article  Google Scholar 

  • Bhattacharya, S., & Hutchinson, S. (2009). On the existence of nash equilibrium for a two-player Pursuit–Evasion game with visibility constraints. International Journal of Robotics Research (IJRR), 29(7), 831–839. doi:10.1177/0278364909354628.

    Article  Google Scholar 

  • Bopardikar, S. D., Bullo, F., & Hespanha, J. P. (2007). Cooperative pursuit with sensing limitations. In American control conference (ACC), pp. 5394–5399. doi:10.1109/ACC.2007.4282474.

  • Borie, R., Tovey, C., & Koenig, S. (2011). Algorithms and complexity results for graph-based pursuit evasion. Autonomous Robots, 31(4), 317–332. doi:10.1007/s10514-011-9255-y.

    Article  Google Scholar 

  • Cai, Z., Sun, L., Gao, H., & Zhou, P. (2008). Multi-robot cooperative pursuit based on task bundle auctions. In Intelligent robotics and applications (pp. 235–244).

  • Cao, Z., Tan, M., Li, L., Gu, N., & Wang, S. (2006). Cooperative hunting by distributed mobile robots based on local interaction. IEEE Transactions on Robotics, 22(2), 403–407.

    Google Scholar 

  • Casbeer, D., & Kingston, D. (2006). Cooperative forest fire surveillance using a team of small unmanned air vehicles. International Journal of Systems Science, 37(6), 351–360.

  • Choset, H. (2000). Coverage of known spaces: The boustrophedon cellular decomposition. Autonomous Robots, 9(3), 247–253. doi:10.1023/A:1008958800904.

    Article  Google Scholar 

  • Choset, H. (2001). Coverage for robotics a survey of recent results. Annals of Mathematics and Artificial Intelligence, 31(1–4), 113–126. doi:10.1023/A:1016639210559.

    Article  Google Scholar 

  • Chu, H. N., Glad, A., Simonin, O., Sempe, F., Drogoul, A., & Charpillet, F. (2007). Swarm approaches for the patrolling problem, information propagation vs. pheromone evaporation. In IEEE international conference on tools with artificial intelligence (ICTAI) (pp. 442–449).

  • Chung, T. H., Ga, Hollinger, & Isler, V. (2011). Search and pursuit-evasion in mobile robotics. Autonomous Robots, 31(4), 299–316. doi:10.1007/s10514-011-9241-4.

    Article  Google Scholar 

  • Clark, J., & Fierro, R. (2007). Mobile robotic sensors for perimeter detection and tracking. ISA Transactions, 46(1), 3–13. doi:10.1016/j.isatra.2006.08.001.

    Article  Google Scholar 

  • Cole, D. T., Thompson, P., Göktogan, A. H., & Sukkarieh, S. (2010). System development and demonstration of a cooperative UAV team for mapping and tracking. International Journal of Robotics Research (IJRR), 29(11), 1371–1399. doi:10.1177/0278364910364685.

    Article  Google Scholar 

  • Cowley, A., Hsu, H. C., & Taylor, C. J. (2004). Distributed sensor databases for multi-robot teams. In IEEE international conference on robotics and automation (ICRA).

  • Daniel, K., Borie, R., Koenig, S., & Tovey, C. (2010). ESP: Pursuit evasion on series-parallel graphs (Extended Abstract). In International conference on autonomous agents and multiagent systems (AAMAS) (pp. 4–5).

  • Derenick, J., Spletzer, J., & Hsieh, A. (2009). An optimal approach to collaborative target tracking with performance guarantees. Journal of Intelligent and Robotic Systems, 56(1–2), 47–67. doi:10.1007/s10846-008-9302-x.

    Article  MATH  Google Scholar 

  • Dornhege, C., Kleiner, A., & Kolling, A. (2013). Coverage Search in 3D. In IEEE international symposium on safety, security, and rescue robotics (SSRR) (pp. 1–8). doi:10.1109/SSRR.2013.6719340.

  • Durham, J. W., Franchi, A., & Bullo, F. (2011). Distributed pursuit-evasion without mapping or global localization via local frontiers. Autonomous Robots.

  • Eaton, J. H., & Zadeh, L. (1962). Optimal pursuit strategies in discrete-state probabilistic systems. Journal of Fluids Engineering, 84(1), 23–29.

    MathSciNet  Google Scholar 

  • Echeverria, G., Lemaignan, S., Degroote, A., Lacroix, S., Karg, M., Koch, P., Lesire, C., & Stinckwich, S. (2012). Simulating complex robotic scenarios with MORSE. In Simulation, modeling, and programming for autonomous robots (SIMPAR) (pp. 197–208). Berlin: Springer.

  • Ehlers, F. (2010). Multi-robot teamwork in multistatic sonar. In ICRA Workshop: Search and pursuit/evasion in the physical world.

  • Elmaliach, Y., Agmon, N., & Kaminka, G. A. (2009). Multi-robot area patrol under frequency constraints. Annals of Mathematics and Artificial Intelligence, 57, 293–320. doi:10.1007/s10472-010-9193-y.

    Article  MathSciNet  MATH  Google Scholar 

  • El-Rayes, A. B., Mohamed, A. E. M. A., & Gabal, H. M. A. (2003). Linear search for a Brownian target motion. Acta Mathematica Scientia, 23(3), 321–327.

    MathSciNet  MATH  Google Scholar 

  • Erol, K. (1996). Hierarchical task network planning: Formalization, analysis, and implementation. PhD thesis, University of Maryland.

  • Fazli, P., Davoodi, A., Pasquier, P., & Mackworth, A. K. (2010). Fault-tolerant multi-robot area coverage with limited visibility. In ICRA workshop: search and pursuit/evasion in the physical world.

  • Ferrari, S., Fierro, R., & Tolic, D. (2009). A geometric optimization approach to tracking maneuvering targets using a heterogeneous mobile sensor network. In IEEE conference on decision and control, held jointly with the Chinese control conference (CDC-CCC) (pp. 1080–1087).

  • Flushing, E. F., Gambardella, L., & Caro, G. A. D. (2012). GIS-based mission support system for wilderness search and rescue with heterogeneous agents. In IEEE/RSJ international conference on intelligent robots and systems (IROS), Workshop on robots and sensors integration in future rescue INformation system (ROSIN).

  • Gan, S. K., Fitch, R., & Sukkarieh, S. (2012). Real-time decentralized search with inter-agent collision avoidance. In IEEE international conference on robotics and automation (ICRA) (pp. 504–510). doi:10.1109/ICRA.2012.6224975.

  • Gerkey, B. P., & Matarić, M. J. (2004). A formal analysis and taxonomy of task allocation in multi-robot systems. International Journal of Robotics Research (IJRR), 23(9), 939–954.

    Article  Google Scholar 

  • Gerkey, B. P., Thrun, S., & Gordon, G. (2006). Visibility-based pursuit-evasion with limited field of view. International Journal of Robotics Research (IJRR), 1(c), 20–27.

    Google Scholar 

  • Ghosh, S. K. (2009). Approximation algorithms for art gallery problems in polygons. In Conference on discrete mathematics.

  • Glad, A., Simonin, O., Buffet, O., & Charpillet, F. (2008). Theoretical study of ant-based algorithms for multi-agent patrolling. In Proceedings—2008 European conference on artificial intelligence.

  • Glad, A., Simonin, O., Buffet, O., & Charpillet, F. (2010). Influence of different execution models on patrolling ant behaviors: From agents to robots. In International conference on autonomous agents and multiagent systems (AAMAS).

  • González-Baños, H., & Latombe, J. C. (2001). A randomized art-gallery algorithm for sensor placement. In 7th Annual symposium on computational geometry.

  • Grocholsky, B., Swaminathan, R., Keller, J., Kumar, V., & Pappas, G. (2005). Information driven coordinated air-ground proactive sensing. In IEEE international conference on robotics and automation (ICRA) (pp. 2223–2228).

  • Hereford, J., & Siebold, M. (2010). Bio-inspired search strategies for robot swarms. Swarm Robotics, From Biology to Robotics.

  • Hespanha, J. P., Kim, H. J., & Sastry, S. (1999). Multiple-agent probabilistic pursuit-evasion games. In IEEE conference on decision and control (CDC).

  • Hollinger, G. A., & Sukhatme, G. (2013). Sampling-based motion planning for robotic information gathering. In Proceedings of robotics: Science and systems (RSS).

  • Hollinger, G., Singh, S. (2010). Multi-robot coordination with periodic connectivity. In IEEE international conference on robotics and automation (ICRA).

  • Hollinger, G., Kehagias, A., & Singh, S. (2010). GSST: Anytime guaranteed search. Autonomous Robots, 29(1), 99–118. doi:10.1007/s10514-010-9189-9.

    Article  Google Scholar 

  • Hollinger, G. A., & Singh, S. (2012). Multirobot Coordination With Periodic Connectivity: Theory and Experiments. IEEE Transactions on Robotics, 28(4), 967–973. doi:10.1109/TRO.2012.2190178.

    Article  Google Scholar 

  • Hollinger, G., Singh, S., Djugash, J., & Kehagias, A. (2009). Efficient multi-robot search for a moving target. International Journal of Robotics Research (IJRR), 28(2), 201–219. doi:10.1177/0278364908099853.

    Article  Google Scholar 

  • Hsieh, A., & Lacroix, S. (Eds.). (2012). Special issue on “multiple collaborative field robots”. Journal of Field Robotics, 29(5), 687–688.

  • Isler, V., Khanna, S., Spletzer, J., & Taylor, C. J. (2005). Target Tracking with distributed sensors: The focus of attention problem. In Computer vision and image understanding (pp. 1–37).

  • Israel, M., Khmelnitsky, E., Kagan, E. (2012). Search for a mobile target by ground vehicle on a topographic terrain. In 2012 IEEE 27th convention of electrical and electronics engineers in Israel. doi:10.1109/EEEI.2012.6377123.

  • Jacoff, A., Messina, E., Weiss, B. A., Tadokoro, S., Nakagawa, Yuki (2003). Test arenas and performance metrics for urban search and rescue robots. In IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 3396–3403).

  • Jennings, J. S., Whelan, G., & Evans, W. F. (1997). Cooperative search and rescue with a team of mobile robots. In IEEE international conference on advanced robotics (ICAR) (pp. 193–200).

  • Jung, B., & Sukhatme, G. S. (2002). Tracking targets using multiple robots: The effect of environment occlusion. In Autonomous robots (pp. 191–205).

  • Kalra, N., Ferguson, D., & Stentz, A. (2005). Hoplites: A market-based framework for planned tight coordination in multirobot teams. In IEEE international conference on robotics and automation (ICRA).

  • Kamath, S., Meisner, E., & Isler, V. (2007). Triangulation based multi target tracking with mobile sensor networks. In IEEE international conference on robotics and automation (ICRA).

  • Karaman, S., & Frazzoli, E. (2011). Incremental sampling-based algorithms for a class of pursuit-evasion games. In Algorithmic foundations of robotics IX.

  • Karnad, N., & Isler, V. (2009). Lion and man game in the presence of a circular obstacle. In IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 5045–5050). doi:10.1109/IROS.2009.5354443.

  • Katsev, M., Yershova, A., Tovar, B., Ghrist, R., & LaValle, S. M. (2011). Mapping and pursuit-evasion strategies for a simple wall-following robot. IEEE Transactions on Robotics, 27(1), 113–128. doi:10.1109/TRO.2010.2095570.

    Article  Google Scholar 

  • Katsilieris, F., Lindhé, M., & Dimarogonas, D. (2010). Demonstration of multi-robot search and secure. In IEEE international conference on robotics and automation (ICRA).

  • Kloder, S., & Hutchinson, S. (2007). Barrier coverage for variable bounded-range line-of-sight guards. In IEEE international conference on robotics and automation (ICRA) (pp. 10–14).

  • Koenig, N., & Howard, A. (2004). Design and use paradigms for gazebo, an open-source multi-robot simulator. In IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 2149–2154).

  • Kolling, A., & Carpin, S. (2008). Extracting surveillance graphs from robot maps. In IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 2323–2328). doi:10.1109/IROS.2008.4650763.

  • Kolling, A., & Carpin, S. (2010a) Multi-robot pursuit-evasion without maps. In IEEE international conference on robotics and automation (ICRA).

  • Kolling, A., Kleiner, A., Lewis, M., & Sycara, K. (2010). Pursuit-Evasion in 2.5D based on team-visibility. In IEEE/RSJ international conference on intelligent robots and systems (IROS).

  • Kolling, A., & Carpin, S. (2007). Cooperative observation of multiple moving targets: An algorithm and its formalization. International Journal of Robotics Research (IJRR), 26(9), 935–953. doi:10.1177/0278364907080424.

    Article  Google Scholar 

  • Kolling, A., & Carpin, S. (2010b). Pursuit-evasion on trees by robot teams. IEEE Transactions on Robotics, 26(1), 32–47. doi:10.1109/TRO.2009.2035737.

    Article  Google Scholar 

  • Kuhlman, M., Svec, P., Kaipa, K., Sofge, D., & Gupta, S. (2014). Physics-aware informative coverage planning for autonomous vehicles. In IEEE international conference on robotics and automation (ICRA) (pp. 4741–4746). doi:10.1109/ICRA.2014.6907553.

  • LaPaugh, A. (1982). Recontamination does not help. Princeton University, Computer Science Department.

  • LaValle, S. M., Gonzales-Banos, H. H., Becker, C., & Latombe, J. C. (1997). Motion strategies for maintaining visibility of a moving target. In IEEE international conference on robotics and automation (ICRA) (pp. 731–736).

  • Liu, M., Colas, F., Oth, L., & Siegwart, R. (2015). Incremental topological segmentation for semi-structured environments using discretized GVG. Autonomous Robots, 38(2), 143–160. doi:10.1007/s10514-014-9398-8.

    Article  Google Scholar 

  • Mamei, M., & Zambonelli, F. (2005). Spreading pheromones in everyday environments through RFID technology. In IEEE swarm intelligence symposium (SIS) (pp. 281–288).

  • Markov, S., & Carpin, S. (2007). A cooperative distributed approach to target motion control in multirobot observation of multiple targets. In IEEE/RSJ international conference on intelligent robots and systems (IROS).

  • Megiddo, N., HAKIMI, S. L., Garey, M. R., Johnson, D. S., & Papadimitriou, C. H. (1988). The complexity of searching a graph. Journal ofthe Association for Computing Machinery 35(1), 18–44.

  • Miao, Y. Q. (2010). A study of mobility models in mobile surveillance systems. PhD thesis, University of Waterloo.

  • Miao, Y. Q., Khamis, A., & Kamel, M. S. (2010). Applying anti-flocking model in mobile surveillance systems. In Autonomous and Intelligent Systems (AIS). doi:10.1109/AIS.2010.5547036.

  • Mirzaei, F. M., Mourikis, A. I., & Roumeliotis, S. I. (2007). On the performance of multi-robot target tracking. In IEEE international conference on robotics and automation (ICRA).

  • Moors, M., Rohling, T., & Schulz, D. (2005). A probabilistic approach to coordinated multi-robot indoor surveillance. In IEEE/RSJ international conference on intelligent robots and systems (IROS).

  • Moseley, M. B., Grocholsky, B. P., Cheung, C., & Singh, S. (2009). Integrated long-range UAV/UGV collaborative target tracking. In SPIE defense, security, and sensing.

  • Mosteo, A. R. (2010). Multi-robot task allocation for service robotics: From unlimited to limited communication range. PhD thesis, Universidad de Zaragoza.

  • Mottaghi, R., & Vaughan, R. (2007). An integrated particle filter and potential field method applied to cooperative multi-robot target tracking. Autonomous Robots, 23(1), 19–35.

    Article  Google Scholar 

  • Murray, R. M. (2007). Recent research in cooperative control of multivehicle systems. Journal of Dynamic Systems, Measurement, and Control, 129, 571. doi:10.1115/1.2766721.

    Article  Google Scholar 

  • Murrieta, R., Sarmiento, A., Bhattacharya, S., & Hutchinson, S. (2004). Maintaining visibility of a moving target at a fixed distance: the case of observer bounded speed. In IEEE international conference on robotics and automation (ICRA) (pp. 479–484, Vol.1). doi:10.1109/ROBOT.2004.1307195.

  • Murrieta-Cid, R., Gonzales-Banos, H. H., & Tovar, B. (2002). A reactive motion planner to maintain visibility of unpredictable targets. In IEEE international conference on robotics and automation (ICRA).

  • Murrieta-Cid, R., Monroy, R., Hutchinson, S., Jea (2008). A complexity result for the pursuit-evasion game of maintaining visibility of a moving evader. In IEEE international conference on robotics and automation (ICRA).

  • Murrieta-Cid, R., Muppirala, T., Sarmiento, A., Bhattacharya, S., & Hutchinson, S. (2007). Surveillance strategies for a pursuer with finite sensor range. International Journal of Robotics Research (IJRR), 26(3), 233–253. doi:10.1177/0278364907077083.

    Article  Google Scholar 

  • Murrieta-Cid, R., Ruiz, U., Marroquin, J. L., Laumond, J. P., & Hutchinson, S. (2011). Tracking an omnidirectional evader with a differential drive robot. Autonomous Robots, 31(4), 345–366. doi:10.1007/s10514-011-9246-z.

    Article  Google Scholar 

  • Nahin, P. J. (2012). Chases and escapes: The mathematics of pursuit and evasion (New in Paper). Princeton University Press.

  • Nettleton, E. (2003). Decentralised architectures for tracking and navigation with multiple flight vehicles. PhD thesis, University of Sydney.

  • Noori, N., & Isler, V. (2014). Lion and man with visibility in monotone polygons. International Journal of Robotics Research (IJRR), 33(1), 155–181. doi:10.1177/0278364913498291.

    Article  Google Scholar 

  • Ohsumi, A. (1991). Optimal search for a Markovian target. Naval Research Logistics, 38(4), 531–554. doi:10.1002/1520-6750(199108)38:4<531.0.CO;2-L

  • O’rourke, J. (1987). Art gallery theorems and algorithms. Princeton: Princeton University Press.

    MATH  Google Scholar 

  • Oskam, T., Sumner, R. W., Thuerey, N., & Gross, M. (2009). Visibility transition planning for dynamic camera control. In SIGGRAPH/Eurographics symposium on computer animation (SCA) (vol. 1). New York: ACM Press. doi:10.1145/1599470.1599478.

  • Papanikolopoulos, N. P., Khosla, P. K., & Kanade, T. (1993). Visual tracking of a moving target by a camera mounted on a robot: A combination of control and vision. IEEE Transactions on Robotics and Automation, 9(1), 14–35.

    Article  Google Scholar 

  • Parker, L. E. (2002). Distributed algorithms for multi-robot observation of multiple moving targets. In Autonomous robots (pp. 231–255).

  • Parker, L. E., Emmons, B. A. (1997). Cooperative multi-robot observation. In IEEE international conference on robotics and automation (ICRA) (pp. 2082–2089).

  • Parsons, T. (1978). Pursuit-evasion in a graph. Theory and Applications of Graphs.

  • Pasqualetti, F., Franchi, A., & Bullo, F. (2010). On optimal cooperative patrolling. In IEEE Conference on Decision and Control (CDC) (pp. 7153–7158).

  • Pimenta, L. C., Schwager, M., Lindsey, Q., Kumar, V., Rus, D., & Mesquita, R. C., et al. (2010). Simultaneous coverage and tracking (SCAT) of moving targets with robot networks. Algorithmic foundation of robotics VIII (pp. 85–99), Springer Tracts in Advanced Robotics. Berlin: Springer.

  • Pirjanian, P., & Mataric, M. (2000). Multi-robot target acquisition using multiple objective behavior coordination. In IEEE international conference on robotics and automation (ICRA) (pp. 2696–2702).

  • Pita, J., Jain, M., Ordónez, F., & Portway, C. (2009). Using game theory for Los Angeles airport security. AI Magazine pp 43–57.

  • Portugal, D., & Rocha, R. (2010). MSP algorithm: multi-robot patrolling based on territory allocation using balanced graph partitioning. In Symposium on applied computing (pp. 1271–1276).

  • Portugal, D., & Rocha, R. (2011). A survey on multi-robot patrolling algorithms. In Technological innovation for sustainability (pp. 139–146).

  • Portugal, D., & Rocha, R. P. (2013). Distributed multi-robot patrol: A scalable and fault-tolerant framework. Robotics and Autonomous Systems. doi:10.1016/j.robot.2013.06.011.

  • Pugh, J., & Martinoli, A. (2007). Inspiring and Modeling Multi-Robot Search with Particle Swarm Optimization. In IEEE swarm intelligence symposium (SIS) (pp. 332–339). doi:10.1109/SIS.2007.367956.

  • Qian, K., Ma, X., & Dai, X. (2008). Simultaneous robot localization and person tracking using Rao-Blackwellised particle filters with multi-modal sensors. In IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 22–26).

  • Quigley, M., Conley, K., Gerkey, B., Faust, J., Foote, T., Leibs, J., Wheeler, R., & Ng A.Y. (2009). ROS: An open-source robot operating system. In ICRA Workshop on open source software 3(3.2).

  • R4SIM. (2015). Robotics, science and systems conference, Roma 2938 (Italy): Workshop on Rapid and repeatable robot simulation.

  • Raboin, E., Kuter, U., Nau, D. S. (2012). Generating strategies for multi-agent pursuit-evasion games in partially observable euclidean space. In International conference on autonomous agents and multiagent systems (AAMAS) (pp. 1201–1202).

  • Raboin, E., Nau, D., Kuter, U., Gupta, S. K., & Svec P. (2010). Strategy generation in multi-agent imperfect-information pursuit games. In International conference on autonomous agents and multiagent systems (AAMAS).

  • Raboin, E., Svec, P., Nau, D., & Gupta, S. (2013). Model-predictive target defense by team of unmanned surface vehicles operating in uncertain environments. In IEEE international conference on robotics and automation (ICRA) (pp. 3517–3522). doi:10.1109/ICRA.2013.6631069.

  • Renzaglia, A. (2012). Adaptive stochastic optimization for cooperative coverage with a swarm of Micro Aerial Vehicles. PhD thesis, Université de Grenoble.

  • Riehl, J. R., Collins, G. E., & Hespanha, J. P. (2007). Cooperative graph-based model predictive search. In IEEE conference on decision and control (CDC) (pp. 2998–3004).

  • Robin, C., & Lacroix, S. (2012). Failure anticipation in pursuit-evasion. In Proceedings of robotics: Science and systems (RSS).

  • Roy, N., Gordon, G., & Thrun, S. (2005). Finding approximate POMDP solutions through belief compression. Journal of Artificial Intelligence Research (JAIR).

  • Ruan, S., Meirina, C., Yu, F., Pattipati, K., & Popp, R. (2005). Patrolling in a stochastic environment. Technical Report, DTIC Document.

  • Rybski, P. E., Stoeter, S. A., Erickson, M. D., Gini, M., Hougen, D. F., & Papanikolopoulos, N. (2000). A team of robotic agents for surveillance. In Proceedings of the 4th international conference on autonomous agents (pp. 9–16. New York: ACM.

  • Sak T., Wainer J., & Goldenstein S. K. (2008). Probabilistic multiagent patrolling. in Advances in artificial intelligence (pp. 124–133).

  • Santos J., & Lima P. (2010). Multi-robot cooperative object localization. In RoboCup 2009: Robot Soccer World Cup XIII (pp. 332–343).

  • Sarmiento, A., Murrieta-Cid, R., & Hutchinson, S. (2009). An efficient motion strategy to compute expected-time locally optimal continuous search paths in known environments. Advanced Robotics, 23(12), 1533–1560. doi:10.1163/016918609X12496339799170.

    Article  Google Scholar 

  • Shi K., Cao Z., Zhang W., & Zhou C. (2010). The targets pursuit for multi-robot system with hybrid wireless sensor networks. In IEEE international conference on robotics and automation (ICRA) (pp. 538–547).

  • Soltero, D. E., Schwager, M., & Rus, D. (2013). Decentralized path planning for coverage tasks using gradient descent adaptive control. International Journal of Robotics Research (IJRR). doi:10.1177/0278364913497241.

  • Stone, L. D. (2007). Theory of optimal search (2nd Edn.). New York: Academic Press. doi:10.2307/2286890.

  • Strom, J., Morton, R., Reilly, K., & Olson, E. (2010). Online probabilistic pursuit of adversarial evaders. In ICRA workshop: Search and pursuit/evasion in the physical world.

  • Svec, P., Thakur, A., Raboin, E., Shah, B., & Gupta, S. (2014). Target following with motion prediction for unmanned surface vehicle operating in cluttered environments. Autonomous Robots, 36(4), 383–405. doi:10.1007/s10514-013-9370-z.

    Article  Google Scholar 

  • Tang, Z., & Ozguner, U. (2005). Motion planning for multi-target surveillance with mobile sensor agents. IEEE Transactions on Robotics, 21(5), 898–908.

    Article  Google Scholar 

  • Tanner, H. G. (2007). Switched UAV-UGV cooperation scheme for target detection. In IEEE international conference on robotics and automation (ICRA).

  • Theodorakopoulos, P. (2009). On autonomous target tracking for UAVs. PhD thesis, University of Toulouse.

  • Tsokas, N. A., & Kyriakopoulos, K. J. (2011). Multi-robot multiple hypothesis tracking for pedestrian tracking. Autonomous Robots, 32(1), 63–79. doi:10.1007/s10514-011-9259-7.

    Article  Google Scholar 

  • Urrutia, J. (2000). Art gallery and illumination problems. In Handbook of computational geometry.

  • Vidal, R., Shakernia, O., Kim, H. J., Shim, D. H., & Sastry, S. (2002). Probabilistic pursuitevasion games: Theory, implementation, and experimental evaluation. IEEE Transactions on Robotics and Automation, 18(5), 662–669.

    Article  Google Scholar 

  • Vieira, M., Govindan, R., & Sukhatme, G. (2009). Scalable and practical pursuit-evasion with networked robots. Intelligent Service Robotics, 2(4), 247–263.

  • Vo, C., & Jm, Lien. (2010). Visibility-based strategies for tracking and searching unpredictable coherent targets among known obstacles. In ICRA workshop: Search and pursuit/evasion in the physical world.

  • Wang, Z., Gu, D., Meng, T., & Zhao, Y. (2010). Consensus target tracking in multi-robot systems. Intelligent Robotics and Applications, pp. 724–735.

  • Wong, E. M., Bourgault, F., Furukawa, T. (2005). Multi-vehicle Bayesian search for multiple lost targets. In IEEE international conference on robotics and automation (ICRA) (pp. 3180–3185).

  • Xu, Z., Douillard, B., Morton, P., Vlaskine, V., Wohlleber, C., Calleija, M., Underwood, J., & Sukkarieh, S. (2012). Towards Collaborative Multi-MAV-UGV teams for target tracking. In Proceedings of robotics: Science and systems (RSS), Workshop on Integration of perception with control and navigation for resource-limited, highly dynamic, autonomous systems.

  • Xu, Z., Fitch, R., & Sukkarieh, S. (2013). Decentralised coordination of mobile robots for target tracking with learnt utility models. In IEEE international conference on robotics and automation (ICRA) (pp. 2006–2012).

  • Yau, J., Chung, T. H. (2012). Search-theoretic and ocean models for localizing drifting objects. In IEEE/RSJ international conference on intelligent robots and systems (IROS).

  • Yu, H., & Beard, R. (2011). Probabilistic path planning for cooperative target tracking using aerial and ground vehicles. In American control conference (ACC) (pp. 4673–4678).

  • Zhou, P. C., Hong, B. R., Wang, Y. H., & Zhou, T. (2004). Multi-agent coopoerative pursuit based on extended contract net protocol. In Machine learning and cybernetics.

  • Zhou, K., & Roumeliotis, S. I. (2011). Multirobot active target tracking with combinations of relative observations. IEEE Transactions on Robotics, 27(4), 678–695. doi:10.1109/TRO.2011.2114734.

    Article  Google Scholar 

Download references

Acknowledgments

The authors are thankful to Wheeler Ruml for his helpful remarks. This research is partially funded by the DGA.

Author information

Authors and Affiliations

  1. CNRS, LAAS, 7 Avenue du colonel Roche, F-31400, Toulouse, France

    Cyril Robin & Simon Lacroix

  2. Univ de Toulouse, LAAS, F-31400, Toulouse, France

    Cyril Robin & Simon Lacroix

Authors
  1. Cyril Robin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Simon Lacroix
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Cyril Robin.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Robin, C., Lacroix, S. Multi-robot target detection and tracking: taxonomy and survey. Auton Robot 40, 729–760 (2016). https://doi.org/10.1007/s10514-015-9491-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10514-015-9491-7

Keywords

Search

Navigation