# Reach-Avoid Games with a Time Limit and Detection Range: A Geometric Approach

Authors: Xi Chen; Jianqiao Yu; Kang Niu; Di Yang; Jiaxun Li
Journal: Complexity
 (2022)

---

## Abstract

The reach-avoid game theory is an ideal tool to handle the conflicts among intelligent agents and has been previously studied assuming full state information and no time limits on the players in the past decades. In this article, we extend the problem by requiring the defender to detect the attacker and adding maximum operation time constraints to the attacker. The attacker aims to reach the target region without being captured or reaching its time limit. The defender can employ strategies to intercept the attacker only when the attacker is detected. A geometric method is proposed to solve this game qualitatively. By analyzing the geometric property of the Apollonian circle and the detection range, we give the barrier under the condition that the attacker is initially detected and the attacker’s shortest route which guarantees its arrival at the target region when it is initially outside the detection range. Then, a barrier that separates the game space into two respective winning regions of the players is constructed based on the shortest route and the time limit of the attacker. The main contributions of this work are that this paper provides the first attempt to introduce the abovementioned two concepts simultaneously, which makes the game more practical, and we provide the complete solution of the game in all possible situations.


---

## Body

## 1. Introduction

The differential game theory is first introduced in 1965 to analyze the interception of incoming aircraft by missiles [1]. This theory has strong aerospace connotations [2–8]. The conflicts and cooperation among multiple aircrafts or spacecrafts can be formulated as differential game problems. For example, Tang et al. [7] solved the problem of spacecraft interception and proposed switching strategies based on the differential game theory. Pachter et al. [3, 4] used the game theory to investigate the interception of an air threat by two attacking missiles, and the situation that an attacking missile pursues a target aircraft, while a defending missile tried to intercept the attacking missile. Liu et al. [6] proposed a novel cooperative guidance law of a leader-follower multiagent system based on robust multiagent differential games. Ye et al. [5] investigated a proximate satellite pursuit-evasion game and obtained the open-loop solution to the game. There are two kinds of differential games introduced by Isaacs in his book. The first kind of game is called the game of degree, in which there is a continuous payoff function and the adversarial players try to minimize or maximize the value of the function, respectively. The game of degree theory parallels optimal control theory greatly and the existing control theories can be utilized to solve this kind of problem [5, 6]. The second kind of game is called the game of kind, in which we are only interested in which player can win the game, rather than finding an equilibrium value of a certain function. Unlike the game of degrees, there is still no mature method to solve the game of kind problems. This means that there are many blanks to be filled in this research direction and they are worth studying. In this work, we investigate a typical kind of these games, the reach-avoid game. In a classic reach-avoid game, the attacker or the evader tries to reach the target area and avoids being captured by its opponent, while its opponent, which is often named the defender or the pursuer, strives to prevent it from reaching its goal by intercepting it or delay its intrusion indefinitely. This kind of a game has received a great deal of interest because it can be utilized to handle a wide range of problems in many realistic situations [9–16]. For example, in the military field, the scenarios where an interceptor missile intercepts an offensive missile to protect national borders, or an attacking bomber invades a target area protected by some antiair weapons, can be formulated as a reach-avoid game.Referring to Isaacs’ book [1], the key point of this kind of question is to obtain a hypersurface in the game space, which is called the barrier. This hypersurface divides the game space into two disjoint parts: the winning region of the attacker and that of the defender. In the literature, the Hamilton–Jacobi–Isaacs approach (HJI approach) is ideal for solving the low-dimensional game. By solving an HJI partial differential equation, the optimal strategies of the players can be obtained, as well as the winning regions of the players. Up till now, lots of seminal works have been put forward about reach-avoid differential games and many variations of this kind of game have been proposed. For example, Margellos and Lygeros [17] developed a framework for formulating reach-avoid games with nonlinear dynamics as optimal control problems. Bhattacharya et al. [18, 19] studied a visibility-based target-tracking game in the presence of a circular obstacle. The barrier was constructed by using Isaacs’ techniques according to the symmetry of the environment in reduced state space. The authors of [20] obtained the barrier of the lifeline game by integrating the HJI partial differential equations. They proposed a resultant force method for the attacker to balance the active goal of reaching the lifeline and the passive goal of avoiding capture. In the past few years, lots of work focused on the reach-avoid game with multiple players [21–24]. This kind of game is a significant research topic and is also difficult to analyze due to the raising dimension of the state space, the complex cooperative interactions among the players in the same team, and the conflicting and complicated goals of the players in different teams. Chen et al. [25, 26] provided a graph-theoretic maximum matching approach to decompose the multiplayer reach-avoid game into several subgames with two players and merged the pairwise outcomes of the subgames for a solution of multiplayer version. Based on the time derivative of an appropriately defined risk metric, Selvakumar and Bakolas [27] provided a nonlinear state feedback strategy for the evader in a multiplayer reach-avoid game. A decentralized, real-time algorithm for the cooperative pursuit of a single evader by multiple pursuers was presented based on the idea of minimizing the area of the generalized Voronoi partition of the evader by Zhou et al. [21]. Yan et al. [28] considered a reach-avoid game with two defenders and one attacker on a rectangular domain. In the work, they proposed a geometric approach to construct the related barrier analytically. Also, they fused the game of kind and the game of degree by defining some payoff functions, and the optimal strategies of the players can be obtained simultaneously. They further studied a new multiplayer reach-avoid game of assigning tasks to guarantee the most evaders intercepted based on their previous work and obtained the solution of this game between two adversarial teams with an arbitrary number of players in a general convex planar domain. The authors of [29–31] introduced a new kind of reach-avoid games with multiple homogeneous intruders and defenders, which is called the perimeter-defense game. In this game, the defenders are confined to the boundary of the target area. They decomposed the game into games of local subteams and reduced the design of the defense strategy to an assignment problem to handle the complexity brought by the high dimensionality of the joint state space. Apart from adding the number of players involved in the game, the so-called target-attacker-defender game is also a significant kind of game in this research field. In a TAD game, the attacker aims to capture the target and avoid being intercepted by the defender, while the defender and the target cooperate to prevent the attacker from reaching its goal. This kind of game can be considered a special kind of the reach-avoid game whose target area is moveable. A pursuit-evasion-defense differential game in dynamic constrained environments was investigated through the solution of a double-obstacle HJI variational inequality by Fisac and Sastry [32]. Oyler et al. [33] presented the TAD game in the presence of obstacles which is more suitable to analyze realistic situations than the general differential game. Liang et al. [34] studied a two-pronged pursuit-evasion problem, and based on the explicit policy method, they give the complete expression of the barrier. They provided a further study on strategies’ switch of the players for cooperative target defense [35].All these works have made seminal contributions to the research of the reach-avoid game. However, most of these works consider only the situation when both sides of the game have full state information of the other. In a realistic situation, the agent must be equipped with sensors to acquire information about the environment nearby and the detection ranges of the sensors are always limited. In this work, we assume that the defender is equipped with a radar with a limited detection range and the attacker has full state information of the defender, including the radius of its detection range. This assumption corresponds to the realistic military conflict in which the attacker has the initiative and the defender side has less information than its opponent when the attacker plans its attack. The defender can get access to the position and velocity information of its opponent only when the attacker is inside its detection range. This assumption makes the game more realistic than the classic games and more valuable to investigate. Furthermore, only a few works have considered the maximum operation times of the players involved in the game. For example, Yan et al. [36] considered the aforementioned constraints in the differential game. In fact, due to the limited energy of the agents, the time requirements of their missions, and other practical constraints, the operating times of the agents are always limited. Motivated by this fact, a kind of reach-avoid game with a time limit is considered in this article. Since the defenders are always deployed near the target area, which is friendly to them, and the attackers come from their bases far away from the target area, it is reasonable to assume that the defender has adequate energy to support its operation during the game. Therefore, we only consider the time limit of the attacker in this article. In this work, the players have simple motion in a two-dimensional plane, which is partitioned by a straight line called the target line into two disjoint parts: the target region and the play region. The objective of the attacker is to reach the target region before reaching its maximum running time or being captured. Contrarily, the defender employs strategies when the attacker is detected to intercept the attacker or forces the attacker to terminate in the play region. It can be easily found that if there is no constraint on the attacker, the attacker can always adopt strategies to bypass its opponent’s detection range and ensure its victory. So, we need to make restrictions on the attacker. Due to the increasing complexity of terminal conditions caused by the time limit and detection range, the classic Hamilton–Jacobi–Isaacs approach is not suitable to handle the problem proposed here. To overcome these disadvantages, instead of using the classical approach, this paper introduces a geometric method to solve the new kind of reach-avoid game qualitatively and obtain the complete barrier of the game. The shortest trajectories that guarantee the victory of the attacker are also provided in this article.We divide the game into two parts. The first part is that the attacker is initially located inside the detection range of the defender and the second part is the attacker is located outside that. The main contributions of this article are as follows.(1)
For the first part, we prove that the attacker cannot leave the detection range of the defender, which is a common conclusion that can be used in other games considering the time limit and detection range with different game setups. Also, we obtain the expressions of the related barrier.(2)
We investigate the possible equilibrium terminal states of the game and prove that if the attacker is located on the part of the barrier outside the detection range, it must reach the target line at its time limit by employing its optimal strategy. This means that the optimal strategy of the attacker must be moving along the shortest trajectory that guarantees its arrival at the target line without being intercepted in advance. This is a common conclusion in all the reach-avoid games with different game setups considering the time limit and detection range. It shrinks the possible set of the game’s terminal states and reduces the difficulty of solving the problem.(3)
Using the properties of the circle and the form of the players’ optimal strategies obtained via the HJI differential equations, we acquire the optimal strategies and the related optimal trajectories of the attacker according to its initial location. The optimal trajectories of the attacker obtained in this work are valid when the defender is equipped with radar of which the detection range is circular or seekers of which the detection area is sectorial.(4)
By comparing the optimal trajectories and the time limit of the attacker, the barrier of the reach-avoid game with a time limit and detection range for the second part is constructed and illustrated. Combining the barriers of the first part and the second part, the complete barrier of the reach-avoid game with a time limit and detection range is obtained.To our best knowledge, it is the first time that someone brings the time limit and the detection range to the reach-avoid game simultaneously. The introduction of these concepts makes the game more complex and more practical than most of the previous works in this research direction. The solution obtained in this article can be used to quickly judge the result of the game via the initial configuration of the game and can handle practical situations which have real-time requirements.The rest part of this article is organized as follows. In Section2, the formulation of the reach-avoid game with a time limit and detection range is presented and the game is divided into two parts, the part where the attacker is inside the detection range and the part that the attacker is outside the detection range. In Section 3, the possible neutral terminal states of the game are provided and the barrier of the former part of the reach-avoid game is constructed utilizing a geometric method. In Section 4, we prove that the optimal trajectory of the attacker is the shortest trajectory that guarantees the arrival at the target line when it is outside the detection range, and we give the expressions of the optimal trajectories in all possible situations. In Section 5, the barrier of the game is provided and illustrated based on the optimal trajectories obtained and the time limit of the attacker. In Section 6, some numerical simulations are provided to prove the correctness of the barrier obtained in this work. Finally, in Section 7, the conclusion and future work are summarized.For the ease of the reader, some of the important notations with summarized descriptions are listed in Table1. These notations will also be explained in detail in the rest of the paper.Table 1
Notation table.
SymbolDescriptionΩ=ℝ2Game domainxA=xAt,yAtTThe position ofA at time tx=xAT,xDTTThe state of the gameS=SA∪SDThe set of the game’s terminal statesℬThe barrier of the game with a time limit and detection ranget¯AThe maximum operating time ofARA=vAt¯AThe maximum range ofAIPThe point whereA enters the detection rangeRD,θPThe polar coordinate ofIPPlThe left one of the intersection points ofIPD-based Apollonian circle and TT⊂ΩThe target linexD=xDt,yDtTThe position ofD at time tα<1Speed ratiovA/vDSNThe set of the game’s neutral terminal statesℬTThe barrier of the game with a time limit onlyRDThe radius of the defender’s detection rangeyD,0They-coordinate of the defender’s initial positionIFThe point whereA reaches the boundary of the detection range for the first timeRD,θFThe polar coordinate ofIFxlThex-coordinate of the point Pl


