Research in Differential Games

A Summer Undergraduate Research Project

David Szurley and Edward Aboufadel

The term "Differential Games" is applied to a group of problems in applied mathematics that share certain characteristics related to the modeling of conflict. In a basic differential game there are two actors -- a pursuer and an evader -- with conflicting goals. The pursuer wishes, in some sense, to catch the evader, while the evader's mission is to prevent this capture. These "games" are modeled mathematically by first defining state variables that represent the position (and perhaps velocity) of the participants, determining (differential) equations of motion for the rivals, and then describing sets in the state space called target sets. (For example, a target set for a pursuer may include points in the state space where the distance between the pursuer and the evader is small.) Each participant in the game tries to drive the state variables of the game into a particular target set by controlling key variables called, naturally, controls. The study of these games has implications for real-life air combat and for artificial intelligence.

An archetypal example of a differential game is known as the Homicidal Chauffeur (described in Lewin, 1994, and created by Issacs). In this game, the driver of a circular car acts to knock down a pedestrian, who, of course, does not wish to be flattened. The car can move faster than the pedestrian, but the pedestrian can maneuver better. What is the best strategy for the pursuer (the car) and the evader (the pedestrian) to follow in order for each to achieve their conflicting goals? This is a case the car is always considered as being at the origin, and the state variables are the position of the pedestrian. The solution to this problem can be applied to air combat where a slow, but more maneuverable airplane is pursued by a faster but less maneuverable craft.

This problem, and others (with names such as the Lion and Man problem, the Obstacle Tag game, and the Lady in the Lake problem), all involve similar geometric constructions to create mathematical models, but the methods of analysis vary greatly. As a result, an active group of researchers have been working on these problems since World War II, people whose prime research interests have included game theory, astronomy, computer science, and engineering. These problems are also called "pursuit problems", and a recent search of the Math-Sci disks in our library, using the word "pursuit", indicated over one-hundred recent research articles published during the past 3 years alone.

The differential game that initially caught our interest could be called "the ant game." Bruckstein (1993), influenced by a passage in Fenyman's autobiography (1985), considered why it is that ant trails "look so straight and nice." The solution involved creating and analyzing a mathematical model of ant motion in pursuit of food. The model is constructed in the plane, with the origin being the anthill and a point (L,0) representing the food. The first ant leaves the anthill in pursuit of the food, and he follows a somewhat random path. The second ant leaves the anthill a short time later and along another path, following the strategy that its velocity vector is always pointing toward the first ant. (The first ant's control is the direction of its velocity vector.) The third ant follows the second ant using the same strategy, and so on. The analysis of this system of differential equations focuses on the angle made by the velocity vectors of the nth and n+1th ants. Bruckstein showed that as n gets larger -- in other words, as more ants leave the anthill and follow the strategy -- the angle approaches zero, hence the ants walk more and more in a straight line.

During the Summer of 1996, we plan to tackle three problems. The first, and simplest, is to create an effective computer demonstration of Bruckstein's ant trails analysis. The demonstration will be an effective tool to teach others about differential games, and writing the demonstration will help us in our learning. The second challenge is to re-cast a problem recently investigated by Aboufadel (1996) -- what strategy does a baseball player use to catch a fly ball -- in the language of differential games in order to analyze the problem from a new direction. McBeath, et. al. (1995) demonstrated empirically that baseball players use a technique called the Linear Optical Trajectory (LOT) method. The idea is that the fielder moves in such a way as to keep constant the perceived angle made by the image of the baseball, home plate, and the player. Aboufadel proved algebraically that if the LOT method was, in fact, the strategy that fielders really use, then a number of qualitative statements made by McBeath et. al. about the LOT method were justified.

Our third, and most difficult, challenge is to consider the modeling of air combat between two planes as a differential game. Most of the theory of differential games has been done in two-dimensions, because it is easier. Air combat involves three-dimensions, and much of the work that has been done on this problem has restricted the airplanes to a fixed height above the ground, effectively returning the problem to two dimensions. There is also the issue of who is the pursuer and who is the evader when fighter pilots are trying to destroy each other. Grimm and Well (1990) have reviewed the literature and have found a number of areas that can be explored. In particular, we wish to create a three-dimensional model of air combat between two fighter pilots, building in a difference of speed, maneuverability, and weapon range between the two airplanes, along with the blinding effects of the position of the sun. The object will be to develop this model as a differential game, with a mathematical analysis leading to the optimal strategies for the two participants.

For more information about this project, contact Edward Aboufadel: