Homicidal chauffeur problem

Last updated

In game theory, the homicidal chauffeur problem is a mathematical pursuit problem which pits a hypothetical runner, who can only move slowly, but is highly maneuverable, against the driver of a motor vehicle, which is much faster but far less maneuverable, who is attempting to run him down. Both runner and driver are assumed to never tire. The question to be solved is: under what circumstances, and with what strategy, can the driver of the car guarantee that he can always catch the pedestrian, or the pedestrian guarantee that he can indefinitely elude the car?

Contents

The problem is often used as an unclassified proxy for missile defense and other military targeting, allowing scientists to publish on it without security implications. [1]

The problem was proposed by Rufus Isaacs in a 1951 report [2] for the RAND Corporation, and in the book Differential Games. [3]

The homicidal chauffeur problem is a classic example of a differential game played in continuous time in a continuous state space. The calculus of variations and level set methods can be used as a mathematical framework for investigating solutions of the problem. Although the problem is phrased as a recreational problem, it is an important model problem for mathematics used in a number of real-world applications.

A discrete version of the problem was described by Martin Gardner (in his book Mathematical Carnival, chapter 16), where a squad car of speed 2 chases a crook of speed 1 on a rectangular grid, where the squad car but not the crook is constrained not to make left-hand turns or U-turns.

See also

Related Research Articles

<span class="mw-page-title-main">Discrete mathematics</span> Study of discrete mathematical structures

Discrete mathematics is the study of mathematical structures that can be considered "discrete" rather than "continuous". Objects studied in discrete mathematics include integers, graphs, and statements in logic. By contrast, discrete mathematics excludes topics in "continuous mathematics" such as real numbers, calculus or Euclidean geometry. Discrete objects can often be enumerated by integers; more formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics".

<span class="mw-page-title-main">Mathematical analysis</span> Branch of mathematics

Analysis is the branch of mathematics dealing with continuous functions, limits, and related theories, such as differentiation, integration, measure, infinite sequences, series, and analytic functions.

<span class="mw-page-title-main">Differential calculus</span> Area of mathematics; subarea of calculus

In mathematics, differential calculus is a subfield of calculus that studies the rates at which quantities change. It is one of the two traditional divisions of calculus, the other being integral calculus—the study of the area beneath a curve.

<span class="mw-page-title-main">Calculus of variations</span> Differential calculus on function spaces

The calculus of variations is a field of mathematical analysis that uses variations, which are small changes in functions and functionals, to find maxima and minima of functionals: mappings from a set of functions to the real numbers. Functionals are often expressed as definite integrals involving functions and their derivatives. Functions that maximize or minimize functionals may be found using the Euler–Lagrange equation of the calculus of variations.

<span class="mw-page-title-main">Stochastic calculus</span> Calculus on stochastic processes

Stochastic calculus is a branch of mathematics that operates on stochastic processes. It allows a consistent theory of integration to be defined for integrals of stochastic processes with respect to stochastic processes. This field was created and started by the Japanese mathematician Kiyosi Itô during World War II.

<span class="mw-page-title-main">Optimal control</span> Mathematical way of attaining a desired output from a dynamic system

Optimal control theory is a branch of mathematical optimization that deals with finding a control for a dynamical system over a period of time such that an objective function is optimized. It has numerous applications in science, engineering and operations research. For example, the dynamical system might be a spacecraft with controls corresponding to rocket thrusters, and the objective might be to reach the moon with minimum fuel expenditure. Or the dynamical system could be a nation's economy, with the objective to minimize unemployment; the controls in this case could be fiscal and monetary policy. A dynamical system may also be introduced to embed operations research problems within the framework of optimal control theory.

<span class="mw-page-title-main">Richard E. Bellman</span> American mathematician

Richard Ernest Bellman was an American applied mathematician, who introduced dynamic programming in 1953, and made important contributions in other fields of mathematics, such as biomathematics. He founded the leading biomathematical journal Mathematical Biosciences.

<span class="mw-page-title-main">Differential equation</span> Type of functional equation (mathematics)

In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, and the differential equation defines a relationship between the two. Such relations are common; therefore, differential equations play a prominent role in many disciplines including engineering, physics, economics, and biology.

<span class="mw-page-title-main">Ennio de Giorgi</span> Italian mathematician

Ennio De Giorgi, a member of the House of Giorgi, was an Italian mathematician who worked on partial differential equations and the foundations of mathematics.

Hilbert's twentieth problem is one of the 23 Hilbert problems set out in a celebrated list compiled in 1900 by David Hilbert. It asks whether all boundary value problems can be solved.

<span class="mw-page-title-main">Lawrence C. Evans</span> American mathematician

Lawrence Craig Evans is an American mathematician and Professor of Mathematics at the University of California, Berkeley.

Pursuit–evasion is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early work on problems of this type modeled the environment geometrically. In 1976, Torrence Parsons introduced a formulation whereby movement is constrained by a graph. The geometric formulation is sometimes called continuous pursuit–evasion, and the graph formulation discrete pursuit–evasion. Current research is typically limited to one of these two formulations.

Calculus is a branch of mathematics focused on limits, functions, derivatives, integrals, and infinite series. This subject constitutes a major part of contemporary mathematics education. Calculus has widespread applications in science, economics, and engineering and can solve many problems for which algebra alone is insufficient.

In mathematics, secondary calculus is a proposed expansion of classical differential calculus on manifolds, to the "space" of solutions of a (nonlinear) partial differential equation. It is a sophisticated theory at the level of jet spaces and employing algebraic methods.

Rufus Philip Isaacs was a game theorist especially prominent in the 1950s and 1960s with his work on differential games.

A princess and monster game is a pursuit–evasion game played by two players in a region.

In game theory, differential games are a group of problems related to the modeling and analysis of conflict in the context of a dynamical system. More specifically, a state variable or variables evolve over time according to a differential equation. Early analyses reflected military interests, considering two actors—the pursuer and the evader—with diametrically opposed goals. More recent analyses have reflected engineering or economic considerations.

A search game is a two-person zero-sum game which takes place in a set called the search space. The searcher can choose any continuous trajectory subject to a maximal velocity constraint. It is always assumed that neither the searcher nor the hider has any knowledge about the movement of the other player until their distance apart is less than or equal to the discovery radius and at this very moment capture occurs. As mathematical models, search games can be applied to areas such as hide-and-seek games that children play or representations of some tactical military situations. The area of search games was introduced in the last chapter of Rufus Isaacs' classic book "Differential Games" and has been developed further by Shmuel Gal and Steve Alpern. The princess and monster game deals with a moving target.

Mathematics is a broad subject that is commonly divided in many areas that may be defined by their objects of study, by the used methods, or by both. For example, analytic number theory is a subarea of number theory devoted to the use of methods of analysis for the study of natural numbers.

<i>Chases and Escapes</i> Mathematics book on pursuit-evasion games

Chases and Escapes: The Mathematics of Pursuit and Evasion is a mathematics book on continuous pursuit–evasion problems. It was written by Paul J. Nahin, and published by the Princeton University Press in 2007. It was reissued as a paperback reprint in 2012. The Basic Library List Committee of the Mathematical Association of America has rated this book as essential for inclusion in undergraduate mathematics libraries.

References

  1. Becker, A. T., & Garcia, J. (2018, January 22). Wolfram Demonstrations Project. The Homicidal Chauffeur Problem. https://demonstrations.wolfram.com/TheHomicidalChauffeurProblem/
  2. R. Isaacs, Games of Pursuit, RAND Corporation (1951)
  3. R. Isaacs, Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization, John Wiley & Sons, New York (1965), PP 349350.