Задача о водителе-убийце

В теории игр задача о водителе-убийце — это математическая задача преследования, в которой гипотетический убегающий, который может двигаться медленно, но маневренно, пытается уйти от водителя, ведущего машину куда быстрее, но существенно ограниченного в маневре. Предполагается, что оба, убегающий и водитель, никогда не устают. Вопрос ставится так: при каких обстоятельствах и используя какую стратегию водителю удастся догнать убегающего или убегающий сможет избегать встречи бесконечно долго?

Задача предложена Руфусом Айзексом в его книге Дифференциальные игры[1].

Задача о водителе-убийце является классическим примером дифференциальной игры, которая играется в непрерывное время в непрерывном пространстве состояний. Методы вариационного исчисления и уровня можно использовать в качестве математического каркаса для исследования решений задачи. Хотя задача декларируется занимательной, для математиков она является важной задачей моделирования и применяется во многих задачах реального мира.

Надо отметить, что сам Айзекс вместо «водителя» и «пешехода» подразумевал торпеду и увёртывающийся от неё небольшой катер[2].

Дискретная версия задачи описана Мартином Гарднером в его книге Математические новеллы (глава 18). В этой постановке квадратный автомобиль на прямоугольной решётке со скоростью 2 преследует бандита, имеющего скорость 1, но автомобиль не имеет право делать левые повороты или переходить к движению в противоположном направлении (поворот на 180 градусов)[3].