In 1889, Andrey Andreevich Markov published a paper in "Soobscenija Charkovskogo Matematiceskogo Obscestva"' where he considered several mathematical problems related to the design of railways. The simplest among these problems (and the first one in course of the presentation) is described as follows. Find a minimum length curve between two points in the plane provided that the curvature radius of the curve should not be less than a given quantity and the tangent to the curve should have a given direction at the initial point.
In 1951, Rufus Philip Isaacs presented his first Rand Corporation Report on differential game theory where he stated and lined out a solution to the "homicidal chauffeur" problem. In that problem, a "car" with a bounded turning radius and a constant magnitude of the linear velocity tries as soon as possible to approach a "pedestrian" striving to avoid the encounter. At the initial time, the direction of the car velocity is given.
In 1957, in American Journal of Mathematics, Lester Eli Dubins considered a problem in the plane on finding among smooth curves of bounded curvature a minimum length curve connecting two given points provided that the outgoing direction at the first point and incoming direction at the second point are specified.
Obviously, if one considers a particular case of Isaacs' problem when the "pedestrian" is immovable, then the "car" will minimize the length of the curve of bounded curvature. The arising task coincides with the problem considered by A.A. Markov. The difference from the problem by L.E. Dubins is in the absence of a specified direction at the incoming point. The fixation of incoming and outgoing directions presents in the other three problems by A.A. Markov. However, they contain additional conditions inherent to the railway construction.
In such a way the notion of a "car", which moves only forward and has bounded turning radius, appeared. Later, more sophisticated models with more realistic moving objects like e.g. controlled wheel, bicycle, car with two chassis, and car with a trailer were developed. Optimization problems related to such more complicated models are extremely difficult. The simplest models serve as "samples" showing where the situation is easy and where it becomes complex.
The paper by A.A. Markov was long little-known. Probably, there were M.G. Krein and A.A. Nudelman who focused attention on it in their book "Problema momentov Markova i exstremal'nye zadachi", Moskwa, Nauka, 1973 (pages 32–36) translated as M.G. Krein and A.A. Nudel'man "The Markov Moment Problem and Extremal Problems", American Mathematical Society, 1977 (pages 17–20).
V.S. Patsko, V.L. Turova
Markov, A. A. Some examples of the solution of a special kind of problem on greatest and least quantities. Soobscenija Charkovskogo Matematiceskogo Obscestva, Vol. 2-1 (No. 5,6), 250–276 (in Russian).
markov_1889.pdf — PDF-file (17 MB)
markov_1889.djvu — DJVU-file (920 KB)