TheChaseProblem(Part1)DavidC.ArneyWebuild systemsliketheWright brothersbuilt airplanes-buildthewhole thing, push it off a cliff, let it crash, and start all over again--R.M.Graham[1970]IntroductionThere are many situations whereone thing,person, animal, ormachine,chasesanother.Someofthe applications ofthiskind ofchasing in the military are:missilesinterceptingplanes(orothermissiles),smartmunitions seekingtargets(i.e.anti-tankroundsseekinga tank),a unit or soldier pursuingand closingwithan enemy unit orsoldier,shipsclosinginonotherships,and torpedoes tracking andexplodingonenemyships.Ofcourse,therearemanynon-militaryapplications of chasingaswellSome of these are dogs runningafter cats,tacklerschasing andtackling ball carriers in football, hunters after their quarry (predators after prey)and children playing tag.All ofthese applications are three-dimensional (theyoccurinourthree-dimensionalworld),butsomearemoreeasily,andpossiblybetter,modeled intwo dimensionsbecause onedimension, likeheight, is notverysignificant.Inthis section,wewillmodel thesekindsof chaseproblems.We'llstartintwodimensions,thenrefineourmodeltohandlethreedimensions.Ourproblemistodeterminethemovementpathforthechaser,givenweknowthelocation of thetarget. We will start with the assumption that the chaserhascomplete vision ofthetarget andknowsthetarget'sposition exactly.Thechaser'spositionwillberepresentedintwo-dimensionalCartesiancoordinatesby (xo(t), yo(t).Let's also start with assumptions that the chaser moves at aconstantspeed(givenbys)andthetarget'spositionintwodimensionsisgivenbytheparametricrelationship (xi(t),yi(t).Onetechniquetouseforthechasemodel is to have the chaser move directly towards the target. This means thatthe chaserreceives information as to the exact location of the target and headsin that direction.As the location ofthetarget changes,the chaseradjusts itspathtocontinuetomovedirectlytowardthetarget109
109 The Chase Problem (Part 1) David C. Arney We build systems like the Wright brothers built airplanes— build the whole thing, push it off a cliff, let it crash, and start all over again. - R. M. Graham [1970] Introduction There are many situations where one thing, person, animal, or machine, chases another. Some of the applications of this kind of chasing in the military are: missiles intercepting planes (or other missiles), smart munitions seeking targets (i.e. anti-tank rounds seeking a tank), a unit or soldier pursuing and closing with an enemy unit or soldier, ships closing in on other ships, and torpedoes tracking and exploding on enemy ships. Of course, there are many non-military applications of chasing as well. Some of these are dogs running after cats, tacklers chasing and tackling ball carriers in football, hunters after their quarry (predators after prey), and children playing tag. All of these applications are three-dimensional (they occur in our three-dimensional world), but some are more easily, and possibly better, modeled in two dimensions because one dimension, like height, is not very significant. In this section, we will model these kinds of chase problems. We’ll start in two dimensions, then refine our model to handle three dimensions. Our problem is to determine the movement path for the chaser, given we know the location of the target. We will start with the assumption that the chaser has complete vision of the target and knows the target’s position exactly. The chaser’s position will be represented in two-dimensional Cartesian coordinates by (x0(t), y0(t)). Let’s also start with assumptions that the chaser moves at a constant speed (given by s) and the target’s position in two dimensions is given by the parametric relationship (x1(t), y1(t)). One technique to use for the chase model is to have the chaser move directly towards the target. This means that the chaser receives information as to the exact location of the target and heads in that direction. As the location of the target changes, the chaser adjusts its path to continue to move directly toward the target
Wecanmodelthisprocedurethroughadiscreteeventmodel oftimeperiods(intervals or timesteps) of length t.We use n to indicate the number of thetime stepinthemodel.Our genericmodeling processfora time changingeventistosetuparelationshipthatexpressesthefuturestateasthepresentstateplusthechangethatoccursduringthetimeinterval.Wewill callthischangeourhypothesisforthechangesinceweusuallydon'tknowbefore-handexactlywhatwill happenduringthetimeinterval.Figure1showsaschematicofthisprocessusingagenericfunctionf(t)asthevariableof interest.FUTUREPRESENT+CHANGE二f(t)+f(t + At)t (hypothesis)f(+A)f)time (0)1+41difference equation:f(n+1) =f(n) + per periodFigure1:ModelingchangeofadiscretetimeeventsimulationThelaststep inthediagramof Figure1,shows adifferenceequation of theform(1)y(n+1) =y(n) + per time periodWe will try toget our model for the movement of the chaser in this form toproduce a simulation of the chase.Let's draw a diagram ofwhat happens duringa time interval t. Figure 2 shows the locations of the chaser and the target atsome timet.Themovement madeby the chaser over that interval is indicatedwiththebold arrow.Thefinal position of the chaseris givenby (xo(t+t),yo(t+ △ t).110
110 We can model this procedure through a discrete event model of time periods (intervals or timesteps) of length D t. We use n to indicate the number of the time step in the model. Our generic modeling process for a time changing event is to set up a relationship that expresses the future state as the present state plus the change that occurs during the time interval. We will call this change our hypothesis for the change since we usually don’t know before-hand exactly what will happen during the time interval. Figure 1 shows a schematic of this process using a generic function f(t) as the variable of interest. FUTURE = PRESENT + CHANGE f (t + Dt) = f (t) + Dt (hypothesis) time (t) · · t f(t) f t + Dt f (t + D t) difference equation: f(n+1) = f(n) + D per period Figure 1: Modeling change of a discrete time event simulation. The last step in the diagram of Figure 1, shows a difference equation of the form y(n+1) = y(n) + D per time period (1) We will try to get our model for the movement of the chaser in this form to produce a simulation of the chase. Let’s draw a diagram of what happens during a time interval D t. Figure 2 shows the locations of the chaser and the target at some time t. The movement made by the chaser over that interval is indicated with the bold arrow. The final position of the chaser is given by (x0(t+ D t), y0(t+ D t))
movingtarget att(x(t),y()direct pathtotarget(x(t +At),y(t +△t)chaserat(t+t)(x(t), yo(t)movementvector (speeds)Vchaser attFigure2:Movementby the chaser during the time interval t to △tOurmodel needs tobeabitmore sophisticatedthan thegeneric one shown inFigure1.Weneedtokeeptrackoftwovariablesofinterest,sincewehaveatwo-dimensionalmodel.Ourtwo changingvariablesofinterestarethepositioncomponents Xo(t) and yo(t).Let's convertthese two functions ofthe continuousvariable t to discretefunctions of our discrete time interval n.If we usethegenericrelationthat t=nAt,then,without explicitly showingthe Atinthediscrete functions, we can represent xo(t) by xo(n), yo(t) by yo(n), Xo(t+t) byXo(n+1), and yo(t+t) by yo(n+1). Next we'll try to relate these variables in theformof Equation (1)to obtain ourmathematical modelforthis chasingprocess.Let's visualize our relationships again. This time we carefully label the criticalparts of our diagram, the points (xo(n),yo(n), (xo(n+1),yo(n+1), (xi(n), y1(n)andthe change in location of the chaser in each direction xo =(xo(n+1)- (Xo(n), and△ yo.= (yo(n+1)-(yo(n). This new visual model is given in Figure 3.(x(n), y(n)(x(n+1 ), yd(n+1))(x(n),y(n))Figure3:Movementbythechaserduringthediscretetimeintervalnton+1111
111 moving target at t (x1 (t), y1 (t)) y direct path to target chaser at (t + Dt ) movement vector (speed s ) chaser at t (xo (t), yo (t)) x (xo (t + D t ), yo (t + D t )) Figure 2: Movement by the chaser during the time interval t to D t . Our model needs to be a bit more sophisticated than the generic one shown in Figure 1. We need to keep track of two variables of interest, since we have a two-dimensional model. Our two changing variables of interest are the position components x0(t) and y0(t). Let’s convert these two functions of the continuous variable t to discrete functions of our discrete time interval n. If we use the generic relation that t = n D t , then, without explicitly showing the D t in the discrete functions, we can represent x0(t) by x0(n), y0(t) by y0(n), x0(t+ D t) by x0(n+1), and y0(t+ D t) by y0(n+1). Next we’ll try to relate these variables in the form of Equation (1) to obtain our mathematical model for this chasing process. Let’s visualize our relationships again. This time we carefully label the critical parts of our diagram, the points (x0(n), y0(n)), (x0(n+1), y0(n+1)), (x1(n), y1(n)) and the change in location of the chaser in each direction D x0 =(x0(n+1)- (x0(n)), and D y0.= (y0(n+1)- (y0(n)). This new visual model is given in Figure 3. (xo (n+1 ), yo (n+1 )) (x1(n), y1(n)) (xo(n), yo(n)) Dyo Dxo Figure 3: Movement by the chaser during the discrete time interval n to n+1
Wefindtwosimilartriangles inFigure3.It'stherelationbetweenthesesimilarright triangles that will enable us to write ourmodel.Recall that we can setupproportionalequationsrelatingthesidesofthetriangleswiththehypotenuseofthetriangles.Firstlet'sdetermineformulasforeachofthesidesofourtwotriangles.ThelargertriangleinFigure3hasitshorizontalsideoflength(x,(n)Xo(n). The vertical side has length (y(n)- yo(n). Therefore, by thePythagoreanTheoremthehypotenusehaslength(x,(n)-x(n))+(y,(n)-yo(n))?.The smallertrianglehas sides Xo andAyo.Weneedtodeterminethelengthofthehypotenuseintermsof valuesother than △Xo and yo.We alsoknowthatthe chaser moves at speed s overthetimeoftheinterval △t.Therefore,thelengthofthehypotenuserepresentsthedistancemoved overthe interval st.Now,wecandisplay ourresultsgeometrically,as we do in Figure 4.(xi(n) - Xo(n)2+ (on(n) - yo(n)yi(n)-yo(n)e(n+1)-ye(n)(n)-xe(n)xo(n+1)-x。(n)Figure4:SimilartrianglesfromFigure3withsides labeledwithdistances.Our next step is to write out the equations relating the sides of the triangles withthe hypotenuse of thetriangles.First thehorizontal side and hypotenuse ofbothtriangles produce the relationship:xo(n+ 1)-xo(n)x,(n)-x(n)(2)SA/(x;(n) - xo(n)2 +(y,(n) - yo (n)Theverticalsidesandhypotenuseproduceyo(n +1)- yo(n)y(n)- yo(n)(3)SAt/(x,(n) -xo(n)2 + (y(n) - yo(n)WecancleanupEquations(2)and(3)tocreateasystemoftwononlineardifferenceequationsfortheunknownsXo(n+1)andyo(n+1),wherebothoftheseequationsofourmodelareintheformofEquation(1):112
112 We find two similar triangles in Figure 3. It’s the relation between these similar right triangles that will enable us to write our model. Recall that we can set up proportional equations relating the sides of the triangles with the hypotenuse of the triangles. First let’s determine formulas for each of the sides of our two triangles. The larger triangle in Figure 3 has its horizontal side of length (x1(n)- x0(n)). The vertical side has length (y1(n)- y0(n)). Therefore, by the Pythagorean Theorem the hypotenuse has length (x (n) x (n)) (y (n) y (n)) 1 0 2 1 0 2 - + - . The smaller triangle has sides D x0 and D y0 . We need to determine the length of the hypotenuse in terms of values other than D x0 and D y0 . We also know that the chaser moves at speed s over the time of the interval D t. Therefore, the length of the hypotenuse represents the distance moved over the interval s D t. Now, we can display our results geometrically, as we do in Figure 4. x 1 ( n ) - x o ( n ) y 1 ( n ) - y o ( n ) x o ( n + 1 ) - x o ( n ) y o ( n + 1 ) - y o ( n ) sD t ( ) ( ) 2 1 0 2 1 0 x ( n ) - x ( n ) + y ( n ) - y ( n ) Figure 4: Similar triangles from Figure 3 with sides labeled with distances. Our next step is to write out the equations relating the sides of the triangles with the hypotenuse of the triangles. First the horizontal side and hypotenuse of both triangles produce the relationship: x n x n s t x n x n x n x n y n y n 0 0 1 0 1 0 2 1 0 2 ( 1) ( ) ( ) ( ) ( ( ) ( )) ( ( ) ( )) + - = - D - + - (2) The vertical sides and hypotenuse produce: y n y n s t y n y n x n x n y n y n 0 0 1 0 1 0 2 1 0 2 ( 1) ( ) ( ) ( ) ( ( ) ( )) ( ( ) ( )) + - = - D - + - (3) We can clean up Equations (2) and (3) to create a system of two nonlinear difference equations for the unknowns x0(n+1) and y0(n+1), where both of these equations of our model are in the form of Equation (1):
s△(x,(n) - x。(n))(4)X(n+1)=xo(n)+/(x,(n)- xo(n)2 +(y(n)- yo(n)si(y,(n) - yo(n))(5)yo(n +1)= yo(n)+/(x,(n) - xo(n)* +(y,(n) - yo(n)2This is our model, which will provide a means of determining the movement ofthe chaser, when weknowthe movement of thetarget.This system ofdifferenceequationsisnonlinearandmustbesolvednumericallybyiteration.However,foranyreasonablechase,wewillneedacomputationaltool,computeror calculator,toperformthe iterationstodeterminethepathofthechase.Rememberourassumptions:thechasermovesataconstantspeed,thechasermoves in a setdirection over thetime interval, and the chaseralways sees thetarget. Let's look at anexample.Example1:Targetmovinginastraightline.Inthisexample,wherethetargetmovesinastraight line,weneedtohave the starting coordinates and speed for the chaser and theparametricequationsforthemovementofthetarget.Let'sstartthechaser at the point (-3,0). We will use the following parametricequationsforthetarget'smovement:(6)x(t)=3+3tandy(t)=4t.Therefore,at t=0,the target is locatedat the point (3,o).The target'sspeed isdeterminedbythemagnitudeformulaforitsvelocity.ForEquation(6),thecalculationsforthespeedusederivativesandsimplifyto/32+42=5.Wemodelourchaserwithspeed7,soweshouldeventually catch the target, and our time interval set to At=0.1. Weconvertourcontinuousparametricequations of Equation (6)tothefollowing discrete equations:(7)x,(n)=3+3n△tandyi(n)= 4n△t.Nowwecanuseourmodel inEquations (4)and (5)to solveforthemovement ofthechaser.Substituting thepropervalues andfunctionsinto Equations (4)and (5)we obtain:7(0.1)(3 + 3(0.1)n-xo(n)xo(n+1)= xo(n)+/(3 + 3(0.1)n - xo(n) +(4(0.1)n - yo(n)113
113 x n x n s t x n x n x n x n y n y n 0 0 1 0 1 0 2 1 0 2 ( 1) ( ) ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) + = + - - + - D (4) y n y n s t y n y n x n x n y n y n 0 0 1 0 1 0 2 1 0 2 ( 1) ( ) ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) + = + - - + - D (5) This is our model, which will provide a means of determining the movement of the chaser, when we know the movement of the target. This system of difference equations is nonlinear and must be solved numerically by iteration. However, for any reasonable chase, we will need a computational tool, computer or calculator, to perform the iterations to determine the path of the chase. Remember our assumptions: the chaser moves at a constant speed, the chaser moves in a set direction over the time interval, and the chaser always sees the target. Let’s look at an example. Example 1: Target moving in a straight line. In this example, where the target moves in a straight line, we need to have the starting coordinates and speed for the chaser and the parametric equations for the movement of the target. Let’s start the chaser at the point (-3,0). We will use the following parametric equations for the target’s movement: x t t 1 ( ) = 3 + 3 and y t t 1 ( ) = 4 . (6) Therefore, at t=0, the target is located at the point (3,0). The target’s speed is determined by the magnitude formula for its velocity. For Equation (6), the calculations for the speed use derivatives and simplify to 3 4 5 2 2 + = . We model our chaser with speed 7, so we should eventually catch the target, and our time interval set to Dt = 0.1. We convert our continuous parametric equations of Equation (6) to the following discrete equations: x n n t 1 ( ) = 3 + 3 D and y n n t 1 ( ) = 4 D . (7) Now we can use our model in Equations (4) and (5) to solve for the movement of the chaser. Substituting the proper values and functions into Equations (4) and (5) we obtain: x n x n n x n n x n n y n 0 0 0 0 2 0 2 1 7 0 1 3 3 01 3 3 01 4 0 1 ( ) ( ) ( . )( ( . ) ( )) ( ( . ) ( )) ( ( . ) ( )) + = + + - + - + -