Logo PTI Logo FedCSIS

Proceedings of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 35

Target search with an allocation of search effort to overlapping cones of observation

, , ,

DOI: http://dx.doi.org/10.15439/2023F7181

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 801–811 ()

Full text

Abstract. This paper addresses the problem of an aerial moving target search with a radar on an airborne platform. An observation of the radar is a modeled as a cone covering a set of regions of the search area. We assume overlapping cones of observation, and we want to find the discrete allocation plan of search effort to the cones in order to optimize target detection. For the stationary target search with overlapping cones, we present a dynamic programming algorithm that computes the optimal allocation. An approximate greedy heuristic, which is more appropriate in a real time context, is also presented and assessed. The moving target search problem is solved with the Forward And Backward (FAB) algorithm coupled with the different stationary search algorithms. In this paper, we use radar detection model that has been shown to be more realistic than the ones usually considered. Also, several models of movement of the target are considered with different Markovian transition matrices. We compare the performance of the mentioned algorithms on several scenarios.

References

  1. L. D. Stone, J. O. Royset, and A. R. Washburn, Optimal search for moving targets. Springer, 2016.
  2. M. Raap, M. Preuß, and S. Meyer-Nieberg, “Moving target search optimization – a literature review,” Computers and Operations Research, vol. 105, pp. 132–140, 2019.
  3. F. Delavernhe, P. Jaillet, A. Rossi, and M. Sevaux, “Planning a multi-sensors search for a moving target considering traveling costs,” European Journal of Operational Research, vol. 292, no. 2, pp. 469–482, 2021.
  4. J. N. Eagle, “The optimal search for a moving target when the search path is constrained.” Operations Research, vol. 32, pp. 1107–15, 1984.
  5. C. Simonin, J.-P. Le Cadre, and F. Dambreville, “A common framework for multitarget search and cross-cueing optimization,” in International Conference on Information Fusion, 2008, pp. 1–8.
  6. H. A. L. Thi, D. M. Nguyen, and T. P. Dinh, “A DC programming approach for planning a multisensor multizone search for a target,” Computers and Operations Research, vol. 41, pp. 231–239, 2014.
  7. A. R. Washburn, “Search for a moving target: The FAB algorithm,” Operations Research, vol. 31, no. 4, pp. 739–751, 1983.
  8. A. Washburn, “Branch and bound methods for a search problem,” Nav. Res. Logist., vol. 45, no. 3, pp. 243–257, 1998.
  9. M. Morin, I. Abi-Zeid, P. Lang, L. Lamontagne, and P. Maupin, “The optimal searcher path problem with a visibility criterion in discrete time and space,” in International Conference on Information Fusion, 2009, pp. 2217–2224.
  10. S. S. Blackman and R. Popoli, Design and analysis of modern tracking systems, ser. Artech House radar library. Boston: Artech House, 1999.
  11. J. L. Williams, “Search theory approaches to radar resource allocation,” 7th U.S. / Australia Joint Workshop on Defense Applications of. Signal Processing, 2011.
  12. H. Vaillaud, C. Hanen, E. Hyon, and C. Enderli, “Target search with a radar on an airborne platform,” in International Conference on Information Fusion, 2023, to appear in IEEE Xplore.
  13. S. Pérez Carabaza, Multi-UAS Minimum Time Search in Dynamic and Uncertain Environments, ser. Springer Theses. Cham: Springer International Publishing, 2021. [Online]. Available: https://link.springer.com/10.1007/978-3-030-76559-0
  14. J. W. Caspers, “Radar random permutation scan method,” Patent, oct, 1966.
  15. S. S. Brown, “Optimal search for a moving target in discrete time and space,” Operations Research, vol. 28, no. 6, pp. 1275–1289, 1980.