## 2. Problem Formulation

### 2.1. The Reach-Avoid Game with a Time Limit and Detection Range

In this section, the problem formulation of the reach-avoid game with a time limit and detection range is provided. The attackerA and the defender D move in a planar environment Ω=ℝ2, as is shown in Figure 1. The planar space is separated by the target line, which is a straight line and is denoted as T, into two parts: the play region ΩP and the target region ΩT. It can be seen that all the possible target areas in practical situations can be approximated by polygons whose boundaries consist of line segments. Thus, it is essential to investigate the reach-avoid game with the aforementioned game setup. In this article, both players are considered as mass points with simple motion and they are initially located in the play region ΩP. A Cartesian coordinate system is built with the origin and the x-axis located on the target line T. Thus, ΩP=x,y|y>0, ΩT=x,y|y<0, and T=x,y|y=0. The states of the players at the time t are denoted by their Cartesian coordinates xA=xAt,yAtT and xD=xDt,yDtT. We assume that the origin of the coordinate system is below the initial position of D. This means that xD0=0, and this assumption does not influence the solution to the problem. The state of the game is given by x=xAT,xDTT, and the state space of the game is ℝ4. In this article, we assume that the players have a simple motion with speeds vAt,vDt, respectively. The maximum speeds of the players are two constants, which are denoted as v¯A,v¯D, respectively. This model and the game environment are typically encountered in the games of Isaacs and there exist many seminal works analyzing practical conflicts based on them [3, 4, 12]. The maximum speed of the defender is assumed to be larger than that of the attacker, and the speed ratio between these two players is defined as α=v¯A/v¯D<1. Their control variables are their instantaneous heading angles ϕAt,ϕDt∈−π,π. The dynamics of the players are expressed as follows:(1)x˙=x˙Aty˙Atx˙Dty˙Dt=vAtcosϕAtvAtsinϕAtvDtcosϕDtvDtsinϕDt=fx.Figure 1
The reach-avoid game with a time limit and detection range.The defender can respond to the attacker’s strategy instantly and the control variablesϕA,ϕD are selected simultaneously and can change instantaneously.In practical application, due to the constraints like the limited energy, the time requirements of the attacker’s missions, and so on, the maximum operating time of the attacker is always limited. Since the defender is always deployed near the target area which is friendly to it, we assume that the defender has adequate energy to support its operation. Also, the defender can employ state feedback strategies against the attacker only when it has access to the position of the attacker. The defender stays still before it detects the attacker via the sensors it equipped. The shape of the sensor’s detection area, for example, the radar, is usually circular. The detection area of the defender considered in this work is shown in Figure1. We assume that the attacker knows the detection range and location of its opponent. This assumption is reasonable since the attacker often has the initiative when it plans its attack in the conflict and the defender often has less information than its opponent in realistic situations. Also, we assume that the defender cannot foresee the intrusion to show the initiative of the attacker. Thus, when the attacker is initially outside the detection range, the defender does not know the existence of the attacker and cannot adopt any strategies against it. In this situation, x˙D=0 and y˙D=0. However, if the attacker is once detected and then leaves the detection range, the defender will exhibit a random walk until it finds the attacker.Lett¯A be the maximum operating time of A. Since v¯A is a constant, the possible maximum range of A is a constant and is denoted as RA=v¯At¯A. From the time limit and simple motion of A, we can learn that the possible terminal position set of the attacker, which is called the reachable area of the attacker (RAA), is a circle with the center located at xA. The radius of this circle is RA. Let RD be the detection radius of D. The boundary of the detection range is called the circle of detection. The condition that the defender finds the attacker is given as follows:(2)D=x|xAt−xDt2<RD,where ⋅2 stands for the Euclidean norm in ℝ2. The RAA and the detection range of the defender are shown in Figure 1.In this article, only point capture is considered, which means that the interception happens when the separation between the attacker and the defender becomes zero. Suppose that the game terminates at the timetf, which cannot be larger than t¯A. The capture set of this game is given as follows:(3)C=x|xAtf−xDtf2=0,tf⩽t¯A.The terminal set of the game can be denoted as follows:(4)S=SA∪SD.The subspaceSA is defined as follows:(5)SA=x|yAtf⩽0,xAt−xDt2>0,t⩽tf⩽t¯A.If the game state terminates inSA, the attacker wins the game. Contrarily, the defender wins if the game state terminates in SD, which is(6)SD=x|yAt>0,xtf∈C,t⩽tf∪x|yAtf>0,xtf∉C.Thus, the target of the attacker is to drive the game statex into SA, while the defender tries to force the state of the game into SD. Since the reach-avoid game terminates immediately when the attacker enters the ΩT, in this article, we assume that the initial position of the attacker lies in the play region ΩP to ensure that the game exists [37].


### 2.2. Main Problem

In this article, we mainly focus on solving the reach-avoid game with a time limit and detection range qualitatively. This kind of problem is known as the game of kind and it requires us to answer the question that which player wins the game with a given game spaceΩ and T, the initial positions of the attacker and the defender, the maximum speeds of the players v¯A and v¯D, the time limit t¯A, and the detection radius RD. Referring to Isaacs’ book, to solve this problem, we need to construct the hypersurface called the barrier ℬ in ℝ4 based on the aforementioned information. When the initial position of D is fixed, the barrier degenerates into a 2-dimensional curve that can be illustrated. The barrier ℬ divides the game space Ω into two disjoint parts: the attack dominance region (ADR) and the defense dominance region (DDR). These concepts of regions were introduced by Yan et al. [28], which are similar to the concepts of the capture zone and the escape zone in Isaacs’ book. If the game state is located in ADR, the attacker can ensure the successful arrival at ΩT without being intercepted by the defender or reaching its time limit, irrespective of the strategies that the defender employs. On the contrary, if the state of the game is located in DDR, the attacker cannot reach its goal, which ensures the victory of the defender.When the state of the game lies on the barrierℬ, the attacker must apply the optimal control variables vA∗ and ϕA∗ to ensure the state stays outside the DDR, while the defender must choose its optimal strategies vD∗ and ϕD∗ to prevent the state of the game from getting into the ADR. Both players adopt their optimal strategies and the game achieves an equilibrium outcome. This outcome is called the neutral state of the game and is regarded as a situation where neither the attacker nor the defenders win the game. Although it may guarantee the victory of one player, any tiny change could lead to a different result in the game. This kind of situation is also regarded as the equilibrium outcome. The set of the game’s neutral states SN consists of three parts and can be delineated as [37].(7)SN,1=x|yAtf=0,xAtf−xDtf2=0,tf<t¯A,SN,2=x|yAtf=0,xAtf−xDtf2≠0,tf=t¯A,(8)SN,3=x|yAtf=0,xAtf−xDtf2=0,tf=t¯A.The first part of the setSN,1 indicates that when the players both adopt their optimal strategies, they coincide with each other once the attacker reaches T before reaching its time limit. The equilibrium outcome is caused by the capture. The second part SN,2 indicates that the attacker reaches its goal at time t¯A without being intercepted. The equilibrium outcome is caused by its time limit here. The third part is the aggregation of the other two kinds of equilibrium outcomes. In general, the barrier is constructed based on the set of neutral states. However, it is obvious that the set of the game is complex and it is difficult to construct the barrier via Isaacs’ classic approach since sketching the boundary of the terminal set is a challenge [34].Also, different from the traditional reach-avoid game which usually assumes that the attacker and the defender have full access to the positions of each other, in this work, the location of the attacker is unknown to the defender if the attacker stays outside the detection range. Thus, when the attacker is outside the detection range, this game degenerates into an optimization problem related to the attacker and this degeneration increases the difficulty of the game. Since there is a time limit of the attacker, the optimal strategy of the attacker is to find the shortest path towardT when it remains undetected. Due to the existence of this degeneration, two situations need to be discussed.(1)
The attacker is initially located inside the detection range, which means thatxA0−xD02<RD.(2)
The attacker is initially located outside the detection range, which means thatxA0−xD02>RD.In the following part of the article, we will discuss these two situations to form the complete solution of the reach-avoid game considered in this work.


## 2.1. The Reach-Avoid Game with a Time Limit and Detection Range

In this section, the problem formulation of the reach-avoid game with a time limit and detection range is provided. The attackerA and the defender D move in a planar environment Ω=ℝ2, as is shown in Figure 1. The planar space is separated by the target line, which is a straight line and is denoted as T, into two parts: the play region ΩP and the target region ΩT. It can be seen that all the possible target areas in practical situations can be approximated by polygons whose boundaries consist of line segments. Thus, it is essential to investigate the reach-avoid game with the aforementioned game setup. In this article, both players are considered as mass points with simple motion and they are initially located in the play region ΩP. A Cartesian coordinate system is built with the origin and the x-axis located on the target line T. Thus, ΩP=x,y|y>0, ΩT=x,y|y<0, and T=x,y|y=0. The states of the players at the time t are denoted by their Cartesian coordinates xA=xAt,yAtT and xD=xDt,yDtT. We assume that the origin of the coordinate system is below the initial position of D. This means that xD0=0, and this assumption does not influence the solution to the problem. The state of the game is given by x=xAT,xDTT, and the state space of the game is ℝ4. In this article, we assume that the players have a simple motion with speeds vAt,vDt, respectively. The maximum speeds of the players are two constants, which are denoted as v¯A,v¯D, respectively. This model and the game environment are typically encountered in the games of Isaacs and there exist many seminal works analyzing practical conflicts based on them [3, 4, 12]. The maximum speed of the defender is assumed to be larger than that of the attacker, and the speed ratio between these two players is defined as α=v¯A/v¯D<1. Their control variables are their instantaneous heading angles ϕAt,ϕDt∈−π,π. The dynamics of the players are expressed as follows:(1)x˙=x˙Aty˙Atx˙Dty˙Dt=vAtcosϕAtvAtsinϕAtvDtcosϕDtvDtsinϕDt=fx.Figure 1
The reach-avoid game with a time limit and detection range.The defender can respond to the attacker’s strategy instantly and the control variablesϕA,ϕD are selected simultaneously and can change instantaneously.In practical application, due to the constraints like the limited energy, the time requirements of the attacker’s missions, and so on, the maximum operating time of the attacker is always limited. Since the defender is always deployed near the target area which is friendly to it, we assume that the defender has adequate energy to support its operation. Also, the defender can employ state feedback strategies against the attacker only when it has access to the position of the attacker. The defender stays still before it detects the attacker via the sensors it equipped. The shape of the sensor’s detection area, for example, the radar, is usually circular. The detection area of the defender considered in this work is shown in Figure1. We assume that the attacker knows the detection range and location of its opponent. This assumption is reasonable since the attacker often has the initiative when it plans its attack in the conflict and the defender often has less information than its opponent in realistic situations. Also, we assume that the defender cannot foresee the intrusion to show the initiative of the attacker. Thus, when the attacker is initially outside the detection range, the defender does not know the existence of the attacker and cannot adopt any strategies against it. In this situation, x˙D=0 and y˙D=0. However, if the attacker is once detected and then leaves the detection range, the defender will exhibit a random walk until it finds the attacker.Lett¯A be the maximum operating time of A. Since v¯A is a constant, the possible maximum range of A is a constant and is denoted as RA=v¯At¯A. From the time limit and simple motion of A, we can learn that the possible terminal position set of the attacker, which is called the reachable area of the attacker (RAA), is a circle with the center located at xA. The radius of this circle is RA. Let RD be the detection radius of D. The boundary of the detection range is called the circle of detection. The condition that the defender finds the attacker is given as follows:(2)D=x|xAt−xDt2<RD,where ⋅2 stands for the Euclidean norm in ℝ2. The RAA and the detection range of the defender are shown in Figure 1.In this article, only point capture is considered, which means that the interception happens when the separation between the attacker and the defender becomes zero. Suppose that the game terminates at the timetf, which cannot be larger than t¯A. The capture set of this game is given as follows:(3)C=x|xAtf−xDtf2=0,tf⩽t¯A.The terminal set of the game can be denoted as follows:(4)S=SA∪SD.The subspaceSA is defined as follows:(5)SA=x|yAtf⩽0,xAt−xDt2>0,t⩽tf⩽t¯A.If the game state terminates inSA, the attacker wins the game. Contrarily, the defender wins if the game state terminates in SD, which is(6)SD=x|yAt>0,xtf∈C,t⩽tf∪x|yAtf>0,xtf∉C.Thus, the target of the attacker is to drive the game statex into SA, while the defender tries to force the state of the game into SD. Since the reach-avoid game terminates immediately when the attacker enters the ΩT, in this article, we assume that the initial position of the attacker lies in the play region ΩP to ensure that the game exists [37].


