Задача переслідування

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

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

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

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

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

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

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

Варіації

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

Настільна гра ^[en] є варіантом задачі переслідування-ухилення.

Складність

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

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

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

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

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

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

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

Див. також

• Принцеса і Чудовисько (гра)
• (Пошукова гра)
• (Поліційне число)

Примітки

1. Isaacs, 1965.
2. Parsons, 1976.
3. Ellis, Sudborough, Turner, 1994.
4. Borie, Tovey, Koenig, 2009.
5. Vidal, Shakernia, Kim, Shim, Sastry, 2002, с. 662–669.
6. Chung, Furukawa, 2008, с. 67-93.
7. Hespanha, Kim, Sastry, 1999, с. 2432–2437.
8. Vieira, Govindan, Sukhatme, 2009.

Література

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