TheChaseProblem(Part2)DavidC.ArneyIntroductionIntheprevioussection,entitledTheChaseProblem(Part1),wediscussedadiscretemodelforachasingscenariowhereonethingchasesanother.Someoftheapplications of thiskind of chasing weregiven intheexamples of theprevious section:missiles intercepting other missiles,anti-tankround seekingatank, andtorpedotrackinganenemyship.Inthissection,weextendandrefinethisfirst model, builda continuous model forthis problem,and build moreeffectivenessandsophisticationintoourchasealgorithm.TheProblemOurproblemistodeterminethemovementpathforthechaser,giventhatweknowthelocation (andsometimesmoreinformation)ofthetarget.Westartwiththeassumptionthatthechaserknowsthetarget'spositionexactly.Thechaser'spositionisrepresented intwo-dimensional Cartesiancoordinatesby (xo(t),yo(t)Wealsoassumethatthechasermoves at a constant speed (givenby s)andthetarget's position intwo dimensions isgivenbytheparametricrelationship(x(t),y(t).Westartwiththetechniquethatthechasermovesdirectlytowardsthetarget.Laterwe'll allowfor the chaserto"lead"thetarget.As the location of thetargetchanges,thechasercontinuallyadjustsitspathtocontinuetomovedirectly toward the target.The ModelWecanmodel thisprocedurewithasystemofdifferential equations,oneforeachspacedimensionwemodel.Sincewe'llperformourmodelingintwospacedimensions (xand y),we'll build systems oftwodifferential equations.Ourmodelingprocessforacontinuoustimechangingevent isto setuprelationships that expressthe derivatives ofthechanging variables (xo(t),yo(t)intermsoffunctionsofvariables.Let's draw a diagram of what happens during a time interval △t. We will takethe limit as At→o in orderto get continuous feedback and continuousmovementforthechaser.Figure1showsthelocationsofthechaserandthetargetatsometimet.Themovementmadebythechaseroverthat interval isindicated. The final position of the chaser is given by (xo(t+t),yo(t+△t)129
129 The Chase Problem (Part 2) David C. Arney Introduction In the previous section, entitled The Chase Problem (Part 1), we discussed a discrete model for a chasing scenario where one thing chases another. Some of the applications of this kind of chasing were given in the examples of the previous section: missiles intercepting other missiles, anti-tank round seeking a tank, and torpedo tracking an enemy ship. In this section, we extend and refine this first model, build a continuous model for this problem, and build more effectiveness and sophistication into our chase algorithm. The Problem Our problem is to determine the movement path for the chaser, given that we know the location (and sometimes more information) of the target. We start with the assumption that the chaser knows the target’s position exactly. The chaser’s position is represented in two-dimensional Cartesian coordinates by (x0(t), y0(t)). We also assume 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)). We start with the technique that the chaser moves directly towards the target. Later we’ll allow for the chaser to “lead” the target. As the location of the target changes, the chaser continually adjusts its path to continue to move directly toward the target. The Model We can model this procedure with a system of differential equations, one for each space dimension we model. Since we’ll perform our modeling in two space dimensions (x and y), we’ll build systems of two differential equations. Our modeling process for a continuous time changing event is to set up relationships that express the derivatives of the changing variables (x’0(t), y’0(t)) in terms of functions of variables. Let’s draw a diagram of what happens during a time interval D t. We will take the limit as Dt ® 0 in order to get continuous feedback and continuous movement for the chaser. Figure 1 shows the locations of the chaser and the target at some time t. The movement made by the chaser over that interval is indicated. The final position of the chaser is given by (x0(t+ D t), y0(t+ D t))
(x(n),y(n)(x(n+1 ),yd(n+1))(xo(n), ydAxoFigure 1:Movement by the chaser during the time interval from stepn tostep n+1Weseetwo similartriangles inFigure1.Likethediscretecasedeveloped inPart1,therelationbetweenthesesimilarrighttrianglesenablesustowriteourmodel.Recall that we cansetupproportional equationsrelatingthesides ofthetriangles with thehypotenuse of the triangles.First let's determine formulas foreachofthesidesofourtwotriangles.ThelargertriangleinFigure1hasitshorizontal side of length (x(t)- xo(t). The vertical side has length (yi(t)- yo(t).Therefore,bythePythagoreanTheoremthehypotenusehas lengthV(x,(t)-x(t)+(y:(t)-yo(t)?.ThesmallertrianglehassidesXo(t+△t)-xo(t)=△xo and yo(t+△t)-yo(t)=△yo.We need to determinethelength ofthehypotenuse interms of values other than AXo and Ayo.Wealsoknowthatthe chasermoves at speed s.Therefore,thelengthofthehypotenuse canbeapproximated bythedistancetraveled duringthetime interval or sAt.We writeout the equations relatingthe sides of the triangleswith the hypotenuse ofthetriangles.Firstthehorizontal side and hypotenuse of bothtriangles producetherelationship:Xo(t +△t)-xo(t)x,(t)-xo(t)(1)sAt/(x,() - xo(t)* +(y (t) - y (t)"The vertical sides andhypotenuseproduce:yo(n + 1)-yo(n)y,(n)-yo(n)(2)SAt(x,(n)-xo(n))2 + (y (n) - yo(n)Wenowhavedifferencequotients ontheleft sidesof Equations(1)and (2).WetakethelimitasAt→0of(1)and(2)toproducethedifferentialequations130
130 (xo (n+1 ), yo (n+1 )) (x1(n), y1(n)) (xo(n), yo(n)) Dyo Dxo Figure 1: Movement by the chaser during the time interval from step n to step n+1 . We see two similar triangles in Figure 1. Like the discrete case developed in Part 1, the relation between these similar right triangles enables 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 1 has its horizontal side of length (x1(t)- x0(t)). The vertical side has length (y1(t)- y0(t)). Therefore, by the Pythagorean Theorem the hypotenuse has length (x (t) x (t)) (y (t) y (t)) 1 0 2 1 0 2 - + - . The smaller triangle has sides x0(t+ D t)-x0(t)= D x0 and y0(t+ D t)-y0(t)= 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. Therefore, the length of the hypotenuse can be approximated by the distance traveled during the time interval or s D t. We 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 t t x t s t x t x t x t x t y t y t 0 0 1 0 1 0 2 1 0 2 ( ) ( ) ( ) ( ) ( ( ) ( )) ( ( ) ( )) + - = - - + - D D (1) 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 - + - (2) We now have difference quotients on the left sides of Equations (1) and (2). We take the limit as Dt ® 0 of (1) and (2) to produce the differential equations
x(t+t)-xo(t)dx(t)s(x,()-x(t)(3)limAtdtV(x,(t)-xo(0)2 +(y(0)- yo(0)yo(t +Atr) - yo(t)_ dyo(t)s(y,(t)-yo(t)(4)lim△tdt/(x(t)-xo(0) +(y,(t)-yo(0)This is ourchase/movementmodel (equations(3)and(4)),which will provideameans ofdeterminingthe movement of the chaser,when weknowthe movementofthetarget.Thissystemofdifferentialequationsisnonlinearandmustbesolved numerically.Therefore,wewillneedanumerical solverona computerorcalculatortodeterminethepathofthechase.ManysoftwarepackagesthatuseEuler'smethodortheRunge-Kuttamethodareavailable.Jtisalsopossibletoimplementthesealgorithmsbyconvertingthedifferentialeguationstodifferenceequations and implementing iteration on a spread sheet.Remember ourassumptions:thechasermovesataconstantspeedandthechaseralwayssees thetarget.When we solve ourdifferentialequations witha numericalmethod,weactuallymodelthechasermovingtowardthetargetforasettimeinterval.At.usedinthenumericalscheme.Weusuallysetthetimeintervaltobe very small to assure accuracy of the solution and to approximate accuratelythe continuous movement of the chaser.Weneedtodeterminewhentostopourcalculations.Intheprevioussection,wediscussedseveralofthefactorsinvolvedinthisdecision.Thereisnoneedtocontinue after the chaser has caught the target.We need a stopping criteria thatreflects"catching"thetarget.Wewill assumethat"catching”thetargetmeansjustbeing"close enough"or within the toleranceof the stopping criteria denotedby.Wehavechoicesfordeterminingthistolerancevalue.It couldbeafixedvalue ora function ofthe speed s and time interval At.We implement stoppingcriteria in our model by determining the distance, denoted d(t),between thechaserand target aftereach iteration.The value of d(t) is determined by thedistanceformula betweentwopoints,(5)d(t)= /(xo(t) - x,(t)? + (y(t) - y,(t)2Westopwhend(t)M)Let'slook atan exampleto see howthis works.Example1:Anti-tank RoundAsoldierlocated atpoint (0,3)launchesatrackinganti-tank roundwithspeed3.5atatankattimet=0following aelliptical coursegivenbythefollowingparametricequations:(6)x,(t)=8-3cost and y,(t)=4sintWewill determinetheround'spathbasedon itsseekerusingourtrackingmodelofmovingdirectly131
131 lim ( ) ( ) ( ) ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) t x t t x t t dx t dt s x t x t x t x t y t y t ® + - = = - - + - 0 0 0 0 1 0 1 0 2 1 0 2 D D (3) lim ( ) ( ) ( ) ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) t y t t y t t dy t dt s y t y t x t x t y t y t ® + - = = - - + - 0 0 0 0 1 0 1 0 2 1 0 2 D D (4) This is our chase/movement model (equations (3) and (4)), which will provide a means of determining the movement of the chaser, when we know the movement of the target. This system of differential equations is nonlinear and must be solved numerically. Therefore, we will need a numerical solver on a computer or calculator to determine the path of the chase. Many software packages that use Euler’s method or the Runge-Kutta method are available. It is also possible to implement these algorithms by converting the differential equations to difference equations and implementing iteration on a spread sheet. Remember our assumptions: the chaser moves at a constant speed and the chaser always sees the target. When we solve our differential equations with a numerical method, we actually model the chaser moving toward the target for a set time interval, D t, used in the numerical scheme. We usually set the time interval to be very small to assure accuracy of the solution and to approximate accurately the continuous movement of the chaser. We need to determine when to stop our calculations. In the previous section, we discussed several of the factors involved in this decision. There is no need to continue after the chaser has caught the target. We need a stopping criteria that reflects “catching” the target. We will assume that “catching” the target means just being “close enough” or within the tolerance of the stopping criteria denoted by e . We have choices for determining this tolerance value. It could be a fixed value or a function of the speed s and time interval D t. We implement stopping criteria in our model by determining the distance, denoted d(t), between the chaser and target after each iteration. The value of d(t) is determined by the distance formula between two points, d(t) = (x (t) - x (t)) + (y (t) - y (t)) 0 1 2 0 1 2 (5) We stop when d(t) M). Let’s look at an example to see how this works. Example 1: Anti-tank Round A soldier located at point (0,3) launches a tracking anti-tank round with speed 3.5 at a tank at time t = 0 following a elliptical course given by the following parametric equations: x t t 1 ( ) = 8 - 3cos and y t t 1 ( ) = 4 sin (6) We will determine the round’s path based on its seeker using our tracking model of moving directly
toward the tank.If thekill radius of the round is 0.25units, our stopping criteriais=0.25.Substitutingtheknownvalues andfunctions intoourmodel,Equations (3)and(4),producesdx(t)3.5(8-3cost-x(t))(7)dt/(8-3cost-x(t)+(4sint-yo(t)dy,(t)3.5 (4sint- yo(t)(8)dt/(8-3cost-x(t)2+(4sint-yo(t))Starting with our initial condition, xo(0) =0 and yo(O)=3, we use a Runge-Kuttasolver with t =0.06 until we achieve our stopping criteria of d(t)< =0.25.This producesthesolutionforthepathof theround.Thegraphsofthepathsforboth the round and the tank, until their impact at a time slightly great than 5seconds,aregiven inFigure2.Noticehowtheround curvesaroundtofollowthetankand eventuallycatches it.7n,261212.0,n,panFigure2.Graph of thepaths of the round (solid curve)and thetank (dottedcurve),fromlaunch(t=O)toimpactDoesoursolutionmake sense?Doesthechasermove inanefficientpathtoward thetarget? Does the chaser stop when the stopping criteria is achieved?Ingeneral the answers to these questions are“yes".It appears that we haveagood model, but it maynot be the best. It could help if the round was ableto"lead”the tank so it could catch it faster. We'll try implementing a "lead"algorithmforthischaseproblemlaterinthissection.132
132 toward the tank. If the kill radius of the round is 0.25 units, our stopping criteria is e =0.25. Substituting the known values and functions into our model, Equations (3) and (4), produces 2 0 2 0 0 0 (8 3cos ( )) (4sin ( )) ( ) 3.5(8 3cos ( )) t x t t y t t x t dt dx t - - + - - - = (7) 2 0 2 0 0 0 (8 3cos ( )) (4sin ( )) ( ) 3.5 (4sin ( )) t x t t y t t y t dt dy t - - + - - = (8) Starting with our initial condition, x0(0) = 0 and y0(0) =3, we use a Runge-Kutta solver with Dt =0.06 until we achieve our stopping criteria of d(t) < e =0.25. This produces the solution for the path of the round. The graphs of the paths for both the round and the tank, until their impact at a time slightly great than 5 seconds, are given in Figure 2. Notice how the round curves around to follow the tank and eventually catches it. Figure 2. Graph of the paths of the round (solid curve) and the tank (dotted curve), from launch (t=0) to impact. 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 that we have a good model, but it may not be the best. It could help if the round was able to “lead” the tank so it could catch it faster. We’ll try implementing a “lead” algorithm for this chase problem later in this section. 4 4 z n,2 b n 0 z 12 n,1 a n , 0 6 12 4 4
TheModeling ProcessLet'sreviewourmodelingprocessforthisproblem.Ourbehaviorof interest,themovementofthechaser,iscontinuousinnature.Wemodeledthismovementwithacontinuousdifferentialeguation.Oursolutionmethodforthismodel,theRunge-Kutta numerical method,is discrete and gives an approximate solutiontothecontinuousmodel.Wethenconvertedthediscrete sequenceoflocations ofthe path to a continuouspathby connecting thepoints in thegraphs of Figure2.We showthis interplay between discrete and continuous representations in ourmodelingprocessinFigure3.BehaviorModelSolution MethodVerification Method(differential(movement(Runge-Kutta(graph inFigure 2)of chaser)numerical scheme)equations)discretecontinuouscontinuouscontinuousFigure3.Interplaybetweendiscreteandcontinuous inthemodelingprocessofthedifferentialequationchasemodelThe"lead"”algorithmHowdo weget the chaserto"lead"thetarget? We needtotake into accountboththespeedandthevelocityofthetarget,thenusethat informationtopredictwhere the target will be when the chaser catches the target.We use the Taylorpolynomial to do this. The Taylor polynomial is an approximation to afunction.For the function f(x) and using the start point as x=a, we write the Taylorpolynomialofdegreenasn(a)f"(a)f"(a))2+f(x)= f(a)+ f'(a)(x -a)+g)34(9)2!3!n!Wecanusethisapproximationforthetwofunctionsxi(t)andyi(t)representingthetwodimensions ofthetarget's path.First, let's usethe1st-degreepolynomial approximations,whichtake intoaccountthe location and the velocity(but not the acceleration). We must be expeditious in our selection of a and x inEquation(9),and setn=1.Togetourapproximations intheproperform, weusex=t+△ t and a=t, and therefore, (x-a)=△ t. Then, we can write(10)x,(t+△t)=x,(t)+x(t)Atandy,(t+At)=y,(t)+y'(t)At.133
133 The Modeling Process Let’s review our modeling process for this problem. Our behavior of interest, the movement of the chaser, is continuous in nature. We modeled this movement with a continuous differential equation. Our solution method for this model, the Runge-Kutta numerical method, is discrete and gives an approximate solution to the continuous model. We then converted the discrete sequence of locations of the path to a continuous path by connecting the points in the graphs of Figure 2. We show this interplay between discrete and continuous representations in our modeling process in Figure 3. Behavior Model Solution Method Verification Method (movement (differential (Runge-Kutta (graph in Figure 2) of chaser) equations) numerical scheme) Figure 3. Interplay between discrete and continuous in the modeling process of the differential equation chase model. The “lead” algorithm How do we get the chaser to “lead” the target? We need to take into account both the speed and the velocity of the target, then use that information to predict where the target will be when the chaser catches the target. We use the Taylor polynomial to do this. The Taylor polynomial is an approximation to a function. For the function f(x) and using the start point as x=a, we write the Taylor polynomial of degree n as f x f a f a x a f a x a f a x a f a n x a n n ( ) ( ) ( )( ) ( ) ! ( ) ( ) ! ( ) . ( ) ! ( ) ( ) » + ¢ - + ¢¢ - + ¢¢¢ - + + - 2 3 2 3 (9) We can use this approximation for the two functions x1(t) and y1(t) representing the two dimensions of the target’s path. First, let’s use the 1st-degree polynomial approximations, which take into account the location and the velocity (but not the acceleration). We must be expeditious in our selection of a and x in Equation (9), and set n=1. To get our approximations in the proper form, we use x=t+ D t and a=t, and therefore, (x-a)= D t . Then, we can write x t x t x t 1 1 1 ( + Dt) = ( ) + ¢( )Dt and y t y t y t 1 1 1 ( + Dt) = ( ) + ¢( )Dt . (10) continuous continuous discrete continuous
ThevalueofAtistheyalueofthetimeadvancetothelocationwherethetarget ispredicted to be,inorderto havea properlead.The“phantom"locationto aimforis simply the point (x,(t+t),y,(t+ △t)).Therefore,wemodifythemodel in Equations (3)and (4),usingthis“phantom"leadpoint in place of(xi(t),yi(t)andtheformulas inEquation (10)to obtaindxo(t)s(x,(t)+x;(t)At-xo(t))(11)dtV(x(0)+x'(t)At - x()? +(y,(t)+yi(t)At -yo(t)2dyo(t)s(y,(t) + y(t)At -yo(t))(12)dtV(x(t)+xi(t)At -x(t)2 +(y,(t)+yi(t)At -yo(t)2Thegeometryof thislead algorithmisshown inFigure4.lead pointx(t+ At), y(t+ At)x(0),y(0)-(Target's currentlocation)Chaser'smovemendirectionAyAxx(t),yo(0)(Chaser's currentlocation)Figure4:Pathofchaserwhenheadingforthe"lead”pointWeneed analgorithmtodeterminethevaluefor△t.Howmuchshouldwelead?Wecoulddothisseveralways.Onewayistothinkoftasthetimeneeded to catch thetarget.We will approximatethis"catch"timeby usingthetimeforthe chasertoreachthetarget'scurrentlocation.Therefore,theformulaforA issimplythe current distancebetweenthechaserandthetargetgiven inEquation(5)divided by the speed s.WewritethisasV(xo(t)-xi(t)2 +(o(t)-yi(t)2(13)AT-s134
134 The value of D t is the value of the time advance to the location where the target is predicted to be, in order to have a proper lead. The “phantom” location to aim for is simply the point (x (t ), y (t )) 1 1 + Dt + Dt . Therefore, we modify the model in Equations (3) and (4), using this “phantom” lead point in place of (x1(t),y1(t)) and the formulas in Equation (10) to obtain dx t dt s x t x t x t x t x t x t y t y t y t 0 1 1 0 1 1 0 2 1 1 0 2 ( ) ( ( ) ( ) ( )) ( ( ) ( ) ( )) ( ( ) ( ) ( )) = + ¢ - + ¢ - + + ¢ - D D D t t t (11) dy t dt s y t y t y t x t x t x t y t y t y t 0 1 1 0 1 1 0 2 1 1 0 2 ( ) ( ( ) ( ) ( )) ( ( ) ( ) ( )) ( ( ) ( ) ( )) = + - + ¢ - + + ¢ - D D D t t t (12) The geometry of this lead algorithm is shown in Figure 4. xo (t) , yo (t) Dx D y x1 (t+ Dt) , y1 (t + Dt) x1 (t) , y1 (t) (Target’s current location) lead point Chaser’s movement direction (Chaser’s current location) Figure 4: Path of chaser when heading for the “lead” point. We need an algorithm to determine the value for Dt . How much should we lead? We could do this several ways. One way is to think of D t as the time needed to catch the target. We will approximate this “catch” time by using the time for the chaser to reach the target’s current location. Therefore, the formula for D t is simply the current distance between the chaser and the target given in Equation (5) divided by the speed s. We write this as s x t x t y t y t 2 0 1 2 0 1 ( ( ) - ( )) + ( ( ) - ( )) Dt = (13)
Thenournew"lead"modelisformedbysubstitutingEquation(13)intoEquations (11)and (12):/((0)-x(0) +(%()-(0)s(x(0+x()(0)dg(0)dtV(%(0)-x(0) +(%(0)-(0)(%(0)-x(0) +(%()-(0)5()+@+()a0+xt0ss(14)/%(0)-x(0)P +(%(0)-(0)st)+(%()dx(0)Sdt/(6(0)-x(0) +(%()-(0)(0) +0()+/0 /(0-(0 +0(0-3(0)x0+x(ss(15)Let's try this model in our previous scenario of an anti-tank roundExample2:Anti-tankRound (revisited)A soldierlocated at (0,3) launches a tracking anti-tank round with speed3.5 at atank at time t = o, following a elliptical course given by:and(16)x,(t)=8- 3costyi(0) = 4sint .Wedeterminetheround'spathbasedon itsseekerusing ournewtrackingmodel ofleading"thetank.Weuse =0.25and substitutetheknownvaluesandfunctions intoEquations(14)and(15).Startingwiththe initialcondition,Xo(0)=0 and yo(0)=3, we usea Runge-Kutta solver with △ t=0.06 until weachieve our stopping criteria of d(t) < =0.25. This produces the solution forthepath oftheround.Thegraphs ofthepaths for both the round and thetankuntil their impact are given in Figure 5. By comparing this graph with that ofFigure2,we see thattheleadalgorithm saves time and chasedistancebyturning soonerand more sharplytocatchthetank.135
135 Then our new “lead” model is formed by substituting Equation (13) into Equations (11) and (12): 2 0 2 0 1 2 0 1 1 1 2 0 2 0 1 2 0 1 1 1 0 2 0 1 2 0 1 1 1 0 ( )) ( ( ) ( )) ( ( ) ( )) ( )) ( ( ) ( ) ( ( ) ( )) ( ( ) ( )) ( ( ) ( ) ( )) ( ( ) ( )) ( ( ) ( )) ( ( ) ( ) ( ) y t s x t x t y t y t x t y t y t s x t x t y t y t x t x t x t s x t x t y t y t s x t x t dt dx t - - + - - + + ¢ - + - + ¢ - - + - + ¢ = (14) 2 0 2 0 1 2 0 1 1 1 2 0 2 0 1 2 0 1 1 1 0 2 0 1 2 0 1 1 1 0 ( )) ( ( ) ( )) ( ( ) ( )) ( )) ( ( ) ( ) ( ( ) ( )) ( ( ) ( )) ( ( ) ( ) ( )) ( ( ) ( )) ( ( ) ( )) ( ( ) ( ) ( ) y t s x t x t y t y t x t y t y t s x t x t y t y t x t x t y t s x t x t y t y t s y t y t dt dy t - - + - - + + ¢ - + - + ¢ - - + - + ¢ = (15) Let’s try this model in our previous scenario of an anti-tank round. Example 2: Anti-tank Round (revisited) A soldier located at (0,3) launches a tracking anti-tank round with speed 3.5 at a tank at time t = 0, following a elliptical course given by: x t t 1 ( ) = 8 - 3cos and y t t 1 ( ) = 4 sin . (16) We determine the round’s path based on its seeker using our new tracking model of “leading” the tank. We use e =0.25 and substitute the known values and functions into Equations (14) and (15). Starting with the initial condition, x0(0) = 0 and y0(0) =3, we use a Runge-Kutta solver with D t =0.06 until we achieve our stopping criteria of d(t) < e =0.25. This produces the solution for the path of the round. The graphs of the paths for both the round and the tank until their impact are given in Figure 5. By comparing this graph with that of Figure 2, we see that the lead algorithm saves time and chase distance by turning sooner and more sharply to catch the tank
443n,20.25D1212.0,n,panFigure4.Graphofthepathsoftheround (solidcurve)andthetank (dottedcurve),fromlaunch (t=0)to impact.It appears that we have developed a better model by leading the target. Is it thebest we can do? Are there better lead models? Of course, these are leadingquestions.Thereprobablyarebetterwaystocomputet.Andwecouldkeepmorethan justonetermoftheTaylorPolynomialEquation(9).Ifwekeeptwoterms,n=2,we would getnewapproximations for our“lead"location of thetarget.We would nowbe taking into account the acceleration of the tank,aswell as its velocity.The newmodel is writtenasfollows:x,(t+At)= x, (t)+x;(t)At+x;(t)Ar? and yi(t + At)=yi(t)+ yi(t)At + yi(0)Ar?.(17)Substitution of theseformulas into Equations (3)and (4),along with usingEquation (13) for t, creates a model with very large,messy differentialequations. We won'ttry to showthem here, butwe'll show an example whichcompares the various models we have discussedExample3:ToLeadornottoLeadThis time the soldier firing the anti-tank round is located at the origin, (O,O). Helaunches a tracking round with speed 5 at a tank at time t = 0. The tank followsanoscillatingcoursegivenby:(18)andx,(t)=3 + 3ty,(t)= 2 sin(3t)Wedetermine the round's pathbased on its seeker using threedifferent trackingmodels:1)moving directlytoward thetank,2)leadingthetank by using thevelocity(onederivative term inthe Taylorpolynomial as in Equations 14 and136
136 Figure 4. Graph of the paths of the round (solid curve) and the tank (dotted curve), from launch (t=0) to impact. It appears that we have developed a better model by leading the target. Is it the best we can do? Are there better lead models? Of course, these are leading questions. There probably are better ways to compute D t . And we could keep more than just one term of the Taylor Polynomial Equation (9). If we keep two terms, n=2, we would get new approximations for our “lead” location of the target. We would now be taking into account the acceleration of the tank, as well as its velocity. The new model is written as follows: 2 1 1 1 1 x (t + Dt) = x (t) + x¢(t)Dt + x¢¢(t)Dt and 2 1 1 1 1 y (t + Dt) = y (t) + y¢(t)Dt + y¢¢(t)Dt . (17) Substitution of these formulas into Equations (3) and (4), along with using Equation (13) for D t , creates a model with very large, messy differential equations. We won’t try to show them here, but we’ll show an example which compares the various models we have discussed. Example 3: To Lead or not to Lead This time the soldier firing the anti-tank round is located at the origin, (0,0). He launches a tracking round with speed 5 at a tank at time t = 0. The tank follows an oscillating course given by: x (t) 3 3t 1 = + and ( ) 2sin(3 ) 1 y t = t (18) We determine the round’s path based on its seeker using three different tracking models: 1) moving directly toward the tank, 2) leading the tank by using the velocity (one derivative term in the Taylor polynomial as in Equations 14 and 4.5 4 z n,2 b n 0 z 12 n,1 a n , 0 6 12 4 0.25 4.5
15).and3)leadingthetankbyusingvelocityandacceleration(including2termsin the Taylor Polynomial shown in Equation 17). Our stopping criteria is =0.25. The path of the round tracking directly for the tank is given in Figure 5.The round catches thetankat t=3.9seconds.Thepath oftheround whenleadingthetarget usingthetank'svelocityisshown inFigure6.Thispath ismoredirectandcatchesthetankin2.8seconds.Finally,thenewleadalgorithmusing bothvelocityand accelerationproduces the graph inFigure7.This modelproducesacatchat2.7seconds.Thislastmethodisnotmuchfasterthanthevelocity only model. Sometimes it doesn't help or may even hinder to lead thetarget,but, in general,the more information youuse the quickeryou can catchyourtarget0.10n,ranFigure 5:Paths oftarget (dotted curve)and chaser (solid curve) using the modelofmovingdirectlytowardthetarget.Zn,2D1515-n,IaFigure 6:Paths oftarget (dotted curve)and chaser (solid curve)using the modelofleadingthetankbyusingthevelocity137
137 15), and 3) leading the tank by using velocity and acceleration (including 2 terms in the Taylor Polynomial shown in Equation 17). Our stopping criteria is e =0.25. The path of the round tracking directly for the tank is given in Figure 5. The round catches the tank at t=3.9 seconds. The path of the round when leading the target using the tank’s velocity is shown in Figure 6. This path is more direct and catches the tank in 2.8 seconds. Finally, the new lead algorithm using both velocity and acceleration produces the graph in Figure 7. This model produces a catch at 2.7 seconds. This last method is not much faster than the velocity only model. Sometimes it doesn’t help or may even hinder to lead the target, but, in general, the more information you use the quicker you can catch your target. Figure 5: Paths of target (dotted curve) and chaser (solid curve) using the model of moving directly toward the target. Figure 6: Paths of target (dotted curve) and chaser (solid curve) using the model of leading the tank by using the velocity. 2 2 z n,2 b n 0 z 15 n,1 a n , 0 7.5 15 2 2 2 2 z n,2 b n 0 z 15 n,1 a n , 0 7.5 15 2 2
1515Zn,paFigure 7: Paths of target (dotted curve) and chaser (solid curve) using the modelofleadingthetankbyusingboththevelocityandacceleration.Inthissection,wehavestudiedandsolvedachallengingproblemwithmanyapplications.Ourmodelanditssolutionshaveperformedwell intheexampleswehavesolved.Wenowknowwhathappens whenwe lead thetarget,insteadofmovingdirectlytoward it.Therearestill manyquestions wehavenotaddressed.Whataboutthemaneuverabilityofthechaser?Canitalwaysturnfast enoughto makethe necessarymoves ofthealgorithm?How shouldthetargetmovetoevadethe chaser?Thesearedifficultquestionsthatmeritfurtherstudyand more sophisticatedmathematical models.Good lucktothosewhostudythis important problemwithnumerous militaryapplications.Exercises1.An enemy tank, currently at location (12,0), is moving in a zigzag patternawayfrom your location with parametric equations: x,(t)=12 +3t andy,(t)=2 sin(2t).You launch a tank tracking round moving at a speed of12 fromyourlocationat (o,o).Theguidancesystemoftheradar-controlledroundalwaysmovesdirectlytowardthetanktarget.a)Write a system of differential equations thatmodels the movement of theroundtowardsthetarget.b)Useanumerical schemetosolvethe equationsandplotthesolutionfor0<t<2.c)What is thedistancebetween thetank and the round at t=2?Is theroundcloseratt=2ort=o?2. Using thesamegeneral scenario as exercise1for anenemytank starting at(12,0) and moving with equations: x,(t)=12 +3t and y, (t)=2 sin(2t),youlaunchatrackingroundmovingatspeedof12fromyourlocationat(O,O).Thisnew improved roundhas aguidance systemthatleads thetank by consideringits velocity.a)Writea systemof differential equationsbysubstitutingintoEquations(15)and (16)thatmodels themovement of the roundtowards thetarget.b)Use a numerical scheme to solvethe equations and plotthe solution for0<t<2.138
138 Figure 7: Paths of target (dotted curve) and chaser (solid curve) using the model of leading the tank by using both the velocity and acceleration. In this section, we have studied and solved a challenging problem with many applications. Our model and its solutions have performed well in the examples we have solved. We now know what happens when we lead the target, instead of moving directly toward it. There are still many questions we have not addressed. What about the maneuverability of the chaser? Can it always turn fast enough to make the necessary moves of the algorithm? How should the target move to evade the chaser? These are difficult questions that merit further study and more sophisticated mathematical models. Good luck to those who study this important problem with numerous military applications. Exercises 1. An enemy tank, currently at location (12,0), is moving in a zigzag pattern away from your location with parametric equations: x t t 1 ( ) = 12 + 3 and y t t 1 ( ) = 2 sin(2 ) . You launch a tank tracking round moving at a speed of 12 from your location at (0,0). The guidance system of the radar-controlled round always moves directly toward the tank target. a) Write a system of differential equations that models the movement of the round towards the target. b) Use a numerical scheme to solve the equations and plot the solution for 0<t<2. c) What is the distance between the tank and the round at t =2? Is the round closer at t = 2 or t = 0 ? 2. Using the same general scenario as exercise 1 for an enemy tank starting at (12,0) and moving with equations: x t t 1 ( ) = 12 + 3 and y t t 1 ( ) = 2 sin(2 ) , you launch a tracking round moving at speed of 12 from your location at (0,0). This new improved round has a guidance system that leads the tank by considering its velocity. a) Write a system of differential equations by substituting into Equations (15) and (16) that models the movement of the round towards the target. b) Use a numerical scheme to solve the equations and plot the solution for 0<t<2. 2 2 z n,2 b n 0 z 15 n,1 a n , 0 7.5 15 2 2