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)< orafteraspecifiedamount of timehas expired (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) < e or after a specified amount of time has expired (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