## 2.2. Main Problem

In this article, we mainly focus on solving the reach-avoid game with a time limit and detection range qualitatively. This kind of problem is known as the game of kind and it requires us to answer the question that which player wins the game with a given game spaceΩ and T, the initial positions of the attacker and the defender, the maximum speeds of the players v¯A and v¯D, the time limit t¯A, and the detection radius RD. Referring to Isaacs’ book, to solve this problem, we need to construct the hypersurface called the barrier ℬ in ℝ4 based on the aforementioned information. When the initial position of D is fixed, the barrier degenerates into a 2-dimensional curve that can be illustrated. The barrier ℬ divides the game space Ω into two disjoint parts: the attack dominance region (ADR) and the defense dominance region (DDR). These concepts of regions were introduced by Yan et al. [28], which are similar to the concepts of the capture zone and the escape zone in Isaacs’ book. If the game state is located in ADR, the attacker can ensure the successful arrival at ΩT without being intercepted by the defender or reaching its time limit, irrespective of the strategies that the defender employs. On the contrary, if the state of the game is located in DDR, the attacker cannot reach its goal, which ensures the victory of the defender.When the state of the game lies on the barrierℬ, the attacker must apply the optimal control variables vA∗ and ϕA∗ to ensure the state stays outside the DDR, while the defender must choose its optimal strategies vD∗ and ϕD∗ to prevent the state of the game from getting into the ADR. Both players adopt their optimal strategies and the game achieves an equilibrium outcome. This outcome is called the neutral state of the game and is regarded as a situation where neither the attacker nor the defenders win the game. Although it may guarantee the victory of one player, any tiny change could lead to a different result in the game. This kind of situation is also regarded as the equilibrium outcome. The set of the game’s neutral states SN consists of three parts and can be delineated as [37].(7)SN,1=x|yAtf=0,xAtf−xDtf2=0,tf<t¯A,SN,2=x|yAtf=0,xAtf−xDtf2≠0,tf=t¯A,(8)SN,3=x|yAtf=0,xAtf−xDtf2=0,tf=t¯A.The first part of the setSN,1 indicates that when the players both adopt their optimal strategies, they coincide with each other once the attacker reaches T before reaching its time limit. The equilibrium outcome is caused by the capture. The second part SN,2 indicates that the attacker reaches its goal at time t¯A without being intercepted. The equilibrium outcome is caused by its time limit here. The third part is the aggregation of the other two kinds of equilibrium outcomes. In general, the barrier is constructed based on the set of neutral states. However, it is obvious that the set of the game is complex and it is difficult to construct the barrier via Isaacs’ classic approach since sketching the boundary of the terminal set is a challenge [34].Also, different from the traditional reach-avoid game which usually assumes that the attacker and the defender have full access to the positions of each other, in this work, the location of the attacker is unknown to the defender if the attacker stays outside the detection range. Thus, when the attacker is outside the detection range, this game degenerates into an optimization problem related to the attacker and this degeneration increases the difficulty of the game. Since there is a time limit of the attacker, the optimal strategy of the attacker is to find the shortest path towardT when it remains undetected. Due to the existence of this degeneration, two situations need to be discussed.(1)
The attacker is initially located inside the detection range, which means thatxA0−xD02<RD.(2)
The attacker is initially located outside the detection range, which means thatxA0−xD02>RD.In the following part of the article, we will discuss these two situations to form the complete solution of the reach-avoid game considered in this work.


## 3. The Reach-Avoid Game When the Attacker Is inside the Detection Range

In this section, we investigate the reach-avoid game with a time limit and detection range when the attacker is initially located inside the detection range. For simplicity, timet will be omitted in the rest part of the article. It is obvious that at the beginning of the game, in this situation, the attacker and the defender can adopt strategies against their opponent and the game is a traditional reach-avoid game. This leads to the following theorem:Theorem 1.
When the attacker is inside the detection range, the optimal trajectories of the players are straight lines, and the attacker remains inside the detection range during the rest of the game process.Proof.
Referring to Isaacs’s book, we can easily obtain the optimal strategies of the players via the HJI approach. The attacker strives to reach the target line without being intercepted before reaching its time limit. The payoff function of the game can be expressed as follows:(9)Jx,vA,vD,ϕA,ϕD=Gxtf,tf+∫0tfFx,vA,vD,ϕA,ϕD,tdt,Gxtf,tf=a1xAtf−xDtf2−a2yAtf,where a1>0 and a2>0 are weighting coefficients. The function Gxtf,tf represents the payoff related to the terminal state of the game, and the function Fx,vA,vD,ϕA,ϕD,t represents the payoff accumulated during the game process. Since we are only interested in the outcome of the game, which is only related to the terminal state, we have Fx,vA,vD,ϕA,ϕD,t=0. If the attacker tries to win the game, it needs to adopt proper strategies to maximize the payoff function. On the contrary, the defender strives to minimize the function J. Thus, the value of the game is as follows:(10)Vx,ϕA,ϕD=minϕD,vDmaxϕA,vAJx,vA,vD,ϕA,ϕD.
By adding this payoff function, the game can be considered a minimax optimization problem. From the dynamics of the players, which is equation (1), and the calculus of variations, we can obtain the Hamiltonian of this differential game, which is as follows:(11)ℋx,λ,vA,vD,ϕA,ϕD=F+λTx˙=λTfx=λ1vAcosϕA+λ2vAsinϕA+λ3vDcosϕD+λ4vDsinϕD,where λ=λ1,λ2,λ3,λ4∈ℝ4 is the corresponding co-state vector. Since the Hamiltonian and the dynamics of the game are decoupled in control variables vA,ϕA and vD,ϕD, according to the HJI approach, we have as follows:(12)ℋx,λ,vA∗,vD∗,ϕA∗,ϕD∗=minϕD,vDmaxϕA,vAℋx,λ,vA,vD,ϕA,ϕD=maxϕA,vAminϕD,vDℋx,λ,vA,vD,ϕA,ϕD.
Thus, the optimal strategies of the players can be expressed as follows:(13)cosϕA∗=λ1ρ1,sinϕA∗=λ2ρ1,ρ1=λ12+λ22,vA∗=v¯A,cosϕD∗=−λ3ρ2,sinϕD∗=−λ4ρ2,ρ2=λ32+λ42,vD∗=v¯D,ℋx,λ,ϕA∗,ϕD∗=vAλ12+λ22−vDλ32+λ42.
Additionally, the co-state dynamics are as follows:(14)λ˙=−∂H∂x=0.
Hence, all the co-states are constant and the optimal heading anglesϕA∗, ϕD∗ remain constant during the game process. In other words, the players’ optimal trajectories are straight lines. Also, according to equation (13), when the attacker is detected, the attacker and the defender will move at their maximum constant speeds during the game process. This theorem is also obtained and utilized in many works which have similar game setups [2–4, 37]. In fact, when the attacker is initially located in the detection range, the original game in this work becomes the game that has already been studied by Yan et al. [36].
Referring to Isaacs book [1], the attacker and the defender ultimately coincide with each other when adopting the aforementioned strategies, irrespective of the situation that A reaches the target region or its time limit. All the possible intersection points in this situation form a circle with a center at O=xA−α2xD/1−α2,yA−α2yD/1−α2 and radius of rO=α/1−α2xA−xD2. This circle is called the Apollonian circle. Since they ultimately coincide with each other along straight lines, it is obvious that the distance between the attacker and the defender monotonically decreases to zero. Therefore, once the attacker enters the detection range, it remains inside the detection range during the rest of the game. The proof is completed.Lemma 1 (see [1]).
For a pair of straight-moving agents, the planar space can be partitioned into two disjoint parts by the related Apollonian circle. Moreover, all the points inside the circle can be reached by the attacker before the defender regardless of the attacker’s time limit. Consider the definition of the Apollonian circle: since the attacker and the defender ultimately coincide with each other when they adopt their optimal strategies obtained in Theorem1, the attacker can never reach any point outside the Apollonian circle once it is detected. Moreover, if the Apollonian circle intersects with the target region, the attacker can ensure its victory by moving directly toward any point which is inside both the Apollonian circle and the target region, regardless of its time limit.From Theorem1, we can learn that when the attacker is initially located inside the detection range, the game considered in this work is the same as the game with a time limit of the attacker only. The existence of the defender’s detection range does not influence the game process in this situation. It should be noticed that the game with a time limit only has already been studied in former work [36]. The optimal trajectories of the players are straight lines, which are obtained in both Theorem 1 and Yan et al.’s work [36], and we give the expressions without proof here. The barrier of the reach-avoid game with a time limit only, which is denoted as ℬT, is given by the following equation:(15)ℬT=x,y|x2+1−1α2y2+1−α2yD,02=0,x∈−p1,p1∪x,y|x−RAα2−yD,022+y2=RA2,x∈p1,p2∪x,y|x+RAα2−yD,022+y2=RA2,x∈−p2,p1∪x,y|y=RA,x∈−∞,−p2∪p2,+∞,when yD,0<RA/α, where yD,0=yD0, p1=1−α2RA/α2−yD,02; and p2=RA/α2−yD,02.WhenyD,0⩾RA/α, the barrier of the given game is as follows:(16)ℬT=x,y|y=RA.From equation (16), we can learn that if yD,0⩾RA/α, the initial position of D does not influence the barrier. Thus, in the rest of this article, we mainly focus on the situation that yD,0<RA/α. Some useful conclusions were acquired in Yan’s work [36] that will be utilized to handle the problem considered in this article hereinafter, and we give these conclusions without proof. Due to the symmetry, we investigate the barrier in the condition that xA>0 only. Analogous analysis can be done for the situation when xA⩽0.Lemma 2.
IfA is located on the barrier ℬT with yA0=RA, the defender has no influence on the attacker, and the optimal trajectory of A is to move vertically downward to T. In this situation, A reaches T at time t¯A. The equilibrium outcome of the game is caused by the attacker’s time limit only here. Furthermore, from the time limit of A, the equations (16) and (17), we can find out that the space x,y|y>RA is always inside the DDR because the maximum range of the attacker is RA.The barrier of the game with a time limit of the attacker only is illustrated in Figure2. The part of the barrier when the attacker is inside the detection range can be easily obtained from equations (15) and (16), which are expressed in the following theorem.Figure 2
The barrier of the reach-avoid game with a time limit ofA only.Theorem 2.
The barrier when the attacker is initially located inside the detection range is the part of the barrierℬT inside the detection range. This part of the barrier can be expressed as follows:(17)ℬinner=x,y|x,y∈ℬT,x2+y2<RD.Proof.
This theorem is obvious and the proof is omitted here.Also, there is a simple theorem about the expression of the barrier and the parameterRD.Theorem 3.
For a pointxB,yB on the barrier, if xB…minp2,RD, yB=RA. Furthermore, if RD satisfies that(18)RD…1+α2α2RA2−2RAyD,0,where the barrier of the game considered in this article is ℬ=ℬT.Proof.
It is obvious that if there is no defender, the shortest path for the attacker to get toT is moving vertically downward. When xB…RD and the attacker moves vertically downward, all the points on the attacker’s trajectory are outside the defender’s detection range. In other words, the defender cannot adopt any strategy against its opponent in this situation. Thus, the part of the barrier here satisfies that yB=RA and the attacker reaches T at t¯A. According to Lemma 2, if xB…p2, the defender cannot influence the attacker when it moves vertically downward to T. So, if xB…minp2,RD, yB=RA.
From the conclusion obtained above in this proof, we can learn that the fourth part of the equation (15) is always a part of the barrier ℬ related to the game considered in this work. According to Theorem 2, if the first three parts of the equation (15) are inside the detection range, these parts of the barrier are also the components of ℬ. Thus, in this situation, the whole barrier of the game satisfies ℬ=ℬT. The condition that the first three parts are inside the detection range is that the point p2,RA is inside the detection range, which can be expressed as follows:(19)RD…p22+RA−yD,02=1+α2α2RA2−2RAyD,0.
Thus, we complete the proof.


