Переслідування-ухилення

Переслідування-ухилення (варіантами якого є поліціянти і грабіжники і пошук на графі) — це сімейство задач у математиці й інформатиці, в яких одна група намагається зловити членів іншої групи в певному середовищі. Ранні роботи з проблем такого виду моделювали середовище геометрично. В 1976 році Торренс Парсонс увів формулювання, в якому рухи обмежені графом. Геометричне формулювання здачі іноді називають безперервним переслідуванням-ухиленням, а формулювання на графі дискретним переслідуванням-ухиленням (іноді також пошуком на графі). Поточні дослідження зазвичай обмежені одним із цих двох формулювань.

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

В дискретному формулюванні задачі переслідування-ухилення середовище моделюється у вигляді графа.

Визначення задачі

Існує безліч варіантів переслідування-ухилення, хоча в них є багато спільних елементів. Типовий приклад такий (гра поліціянти і грабіжники): переслідувачі і переслідувані займають вершини графа. Противники ходять по черзі, і кожен хід полягає або у відмові від руху, або в русі уздовж ребра в сусідній вузол. Якщо переслідувач займе той самий вузол, що й переслідуваний, той вважається спійманим і видаляється з гри. Питання зазвичай ставиться так: як багато переслідувачів необхідно для захоплення всіх переслідуваних. Якщо переслідування завершується успіхом, граф називається виграшним графом поліціянта. В цьому випадку, одного переслідуваного можна завжди захопити за лінійний час від числа вершин n графа. Для захоплення r переслідуваних k переслідувачами потрібен час порядку rn, але точні межі для більш ніж одного переслідувача не відомі.

Часто правила руху змінюються зміною швидкості переслідуваних. Швидкість — це найбільше число ребер, на які переслідуваний може пройти за один хід. У наведеному вище прикладі переслідуваний має швидкість одиниця. Іншим екстремумом є концепція нескінченної швидкості, яка дозволяє переслідуваному рухатися в будь-який вузол, до якого існує шлях між початковою і кінцевою позицією, який не містить вузлів з переслідувачами. Аналогічно деякі варіанти надають переслідувачам «вертольоти», які дозволяють зробити хід на будь-яку вершину.

Інші варіанти нехтують обмеження, що переслідувачі і переслідувані мають перебувати у вузлі і дозволяють перебувати десь усередині ребра. Ці варіанти часто згадуються як задачі вимітання, тоді як попередні варіанти тоді потрапляють у категорію задач пошуку.

Варіації

Деякі варіанти еквівалентні важливим параметрам графа. Зокрема, знаходження числа переслідувачів, необхідних для захоплення одного переслідуваного з нескінченною швидкістю на графі G (коли переслідувачі і переслідуваний не обмежені пересуваннями хід за ходом, а можуть рухатися одночасно), еквівалентне знаходженню деревної ширини графа G, а виграшну стратегію для переслідуваного можна описати в термінах укриття в графі G. Якщо цей переслідуваний невидимий для переслідувачів, то задача еквівалентна знаходженню шляхової ширини або розділення вершин. Знаходження числа переслідувачів необхідних для захоплення одного невидимого переслідуваного в графі G за один хід еквівалентне знаходженню числа найменшої домінівної множини графа G, в припущенні, що переслідувачі можуть спочатку перебувати в будь-якому місці, де захочуть.

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

Складність

Складність деяких варіантів задач переслідування-ухилення, а саме, скільки переслідувачів потрібно, щоб очистити даний граф і як дане число переслідувачів мають рухатися по графу, щоб очистити його або з мінімальною сумою пройдених ними відстаней, або з мінімальним часом завершення гри, вивчали Німрод Мегіддо, Сейфолла Хакімі, Майкл Ґарей, Девід Джонсон і Христос Пападімітріу і Р. Борі, К. Тові і С. Кеніг.

Ігри переслідування-ухилення з декількома гравцями

Розв'язання ігор переслідування-ухилення з декількома гравцями також отримує дедалі більшу увагу. Див. статті Р. Відаля та ін., Чанга і Фурукави, Еспанії, Кіма і Састрі та посилання в цих статтях. Маркос А. М. Вієйра, Рамеш Говіндан і Гаурав С. Сукатмі запропонували алгоритм, який обчислює стратегію з мінімальним часом виконання для переслідувачів, щоб схопити всіх переслідуваних, коли всі гравці приймають оптимальне рішення, засноване на повному знанні. Цей алгоритм можна застосовувати також у випадках, коли переслідувані істотно швидші від переслідувачів. На жаль цей алгоритм не масштабується на значне число роботів. Щоб подолати цю проблему, Маркос А. М. Вієйра, Рамеш Говіндан і Гаурав С. Сукатмі розробили й реалізували алгоритм розбиття, де переслідувачі захоплюють переслідуваних розкладаючи гру на ігри з одним переслідуваним і декількома переслідувачами.

Неперервне формулювання

В неперервному формулюванні ігор переслідування-ухилення середовище моделюється геометрично, зазвичай набуваючи вигляду евклідової площини або іншого многовиду. Варіації гри можуть виставляти обмеження на маневреність гравців, такі як обмежені рамки швидкостей або прискорень. Можуть також використовуватися перешкоди.

Застосування

Одними з перших застосувань задачі переслідування-ухилення були системи керування ракетами. Задачі для цих систем сформулював Руфус Айзекс із корпорації RAND.

Див. також

• Задача про Ангела й Диявола
• Задача про водія-вбивцю
• Принцеса і Чудовисько (гра)
• Пошукова гра
• Поліційне число

Література

• Isaacs R. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. — New York : John Wiley & Sons, 1965. — 4 листопада.
• 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. — 4 листопада. Процитовано 2010-03-11.
• Ellis J., Sudborough I., Turner J. The vertex separation and search number of a graph // Information and Computation. — 1994. — Т. 113, вип. 1 (4 листопада). — С. 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 (4 листопада). — С. 236–245. — DOI:10.1016/j.tcs.2008.02.040.
• Kirousis M.; Papadimitriou C. Searching and pebbling // Theoretical Computer Science. — 1986. — Т. 42, вип. 2 (4 листопада). — С. 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 (4 листопада). — С. 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 (4 листопада).
  • Петросян Л.А., Рихсиев Б.Б. Преследование на плоскости. — Москва : «Наука», 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 (4 листопада). — С. 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 (4 листопада). — 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. — 4 листопада. — С. [1].
• Chern F. Chung, Tomonari Furukawa. A Reachability-Based Strategy for the Time-Optimal Control of Autonomous Pursuers // Engineering Optimization. — 2008. — Т. 40, вип. 1 (4 листопада).
• Joao P. Hespanha, Hyoun Jin Kim, Shankar Sastry. Multiple-agent probabilistic pursuit-evasion games. — 1999.