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 ( ) ( ) ( . )( ( . ) ( )) ( ( . ) ( )) ( ( . ) ( )) + = + + - + - + -
7(0.1)(4(0.1)n- yo(n)yo(n + 1)= yo(n) +(3 + 3(0.1)n - x。(n)2 + (4(0.1)n - y(n)A little algebraic clean up gives us the following equations:0.7(3+0.3n-xo(n)(8)Xo(n +I)= xo(n)+/(3 +0.3n- x(n)2 +(0.4n- y(n)20.7(0.4n-y。(n)(9)yo(n + 1)= y(n)+/(3 + 0.3n -x (n)* +(0.4n - yo(n)2with the initial condition that xo(0) = -3 and yo(O) = 0.Now we can iterate Equations (8) and (9) to determine the path of thechaser.We'll do oneby hand here,but continuingthis work is verytedious andtimeconsuming.We'll needtogetmore computational helptoperformmoreiteration.WebeginbysubstitutingOforninEquation(8) to get0.7(3 + 0.3(0)- x(0))xo(0 + 1)= X(0) +/(3 + 0.3(0)- xo (0)* + (0.4(0)- y (0)2Thenwe simplify,substitutethe initial conditions,andperformmoresimplifying to obtain:0.7(6)4.20.7(3 - (-3)xo(I)= -3 + 2.3V626/(3 -(-3)2Wedo thesameforEquation(9),wheremanypartsoftheequationevaluate to O and disappear in the calculations to obtain:0.7(0 - 0)=0+0=0 (1) = yo (0) +V(3 - (-3)2Therefore,thechasermovestothepoint (-2.3,0)duringthefirsttimestep ofthe chase.We continue thisprocedure for n =1,2,3,..,10toproduce the iterates given in Table 1. We determined these valuesusing a computertoperform all thetedious,butnecessarycomputations.114
114 y n y n n y n n x n n y n 0 0 0 0 2 0 2 1 7 0 1 4 0 1 3 3 0 1 4 0 1 ( ) ( ) ( . )( ( . ) ( )) ( ( . ) ( )) ( ( . ) ( )) + = + - + - + - A little algebraic clean up gives us the following equations: x n x n n x n n x n n y n 0 0 0 0 2 0 2 1 0 7 3 0 3 3 0 3 0 ( ) ( ) . ( . ( )) ( . ( )) ( .4 ( )) + = + + - + - + - (8) y n y n n y n n x n n y n 0 0 0 0 2 0 2 1 0 7 0 3 0 3 0 ( ) ( ) . ( .4 ( )) ( . ( )) ( .4 ( )) + = + - + - + - (9) with the initial condition that x0(0) = -3 and y0(0) = 0. Now we can iterate Equations (8) and (9) to determine the path of the chaser. We’ll do one by hand here, but continuing this work is very tedious and time consuming. We’ll need to get more computational help to perform more iteration. We begin by substituting 0 for n in Equation (8) to get x x x x y 0 0 0 0 2 0 2 0 1 0 0 7 3 0 3 0 0 3 0 3 0 0 0 0 0 ( ) ( ) . ( . ( ) ( )) ( . ( ) ( )) ( .4( ) ( )) + = + + - + - + - Then we simplify, substitute the initial conditions, and perform more simplifying to obtain: x 0 2 2 1 3 0 7 3 3 3 3 3 0 7 6 6 3 4 2 6 ( ) 2 3 . ( ( )) ( ( )) . ( ) . = - + . - - - - = - + = - + = - We do the same for Equation (9), where many parts of the equation evaluate to 0 and disappear in the calculations to obtain: y y 0 0 2 1 0 0 7 0 0 3 3 ( ) ( ) 0 0 0 . ( ) ( ( )) = + - - - = + = Therefore, the chaser moves to the point (-2.3,0) during the first timestep of the chase. We continue this procedure for n = 1,2,3,.,10 to produce the iterates given in Table 1. We determined these values using a computer to perform all the tedious, but necessary computations
nXo(n)Yo(n00-310-2.32-1.60.053-0.910.1540.30-0.2350.450.5061.100.7471.741.0382.361.3592.961.72103.542.11Table1.IteratesforEquations (8)and (9),providingthepathforthechaser.Whendo we stop our iteration?There is noneedtocontinue afterthe chaserhas caught thetarget.We need to refineour modelto includea stopping criteriaforthe iteration that reflects“catching"thetarget.This does notmean that thelocationofthechaserandthetargethavetobeexactlythesameattheendofatimeinterval.Thiswouldbeextremelydifficultorimpossibletoachieve.Sincewe don't have a continuous functionforlocation,we don't have an easymechanism to check locations during the time interval. Therefore,we willassume that"catching"the target means just being"close enough"at the end ofa timestep.First, we need to determine whatis"close enough."Ifthe chaserisanexplosivemunition with a large"kill radius,"then wemight use that radiustodetermine"close enough.”Ifwe need an impact of the chaser and the target,wemay say"close enough"is a very small radius. We usually call this“closeenough"distance or the radius of kill,the tolerance of the stopping criteria anddenoteitby.Wehavenumerouschoicesfordeterminingthistolerancevalue.Itcouldbeafixedvalue,liketheradiusofkill.Itcouldbeafunctionofthespeedsandtimeintervalt.Weknowthatinourdiscretemodelthechasermovesadistances△tovereachtimestep.Evenmoresophisticatedmodelscombiningthesetwocriteriaandothersarepossible.Forourexample,wewillusethedistance=0.5(s△t).Thismeanthatouriterationwillstopwhenthechaserandthetarget arewithin half the distance traveled by the chaser in a timestep. Let'sreturntoourproblemtocompletethecalculationswestartedinExample1.115
115 n x0(n) y0(n 0 -3 0 1 -2.3 0 2 -1.6 0.05 3 -0.91 0.15 4 -0.23 0.30 5 0.45 0.50 6 1.10 0.74 7 1.74 1.03 8 2.36 1.35 9 2.96 1.72 10 3.54 2.11 Table 1. Iterates for Equations (8) and (9), providing the path for the chaser. When do we stop our iteration? There is no need to continue after the chaser has caught the target. We need to refine our model to include a stopping criteria for the iteration that reflects “catching” the target. This does not mean that the location of the chaser and the target have to be exactly the same at the end of a time interval. This would be extremely difficult or impossible to achieve. Since we don’t have a continuous function for location, we don’t have an easy mechanism to check locations during the time interval. Therefore, we will assume that “catching” the target means just being “close enough” at the end of a timestep. First, we need to determine what is “close enough.” If the chaser is an explosive munition with a large “kill radius,” then we might use that radius to determine “close enough.” If we need an impact of the chaser and the target, we may say “close enough” is a very small radius. We usually call this “close enough” distance or the radius of kill, the tolerance of the stopping criteria and denote it by e . We have numerous choices for determining this tolerance value. It could be a fixed value, like the radius of kill. It could be a function of the speed s and time interval D t. We know that in our discrete model the chaser moves a distance s D t over each timestep. Even more sophisticated models combining these two criteria and others are possible. For our example, we will use the distance e = 0.5(sDt). This mean that our iteration will stop when the chaser and the target are within half the distance traveled by the chaser in a timestep. Let’s return to our problem to complete the calculations we started in Example 1
Example2:RevisitofExample1(Targetmovinginastraightline)We implement stopping criteria in our model by determining the distance,denoted d(n),between the chaser and target after each iteration. The value ofd(n)isdeterminedbythedistanceformulabetweentwopoints,d(n)= /(x (n)- x;(n)° +(y(n) - y;(n)2(10)Inthisexample,we'vedecidedtostoptheiterationwhend(n)≤=0.5(st)Since we are using s=7 and t=0.1, we have =0.35.We redo our iteration,now showing d(n), Xi(n), and yi(n), in addition to n, Xo(n), and yo(n). These newdataaregiven inTable2withtwodecimal points ofaccuracy.As we see inTable 2, when n = 24, we achieve our stopping criteria since d(24) = 0.26 <0.3=The chaser has "caught"the target near the point (10, 9.5). The graphs of.the actual pathsof the chaser and the target aregiven in Figure5.d(n)nXo(n)Yo(n)Xi(n)Y(n)0-30306103.3-2.30.45.6120.053.60.8-1.605.2630.910.153.91.24.9240.230.304.21.64.6150.450.504.524.3261.100.744.82.44.0571.035.12.81.743.8083.25.42.361.353.563.692.961.725.73.33104.03.542.116.03.10114.092.546.34.42.89124.632.996.64.82.68135.143.466.95.22.47147.25.643.965.62.27156.124.467.56.02.06166.594.997.86.41.86177.045.528.16.81.66186.068.47.27.491.46197.936.608.77.61.26209.08.367.168.01.06218.48.787.719.30.86229.208.279.68.80.66238.839.99.29.620.46249.610.049.3910.20.26Table 2.Iterates anddistancesbetweenthepathsfor thechaserandtarget.116
116 Example 2: Revisit of Example 1 (Target moving in a straight line). We implement stopping criteria in our model by determining the distance, denoted d(n), between the chaser and target after each iteration. The value of d(n) is determined by the distance formula between two points, d(n) = (x (n) - x (n)) + (y (n) - y (n)) 0 1 2 0 1 2 (10) In this example, we’ve decided to stop the iteration when d(n) £e = 0.5(sDt) . Since we are using s=7 and D t=0.1, we have e =0.35. We redo our iteration, now showing d(n), x1(n), and y1(n), in addition to n, x0(n), and y0(n). These new data are given in Table 2 with two decimal points of accuracy. As we see in Table 2, when n = 24, we achieve our stopping criteria since d(24) = 0.26 < 0.3 = e . The chaser has “caught” the target near the point (10, 9.5). The graphs of the actual paths of the chaser and the target are given in Figure 5. n x0(n) y0(n) x1(n) y1(n) d(n) 0 -3 0 3 0 6 1 -2.3 0 3.3 0.4 5.61 2 -1.60 0.05 3.6 0.8 5.26 3 -0.91 0.15 3.9 1.2 4.92 4 -0.23 0.30 4.2 1.6 4.61 5 0.45 0.50 4.5 2 4.32 6 1.10 0.74 4.8 2.4 4.05 7 1.74 1.03 5.1 2.8 3.80 8 2.36 1.35 5.4 3.2 3.56 9 2.96 1.72 5.7 3.6 3.33 10 3.54 2.11 6.0 4.0 3.10 11 4.09 2.54 6.3 4.4 2.89 12 4.63 2.99 6.6 4.8 2.68 13 5.14 3.46 6.9 5.2 2.47 14 5.64 3.96 7.2 5.6 2.27 15 6.12 4.46 7.5 6.0 2.06 16 6.59 4.99 7.8 6.4 1.86 17 7.04 5.52 8.1 6.8 1.66 18 7.49 6.06 8.4 7.2 1.46 19 7.93 6.60 8.7 7.6 1.26 20 8.36 7.16 9.0 8.0 1.06 21 8.78 7.71 9.3 8.4 0.86 22 9.20 8.27 9.6 8.8 0.66 23 9.62 8.83 9.9 9.2 0.46 24 10.04 9.39 10.2 9.6 0.26 Table 2. Iterates and distances between the paths for the chaser and target
x46821012D:Algebra Center Delete Help Moue Options Plot Quit Range Scale TransferWindowaXesZoonoptiony:3x:4y:3.9843Scalex:2Derive ZD-plotFigure 5. Graphs of the paths of the chaser and target, from the startofthechasetothe"catch"atapproximatelythepoint (10,9.5)Doesoursolutionmakesense?Doesthechasermove inanefficientpathtoward the target? Does the chaser stopwhen the stopping criteria is achieved?In general the answers to these questions are "yes". It appears we have a goodmodel, but it may not be the best. More work will need to be done to determinebettermodels.Let'sreview ourapplication of the modeling processtothis chaseproblem. Westarted by understanding and analyzing our situation and needs of the problem.We defined our problem to be the determination of a path for the chaser, given aprescribed pathforthetarget.Wemadeassumptions andused theassumptionsandourunderstandingoftheprocesstobuildamodel (thesystemofdifferenceequationsgivenby(8)and(9)andthestoppingcriteriaestablishedin(10).Finally,wesolvedourmodelinExample2by iteratingandplottinggraphs of the paths of the chaser and target.Inourdiscussionofthemodel,webrieflymentionedtheconceptsofdiscreteand continuousmodels.Thesetwoconcepts represent an importantdichotomyinmathematics.Wewillviewourmodelingprocesswiththesetwoconceptsinmind.Ourbehaviorofinterest,themovementofthechaser,iscontinuousinnature.At any value oftime,the chaser's movement can be determined and thechaser moves smoothly, with no jumps or discontinuities. However, we modeled117
117 Figure 5. Graphs of the paths of the chaser and target, from the start of the chase to the “catch” at approximately the point (10, 9.5). Does our solution make sense? Does the chaser move in an efficient path toward the target? Does the chaser stop when the stopping criteria is achieved? In general the answers to these questions are “yes”. It appears we have a good model, but it may not be the best. More work will need to be done to determine better models. Let’s review our application of the modeling process to this chase problem. We started by understanding and analyzing our situation and needs of the problem. We defined our problem to be the determination of a path for the chaser, given a prescribed path for the target. We made assumptions and used the assumptions and our understanding of the process to build a model (the system of difference equations given by (8) and (9) and the stopping criteria established in (10)). Finally, we solved our model in Example 2 by iterating and plotting graphs of the paths of the chaser and target. In our discussion of the model, we briefly mentioned the concepts of discrete and continuous models. These two concepts represent an important dichotomy in mathematics. We will view our modeling process with these two concepts in mind. Our behavior of interest, the movement of the chaser, is continuous in nature. At any value of time, the chaser’s movement can be determined and the chaser moves smoothly, with no jumps or discontinuities. However, we modeled
thismovementas being discrete. We only determine the chaser's location atdiscretevalues of time,At apart.Our solution, the sequence of location pointsgiven inTable2,isalsodiscrete.Wefinallyconvertthediscretesequenceofthepath to a continuouspathbyconnecting thepoints in thegraphs of Figure5.Weshowthis interplaybetween discrete and continuous representations inourmodeling process in Figure 6.ModelBehaviorSolution MethodVerification Method(movement(difference(iteration)(graph in figures)of chaser)equation)discretediscretecontinuouscontinuousFigure6.Interplaybetweendiscreteand continuous inthemodelingprocessofthe chase algorithm.Ingeneral,thiskind ofinterplay between discrete and continuous canoccurinanyphaseofthemodelingprocess.Aschematicdiagramofpossiblepathsthroughthemodelingprocess isgiven inFigure7.BehaviorModelSolution MethodVerification MethoddiscretediscretediscretediscretecontinuouscontinuouscontinuouscontinuousFigure7.Interplaybetweendiscreteandcontinuous.Let'sdo anotherexamplewhich shows more sophistication in themovements ofthe target and chaser.Let's see what happens when a tracking torpedo islaunchedataship118
118 this movement as being discrete. We only determine the chaser’s location at discrete values of time, D t apart. Our solution, the sequence of location points given in Table 2, is also discrete. We finally convert the discrete sequence of the path to a continuous path by connecting the points in the graphs of Figure 5. We show this interplay between discrete and continuous representations in our modeling process in Figure 6. Behavior Model Solution Method Verification Method (movement (difference (iteration) (graph in figures) of chaser) equation) Figure 6. Interplay between discrete and continuous in the modeling process of the chase algorithm. In general, this kind of interplay between discrete and continuous can occur in any phase of the modeling process. A schematic diagram of possible paths through the modeling process is given in Figure 7. Behavior Model Solution Method Verification Method Figure 7. Interplay between discrete and continuous. Let’s do another example which shows more sophistication in the movements of the target and chaser. Let’s see what happens when a tracking torpedo is launched at a ship. continuous discrete continuous discrete continuous discrete discrete discrete discrete continuous continuous continuous