## 4. The Optimal Strategies of the Attacker outside the Detection Range without a Time Limit

In the rest part of the article, we will investigate the part of the barrier outside the detection range. Different from the situations discussed above, when the attacker is outside the detection range, the part of the reach-avoid game before the attacker enters the detection range is an optimization problem related to the attacker only. Moreover, in the related optimization problem, the attacker’s optimal trajectories can be any kind of curve, rather than just a straight line. If we want to obtain the barrier of the game, we need to obtain the attacker’s optimal strategies in all possible situations first. It is obvious that the attacker’s initial position, the parametersRD, yD,0, and RA all influence the related trajectory. According to equation (16), Lemma 2, and Theorem 3, we only need to discuss the situation when RD<1+α2/α2RA2−2RAyD,0 and yD,0<RA/α in the following.Let us first consider the attacker’s initial position. To simplify the problem, we divide the space outside the detection range of the defender into two different areas. The division is shown in Figure3. The Area1 consists of the area that satisfies x∈−∞,−RD∪RD,+∞ and the area below the detection range. The second area is above the detection range with x∈−RD,RD. When A is initially located in Area1, its optimal strategy is moving vertically downward. This is the shortest trajectory to the target line and D cannot detect A when it moves along the related trajectory.Figure 3
The division of the space outside the detection range.WhenA is initially located in Area2, however, it cannot move vertically downward without remaining undetected during the game process. The possible trajectories of the attacker here can be divided into two types:(1)
All parts of the attacker’s trajectory are outside the detection range. This kind of trajectory is called the bypassing trajectory.(2)
Some part of the attacker’s trajectory is inside the detection range. This kind of trajectory is called the penetrating trajectory.As mentioned in Section2.2, the barrier is generally constructed based on the set of the game’s neutral states in this research direction. However, the possible terminal set of the game in this work is complex, which increases the difficulty of solving the game. Thus, it is necessary to analyze and simplify the neutral terminal set SN to make the game solvable. For the first type, since the attacker remains undetected during the game, the defender cannot capture the attacker, and the related neutral terminal set belongs to SN,2. For the second type, we have the following theorem.Theorem 4.
If the attacker moves along a penetrating trajectory, the possible related neutral states cannot be inSN,1.Proof.
We use reduction to absurdity to prove this theorem. Suppose that there is some position of the attacker that the related optimal strategies of the attacker lead to the terminal states inSN,1. Since the attacker adopts strategies of the second type, according to Theorem 1, the part of the attacker’s optimal trajectory inside the detection range must be a straight line. Let IP be the intersection point of the optimal straight line inside the detection range and the boundary of the detection range. This point is called the penetration point.
As shown in Figure4, if the optimal strategies of the players lead to the terminal states in SN,1, which means A and D coincide with each other on T before t¯A, according to the definition of Apollonian circle, the possible terminal positions of A and D can only be Pl=xl,0 or Pr=xr,0. Pl and Pr are the left and right intersection points of the target line and the IPD-based Apollonian circle. Let t1 be the terminal time in this situation and Cout be the related optimal trajectory outside the detection range. We have t1<t¯A. Notice that xD0=xDt2=0, xOt2=xIP/1−α2>xIP. Thus, it can be easily found out that the distance between IP and Pr is longer than that between IP and Pl. Considering that all the points on T between Pl and Pr are inside the IPD-based Apollonian circle, the attacker can reach any one of these points without being intercepted, regardless of its time limit. If the terminal neutral position is Pr, the attacker can reach any point between Pl and Pr along the trajectory Cout and the straight line between IP and that point within t1. This new trajectory leads to the victory of the attacker without reaching the time limit. So, the terminal neutral position cannot be Pr.
Next, we investigate the situation that the terminal neutral position isPl. There always exists some point PN on the right of Pl satisfies that IPPN−IPPl<vAt¯A−t1. Since PN is located between Pl and Pr, the attacker can reach the target line along Cout and line IPPN without being captured or reaching its time limit. In other words, the attacker can always find a better strategy to avoid making the game states terminate in SN,1 and the possible neutral states cannot be in SN,1. The proof is complete.Thus, the set of the game’s neutral statesSN consists of SN,2 and SN,3 when A is initially outside of the circle of detection. This means that if the attacker is on the barrier outside the detection range, it must reach its time limit once it reaches the target line. From this conclusion, we can learn that the optimal trajectory of the attacker must be the shortest trajectory which guarantees the arrival of the attacker at T without being intercepted in advance, no matter which kind of trajectory it is. If the optimal trajectory is not the shortest, there are always some other trajectories that ensure the arrival of A at T within t¯A. Moreover, the related possible neutral terminal set is SN,1 here, which contradicts Theorem 4. It can be seen that the shortest path which guarantees the arrival at T without being captured in advance has nothing to do with the time limit. If we obtain the shortest path, the barrier can be easily constructed based on the length of the related path and the attacker’s maximum range RA.To construct the barrier of the game and reduce the complexity of the investigation, we need to analyze the aforementioned attacker’s shortest paths in all possible situations first. We start with the bypassing trajectory. Here, we give a simple conclusion which will be utilized in the following part of the article.Figure 4
The position relation between theIPD-based Apollonian circle and the target line.Lemma 3.
As shown in Figure5, for a point P1 outside a certain circle and a point P2 on the boundary of the circle, the shortest path between them without penetrating the circle is as follows:(20)LS=P1P2,P2∈Ω1,P1Pi+P2Pi,P2∈Ω2,where i∈L,R, PL and PR are two tangent points of which the corresponding tangent lines cross point P1. The point Pi is one of the tangent points which is nearer to P2.According to the theorems given above, we can easily obtain the optimal bypassing trajectory. Here, we give the optimal trajectory without proof.Figure 5
The shortest path between a point outside and a point on the circle without penetrating it.Lemma 4.
If the initial location of the attacker is insideArea1 shown in Figure 3, the optimal strategy of it is moving vertically downward. If the attacker is initially located in Area2, the optimal strategy without penetrating the circle of detection consists of three parts. The first part is moving toward the lower one of the tangent points of which the related tangent lines cross A. Then, the second part is moving along the circle of detection to point on the circle of which the y-coordinate is yD,0. Moreover, the third part is moving vertically downward to T.Then, we carry on investigating the penetrating trajectory. Since a part of the attacker’s optimal trajectory is inside the detection range here, whenA moves along the trajectory, there must be a point IF at which the attacker contacts the circle of detection for the first time. The coordinate of this point is denoted as xF,yF. Also, there must be an intersection point of the circle of detection and the part of the optimal trajectory inside the detection range. This point is denoted as IP and the coordinates of IP can be expressed as xP,yP.It is obvious that the penetrating trajectory consists of two parts: the part before reachingIF and the part after reaching IF. Lemma 3 has already proposed the optimal trajectory of the former part and we focus on finding the optimal trajectory of the latter part. Noticing that IF and IP may not be the same point. So, the penetrating trajectory can be further divided into two subtypes:(1)
The first touching pointIF and the penetration point IP are the same. The related trajectory is called the directly penetrating trajectory.(2)
The first touching pointIF and the penetration point IP are different points. The related trajectory is called the bypassing-penetrating trajectory.It is obvious that ifIF and IP are different points, the optimal path that connects these two points is the arc IFIP⌢ with a radius of RD. Moreover, it is indisputably that IP is below the point IF. So, the part of trajectory after reaching IF is the combination of the arc IFIP⌢ and the part of trajectory after reaching IP. The former part is simple. In the following part, we need to answer the questions of what the optimal trajectory of A is after the attacker reaches IP and where the optimal IP is to propose the optimal trajectory of the part after it reaches IF.As mentioned above, the parametersRD, yD,0, and RA all influence the related trajectory and need to be analyzed. To obtain the possible shortest penetrating trajectory, we need to find out the condition that ensures the existence of this kind of trajectory first. From Lemma 4, we can learn that the point IP must be located in Area2 shown in Figure 3. This means that yP⩾yD,0. According to Lemma 2, the space x,y|y>RA is always inside the DDR. Thus, if the attacker can enter the detection range and acquire an equilibrium outcome, yP should satisfy that yP<RA. The conditions yP⩾yD,0 and yP<RA cannot be met simultaneously when yD,0⩾RA. So, if the attacker can move along a penetrating trajectory and reach the target line, there must have yD,0<RA. This also means that if yD,0⩾RA, the attacker can only move along the bypassing trajectory.Also, we can learn from Lemma1 that the attacker can never reach any point outside the Apollonian circle once it is detected. So, if the IPD-based Apollonian circle does not intersect with T and A enters the detection range from IP, the attacker can never reach T and the defender wins the game. Thus, the attacker can enter the detection range only when the IPD-based Apollonian circle intersects with T. This condition means that the lowest point on the related Apollonian circle is on T or inside ΩT, which can be expressed as follows:(21)yO−rO=yP−α2yD,01−α2−α1−α2xP2+yP−yD,02⩽0.Simplifying this in the equation, we have as follows:(22)yP2−α21−α2xP2⩽α2yD,02.In the rest part of this section, we will analyze the possible situations related to the parametersRD, yD,0, and RA and the attacker’s optimal trajectories in these situations. This means we need to answer the question of which kind of trajectory the attacker should choose based on the values of the parameters and provide the precise form of the related paths. From inequality (22), we have a simple conclusion.Theorem 5.
IfRD∈0,1−α2/αyD,0, the attacker cannot enter the detection range without losing the game. In this situation, the attacker can only move along the bypassing trajectory to bypass the defender’s detection range.Proof.
Let us investigate the inequality (22). Similarly, we only consider the situation when xP>0. It is convenient to build a polar coordinate system to help investigate the optimal trajectory in this situation. Let the pole be located on 0,yD,0, and the polar axis be parallel to the x-axis of the Cartesian coordinate system. The coordinates of IP can be expressed as RD,θP. The polar coordinate of IF is denoted as RD,θF. Moreover, we have the following equation:(23)RDcosθi=xi,RDsinθi=yi−yD,0,where i∈P,F. From the definition of the point IP we can learn that the distance between IP and D when the attacker enters the detection range is RD. So, the inequality (22) can be rewritten as follows:(24)f1θP=RDsinθP+yD,02−α21−α2RDcosθD2⩽α2yD,02,where θP∈0,π/2. The function f1θP increases monotonically with the raising of θP. So, if minf1θP>α2yD,02, the inequality (22) is never true. Moreover, the attacker can only move along the bypassing trajectory to bypass the detection range here. This situation can be expressed as follows:(25)minf1θP=f10=yD,02−α21−α2RD2>α2yD,02,which can be rewritten as follows:(26)RD<1−α2αyD,0.
Thus, we complete the proof.
When there exists some pointIP that satisfies condition (22) and xP>0, according to the proof of Theorems 1 and 4, the optimal trajectory of A after it reaches IP must be a straight line connecting IP and some point Pend on T. As shown in Figure 4, this point Pend is Pl, the left intersection point of the related Apollonian circle and T, when Pl is on the right of IP. Moreover, the point Pend is the point below IP when Pl is on the left of IP. The optimal trajectory of A depends on the location of Pl. Let xl be the x-coordinate of Pl. Here, we give an important theorem.Theorem 6.
IfRD∈1−α2/αyD,0,1+α2/α2RA2−2RAyD,0 and yD,0<RA, the optimal trajectory of A must be the penetrating trajectory when it is located in Area2.Proof.
First, as stated above, if the attacker can move along the penetrating trajectory,yD,0 must be smaller than RA. Assume there exists some point IP inside Area2 that meets the condition that the related Pl is on the right of IP. When xP>0 and the attacker moves along the circle of detection from IF to RD,yD,0 (PR to P3 in Figure 5), it must reach that IP before reaching the point RD,yD,0. Moreover, the optimal trajectory inside the detection range is moving vertically downward from that point, which is shorter than moving to the point RD,yD,0 and then moving downward. This means that the bypassing trajectory is not optimal here.
From Figure4, it can be easily found out that, if the point Pl related to the point RD,yD,0 is on the left of RD,yD,0, there must exist a certain IP that meets the condition given above. This means that when the variable RD satisfies the following condition,(27)xP−xl=RD−RD1−α2−α1−α2RD2−yD,02=α1−α2RD2−yD,02−α2RD1−α2>0,the optimal trajectory of A must be the penetrating trajectory. This inequality can be rewritten as follows:(28)RD>1−α2αyD,0.
According to Theorem3, we are investigating the optimal trajectory with RD<1+α2/α2RA2−2RAyD,0 here. It is essential to compare the variables 1−α2/αyD,0 and 1+α2/α2RA2−2RAyD,0 to judge whether there is an interval between these two variables or not. From the condition that guarantees the existence of the penetrating trajectory, we have yD,0<RA. This means that(29)∂∂RA1+α2α2RA2−2RAyD,0=21+α2α2RA−yD,0>2RA−yD,0>0.
It can be seen that the variable1+α2/α2RA2−2RAyD,0 increases monotonically with the raising of RA. So, we have as follows:(30)1+α2α2RA2−2RAyD,0>1+α2α2yD,02−2yD,02=1−α2αyD,0.
Thus, the interval between these two variables exists and the proof is completed. The conclusion whenxP<0 can be obtained easily due to the symmetry and the related proof is omitted here.
Here, the attacker’s optimal trajectory whenRD∈1−α2/αyD,0,1−α2/αyD,0 remains unsolved. This is the most complicated situation because the bypassing trajectory, the directly penetrating trajectory, and the bypassing-penetrating trajectory are all possible. We need to investigate the length of these three kinds of trajectories simultaneously. Instead of directly analyzing this complicated situation, we will discuss the two subtypes of the penetrating trajectory in the interval of RD shown in Theorem 6 first. It is essential to judge which one is better to obtain the attacker’s optimal trajectory, and the analysis will lead to a significant conclusion that can help analyze the unsolved situation mentioned above.Theorem 7.
In the situation thatxP>0, RD∈1−α2/αyD,0,1+α2/α2RA2−2RAyD,0, and yD,0<RA, if the point IF satisfies that θF>θ1, the optimal trajectory of the attacker is a bypassing-penetrating Trajectory. If the point IF satisfies that θF⩽θ1, the optimal trajectory of the attacker is a directly penetrating trajectory. The variable θ1 meets the following condition:(31)∂l∂θP|θP=θ1=RD.The variablel is the distance between the penetrating point IP and the left intersection point Pl shown in Figure 4. There exists a certain angle θ2<θ1 that satisfies(32)RDcosθ2=RDcosθ21−α2−α1−α2RD2−yD,0+RDsinθ21−α22.IfIF satisfies θF⩽θ2, the optimal trajectory of the attacker inside the circle of detection is moving vertically downward.WhenxP<0, if the point IF satisfies that θF<π−θ1, the optimal trajectory of the attacker is a bypassing-penetrating trajectory. Moreover, if the point IF satisfies that θF>π−θ1, the optimal trajectory of the attacker is a directly penetrating trajectory.Proof.
Let us investigate the situation thatxP>0 first. As stated above, if the attacker can move along a penetrating trajectory, the IPD-based Apollonian circle should have at least one intersection point with T. The point IP satisfies the condition that the related Apollonian circle and T have only one intersection point, and the x-coordinate of IP1 is xP/1−α2>xP. From Theorem 6, we can learn that when RD>1−α2/αyD,0, the left intersection point Pl related to the point RD,yD,0 is on the left of the point RD,yD,0. This means that when IP moves clockwise from IP1 to RD,yD,0, there must exist some point IP2 of which the related left intersection point Pl is below it. This situation is shown in Figure 6. Thus, if the attacker moves along a bypassing-penetrating trajectory, the intersection point IP on this trajectory cannot be below IP2. This means that if IF moves clockwise from IP1 to IP2, the optimal trajectory inside the detection range should be the line segment connecting IP and the related Pl. Consider that the x-coordinate of IP2 equals that of the related Pl, the polar angle of IP2 should satisfies that(33)xl−xIP2=RDcosθ21−α2−α1−α2RD2−yD,0+RDsinθ21−α22−RDcosθ2=0.
Defining functionf2θ2=x1−xIP2, we have(34)f2θ2=α2RDcosθ21−α2−α1−α2RD2−yD,0+RDsinθ21−α22=RD1−α2α2cosθ2−α2−1−α2η+sinθ22=RD1−α21−α4sin2θ2+21−α2ηsinθ2+α4+1−α2η2−α2α2cosθ2+α2−1−α2η+sinθ22,where η=yD,0/RD∈0,α/1−α2. The denominator of nf2θ2 is always positive. Hence, if f2θ2=0, the numerator of the function f2θ2 equals zero. The numerator of f2θ2 is the equation of a parabola related to sinθ2. From equation (34), we can learn that(35)α2−sinθP+1−α2η2⩾0,which is(36)sinθP∈0,α−1−α2η.
Substitute the ends of the interval shown above intof2θ2, we have(37)f2θ2|sinθ2=α−1−α2η=α2RD1−α2cosθ2>0,f20=RD1−α2α2−α2−1−α2η2<RD1−α2α2−α2−α1−α22=0.
Hence, there is only one uniqueθ2 satisfying equation (33). All the points RD,θ satisfying θ<θ2 meet the condition that xl<xIP2, which means if the attacker chooses one of these points as IP, the optimal trajectory of the attacker inside the circle of detection is moving vertically downward.
Next, we investigate the parameterθ1. The distance between IP and Pl is as follows:(38)lθP=xP−xl2+yP2=RDcosθP−RDcosθP1−α2+α1−α2RD2−RDsinθP1−α2+yD,022+RDsinθP+yD,02=αRD1−α2cosθP−α2−sinθP+1−α2η22+1−α22η2.
We take two possibleIP between IP1 and IP2 into consideration, the polar angle of the first IP is θP and that of the second one is θP−Δθ, Δθ>0. This means that the second point is below the first one. From Lemma 3 we can learn that the optimal trajectory between these two points is an arc with a radius of RD. The distance of the trajectory from the first point to T is lθP and the corresponding distance of the second one is lθP−Δθ−RDΔθ. We define the function as follows:(39)LθP=lθP−lθP−Δθ−RDΔθΔθ=lθP−lθP−ΔθΔθ−RD.
Thus, whenΔθ⟶0+, the equation (39) becomes(40)LθP|Δθ⟶0=∂lθP∂θP−RD.
WhenLθP>0, the trajectory related to the first possible IP is longer than that of the second point, which means that the second one is better, and vice versa. So, if there exists some point RD,θ1 that Lθ1=0 and IF is above θ1, the attacker should move clockwise from IP to RD,θ1 and enters the detection range there. If IF is below RD,θ1, the attacker should enter the detection from this point, which means IF and IP are the same point. Thus, it is essential to check whether this point RD,θ1 exists.
Substituting equation (38) into function ∂lθP/∂θP, we have(41)∂lθP∂θP=αRD1−α2g3θPg1θP1+1−α22η2/g2θP2,where(42)g1θP=α2−sinθP+1−α2η2,(43)g2θP=cosθP−α2−sinθP+1−α2η2,(44)g3θP=sinθP+1−α2ηcosθP−sinθPα2−sinθP+1−α2η2.
It can be easily found out from (42) that g1θP decreases monotonically with the raising of θP. Equation (43) can be rewritten as follows:(45)g2θP=cosθP−α2−sinθP+1−α2η2cosθP+α2−sinθP+1−α2η2cosθP+α2−sinθP+1−α2η2,=21−α2ηsinθP+1−α2η2+1−α2cosθP+g1θP.
Sinceg1θP and cosθP decrease monotonically with the raising of sinθP, g2θP is monotonically increasing. Consider that minηg20=g20|η=0=1−α>0, we haveg2θP>0 and the denominator of equation (41) decreases monotonically.
Then, let us investigate equation (44). We define p=1−α2η∈0,α1−α2. We take the derivative of equation (44) related to sinθP we have(46)∂g3θP∂sinθP=∂∂sinθPsinθP+p1−sin2θP−sinθPα2−sinθP+p2=1−sin2θP−sinθP+psinθP1−sin2θP−α2−sinθP+p2+sinθPsinθP+pα2−sinθP+p2=1−sin2θP−α2−sinθP+p2+sinθPsinθP+pα2−sinθP+p2−sinθP+p1−sin2θP.
Notice that(47)1−sin2θP>α2−sin2θP>α2−sinθP+p2.
Substituting inequality (47) into equation (46), we have as follows:(48)∂g3θP∂sinθP>0.
This means thatg3θP increases monotonically, and we have g3θP⩾g30=1+1−α2η>0. Consider that the denominator of equation (41) decreases monotonically, the equation (41) is a monotonic increasing function. Notice that sinθP∈0,α−1−α2η, the maximum and minimum value of this function is as follows:(49)maxθP∂lθP∂θP<∂lθP∂θP|sinθP⟶α−1−α2η=+∞,minθP∂lθP∂θP=∂lθP∂θP|sinθP=0=αRD1−α21−α2−1−α22η21−α2ηα2−1−α22η21−α2−1−α22η22+1−α22η2.
Consider the definitionp=1−α2η∈0,α1−α2. The second equation of (49) can be rewritten as follows:(50)minθP∂lθP∂θP=αRD1−α21α2−p21/1−α2−p22+1/p2.
It can be easily found thatmin∂lθP/∂θP increases monotonically with the raising of p. Thus,(51)maxpminθP∂lθP∂θP<minθP∂lθP∂θP|p=α1−α2=αRD1−α21α21/1−α22+1/α21−α2=RD.
SinceminθP∂lθP/∂θP<RD, maxθP∂lθP/∂θP>RD and function ∂lθP/∂θP increases monotonically, there is only one special value θ1 that meets the following condition:(52)∂lθP∂θP|θP=θ1=RD.
Thus, we prove the existence and the uniqueness of the special valueθ1.
Next, we investigate the relationship between variablesθ1 and θ2. Assume that θ2>θ1. If IF satisfies θF=θ2, according to the definition of the variable θ1, the optimal trajectory of the attacker when θ2>θ1 is moving clockwise from point RD,θ2 to RD,θ1 and then moving vertically downward. However, from the definition of θ2, we can find that if the attacker moves vertically downward from the point RD,θ2, it can guarantee its arrival at T, and the latter trajectory is shorter than the former one. This contradicts the definition of θ1. Thus, there always has the condition that θ1>θ2.
Thus, if the pointIF satisfies that θF>θ1, the optimal trajectory of the attacker is a bypassing-penetrating trajectory. If the point IF satisfies that θF<θ1, the optimal trajectory of the attacker is a directly penetrating trajectory. Moreover, if IF satisfies that θF⩽θ2, the optimal trajectory of the attacker is moving vertically downward from there. The conclusions when xP<0 can be acquired easily from symmetry are omitted here, and we complete the proof.Now, we can analyze the situation thatRD∈1−α2/αyD,0,1−α2/αyD,0. With Theorem 7 obtained, this complicated situation is solvable now.Figure 6
The positions ofIP1, IP2 and the related Apollonian circles.Theorem 8.
In a situation whereRD∈1−α2/αyD,0,1−α2/αyD,0, the optimal trajectory of the attacker is the bypassing trajectory.Proof.
Let us investigate the two kinds of penetrating trajectories first. Consider the situation thatxP>0, xF>0. The variables η and p defined in the proof of Theorem 7 meets the following condition:(53)η=yD,0RD∈α1−α2,α1−α2,p=1−α2η∈α1−α2,α.
According to equation (50) and condition (53), the minimum value of minθP∂lθP/∂θP here satisfies that(54)minθP∂lθP∂θP>minpminθP∂lθP∂θP>minθP∂lθP∂θP|p=a1−α2=∂lθP∂θP|θP=0,p=a1−α2=RD.
Since∂lθP/∂θP is a monotonic increasing function, the function LθP is always larger than zero in this situation. This means that the directly penetrating trajectory is always longer than the bypassing-penetrating trajectory. Notice that sinθP∈0,α−1−α2η, if the attacker’s trajectory is the bypassing-penetrating trajectory, A should move clockwise from IF to point RD,yD,0 and then move along a line segment connecting RD,yD,0 and the left intersection point of T and the related Apollonian circle. According to inequalities (27) and (28), when RD<1−α2/αyD,0, the left intersection Pl related to the point RD,yD,0 meets the condition that xl>RD. From the proof of Theorem 3, we can learn that if there exists some point on the attacker’s optimal trajectory of which the x-coordinate is RD, it needs to move vertically downward from that point. Thus, the optimal trajectory of A in this situation is moving clockwise from IF to point RD,yD,0 and then moving vertically downward. It can be easily found out that the optimal described above is exactly the bypassing trajectory. Thus, we complete the proof.Now, the optimal trajectories of the attacker in all possible situations are obtained. The optimal trajectories are summarized as follows:(1)
WhenyD,0⩾RA, the optimal trajectory of the attacker is the bypassing trajectory.(2)
WhenyD,0<RA and RD∈1−α2/αyD,0,1+α2/α2RA2−2RAyD,0, the optimal trajectory of A is the penetrating trajectory. The penetrating trajectory can be further divided into two subtypes in this situation according to Theorem 7.(3)
WhenyD,0<RA and RD⩽1−α2/αyD,0, the optimal trajectory of A is the bypassing trajectory.WhenRD>1+α2/α2RA2−2RAyD,0, according to Theorem 3, the barrier of the game is the same as the barrier with a time limit of the attacker only. Since the solution to the problem has already been obtained, it is unnecessary to investigate the attacker’s optimal trajectory in this situation. Moreover, it is worth noticing that the optimal trajectory obtained in this section is still valid if the defender is equipped with an infrared seeker or vision sensor of which the detection area is usually a sector rather than a circle. The only difference is that we need to further compare the special points RD,θi,i∈1,2,3 with the endpoints of the sector’s arc to build the optimal trajectory. For example, as shown in Figure 7, if the polar angle of the endpoint E1 is larger than the corresponding θ1 and θ3, part of the attacker’s optimal trajectory is moving vertically downward from a point E1 rather than moving clockwise to point RD,θ1. And if the polar angle of the endpoint E2 is between θ1 and θ2, the optimal trajectory is the same as that under the condition that the defender has a circular detection range.With the optimal trajectories in all possible situations obtained, we can now investigate the barrier of the game considered in this article.Figure 7
The optimal trajectories of the attacker with a sectorial detection range.


