World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Optimal Autonomous Pursuit of an Intruder on a Grid Aided by Local Node and Edge Sensors by:3 (Source: Crossref)

    Timely detection of intruders ensures the safety and security of high valued assets within a protected area. This problem takes on particular significance across international borders and becomes challenging when the terrain is porous, rugged and treacherous in nature. Keeping an effective vigil against intruders on large tracts of land is a tedious task; currently, it is primarily performed by security personnel with automatic detection systems in passive supporting roles. This paper discusses an alternate autonomous approach by utilizing one or more Unmanned Vehicles (UVs), aided by smart sensors on the ground, to detect and localize an intruder. To facilitate autonomous UV operations, the region is equipped with Unattended Ground Sensors (UGSs) and laser fencing. Together, these sensors provide time-stamped location information (node and edge detection) of the intruder to a UV. For security reasons, we assume that the sensors are not networked (a central node can be disabled bringing the whole system down) and so, the UVs must visit the vicinity of the sensors to gather the information therein. This makes the problem challenging in that pursuit must be done with local and likely delayed information. We discretize time and space by considering a 2D grid for the area and unit speed for the UV, i.e. it takes one time unit to travel from one node to an adjacent node. The intruder is slower and takes two time steps to complete the same move. We compute the min–max optimal, i.e. minimum number of steps to capture the intruder under worst-case intruder actions, for different number of rows and columns in the grid and for both one and two pursuers.

    This paper was recommended for publication in its revised form by editorial board member, Yunfeng Zhang.


    • 1. J. G. Mooney, S. Haviland and E. N. Johnson , Collaborative autonomy for mapping, search, and pursuit, Unmanned Syst. 04(02) (2016) 167–184. LinkGoogle Scholar
    • 2. M. Ray, O. Evans and J. Jamieson , Three-dimensional laser radar for perimeter security, in Electro-Optical Remote Sensing, eds. G. W. KamermanD. V. Willetts, Vol. 5988 (International Society for Optics and Photonics, SPIE, 2005), pp. 49–60. CrossrefGoogle Scholar
    • 3. C. Olsen, K. Kalyanam, W. Baker and D. Kunz , Maximal distance discounted and weighted revisit period: A utility approach to persistent unmanned surveillance, Unmanned Syst. 7(4) (2019) 215–232. LinkGoogle Scholar
    • 4. S. Semnani and O. Basir , Multi-target engagement in complex mobile surveillance sensor networks, Unmanned Syst. 5(1) (2017) 31–43. LinkGoogle Scholar
    • 5. M. Darrah, J. Wilhelm, T. Munasinghe, K. Duling, S. Yokum, E. Sorton, J. Rojas and M. Wathen , A flexible genetic algorithm system for multi-UAV surveillance: Algorithm and flight testing, Unmanned Syst. 3(1) (2015) 49–62. LinkGoogle Scholar
    • 6. J. Wilhelm, J. Rojas, G. Eberhart and M. Perhinschi , Heterogeneous aerial platform adaptive mission planning using genetic algorithms, Unmanned Syst. 05(01) (2017) 19–30. LinkGoogle Scholar
    • 7. H. Witsenhausen , A minimax control problem for sampled linear systems, IEEE Trans. Autom. Control 13 (1968) 5–21. CrossrefGoogle Scholar
    • 8. D. P. Bertsekas and I. B. Rhodes , On the minimax reachability of target sets and target tubes, Automatica 7 (1971) 233–247. CrossrefGoogle Scholar
    • 9. D. P. Bertsekas, Control of uncertain systems with a set-membership description of the uncertainty, Ph.D. thesis, Massachusetts Institute of Technology (1971). Google Scholar
    • 10. D. P. Bertsekas and I. B. Rhodes , Sufficiently informative functions and the minimax feedback control of uncertain dynamic systems, IEEE Trans. Autom. Control 18 (1973) 117–124. CrossrefGoogle Scholar
    • 11. R. Isaacs , Differential Games: A Mathematical Theory with Applications to Welfare and Pursuit, Control and Optimization (John Wiley & Sons, 1965). Google Scholar
    • 12. G. T. Dzyubenko and B. N. Pshenichnyi , Discrete differential games with information lag, Cybern. Syst. Anal. 8(6) (1972) 947–952. CrossrefGoogle Scholar
    • 13. F. V. Fomin and D. M. Thilikos , An annotated bibliography on guaranteed graph searching, Theor. Comput. Sci. 399 (2008) 236–245. CrossrefGoogle Scholar
    • 14. K. Krishnamoorthy, D. W. Casbeer, P. Chandler, M. Pachter and S. Darbha , UAV search & capture of a moving ground target under delayed information, in 51st IEEE Conf. Decision and Control (CDC), Maui, HI, 2012, pp. 3092–3097. CrossrefGoogle Scholar
    • 15. K. Krishnamoorthy, S. Darbha, P. Khargonekar, D. W. Casbeer, P. Chandler and M. Pachter , Optimal minimax pursuit evasion on a Manhattan grid, in American Control Conf., Washington, DC, 2013, pp. 3427–3434. CrossrefGoogle Scholar
    • 16. K. Krishnamoorthy, S. Darbha, P. Khargonekar, P. Chandler and M. Pachter , Optimal cooperative pursuit on a Manhattan grid, in AIAA Guidance, Navigation and Control Conf. (AIAA 2013-4633), Boston, MA, 2013, pp. 1–10. Google Scholar
    • 17. T. Parsons , Pursuit-evasion in a graph, Theory and Applications of Graphs, Lecture Notes in Mathematics, Vol. 8, No. 1 (Springer, Berlin, 1978), pp. 426–441. CrossrefGoogle Scholar
    • 18. N. E. Clarke , A witness version of the cops and robber game, Discrete Math. 309(10) (2009) 3292–3298. CrossrefGoogle Scholar