Введение

Математическая игра/задача

Преследование-уклонение (варианты которого известны как «копы и грабители» и поиск по графу) — это семейство задач в математике и информатике, в котором одна группа пытается выследить членов другой группы в определенной среде. Ранние работы по задачам этого типа моделировали среду геометрически. В 1976 году Торренс Парсонс предложил формулировку, в которой движение ограничено графом. Геометрическую формулировку иногда называют непрерывным преследованием-уклонением, а графовую формулировку — дискретным преследованием-уклонением (также известным как поиск по графу). Современные исследования обычно ограничиваются одной из этих двух формулировок.

Дискретное формулирование

В дискретной формулировке задачи преследования и уклонения окружающая среда моделируется как граф.

Определение проблемы

Существует бесчисленное множество возможных вариантов преследования и уклонения, хотя они часто имеют много общих элементов. Типичный, базовый пример выглядит следующим образом (игры в «полицейских и грабителей»): преследователи и уклоняющиеся занимают вершины графа. Обе стороны ходят по очереди, каждый участник на своем ходу либо остается на месте, либо перемещается по ребру к смежной вершине. Если преследователь занимает ту же вершину, что и уклоняющийся, то уклоняющийся захвачен и удален из графа. Обычно задают вопрос, сколько преследователей необходимо для гарантированного захвата всех уклоняющихся. Если одного преследователя достаточно, граф называется графом, в котором побеждает полиция. В этом случае одиночного уклоняющегося всегда можно захватить за время, линейное от числа n вершин графа. Захват r уклоняющихся с помощью k преследователей может занять порядка r n времени, но точные границы для более чем одного преследователя до сих пор неизвестны. Часто правила движения изменяются путем изменения скорости уклонения. Эта скорость – максимальное количество ребер, по которым может переместиться уклоняющийся за один ход. В приведенном выше примере уклоняющиеся имеют скорость, равную единице. На другом полюсе находится концепция бесконечной скорости, которая позволяет уклоняющемуся перемещаться в любую вершину графа, при условии, что существует путь между его начальной и конечной позициями, не содержащий вершин, занятых преследователями. Аналогично, в некоторых вариантах преследователи оснащены «вертолетами», позволяющими им перемещаться в любую вершину на своем ходу. Другие варианты отменяют ограничение, согласно которому преследователи и уклоняющиеся всегда должны занимать вершину, и допускают возможность их расположения где-либо на ребре. Эти варианты часто называют задачами «прочесывания», в то время как предыдущие варианты относятся к категории задач «поиска».

Варианты

Несколько вариантов эквивалентны важным параметрам графа. В частности, определение количества преследователей, необходимого для захвата одного уклоняющегося с бесконечной скоростью в графе G (когда преследователи и уклоняющийся не обязаны двигаться поочередно, а двигаются одновременно), эквивалентно определению древовидной ширины G, а выигрышная стратегия для уклоняющегося может быть описана с точки зрения убежища в G. Если этот уклоняющийся невидим для преследователей, то задача эквивалентна определению ширины пути или разделения вершин. Определение количества преследователей, необходимого для захвата одного невидимого уклоняющегося в графе G за один ход (то есть за одно перемещение преследователей от их начального расположения), эквивалентно определению размера минимального доминирующего множества G, при условии, что преследователи могут изначально располагаться где угодно (это последнее предположение справедливо, когда предполагается, что преследователи и уклоняющийся двигаются поочередно). Настольная игра "Скотланд-Ярд" является вариантом задачи преследования и уклонения.

Сложность

Сложность нескольких вариантов задач "преследование-уклонение", а именно, какое количество преследователей необходимо для гарантированного захвата на заданном графе и как заданное число преследователей должно перемещаться по графу для его гарантированного захвата с минимальной суммой пройденных расстояний или минимальным временем выполнения задачи, была изучена Нимродом Мегиддо, С. Л. Хакими, Майклом Р. Гареем, Дэвидом С. Джонсоном и Христосом Х. Пападимитриу (J. ACM 1988), а также Р. Бори, С. Тови и С. Коенигом.

Многопользовательские игры с преследованием и уклонением от ответственности

Решающим многопользовательским играм преследования и уклонения также уделено повышенное внимание; см. R Vidal et al., Chung and Furukawa, Hespanha et al. и ссылки в них. Маркос А. М. Виейра, Рамеш Говиндан и Гаурав С. Сухатме предложили алгоритм, вычисляющий стратегию минимального времени завершения для преследователей, позволяющую захватить всех уклоняющихся при условии, что все игроки принимают оптимальные решения, основываясь на полной информации. Этот алгоритм также применим в случае, когда уклоняющиеся значительно быстрее преследователей. К сожалению, эти алгоритмы не масштабируются для большого числа роботов. Для решения этой проблемы Маркос А. М. Виейра, Рамеш Говиндан и Гаурав С. Сухатме разработали и реализовали алгоритм разделения, при котором преследователи захватывают уклоняющихся, разбивая игру на несколько подзадач типа "несколько преследователей против одного уклоняющегося".

Непрерывная формулировка

В непрерывной формулировке игр преследования-избегания, среда моделируется геометрически, как правило, в виде евклидовой плоскости или другого многообразия. Варианты игры могут накладывать ограничения на маневренность игроков, такие как ограниченный диапазон скорости или ускорения. Также могут использоваться препятствия. Если лев преследует человека с одинаковой скоростью, то очевидно, что человек может убежать на плоскости или сфере, постоянно двигаясь по прямой линии от льва. Однако, когда оба находятся внутри круглой области, может показаться, что лев сможет поймать человека. Бесикович доказал в 1952 году, что у человека есть стратегия, позволяющая бесконечно долго избегать захвата, независимо от стратегии льва.

Приложения

Одним из первых применений задачи преследования и уклонения стали системы наведения ракет, разработанные Руфусом Айзексом в корпорации RAND.