## 5. Game of Kind

In this section, we give the complete solution to the reach-avoid game with time limit and detection range. The expressions of the related barrier in all possible situations are provided. The situations are classified based on the parametersRD, yD,0, and RA. Consider that the barrier whenRD⩾1+α2/α2RA2−2RAyD,0 is obtained in Theorem 3 and depicted in Figure 2; in this section, we mainly focus on the situation that RD<1+α2/α2RA2−2RAyD,0. Also, we only analyze the situation that xA>0, the barrier satisfying xA⩽0 can be obtained easily via symmetry.


### 5.1. The Reach-Avoid Game with a Time Limit and Detection Range WhenyD,0⩾RA

According to Section4, we can find that the attacker can enter the detection range and reach the target area only when the penetrating point IP satisfies θP>0. This means that the point IP satisfies yP>yD,0. Consider that the area x,y|y⩾RA is always inside the DDR. When yD,0⩾RA, we have yP⩾RA and there is no possible IP that the attacker can enter the detection range from it and reach the line T. Hence, the attacker can only move along the bypassing trajectory under this condition.Additionally, we need to investigate the position relation between the circle of detection and the barrierℬT with a time limit only to judge whether the part of the barrier with expression (17) exists. Assume that the circle of detection has intersection points with barriersℬT. The intersection points must meet the condition that(55)x2+y−yD,02=RD2,x2+1−1α2y2+1−α2yD,02=0.Simplifying equation (55), we have as follows:(56)y2α2−2yD,0y+α2yD,02=RD2,yα−αyD,02=RD2.Notice that the coordinates of the points onℬT meets the condition that y>0, the solution of equation (56) is as follows:(57)y=α2yD,0+αRD.Substituting equation (57) into the first equation in (56), and we have(58)x2+α2−1yD,0+α−1RDα2−1yD,0+α+1RD=0.SinceyD,0⩾0, α∈0,1, and RD>0, we have α2−1yD,0+α−1RD<0. Consider that x2⩾0, if equation (58) has real roots, it needs to meet the condition that(59)α2−1yD,0+α+1RD>0,which is(60)1−αyD,0<RD.So, the barrier considered in this subsection can be divided into two situations: the one with1−αyD,0⩾RD and the one with 1−αyD,0<RD. Both situations need to be discussed in detail.


