PROFILBARU.COM

Преследование-уклонение (вариантами которого являются полицейские и грабители и поиск на графе) — семейство задач в математике и информатике, в которых одна группа пытается поймать членов другой группы в определённой среде. Ранние работы по проблемам такого вида моделировали среду геометрически^[1]. В 1976 году Торренс Парсонс ввёл формулировку, в которой движения ограничены графом^[2]. Геометрическая формулировка иногда называется непрерывным преследованием-уклонением, а формулировка на графе — дискретным преследованием-уклонением (иногда также поиском на графе). Текущие исследования обычно ограничены одной из этих двух формулировок.

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

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

Определение задачи

Существует бесчисленно много вариантов преследования-уклонения, хотя они стремятся разделять многие элементы. Типичный базовый пример такой задачи — игра «полицейские и грабители». Преследователи и преследуемые занимают вершины графа. Противники ходят поочерёдно, и каждый ход состоит либо из отказа от движения, либо из движения вдоль ребра в соседний узел. Если преследователь занимает тот же узел, что и преследуемый, тот считается схваченным и удаляется из игры. Вопрос обычно ставится так: как много преследователей необходимо для захвата всех преследуемых? Если преследование завершается успехом, граф называется выигрышным графом полицейского. В этом случае, один преследуемый может быть всегда захвачен за линейное время от числа вершин n графа. Захват r преследуемых k преследуемыми происходит за время порядка rn, но точные границы для более чем одного преследователя не известны.

Часто правила движения меняются путём изменения скорости преследуемых. Скорость — это максимальное число рёбер, на которые преследуемый может пройти за один ход. В примере выше преследуемый имеет скорость равную единице. Другим экстремумом является концепция бесконечной скорости, которая позволяет преследуемому двигаться в любой узел, в который существует путь между начальной и конечной позицией, который не содержит узлов с преследователями. Аналогично некоторые варианты снабжают преследователей «вертолётами», которые позволяют сделать ход на любую вершину.

Другие варианты игнорируют ограничения, что преследователи и преследуемые должны находиться в узле, и позволяют находиться где-то внутри ребра. Эти варианты часто упоминаются как задачи выметания, в то время как предыдущие варианты тогда попадают в категорию задач поиска.

Вариации

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

Настольная игра «Скотланд-Ярд»^[англ.] является вариантом задачи преследования-уклонения.

Сложность

Сложность некоторых вариантов задач преследования-уклонения, а именно, сколько преследователей необходимо для очистки данного графа и как данное число преследователей должны двигаться по графу, чтобы очистить его либо с минимальной суммой их пройденных расстояний, либо с минимальным временем завершения игры, изучали Нимрод Мегиддо, С. Л. Хакими, Майкл Р. Гарей, Дэвид С. Джонсон и Христос Х. Пападимитриу и Р. Бори, К. Тови и С. Кёниг^[4].

Игры преследования-уклонения с несколькими игроками

Решение игр преследования-уклонения с несколькими игроками также получает возрастающее внимание. См. статьи Р. Видаля и др.^[5], Чанга и Фурукавы^[6], Еспании, Кима и Састри^[7] и ссылки в этих статьях. Маркос А. М. Виейра, Рамеш Говиндан и Гаурав С. Сукатми^[8] предложили алгоритм, который вычисляет стратегию с минимальным временем выполнения для преследователей, чтобы схватить всех преследуемых, когда все игроки делают оптимальное решение, основанное на полном знании. Этот алгоритм можно применять также в случаях, когда преследуемые существенно быстрее преследователей. К сожалению этот алгоритм не масштабируется далее, чем на небольшое число роботов. Чтобы преодолеть эту проблему, Маркос А. М. Виейра, Рамеш Говиндан и Гаурав С. Сукатми разработали и реализовали алгоритм разбиения, где преследователи захватывают преследуемых путём разложения игры на игры с одним преследуемым и несколькими преследователями.

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

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

Приложения

Одним из первых приложений задачи преследования-уклонения были системы управления ракетами. Задачи для этих систем сформулировал Руфус Айзекс из корпорации RAND^[1].

См. также

Примечания

↑ ¹ ² Isaacs, 1965.
↑ Parsons, 1976.
↑ Ellis, Sudborough, Turner, 1994.
↑ Borie, Tovey, Koenig, 2009.
↑ Vidal, Shakernia, Kim, Shim, Sastry, 2002, с. 662–669.
↑ Chung, Furukawa, 2008, с. 67—93.
↑ Hespanha, Kim, Sastry, 1999, с. 2432–2437.
↑ Vieira, Govindan, Sukhatme, 2009.

Литература

Isaacs R. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. — New York: John Wiley & Sons, 1965.
Torrence D. Parsons. Pursuit-evasion in a graph // Theory and Applications of Graphs. — Springer-Verlag, 1976. — С. 426–441.
Richard Borie, Craig Tovey, Sven Koenig. Algorithms and Complexity Results for Pursuit-Evasion Problems. — 2009.
Ellis J., Sudborough I., Turner J. The vertex separation and search number of a graph // Information and Computation. — 1994. — Т. 113, вып. 1. — С. 50–79. — doi:10.1006/inco.1994.1064.
Fomin F.V., Thilikos D. An annotated bibliography on guaranteed graph searching // Theoretical Computer Science. — 2008. — Т. 399, вып. 3. — С. 236–245. — doi:10.1016/j.tcs.2008.02.040.
Kirousis M.; Papadimitriou C. Searching and pebbling // Theoretical Computer Science. — 1986. — Т. 42, вып. 2. — С. 205–218. — doi:10.1016/0304-3975(86)90146-5.
Nowakowski R., Winkler P. Vertex-to-vertex pursuit in a graph // Discrete Mathematics. — 1983. — Т. 43, вып. 2–3. — С. 235–239. — doi:10.1016/0012-365X(83)90160-7.
Petrosjan. Differential Games of Pursuit. — World Scientific Pub Co Inc., 1993. — Т. 2. — (Series on Optimization). — ISBN 978-9810209797.
- Петросян Л.А. Дифференциальные игры преследования // Соросовский Образовательный Журнал. — 1995. — № 1.
- Петросян Л.А., Рихсиев Б.Б. Преследование на плоскости. — Москва: «Наука», 1961. — (Популярные лекции по математике). — ISBN 5-02-014154-2.
Seymour P., Thomas R. Graph searching, and a min-max theorem for tree-width // Journal of Combinatorial Theory, Series B. — 1993. — Т. 58, вып. 1. — С. 22–33. — doi:10.1006/jctb.1993.1027.
Rene Vidal, Omid Shakernia, H. Jin Kim, David Hyunchul Shim, Shankar Sastry. Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation // IEEE Transactions on Robotics and Automation. — 2002. — Т. 18, вып. 5. — doi:10.1109/TRA.2002.804040.
Marcos A. M. Vieira, Ramesh Govindan, Gaurav S. Sukhatme. Scalable and Practical Pursuit-Evasion with Networked Robots // Journal of Intelligent Service Robotics Special Issue on Networked Robots. — 2009. — С. [1].
Chern F. Chung, Tomonari Furukawa. A Reachability-Based Strategy for the Time-Optimal Control of Autonomous Pursuers // Engineering Optimization. — 2008. — Т. 40, вып. 1.
Joao P. Hespanha, Hyoun Jin Kim, Shankar Sastry. Multiple-agent probabilistic pursuit-evasion games. — 1999.