Homicidal chauffeur problem

Homicidal chauffeur problem

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.

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

* 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

External links

* [http://home.imm.uran.ru/kumkov/HHCP/nice4.pdf History of the Homicidal Chauffeur Problem] , presentation at the Colloqium dedicated to the 60th anniversary of Prof. Pierre Bernhard. (in Adobe PDF format)
* [http://www.springerlink.com/content/f466qu1820h00330/ Analytical study of a case of the homicidal chauffeur game problem]
* [http://citeseer.ist.psu.edu/350554.html Homicidal Chauffeur Game. Computation of Level Sets of the Value Function]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Angel problem — The angel problem is a question in game theory proposed by John Horton Conway. The game is commonly referred to as the Angels and Devils game. The game is played by two players called the angel and the devil. It is played on an infinite… …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • Differential game — 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. The problem usually consists of two actors, a pursuer and an evader, with conflicting goals. The… …   Wikipedia

  • performing arts — arts or skills that require public performance, as acting, singing, or dancing. [1945 50] * * * ▪ 2009 Introduction Music Classical.       The last vestiges of the Cold War seemed to thaw for a moment on Feb. 26, 2008, when the unfamiliar strains …   Universalium

  • List of Marvel Family enemies — Through his adventures, Fawcett Comics/DC Comics superhero Captain Marvel and his Marvel Family gained a host of enemies, including the following: Contents 1 Acrobat 2 Adolf Hitler 3 Amoeba Family …   Wikipedia

  • List of Murder, She Wrote episodes — This is a list of Murder, She Wrote episodes in the order that they originally aired on CBS. Many of the episodes took place in either Jessica s hometown of Cabot Cove or in New York, but her travels promoting books or visiting relatives and… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”