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

• Autorzy: Vaillaud Hugo , Hanen Claire , Hyon Emmanuel , Enderli Cyrille

Identyfikatory

DOI

10.15439/2023F7181

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

moving target; target search; dynamic programming; FAB algorithm; overlapping observation cones

PL

wyszukiwanie celu; ruchomy cel; programowanie dynamiczne; algorytm FAB

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 801--811
• Opis fizyczny: Bibliogr. 15 poz., rys., wykr., wz.

Twórcy

autor

Vaillaud Hugo

• Thales DMS Sorbonne Université, CNRS, LIP6 Paris, France

autor

Hanen Claire

• Sorbonne Université, CNRS, LIP6 UPL, Université Paris Nanterre Paris, France

autor

Hyon Emmanuel

• Sorbonne Université, CNRS, LIP6 UPL, Université Paris Nanterre Paris, France

autor

Enderli Cyrille

• Thales DMS Elancourt, France

Bibliografia

• 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.

Uwagi

1. Thematic Tracks Regular Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).