Journal of Systems Engineering and Electronics ›› 2023, Vol. 34 ›› Issue (1): 99-116.doi: 10.23919/JSEE.2023.000022

• SYSTEMS ENGINEERING • Previous Articles     Next Articles

A multi-UAV deployment method for border patrolling based on Stackelberg game

Xing LEI1,2(), Xiaoxuan HU1,2(), Guoqiang WANG1,2,3(), He LUO1,3,*()   

  1. 1 School of Management, Hefei University of Technology, Hefei 230009, China
    2 Key Laboratory of Process Optimization & Intelligent Decision-making, Ministry of Education, Hefei 230009, China
    3 Engineering Research Center for Intelligent Decision-making & Information Systems Technologies, Ministry of Education, Hefei 230009, China
  • Received:2021-07-14 Online:2023-02-18 Published:2023-03-03
  • Contact: He LUO E-mail:leixing@mail.hfut.edu.cn;xiaoxuanhu@hfut.edu.cn;gqwang2017@hfut.edu.cn;luohe@hfut.edu.cn
  • About author:
    LEI Xing was born in 1994. She received her B.S. degree from Hefei University of Technology in 2016. She is currently pursuing her Ph.D. degree in the School of Management, Hefei University of Technology. Her current research interests include deploying multi-UAVs for border patrols and security game theory. E-mail: leixing@mail.hfut.edu.cn

    HU Xiaoxuan was born in 1978. He received his B.S. and Ph.D. degrees from Hefei University of Technology, in 1999 and 2006, respectively. He is a professor in Hefei University of Technology. His current research interests include satellite mission planning, unmanned system intelligence, and aerospace system management. E-mail: xiaoxuanhu@hfut.edu.cn

    WANG Guoqiang was born in 1982. He received his B.S. and M.S. degrees from University of Science and Technology of China, in 2004 and 2007, respectively. He received his Ph.D. degree from Hefei University of Technology in 2016. He is a professor in Hefei University of Technology. His current research interests include management and intelligent decision making of unmanned aerial vehicle formation. E-mail: gqwang2017@hfut.edu.cn

    LUO He was born in 1982. He received his B.S. and Ph.D. degrees from Hefei University of Technology, in 2004 and 2009, respectively. He is a professor in Hefei University of Technology. His current research interests include intelligent decision making, multi-agent system, and the applications of unmanned aerial vehicle. E-mail: luohe@hfut.edu.cn
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (71971075; 71871079), the National Key Research and Development Program of China (2019YFE0110300), the Anhui Provincial Natural Science Foundation (1808085MG213), and the Fundamental Research Funds for the Central Universities (PA2019GDPK0082).

Abstract:

To strengthen border patrol measures, unmanned aerial vehicles (UAVs) are gradually used in many countries to detect illegal entries on borders. However, how to efficiently deploy limited UAVs to patrol on borders of large areas remains challenging. In this paper, we first model the problem of deploying UAVs for border patrol as a Stackelberg game. Two players are considered in this game: The border patrol agency is the leader, who optimizes the patrol path of UAVs to detect the illegal immigrant. The illegal immigrant is the follower, who selects a certain area of the border to pass through at a certain time after observing the leader’s strategy. Second, a compact linear programming problem is proposed to tackle the exponential growth of the number of leader’s strategies. Third, a method is proposed to reduce the size of the strategy space of the follower. Then, we provide some theoretic results to present the effect of parameters of the model on leader’s utilities. Experimental results demonstrate the positive effect of limited starting and ending areas of UAV’s patrolling conditions and multiple patrolling altitudes on the leader ’s utility, and show that the proposed solution outperforms two conventional patrol strategies and has strong robustness.

Key words: border patrol, unmanned aerial vehicle (UAV), Stackelberg game, compact linear programming, dominated strategy elimination