Homicidal chauffeur problem

From Wikipedia, the free encyclopedia

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 be indefatigable. 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?

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.

[edit] See also

• Variational calculus
• Level set method
• Apollonius pursuit problem
• Conway's Angel problem, another mathematical game which pits a powerful and maneuverable adversary against a highly resourceful but less powerful foe

[edit] External links

• History of the Homicidal Chauffeur Problem, presentation at the Colloqium dedicated to the 60th anniversary of Prof. Pierre Bernhard. (in Adobe PDF format)
• Homicidal Chauffeur Game. Computation of Level Sets of the Value Function