#### 5.1.1. The Reach-Avoid Game with a Time Limit and Detection Range When1−αyD,0⩾RD

Let us first investigate the former situation. In this situation, there exist at most one intersection point betweenℬT and the circle of detection, which means the part of barrier with expression (17) does not exist. Considering that the optimal trajectories of the attacker must be the bypassing trajectory, the complete barrier in this situation is as follows:(61)ℬ=x,y|y=yD,0−RD2−x2,x∈−m,m∪x,y|y=yA,x∈−∞,−m∪−m,+∞,where m=RD2−RA−yD,02. The related barrier is depicted in Figure 8. Comparing the barrier ℬ with the barrier ℬT which contains only the time limit of A, we can find that the existence of the detection range expands the area of ADR, which means it benefits the attacker. It is obvious that if yD,0⩾RA, the expression of the barrier is y=RA. The defender cannot influence the barrier under this condition.Figure 8
The barrier of the game withyD,0⩾RA and 1−αyD,0⩾RD.


#### 5.1.2. The Reach-Avoid Game with a Time Limit and Detection Range When1−αyD,0<RD

Next, we investigate the situation when1−αyD,0<RD. In this situation, the circle of detection has two intersection points with ℬT, which are denoted as IR=xIR,yIR and IL=−xIR,yIR. When yIL<RA, according to Theorem 2, the complete barrier is as follows:(62)ℬ=x,y|x,y∈ℬT,x∈−xIR,xIR∪x,y|y=yD,0−RD2−x2,x∈−m,−xIR∪xIR,m∪x,y|y=RA,x∈−∞,−m∪m,+∞.The related barrier is depicted in Figure9.Figure 9
The barrier of the game withyD,0⩾RA and 1−αyD,0<RD.


### 5.2. The Reach-Avoid Game with a Time Limit and Detection Range WhenyD,0<RA

According to Subsection5.1, when RD⩽1−αyD,0, the expression of the barrier is equation (61). Hence, we consider only the situations with 1−αyD,0>RD here. Moreover, this situation can be further divided into two situations and we will analyze them individually.


#### 5.2.1. The Reach-Avoid Game with a Time Limit and Detection Range WhenRD∈1−α,1−α2/αyD,0

Consider that1−α<1−α<1−α/α, we first investigate the situation that RD∈1−α,1−α2/αyD,0. According to Section 4, the optimal trajectory of the attacker here is the bypassing trajectory. If an attacker is initially located on the barrier and its optimal trajectory is the bypassing trajectory, its initial position should satisfy that(63)h2x,y=lFx,y+RDθF+yD,0=vAt¯A,where(64)lFx,y=x−RDcosθF2+y−RDsinθF+yD,02.The first part of the equation represents the length of the segment connecting the initial position and the related first touching pointIF. The second part is the length of the arc connecting IF and point RD,yD,0. Also, the third part is the length of moving vertically downward toward T. When A is initially located on the barrier, the total length of the three parts should be RA. According to the definition of bypassing trajectory, the segment AIF is a segmental tangent line of the circle of detection, and the point IF is the related tangent point. Hence, the corresponding barrier should be as follows:(65)ℬ=x,y|x,y∈ℬT,x∈−xIR,xIR∪x,y|x=RDcosθ,y=RDsinθ+yD,0,θ∈π−θhigh,π−θ3,∪θ3,θhigh∪x,y|h2x,y=vAt¯A,x∈−p2,−RDcosθhigh∪RDcosθhigh,p2∪x,y|y=RA,x∈−∞,−p2∪p2,+∞,where θ3=arctanyIR−yD,0/xIR is the polar angle of the intersection points of ℬT and the circle of detection in the polar coordinate system defined in Theorem 5, the variable θhigh satisfies that(66)RDθhigh+yD,0=vAt¯Aθhigh⩾0.The corresponding barrier is depicted in Figure10. The local enlarged figure of Figure 10 is illustrated in Figure 11. The part of the barrier outside the circle of detection on the left consists of two parts.Figure 10
The barrier of the game withyD,0<RA and RD∈1−α,1−α2/αyD,0.Figure 11
The local enlarged figure of the part of Figure10 surrounded by the black box.


#### 5.2.2. The Reach-Avoid Game with a Time Limit and Detection Range WhenRD>1−α2/αyD,0

Next, we investigate the situation thatRD>1−α2/αyD,0 and xA>0. It should be noticed that if the attacker enters the circle of detection with IP satisfying θP>θ3, it cannot reach T successfully. Hence, the optimal trajectory of A between IF and point RD,θ3 is the bypassing trajectory. According to Theorem 7, the optimal trajectory of the attacker is the penetrating trajectory here. The related barrier is complicated and needs to be discussed in different conditions.First, we consider the situation that the variablesθ1, θ2, and θ3 satisfy θ3⩾θ2. Here, if the variable θF meets the condition θF⩾minθ1,θ3, the optimal trajectory of A after arriving at IF is moving clockwise from point RD,θF to IP=RD,minθ1,θ3 and then moving along the segment IPPl. If an attacker is initially located on the barrier and its optimal trajectory is the penetrating trajectory in this situation, its initial position should satisfy that(67)h3x,y=lFx,y+RDθF−minθ1,θ3+lminθ1,θ3,θF>minθ1,θ3,lFx,y+lθF,θF∈θ2,minθ1,θ3,lFx,y+RDsinθF+yD,0,θF∈0,θ2.The functionlθ is defined as equation (38), and the function lFx,y is defined as equation (64). The optimal trajectory of each condition in expression (67) is illustrated in Figure 12.Figure 12
The optimal trajectories under different conditions whenRD>1−α2/αyD,0. (a) The optimal trajectories when the attacker’s position meets the first or third condition in equation (67). (b) The optimal trajectories when the attacker’s position meets the second condition in equation (67).
(a)(b)The related barrier in this situation can be acquired by comparing the length of the optimal trajectories shown above and the time limitt¯A and is given by the following expression:(68)ℬ=x,y|x,y∈ℬT,x∈−xIR,xIR∪x,y|x=RDcosθ,y=RDsinθ+yD,0,θ∈π−θhigh,π−θ3,∪θ3,θhigh,∪x,y|h3x,y=vAt¯A,x∈−RDcosθ2,−RDcosθhigh∪RDcosθhigh,RDcosθ2,∪x,y|y=RA,x∈−∞,−RDcosθ2∪RDcosθ2,+∞.Moreover, the related barrier is depicted in Figures13 and 14. It can be found that the part of the barrier outside the circle of detection shown in Figure 14 consists of three parts.Figure 13
The barrier whenminθ1,θ3⩾θ2.Figure 14
The local enlarged figure of the part of Figure13 surrounded by the black box.Then, we consider the situation that the variablesθ1, θ2, and θ3 satisfy θ2⩾θ3. In this situation, the attacker needs to move along the boundary of the circle of detection from IF to the point RD,θ3 and then enters the circle of detection. However, we notice that the point RD,θ3 is located on the barrier ℬT, and the time that costs the attacker to reach T from the point RD,θ3 is t¯A, which means A cannot move from IF to RD,θ3 and then reach T within its time limit. Thus, in this situation, the barrier of the game satisfies ℬ=ℬT, which is illustrated in Figure 2.Now, the complete barrier of the original game with a time limit and detection range in all possible situations is provided. The situations and the related barrier are presented in Table2.Table 2
The barrier of the reach-avoid game with a time limit and detection range.
ConditionBarrieryD,0∈RA/α,+∞Equation (16)yD,0∈RA,RA/αRD∈0,1−αyD,0Equation (61) and Figure 8RD∈1−αyD,0,1+α2/α2RA2−2RAyD,0Equation (62) and Figure 9RD∈1+α2/α2RA2−2RAyD,0,+∞Equation (15) and Figure 2yD,0∈0,RARD∈0,1−αyD,0Equation (61) and Figure 8RD∈1−αyD,0,1−α2/αyD,0Equation (65) and Figure 10RD∈1−α2/αyD,0,1+α2/α2RA2−2RAyD,0θ3⩾θ2: Equation (67) and Figure 13θ2⩾θ3: Equation (15) and Figure 2RD∈1+α2/α2RA2−2RAyD,0,+∞Equation (15) and Figure 2


## 5.1. The Reach-Avoid Game with a Time Limit and Detection Range WhenyD,0⩾RA

According to Section4, we can find that the attacker can enter the detection range and reach the target area only when the penetrating point IP satisfies θP>0. This means that the point IP satisfies yP>yD,0. Consider that the area x,y|y⩾RA is always inside the DDR. When yD,0⩾RA, we have yP⩾RA and there is no possible IP that the attacker can enter the detection range from it and reach the line T. Hence, the attacker can only move along the bypassing trajectory under this condition.Additionally, we need to investigate the position relation between the circle of detection and the barrierℬT with a time limit only to judge whether the part of the barrier with expression (17) exists. Assume that the circle of detection has intersection points with barriersℬT. The intersection points must meet the condition that(55)x2+y−yD,02=RD2,x2+1−1α2y2+1−α2yD,02=0.Simplifying equation (55), we have as follows:(56)y2α2−2yD,0y+α2yD,02=RD2,yα−αyD,02=RD2.Notice that the coordinates of the points onℬT meets the condition that y>0, the solution of equation (56) is as follows:(57)y=α2yD,0+αRD.Substituting equation (57) into the first equation in (56), and we have(58)x2+α2−1yD,0+α−1RDα2−1yD,0+α+1RD=0.SinceyD,0⩾0, α∈0,1, and RD>0, we have α2−1yD,0+α−1RD<0. Consider that x2⩾0, if equation (58) has real roots, it needs to meet the condition that(59)α2−1yD,0+α+1RD>0,which is(60)1−αyD,0<RD.So, the barrier considered in this subsection can be divided into two situations: the one with1−αyD,0⩾RD and the one with 1−αyD,0<RD. Both situations need to be discussed in detail.


### 5.1.1. The Reach-Avoid Game with a Time Limit and Detection Range When1−αyD,0⩾RD

Let us first investigate the former situation. In this situation, there exist at most one intersection point betweenℬT and the circle of detection, which means the part of barrier with expression (17) does not exist. Considering that the optimal trajectories of the attacker must be the bypassing trajectory, the complete barrier in this situation is as follows:(61)ℬ=x,y|y=yD,0−RD2−x2,x∈−m,m∪x,y|y=yA,x∈−∞,−m∪−m,+∞,where m=RD2−RA−yD,02. The related barrier is depicted in Figure 8. Comparing the barrier ℬ with the barrier ℬT which contains only the time limit of A, we can find that the existence of the detection range expands the area of ADR, which means it benefits the attacker. It is obvious that if yD,0⩾RA, the expression of the barrier is y=RA. The defender cannot influence the barrier under this condition.Figure 8
The barrier of the game withyD,0⩾RA and 1−αyD,0⩾RD.


### 5.1.2. The Reach-Avoid Game with a Time Limit and Detection Range When1−αyD,0<RD

Next, we investigate the situation when1−αyD,0<RD. In this situation, the circle of detection has two intersection points with ℬT, which are denoted as IR=xIR,yIR and IL=−xIR,yIR. When yIL<RA, according to Theorem 2, the complete barrier is as follows:(62)ℬ=x,y|x,y∈ℬT,x∈−xIR,xIR∪x,y|y=yD,0−RD2−x2,x∈−m,−xIR∪xIR,m∪x,y|y=RA,x∈−∞,−m∪m,+∞.The related barrier is depicted in Figure9.Figure 9
The barrier of the game withyD,0⩾RA and 1−αyD,0<RD.


## 5.1.1. The Reach-Avoid Game with a Time Limit and Detection Range When1−αyD,0⩾RD

Let us first investigate the former situation. In this situation, there exist at most one intersection point betweenℬT and the circle of detection, which means the part of barrier with expression (17) does not exist. Considering that the optimal trajectories of the attacker must be the bypassing trajectory, the complete barrier in this situation is as follows:(61)ℬ=x,y|y=yD,0−RD2−x2,x∈−m,m∪x,y|y=yA,x∈−∞,−m∪−m,+∞,where m=RD2−RA−yD,02. The related barrier is depicted in Figure 8. Comparing the barrier ℬ with the barrier ℬT which contains only the time limit of A, we can find that the existence of the detection range expands the area of ADR, which means it benefits the attacker. It is obvious that if yD,0⩾RA, the expression of the barrier is y=RA. The defender cannot influence the barrier under this condition.Figure 8
The barrier of the game withyD,0⩾RA and 1−αyD,0⩾RD.


## 5.1.2. The Reach-Avoid Game with a Time Limit and Detection Range When1−αyD,0<RD

Next, we investigate the situation when1−αyD,0<RD. In this situation, the circle of detection has two intersection points with ℬT, which are denoted as IR=xIR,yIR and IL=−xIR,yIR. When yIL<RA, according to Theorem 2, the complete barrier is as follows:(62)ℬ=x,y|x,y∈ℬT,x∈−xIR,xIR∪x,y|y=yD,0−RD2−x2,x∈−m,−xIR∪xIR,m∪x,y|y=RA,x∈−∞,−m∪m,+∞.The related barrier is depicted in Figure9.Figure 9
The barrier of the game withyD,0⩾RA and 1−αyD,0<RD.


## 5.2. The Reach-Avoid Game with a Time Limit and Detection Range WhenyD,0<RA

According to Subsection5.1, when RD⩽1−αyD,0, the expression of the barrier is equation (61). Hence, we consider only the situations with 1−αyD,0>RD here. Moreover, this situation can be further divided into two situations and we will analyze them individually.


### 5.2.1. The Reach-Avoid Game with a Time Limit and Detection Range WhenRD∈1−α,1−α2/αyD,0

Consider that1−α<1−α<1−α/α, we first investigate the situation that RD∈1−α,1−α2/αyD,0. According to Section 4, the optimal trajectory of the attacker here is the bypassing trajectory. If an attacker is initially located on the barrier and its optimal trajectory is the bypassing trajectory, its initial position should satisfy that(63)h2x,y=lFx,y+RDθF+yD,0=vAt¯A,where(64)lFx,y=x−RDcosθF2+y−RDsinθF+yD,02.The first part of the equation represents the length of the segment connecting the initial position and the related first touching pointIF. The second part is the length of the arc connecting IF and point RD,yD,0. Also, the third part is the length of moving vertically downward toward T. When A is initially located on the barrier, the total length of the three parts should be RA. According to the definition of bypassing trajectory, the segment AIF is a segmental tangent line of the circle of detection, and the point IF is the related tangent point. Hence, the corresponding barrier should be as follows:(65)ℬ=x,y|x,y∈ℬT,x∈−xIR,xIR∪x,y|x=RDcosθ,y=RDsinθ+yD,0,θ∈π−θhigh,π−θ3,∪θ3,θhigh∪x,y|h2x,y=vAt¯A,x∈−p2,−RDcosθhigh∪RDcosθhigh,p2∪x,y|y=RA,x∈−∞,−p2∪p2,+∞,where θ3=arctanyIR−yD,0/xIR is the polar angle of the intersection points of ℬT and the circle of detection in the polar coordinate system defined in Theorem 5, the variable θhigh satisfies that(66)RDθhigh+yD,0=vAt¯Aθhigh⩾0.The corresponding barrier is depicted in Figure10. The local enlarged figure of Figure 10 is illustrated in Figure 11. The part of the barrier outside the circle of detection on the left consists of two parts.Figure 10
The barrier of the game withyD,0<RA and RD∈1−α,1−α2/αyD,0.Figure 11
The local enlarged figure of the part of Figure10 surrounded by the black box.


### 5.2.2. The Reach-Avoid Game with a Time Limit and Detection Range WhenRD>1−α2/αyD,0

Next, we investigate the situation thatRD>1−α2/αyD,0 and xA>0. It should be noticed that if the attacker enters the circle of detection with IP satisfying θP>θ3, it cannot reach T successfully. Hence, the optimal trajectory of A between IF and point RD,θ3 is the bypassing trajectory. According to Theorem 7, the optimal trajectory of the attacker is the penetrating trajectory here. The related barrier is complicated and needs to be discussed in different conditions.First, we consider the situation that the variablesθ1, θ2, and θ3 satisfy θ3⩾θ2. Here, if the variable θF meets the condition θF⩾minθ1,θ3, the optimal trajectory of A after arriving at IF is moving clockwise from point RD,θF to IP=RD,minθ1,θ3 and then moving along the segment IPPl. If an attacker is initially located on the barrier and its optimal trajectory is the penetrating trajectory in this situation, its initial position should satisfy that(67)h3x,y=lFx,y+RDθF−minθ1,θ3+lminθ1,θ3,θF>minθ1,θ3,lFx,y+lθF,θF∈θ2,minθ1,θ3,lFx,y+RDsinθF+yD,0,θF∈0,θ2.The functionlθ is defined as equation (38), and the function lFx,y is defined as equation (64). The optimal trajectory of each condition in expression (67) is illustrated in Figure 12.Figure 12
The optimal trajectories under different conditions whenRD>1−α2/αyD,0. (a) The optimal trajectories when the attacker’s position meets the first or third condition in equation (67). (b) The optimal trajectories when the attacker’s position meets the second condition in equation (67).
(a)(b)The related barrier in this situation can be acquired by comparing the length of the optimal trajectories shown above and the time limitt¯A and is given by the following expression:(68)ℬ=x,y|x,y∈ℬT,x∈−xIR,xIR∪x,y|x=RDcosθ,y=RDsinθ+yD,0,θ∈π−θhigh,π−θ3,∪θ3,θhigh,∪x,y|h3x,y=vAt¯A,x∈−RDcosθ2,−RDcosθhigh∪RDcosθhigh,RDcosθ2,∪x,y|y=RA,x∈−∞,−RDcosθ2∪RDcosθ2,+∞.Moreover, the related barrier is depicted in Figures13 and 14. It can be found that the part of the barrier outside the circle of detection shown in Figure 14 consists of three parts.Figure 13
The barrier whenminθ1,θ3⩾θ2.Figure 14
The local enlarged figure of the part of Figure13 surrounded by the black box.Then, we consider the situation that the variablesθ1, θ2, and θ3 satisfy θ2⩾θ3. In this situation, the attacker needs to move along the boundary of the circle of detection from IF to the point RD,θ3 and then enters the circle of detection. However, we notice that the point RD,θ3 is located on the barrier ℬT, and the time that costs the attacker to reach T from the point RD,θ3 is t¯A, which means A cannot move from IF to RD,θ3 and then reach T within its time limit. Thus, in this situation, the barrier of the game satisfies ℬ=ℬT, which is illustrated in Figure 2.Now, the complete barrier of the original game with a time limit and detection range in all possible situations is provided. The situations and the related barrier are presented in Table2.Table 2
The barrier of the reach-avoid game with a time limit and detection range.
ConditionBarrieryD,0∈RA/α,+∞Equation (16)yD,0∈RA,RA/αRD∈0,1−αyD,0Equation (61) and Figure 8RD∈1−αyD,0,1+α2/α2RA2−2RAyD,0Equation (62) and Figure 9RD∈1+α2/α2RA2−2RAyD,0,+∞Equation (15) and Figure 2yD,0∈0,RARD∈0,1−αyD,0Equation (61) and Figure 8RD∈1−αyD,0,1−α2/αyD,0Equation (65) and Figure 10RD∈1−α2/αyD,0,1+α2/α2RA2−2RAyD,0θ3⩾θ2: Equation (67) and Figure 13θ2⩾θ3: Equation (15) and Figure 2RD∈1+α2/α2RA2−2RAyD,0,+∞Equation (15) and Figure 2


