Abstract
Target tracking problems have been studied fairly extensively by researchers in the last few years. However, the problem of continuous tracking of all mobile targets using the fewest number of mobile trackers, even when the trajectories of all the targets are known in advance, has received very little attention. In this paper we study this problem, where the goal is to find the fewest number of trackers needed to track all the targets for the entire period of observation. Specifically, given a set of \(n\) targets moving in \(n\) different (known) trajectories in a two (or three) dimensional space, our objective is to find the fewest number of velocity-bounded UAVs (mobile sensors, trackers) and their trajectories, so that all the targets are tracked during the entire period of observation. We also study two other versions of the problem where not only the number of trackers but also the time during which the trackers are active is also taken into account. We formulate these problems as network flow problems and propose algorithms for their solution. We evaluate the performance of our algorithms through simulation and study the impact of parameters such as the speed and sensing range of the trackers.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We present the formulation in two dimensions for brevity. Extensions to higher dimensions is straightforward and is discussed in Sect. 3.
- 2.
This result can be easily extended to spaces with higher dimensions. The difference between velocity \(d\) and velocity \(d-\sqrt{2}\varepsilon \), or between sensing radius \(r\) and \(r-\frac{\sqrt{2}}{2}\varepsilon \), is negligible for all practical purposes.
References
Zorbas, D., Razafindralambo, T., Luigi, D.P.P., Guerriero, F.: Energy efficient mobile target tracking using flying drones. Procedia Comput. Sci. 19, 80–87 (2013)
Zhan, P., Casbeer, D., Swindlehurst, A.: A centralized control algorithm for target tracking with uavs. In: Conference Record of the Thirty-Ninth Asilomar Conference on Signals, Systems and Computers, pp. 1148–1152, October 2005
Wheeler, M., Schrick, B., Whitacre, W., Campbell, M., Rysdyk, R., Wise, R.: Cooperative tracking of moving targets by a team of autonomous uavs. In: IEEE/AIAA 25th Digital Avionics Systems Conference, pp. 1–9, October 2006
Nitinawarat, S., Atia, G., Veeravalli, V.: Efficient target tracking using mobile sensors. In: 4th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pp. 405–408, December 2011
Xu, E., Ding, Z., Dasgupta, S.: Target tracking and mobile sensor navigation in wireless sensor networks. IEEE Trans. Mob. Comput. 12(1), 177–186 (2013)
Zou, Y., Chakrabarty, K.: Distributed mobility management for target tracking in mobile sensor networks. IEEE Trans. Mobile Comput. 6(8), 872–887 (2007)
Naderan, M., Dehghan, M., Pedram, H.: Mobile object tracking techniques in wireless sensor networks. In: International Conference on Ultra Modern Telecommunications Workshops, ICUMT ’09, pp. 1–8, October 2009
Adamey, E., Ozguner, U.: A decentralized approach for multi-UAV multitarget tracking and surveillance. In: Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, vol. 8389. May 2012
Srinivas, A., Zussman, G., Modiano, E.: Construction and maintenance of wireless mobile backbone networks. IEEE/ACM Trans. Networking 17(1), 239–252 (2009)
Radhakrishnan, G., Saripalli, S.: Target tracking with communication constraints: An aerial perspective. In: IEEE International Workshop on Robotic and Sensors Environments (ROSE), pp. 1–6, October 2010
Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are np-complete. Inf. Process. Lett. 12(3), 133–137 (1981)
Even, S.: Graph Algorithms. W. H. Freeman & Co., New York (1979)
Acknowledgments
This research is supported in part by grants from the U.S. Defense Threat Reduction Agency under grant number HDTRA1-09-1-0032, the U.S. Air Force Office of Scientific Research under grant number FA9550-09-1-0120, and the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Hay, D., Shirazipourazad, S., Sen, A. (2014). Optimal Tracking of Multiple Targets Using UAVs. In: Zhang, Z., Wu, L., Xu, W., Du, DZ. (eds) Combinatorial Optimization and Applications. COCOA 2014. Lecture Notes in Computer Science(), vol 8881. Springer, Cham. https://doi.org/10.1007/978-3-319-12691-3_55
Download citation
DOI: https://doi.org/10.1007/978-3-319-12691-3_55
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12690-6
Online ISBN: 978-3-319-12691-3
eBook Packages: Computer ScienceComputer Science (R0)