Multi-agent Visibility-Based Target Tracking Game | SpringerLink
Skip to main content
Springer Nature Link
Log in

Multi-agent Visibility-Based Target Tracking Game

  • Conference paper
  • First Online:
Distributed Autonomous Robotic Systems

Part of the book series: Springer Tracts in Advanced Robotics ((STAR,volume 112 ))

  • 2177 Accesses

Abstract

In this paper, we address the problem of visibility-based target tracking for a team of mobile observers trying to track a team of mobile targets. Based on the results of previous work, the notion of pursuit fields around a single corner is introduced. We use the pursuit fields to generate navigation strategies for a single observer to track a single target in general environments. In order to tackle the case when more than one observer or target is present in the environment, we propose a two level hierarchical approach. At the upper level, the team of observers use a ranking and aggregation technique for allocating each target to an observer. At the lower level, each observer computes its navigation strategy based on the results of the single observer-single target problem, thereby, decomposing a large multi-agent problem into several 2-agent problems. Finally, we present a scalable algorithm that can accommodate an arbitrary number of observers and targets. The performance of this algorithm is evaluated based on simulation and implementation.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 17159
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 21449
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
JPY 21449
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Hollinger, G.A., Djugash, J., Singh, S.: Target tracking without line of sight using range from radio. Auton. Rob. 32(1), 1–14 (2012)

    Article  Google Scholar 

  2. Li, T.-H.S., Chang, S.-J., Tong, W.: Fuzzy target tracking control of autonomous mobile robots by using infrared sensors. IEEE Trans. Fuzzy Syst. 12, 491–501 (2004)

    Article  Google Scholar 

  3. LaValle, S., Gonzalez-Banos, H., Becker, C., Latombe, J.-C.: Motion strategies for maintaining visibility of a moving target. In: IEEE International Conference on Robotics and Automation, Proceedings, vol. 1, pp. 731–736, Apr 1997

    Google Scholar 

  4. Kolling, A., Carpin, S.: Cooperative observation of multiple moving targets: an algorithm and its formalization. Int. J. Robot. Res. 26(9), 935–953 (2007)

    Article  Google Scholar 

  5. Lee, D., Kim, G., Kim, D., Myung, H., Choi, H.-T.: Vision-based object detection and tracking for autonomous navigation of underwater robots. Ocean Eng. 48, 59–68 (2012)

    Article  Google Scholar 

  6. Bhattacharya, S., Hutchinson, S.: Approximation schemes for two-player pursuit evasion games with visibility constraints. In: Proceedings of Robotics: Science and Systems IV, Zurich, Switzerland, June 2008

    Google Scholar 

  7. Bhattacharya, S., Hutchinson, S.: A cell decomposition approach to visibility-based pursuit evasion among obstacles. Int. J. Robot. Res. 30(14), 1709–1727 (2011)

    Article  Google Scholar 

  8. Gonzalez-Banos, H., Lee, C.-Y., Latombe, J.-C.: Real-time combinatorial tracking of a target moving unpredictably among obstacles. In: IEEE International Conference on Robotics and Automation. Proceedings. ICRA ’02, vol. 2, pp. 1683–1690 (2002)

    Google Scholar 

  9. Bandyopadhyay, T., Li, Y., Ang, Jr., M.H., Hsu, D.: Stealth Tracking of an Unpredictable Target Among Obstacles (2004)

    Google Scholar 

  10. Bandyopadhyay, T., Li, Y., Ang, Jr., M.H., Hsu, D.: A greedy strategy for tracking a locally predictable target among obstacles. In: IEEE International Conference on Robotics and Automation, ICRA 2006, Proceedings, pp. 2342–2347, May 2006

    Google Scholar 

  11. Bandyopadhyay, T., Hsu, D., Ang, J., Marcelo, H.: Motion strategies for people tracking in cluttered and dynamic environments. In: Khatib, O., Kumar, V., Pappas, G. (eds.) Experimental Robotics, Springer Tracts in Advanced Robotics, vol. 54, pp. 463–472. Springer, Berlin Heidelberg (2009)

    Google Scholar 

  12. Al-Bluwi, I., Elnagar, A.: Maintaining visibility of a moving target: maximizing escape time versus exposure time. In: 11th International Conference on Control Automation Robotics Vision (ICARCV), pp. 982–987, Dec 2010

    Google Scholar 

  13. Anderson, R., Milutinovic, D.: A stochastic approach to dubins feedback control for target tracking. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3917–3922, Sept 2011

    Google Scholar 

  14. Parker, L.: Distributed algorithms for multi-robot observation of multiple moving targets. Auton. Rob. 12(3), 231–255 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  15. Frew, E.W., Elston, J.: Target assignment for integrated search and tracking by active robot networks. In: Proceedings of the 2008 IEEE International Conference on Robotics and Automation, Pasadena, CA, pp. 2354–9, May 2008

    Google Scholar 

  16. Jung, B., Sukhatme, G.: Tracking targets using multiple robots: the effect of environment occlusion. Auton. Rob. 13(3), 191–205 (2002)

    Article  MATH  Google Scholar 

  17. Jung, B., Sukhatme, G.: Cooperative multi-robot target tracking. In: Gini, M., Voyles, R. (eds.) Distributed Autonomous Robotic Systems, vol. 7, pp. 81–90. Springer, Japan (2006)

    Google Scholar 

  18. Jung, B., Sukhatme, G.: Real-time motion tracking from a mobile robot. Int. J. Soc. Robot. 2(1), 63–78 (2010)

    Article  Google Scholar 

  19. Hollinger, G., Singh, S., Djugash, J., Kehagias, A.: Efficient multi-robot search for a moving target. Int. J. Robot. Res. 28(2), 201–219 (2009)

    Article  Google Scholar 

  20. Derenick, J., Spletzer, J., Hsieh, A.: An optimal approach to collaborative target tracking with performance guarantees. J. Intell. Rob. Syst. 56(1–2), 47–67 (2009)

    Article  MATH  Google Scholar 

  21. Lee, G., Chong, N., Christensen, H.: Tracking multiple moving targets with swarms of mobile robots. Intell. Serv. Robot. 3(2), 61–72 (2010)

    Article  Google Scholar 

  22. Wu, W., Zhang, F.: A switching strategy for target tracking by mobile sensing agents. J. Commun. 8(1), 47–54 (2013)

    Article  Google Scholar 

  23. Ahmad, A., Tipaldi, G., Lima, P., Burgard, W.: Cooperative robot localization and target tracking based on least squares minimization. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 5696–5701, May 2013

    Google Scholar 

  24. Xu, Z., Fitch, R., Sukkarieh, S.: Decentralised coordination of mobile robots for target tracking with learnt utility models. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 2014–2020, May 2013

    Google Scholar 

  25. Chung, T., Hollinger, G., Isler, V.: Search and pursuit-evasion in mobile robotics. Auton. Rob. 31(4), 299–316 (2011)

    Article  Google Scholar 

  26. Bhattacharya, S., Candido, S., Hutchinson, S.: Motion strategies for surveillance. In: Proceedings of Robotics: Science and Systems, Atlanta, GA, USA, June 2007

    Google Scholar 

  27. Isaacs, R.: Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. Dover Publications, Mineola (1965)

    Google Scholar 

  28. Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logistics Quart. 2, 83–97 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  29. Emerson, P.: The original borda count and partial voting. Soc. Choice Welf. 40(2), 353–358 (2013)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Iowa State University, Ames, USA

    Mengzhe Zhang & Sourabh Bhattacharya

Authors
  1. Mengzhe Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sourabh Bhattacharya
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sourabh Bhattacharya .

Editor information

Editors and Affiliations

  1. Japan Advanced Institute of Science and Technology, Nomi, Ishikawa, Japan

    Nak-Young Chong

  2. Electronics and Telecommunications Research Institute, Daejeon, Korea (Republic of)

    Young-Jo Cho

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer Japan

About this paper

Cite this paper

Zhang, M., Bhattacharya, S. (2016). Multi-agent Visibility-Based Target Tracking Game. In: Chong, NY., Cho, YJ. (eds) Distributed Autonomous Robotic Systems. Springer Tracts in Advanced Robotics, vol 112 . Springer, Tokyo. https://doi.org/10.1007/978-4-431-55879-8_19

Download citation

  • DOI: https://doi.org/10.1007/978-4-431-55879-8_19

  • Published:

  • Publisher Name: Springer, Tokyo

  • Print ISBN: 978-4-431-55877-4

  • Online ISBN: 978-4-431-55879-8

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics