Locating a Central Hunter on the Plane

Locating a Central Hunter on the Plane M. Cera · J.A. Mesa · F.A. Ortega · F. Plastria Abstract Protection, surveillance or other types of coverage services of mobile points call for different, asymmetric distance measures than the traditional Euclidean, rectangular or other norms used for fixed points. In this paper, the destinations are mobile points (prey) moving at fixed speeds and directions and the facility (hunter) can capture them using one of two possible strategies: either it is smart, predicting the prey’s movement in order to minimize the time needed to capture it, or it is dumb, following a pursuit curve, by moving at any moment in the direction of the prey. In either case, the hunter location in a plane is sought in order to minimize the maximum time of capture of any prey. An efficient solution algorithm is developed that uses the particular geometry that both versions of this problem possess. In the case of unpre-dictable movement of prey, a worst-case type solution is proposed, which reduces to the well-known weighted Euclidean minimax location problem. The work of the second and third authors was supported in part by a grant from Research Projects BFM2003-04062 and MTM2006-15054. M. Cera () Department of Applied Mathematics I, Agricultural Technical Engineering University School, University of Seville, Seville, Spain e-mail: [email protected] J.A. Mesa Department of Applied Mathematics II, Engineering Higher Technical School, University of Seville, Seville, Spain F.A. Ortega Department of Applied Mathematics I. Architecture Higher Technical University School, University of Seville, Seville, Spain F. Plastria Department of Mathematics, Operational Research, Statistics and Information Systems for Management, Vrije Universiteit, Brussel, Belgium Keywords Continuous location ·Travel time ·Center problem ·Hunter distance · Skewed norm ·Elliptic gauge ·Game theory 1 Introduction The planar center objective, in terms of distance, travel time or global transport cost, is commonly used for location decisions in emergency service systems, in distribution problems or in telecommunications. Typically the points to be protected, serviced or covered in some other way have a fixed and known position, and the distance measure used is derived from some norm, e.g. the Euclidean, rectangular, or another norm, according to the particular circumstances of the problem instance [1]. However, mobility of destination points is also relevant in many contexts. Protecting mobile objects, however, is a different matter from protecting fixed points, since attention should be paid to the strategy used by the pursuing facility (hunter) for the capture of the mobile destinations (prey). Two phases are commonly considered in order to plan strategies for capturing the set of evaders: Phase 1 Determine an initial intelligent location to start the potential capture of any prey. Phase 2 Establish tactical decisions for the hunter once different roles have been assigned to the prey, such as being the first prey to be captured among all the existing options. This paper explores the first phase: it deals with the fixed strategic starting location for the pursuing facility in order to be efficiently available for serving mobile destinations after their capture. When the trajectory of an object is fully predictable it is possible to determine in advance the way in which it may be reached in the shortest possible time. This strategy calls, however, for analytical capacities and data processing, which is why we refer to it as a smart hunter, since its behavior cannot be achieved by an automated or non-rational facility. For such a dumb hunter, another less efficient strategy should be applied: simply keep the target in view at all times during the pursuit and always move head-on in that direction. This is the natural strategy followed by predators and also the simplest to program into an automated system with visual feedback. This movement strategy was already analytically studied by Leonardo da Vinci. For nice prey, always following a straight trajectory at constant velocity, George Boole erroneously derived that it results in a parabolic path of the hunter. Although elementary particular cases have been dealt with before, the general case of analytically describing the pursuit trajectories in 2D and 3D by means of differential equations was obtained only recently by Barton and Eliezer [2,3]. In a further analysis of the dynamics involved, Cera and Ortega [4] derived a simple explicit expression called the hunter distance of the time needed to capture a nice prey under this strategy. In this paper, we study center problems in such dynamic circumstances, considering both the dumb hunter and the smart hunter cases. We show that the ideas based on the classical algorithms for solving the planar Euclidean center problem may be adapted to all the studied cases. In some of these, we may use the classical method directly after a suitable transformation. Then, we also study what to do in case prey is nasty and moves in unpredictable ways (but with known maximum speed). In Sect. 4, we show that the worst-case strategy of minimising the maximum possible capturetime of any prey in any of its movements, may always be reduced to a weighted Euclidean center problem. 2 Hunter Distances 2.1 Dumb Hunter Distance Let X(hunter) be mobile with velocity β, which is pursuing mobile A(prey) moving along a vertical line at velocity α<β. It is assumed that during the pursuit the dumb hunter moves at every moment in the direction of the prey’s current position (pursuit curves, see [3]). In [4], the time τrequired for the capture was shown to be the following linear combination of the Euclidean · and ‘vertical’ distances between the starting points at time t=0 of hunter (X=(x0,y0)) and prey (A=(xA,yA)): τ(A,X)=β β2−α2A−X+ α β2−α2(yA−y0). (1) The general case, for a hunter starting from Xat speed β, and the prey’s unit-time movement given by a general vector pwith p<β, is obtained by a simple rotation of the axes, and using λ2=β2−p2 yields the following expression: τ(A,X)=β λ2A−X− 1 λ2p,A −X.(2) This expression shows that the dumb hunter distance τbelongs to the family of skewed norms introduced by Plastria [5]. In general, for any norm N(·)on Rnwith dual N◦(·)and any vector s∈Rnwith N◦(s) < 1, the skewed norm f(N,s) is defined by f(N,s) (X) =N(X)−s,X, where ·,·denotes scalar product. Here, N(X)=β λ2Xand s=α λ2p. The isochronic curve for time τ(set of all prey’s starting points captured at time τ) will therefore be the (unique) ellipse with the following properties (see Fig. 1a): Xis a focal point, the center of symmetry is at point X−τp and it has long axis parallel to pwith half-length βτ, and short axis half-length λτ. Inversely, for a prey starting from A, all hunter starting positions capturing it at time τis obtained as follows: first construct the ellipse centered at A, with long axis of half-length βτ and parallel to p, and short axis half-length λτ ; secondly, shift it over vector τp (see Fig. 1b). (a) Capture by hunter Xof any prey (b) Capture of prey A any hunter within the ellipse within this ellipse Fig. 1 Dumb hunter isochronic ellipses (τ=1.5) 2.2 Smart Hunter Distance A smart hunter starting from Xand able to move at speed βwill be able to reach at time t, all points of the Euclidean circle C(X,βt) centered at Xand radius βt.For a prey to be caught by the smart hunter at time t, it should reach this same circle exactly at time t. To this end, for a prey starting from Aand moving linearly with unit-movement vector p, we should have A+tp ∈C(X,βt), which is either expressed as A−X+tp=βt or as A∈t(C(X,β)−p). (3) The first equation yields λ2t2−2A−X, pt−A−X2=0, where as before λ2=β2−p2. In the coordinate system with origin Xrotated so that the prey moves downward at speed α,i.e.p=(0,−α), and denoting the coordinates of Ain this system by (xA,yA), the previous equation reduces to λ2t2+2αyAt−(x2 A+y2 A)=0, whose only nonnegative solution is t=(λxA)2+(βyA)2−αyA λ2=T(A)+q,A, with Tthe linear operator of matrix T=1 λ2λ0 0β and q=1 λ2p. This shows that the smart hunter distance is also a gauge from the skewed norm family. A general expression valid in any coordinate system is given by t(A,X)=TR(A−X)+ 1 λ2p,A −X,(4) where Tand λare as above, and Rdenotes the rotation bringing pto a downward vertical position. Moreover, (3) shows that the unit ball of this skewed norm is a circle of radius βwith center displaced over −p. 2.3 Comparison of Hunter Distances As shown in Fig. 2the smart hunter distance unit-ball is the smallest circle containing the unit-ellipse for the dumb hunter distance with the same hunter speed and prey movement. This illustrates (and follows from) the following quite evident facts: •Dumb hunter distance is always larger than smart hunter distance: any prey captured within time τby a dumb hunter is caught by a smart hunter in time t≤τ. •Any prey starting at Euclidean distance dfrom the hunter’s starting position, and moving directly towards this point, will be captured in time d/(β +α) by both a dumb hunter and a smart hunter because both strategies coincide in this particular case and use the same linear hunter trajectory. •Similarly, any prey starting at Euclidean distance dfrom the hunter’s starting position, and moving directly away from this point, will be captured in time d/(β −α) by both a dumb hunter and a smart hunter. Fig. 2 Unit balls for the dumb and the smart hunter •For any prey starting at Euclidean distance dfrom the hunter’s starting position, we have d β+α≤t≤τ≤d β−α. •t=τ, i.e. smart and dumb hunter distances are equal, if and only if α=0orprey moves in the hunter’s direction, or opposite to it. 3 Central Hunter Problem with Nice Prey 3.1 General Case Let A={A1,A2,...,An} be a finite set of points (n>1) on the plane representing the initial positions of prey, each moving linearly as given by the unit-movement vectors pi(i=1,...,n). A single hunter is considered able to move at constant speed β>pifor all i.Itis required to determine a starting position for the hunter, minimising the time needed to capture any of these prey. Denoting the starting position of the hunter by X, the optimal location of a central hunter is obtained by solving the following minimax optimization problem: (PA)min X∈R2F(X):=max ifi(X), where fi(X) is the time of capture of prey Aiby a hunter starting from X. In case of a dumb hunter, fi(X) is calculated as τ(Ai,X)givenby(2) with p=pi, while for a smart hunter, the expression t(Ai,X)in (4), suitably adapted, should be used. As a direct consequence of the results of Pelegrín, Michelot and Plastria [6] and Drezner [7], we obtain the following proposition. Proposition 3.1 The functions fi(X) are continuous,differentiable anywhere except at Ai,convex and have strictly convex and bounded level sets,which are all ellipses, so are strongly quasiconvex.Problem (PA)has a unique optimal solution and there exists a subset A⊂Aeither having 2or 3elements,so that the optimal solution X∗ of problem (PA)is also the optimal solution of problem (PA). Although in principle solvable by any general purpose non-differentiable convex optimisation method, by Proposition 3.1, the general problem may also be solved by considering all subproblems limited to only 2 or 3 prey separately. We consider each case in turn. For two prey with A1=A2, the optimal solution of (PA) is evidently reached at X=A1=A2. In case A1=A2, we have the following proposition. Proposition 3.2 Let A={A1,A2}with A1=A2,then the unique optimal solution to problem (PA)consists of the solution to the equation system in two variables f1(X) =f2(X), (5) ∇f1(X) =−∇f2(X). (6) Proof Consider any point Xwith f1(X) > f2(X). Since f1(·)is continuous, by moving Xcloser to A1,f1strictly decreases, and thus also F, showing that Xcannot be optimal. Similarly any Xwith f1(X) < f2(X) cannot be optimal. Therefore (5) holds for any optimal X∗. Since A1=A2, we cannot have f1(X∗)=f2(X∗)=0. Hence at any point Xwhere f1(X) =f2(X) both functions are differentiable. Equation (6) then expresses the standard optimality condition for F(X)=max(f1(X),f2(X)).  The (by Proposition 3.1 unique) solution to the system (5,6) will be denoted by X(A1,A2)and the corresponding function value obtained in (5)byF(A1,A2).This case is illustrated in Fig. 3. The following two propositions are now evident, describing the case of a threeprey subset either reducible to a two-prey subset or not. Proposition 3.3 For a three-prey set A={A1,A2,A3}the optimal solution to (PA) is determined by its subset {A1,A2}if and only if we have f3(X(A1,A2)) ≤ F(A 1,A2). Proposition 3.4 Let A={A1,A2,A3}be such that no strict subset of Ayields an optimal value to (PA), then the unique optimal solution to this problem (PA)consists of the solution of the system of two equations in two variables given by f1(X) =f2(X) =f3(X), (7) which yields the lowest value for it. In this last case the optimal solution will be denoted by X(A1,A2,A3)and the corresponding function value by F(A1,A2,A3). In the sequel we consider that solving the two or three prey set problems may be done efficiently, e.g. by way of some standard equation solving tools available in mathematical software. Since this may involve relatively intensive calculations, in order to construct the central hunter position efficiently the number of such subproblems to be solved should be reduced as much as possible. This may be obtained using strategies similar to those developed for the Euclidean (weighted and/or unweighted) minmax problem like Elzinga and Hearn [8], Charalambous [9], Hearn and Vijay [10] or Welzl [11]. The algorithm proposed below follows the general ideas of Elzinga and Hearn [8]. Below we give a procedural description following the general lines used in [1]. Note that it explicitly implements the idea of worst point selection at each step as suggested by Elzinga and Hearn [8] and advocated by many later authors: this rule is of particular interest here in order to reduce the number of subproblems to be solved. (a) Dumb hunter (b) Smart hunter Fig. 3 Two-prey optimal solutions Algorithm A1 (General Algorithm) Step 0 Initialize. Pick any two-prey set A={Ai,Aj}and determine X(Ai,Aj)and F(Ai,Aj). Handle the two-prey set A. Step 1 Handle Two-Prey Set. Determine k=i,j maximizing fk(X(Ai,Aj)). Step 1a If fk(X(Ai,Aj)) ≤F(Ai,Aj), then X(Ai,Aj)is the optimal solution to (PA). Stop. Step 1b Otherwise, add Akto Aand proceed to handle this three-prey set (Step 2 below). Step 2 Handle Three-Prey Set. Step 2a Determine X(Ai,Ak)and F(Ai,Ak).Iffj(X(Ai,Ak)) ≤F(Ai,Ak)drop Ajfrom Aand proceed to handle this two-prey set. Otherwise, determine X(Aj,Ak)and F(Aj,Ak).Iffi(X(Aj,Ak)) ≤ F(A j,Ak),dropAifrom Aand proceed to handle this two-prey set. Step 2b Otherwise, determine X(Ai,Aj,Ak)and F(Ai,Aj,Ak)and the m= i,j,k maximizing fm(X(Ai,Aj,Ak)). –Iffm(X(Ai,Aj,Ak)) ≤F(Ai,Aj,Ak), then X(Ai,Aj,Ak)is the optimal solution to (PA). Stop. – Otherwise, determine F(Ai,Ak,Am)and F(Aj,Ak,Am). In case F(Ai,Ak,Am)≤F(Aj,Ak,Am), replace Ajby Amin A, otherwise replace Aiby Amin A. In any case, proceed by handling this new three-prey set. Using Propositions 3.2 and 3.4 it is easy to see that the consecutive calculated function values F(Ai,Ak)and F(Ai,Aj,Ak)strictly increase at each step. So this algorithm cannot cycle and, since there are a finite number of two-prey and three-prey subsets of A, it will stop. By Proposition 3.1 the value and solution obtained at that point is the optimal central hunter position sought. 3.2 Easily Solvable Particular Case: Homogenous Prey When all prey move in exactly the same way, as given by unit-movement vector pi=p, the problem is simplified considerably, because all systems of equations to be solved have analytic solutions. However, it is much easier to use the following geometric arguments. Since all balls for each time of capture are then similar ellipses, the minimax problem is equivalent to covering the set Aof initial positions of prey by means of the enclosing ellipse with minimal area, and then the corresponding hunter position at its focal point must be determined (compare with [12]). Smart Hunter For a smart hunter all the isochrone ellipses are already circles. So we obtain the following algorithm. Algorithm A2 (Homogenous Prey, Smart Hunter) Step 1 Construct the smallest radius circle covering all prey starting positions. Call its radius rand midpoint M. Step 2 The minimax capture time is then given by T=r/β. Step 3 The central hunter’s position then lies at point M+Tp. Dumb Hunter For a dumb hunter all balls will be ellipses with long axis parallel to p, and a same shape, given by a long axis β/λ times longer than its short axis (here λ2=β2−p2, as before). For simplicity, we describe what follows in the coordinate system with second axis opposite to p. Scaling the vertical coordinate down to make the axes of equal length by dividing by this factor β/λ, transforms these ellipses all to circles. Therefore the problem may be reduced to a smallest covering circle problem, yielding the following algorithm. Algorithm A3 (Homogenous Prey, Dumb Hunter) Step 1 Rescale the vertical axis by multiplying all vertical coordinates of all prey points by λ/β. This step produces the new points Bi. Step 2 Find the smallest circle enclosing all Bi. Call its centre QBand its radius rB. Step 3 Scale back the vertical coordinate of point QBby multiplying by β/λ.This yields the symmetry centre QAof the smallest correctly shaped ellipse E containing the original prey points Ai. Step 4 Its short axis half-length equals rBand corresponds to λτ. So the minimax capture time is found as τ=rB/λ. Step 5 The lower focus point X∗of the ellipse Eis then found at distance pτ below QAand corresponds to the optimal location of the central hunter. Figure 4illustrates this simplified procedure. In Fig. 4a seventeen prey with p=(0,−1)are shown. The central hunter has speed β=1.5. Figure 4bshowsthe points after scaling and their smallest covering circle. After scaling back we obtain the smallest covering ellipse in Fig. 4c. Its lower focus gives the central hunter position.