## 5.2.1. The Reach-Avoid Game with a Time Limit and Detection Range WhenRD∈1−α,1−α2/αyD,0

Consider that1−α<1−α<1−α/α, we first investigate the situation that RD∈1−α,1−α2/αyD,0. According to Section 4, the optimal trajectory of the attacker here is the bypassing trajectory. If an attacker is initially located on the barrier and its optimal trajectory is the bypassing trajectory, its initial position should satisfy that(63)h2x,y=lFx,y+RDθF+yD,0=vAt¯A,where(64)lFx,y=x−RDcosθF2+y−RDsinθF+yD,02.The first part of the equation represents the length of the segment connecting the initial position and the related first touching pointIF. The second part is the length of the arc connecting IF and point RD,yD,0. Also, the third part is the length of moving vertically downward toward T. When A is initially located on the barrier, the total length of the three parts should be RA. According to the definition of bypassing trajectory, the segment AIF is a segmental tangent line of the circle of detection, and the point IF is the related tangent point. Hence, the corresponding barrier should be as follows:(65)ℬ=x,y|x,y∈ℬT,x∈−xIR,xIR∪x,y|x=RDcosθ,y=RDsinθ+yD,0,θ∈π−θhigh,π−θ3,∪θ3,θhigh∪x,y|h2x,y=vAt¯A,x∈−p2,−RDcosθhigh∪RDcosθhigh,p2∪x,y|y=RA,x∈−∞,−p2∪p2,+∞,where θ3=arctanyIR−yD,0/xIR is the polar angle of the intersection points of ℬT and the circle of detection in the polar coordinate system defined in Theorem 5, the variable θhigh satisfies that(66)RDθhigh+yD,0=vAt¯Aθhigh⩾0.The corresponding barrier is depicted in Figure10. The local enlarged figure of Figure 10 is illustrated in Figure 11. The part of the barrier outside the circle of detection on the left consists of two parts.Figure 10
The barrier of the game withyD,0<RA and RD∈1−α,1−α2/αyD,0.Figure 11
The local enlarged figure of the part of Figure10 surrounded by the black box.


## 5.2.2. The Reach-Avoid Game with a Time Limit and Detection Range WhenRD>1−α2/αyD,0

Next, we investigate the situation thatRD>1−α2/αyD,0 and xA>0. It should be noticed that if the attacker enters the circle of detection with IP satisfying θP>θ3, it cannot reach T successfully. Hence, the optimal trajectory of A between IF and point RD,θ3 is the bypassing trajectory. According to Theorem 7, the optimal trajectory of the attacker is the penetrating trajectory here. The related barrier is complicated and needs to be discussed in different conditions.First, we consider the situation that the variablesθ1, θ2, and θ3 satisfy θ3⩾θ2. Here, if the variable θF meets the condition θF⩾minθ1,θ3, the optimal trajectory of A after arriving at IF is moving clockwise from point RD,θF to IP=RD,minθ1,θ3 and then moving along the segment IPPl. If an attacker is initially located on the barrier and its optimal trajectory is the penetrating trajectory in this situation, its initial position should satisfy that(67)h3x,y=lFx,y+RDθF−minθ1,θ3+lminθ1,θ3,θF>minθ1,θ3,lFx,y+lθF,θF∈θ2,minθ1,θ3,lFx,y+RDsinθF+yD,0,θF∈0,θ2.The functionlθ is defined as equation (38), and the function lFx,y is defined as equation (64). The optimal trajectory of each condition in expression (67) is illustrated in Figure 12.Figure 12
The optimal trajectories under different conditions whenRD>1−α2/αyD,0. (a) The optimal trajectories when the attacker’s position meets the first or third condition in equation (67). (b) The optimal trajectories when the attacker’s position meets the second condition in equation (67).
(a)(b)The related barrier in this situation can be acquired by comparing the length of the optimal trajectories shown above and the time limitt¯A and is given by the following expression:(68)ℬ=x,y|x,y∈ℬT,x∈−xIR,xIR∪x,y|x=RDcosθ,y=RDsinθ+yD,0,θ∈π−θhigh,π−θ3,∪θ3,θhigh,∪x,y|h3x,y=vAt¯A,x∈−RDcosθ2,−RDcosθhigh∪RDcosθhigh,RDcosθ2,∪x,y|y=RA,x∈−∞,−RDcosθ2∪RDcosθ2,+∞.Moreover, the related barrier is depicted in Figures13 and 14. It can be found that the part of the barrier outside the circle of detection shown in Figure 14 consists of three parts.Figure 13
The barrier whenminθ1,θ3⩾θ2.Figure 14
The local enlarged figure of the part of Figure13 surrounded by the black box.Then, we consider the situation that the variablesθ1, θ2, and θ3 satisfy θ2⩾θ3. In this situation, the attacker needs to move along the boundary of the circle of detection from IF to the point RD,θ3 and then enters the circle of detection. However, we notice that the point RD,θ3 is located on the barrier ℬT, and the time that costs the attacker to reach T from the point RD,θ3 is t¯A, which means A cannot move from IF to RD,θ3 and then reach T within its time limit. Thus, in this situation, the barrier of the game satisfies ℬ=ℬT, which is illustrated in Figure 2.Now, the complete barrier of the original game with a time limit and detection range in all possible situations is provided. The situations and the related barrier are presented in Table2.Table 2
The barrier of the reach-avoid game with a time limit and detection range.
ConditionBarrieryD,0∈RA/α,+∞Equation (16)yD,0∈RA,RA/αRD∈0,1−αyD,0Equation (61) and Figure 8RD∈1−αyD,0,1+α2/α2RA2−2RAyD,0Equation (62) and Figure 9RD∈1+α2/α2RA2−2RAyD,0,+∞Equation (15) and Figure 2yD,0∈0,RARD∈0,1−αyD,0Equation (61) and Figure 8RD∈1−αyD,0,1−α2/αyD,0Equation (65) and Figure 10RD∈1−α2/αyD,0,1+α2/α2RA2−2RAyD,0θ3⩾θ2: Equation (67) and Figure 13θ2⩾θ3: Equation (15) and Figure 2RD∈1+α2/α2RA2−2RAyD,0,+∞Equation (15) and Figure 2


## 6. Numerical Simulation

In this section, we give several numerical simulations to prove the correctness of the barrier obtained in this work. As stated in Lemma4, if the attacker is initially located in Area1, it needs to move vertically downward. In this situation, if yA0<RA, it wins the game, and vice versa. The result is simple and the simulations related to this situation are omitted.Case 1.
The initial positions of the defender and the attacker arexD=0,5, xA,1=1,2.3, which is inside ADR, and xA,2=−1.5,2.8, which is inside DDR. The speeds of the players are vA=1 and vD=2, respectively. The maximum operating time of A is 3 and the maximum detection range of D is 3. Thus, the barrier of the game in this situation satisfies equation (62). The Apollonian circle related to A1 intersects the target line while that of A2 does not. Consequently, the attacker A1 can ensure its winning by moving straight toward any point on the part of T within the Apollonian circle, and the attacker A2 is intercepted. The results of the games are shown in Figure 15.Figure 15
The numerical simulation of the barrier related to equation (62).Case 2.
The initial positions of the defender and the attacker arexD=0,2.5 and xA=4.3,3.8, which is inside ADR, respectively. The maximum operating time of A is 4 and the maximum detection range of D is 4.5. The speed of the attacker is vA=1 and the speed ratio is α=0.5. In this situation, the expression of the related barrier is (66). As is shown in Figure 16, the attacker moves along the bypassing trajectory and wins the game. The length of the trajectory is 3.9179, which is less than vAt¯A=4. In this situation, the attacker remains undetected during the game process. Hence, the defender cannot adopt any strategy against the attacker.Figure 16
The numerical simulation of the barrier related to equation (65).Case 3.
The initial positions of the defender and the attacker arexD=0,1 and xA=4.2,3.8, which is inside ADR, respectively. The maximum operating time of A is 4 and the maximum detection range of D is 5. The speed of the attacker is vA=1 and the speed ratio is α=0.6. In this situation, the expression of the related barrier is (68). Thus, the attacker should move along a bypassing-penetrating trajectory to win the game, the penetrating point IP is RD,θ1 defined in equation (31). The result of the game is shown in Figure 17. The attacker can choose some point on the target line inside the Apollonian circle related to the point RD,θ1 to move toward and win the game. The total length of the trajectory is 3.9240, which is less than vAt¯A=4.
If the attacker enters the detection range before reachingRD,θ1, it may lose the game. This situation is shown in Figure 18. Although the attacker moves toward Pl to save time, it cannot reach the target line before reaching its time limit.Figure 17
The numerical simulation of the barrier related to equation (68).Figure 18
The situation when the attacker loses the game.Case 4.
The initial positions of the defender and the attacker arexD=0,1 and xA=4.05,3.95, which is inside DDR. The rest part of the game configurations is the same as that in Case 3. As is shown in Figure 19, in this situation, if A moves along the bypassing trajectory, it must terminate inside ΩP and lose the game. If A moves along the bypassing-penetrating trajectory, it needs to acquire the shortest path by entering the circle of detection from the point RD,θ1. However, as is illustrated, the shortest path is still longer than the maximum range A, which means the defender can ensure its winning here.
The numerical simulations given above prove the correctness of the barrier constructed in this work. With the complete barrier obtained, the agent participating in the game can judge whether it can win the game or not via the initial configuration of the game easily and adopt proper strategies against its opponent. If the attacker is located in ADR, it can guarantee its victory by moving along the optimal trajectory obtained in Section4. Moreover, if it is located in DDR, it can either choose to abort its mission or sacrifice itself against the defender to help its teammate, if exists, win the game.Figure 19
The numerical simulation of the barrier related to equation (68) when A is inside DDR.


## 7. Conclusion

In this article, we investigate the solutions to the reach-avoid game with a time limit and detection range on an unbounded planar domain. This is the first attempt to add both the maximum operating time of the player and the detection range constraint into the classic reach-avoid game at the same time. The main achievements are listed as follows:(1)
We prove that the attacker cannot leave the detection range of the defender once it is detected, and we obtain the expressions of the barrier when the attacker is initially located inside the detection range.(2)
We investigate the possible equilibrium terminal states of the game and prove that if the attacker is located on the part of the barrier outside the detection range, it must reach the target line at its time limit when it moves along its shortest possible path toward the target line. This is a common conclusion in the reach-avoid game with a time limit and detection range and it shrinks the possible set of the game’s terminal states and reduces the difficulty of solving the problem.(3)
Using the properties of the circle and the form of the players’ optimal strategies obtained via HJI differential equations, we acquire the optimal strategies and the related optimal trajectories of the attacker participating in the reach-avoid game with a time limit and detection range according to its initial location in all possible situations. Moreover, these trajectories are still valid when the defender is equipped with an infrared seeker or vision sensor of which the detection range is usually a sector.(4)
By comparing the length of the attacker’s optimal trajectory and its time limit, we obtain the expressions of the barrier with a time limit and detection range in all possible situations for the first time. Moreover, all the possible barriers are illustrated.To our best knowledge, it is the first time that someone brings the time limit and the detection range to the classic reach-avoid game simultaneously. The introduction of these concepts makes the game more complex and more practical than most of the previous works in this research direction. Based on the expressions of the barrier obtained in this article, the results of the game can be obtained immediately when the initial configurations are given. So, the barrier obtained in this article can be utilized to evaluate the battlefield situation which has critical real-time requirements. In future, more practical and complex dynamic models, rather than simple motion, will be considered. Also, the game with a complex environment such as consisting of obstacles will also be one of our focuses.



---

*Source: 9954014-2022-10-26.xml*