Уклонение от преследования (варианты которого называются полицейскими, грабителями и поиском в графах ) - это семейство задач в математике и информатике, в которых одна группа пытается выследить членов другой группы в окружающей среде. Ранние работы над проблемами этого типа моделировали среду геометрически. [1] В 1976 году Торренс Парсонс ввел формулировку, согласно которой движение ограничивается графом . [2] Геометрическая формулировка иногда называется непрерывным уклонением от преследования , а графовая формулировка дискретным уклонением от преследования (также называемаяпоиск по графу ). Текущие исследования обычно ограничиваются одним из этих двух составов.
Дискретная формулировка
В дискретной постановке задачи преследования-уклонения среда моделируется в виде графа.
Определение проблемы
Существует бесчисленное множество возможных вариантов преследования-уклонения, хотя они, как правило, имеют много общих элементов. Типичный, базовый пример выглядит следующим образом (игры с полицейскими и грабителями): Преследователи и убегающие занимают узлы графа. Две стороны совершают попеременные повороты, при которых каждый элемент либо остается на месте, либо движется вдоль края к соседнему узлу. Если преследователь занимает тот же узел, что и убегающий, убегающий захватывается и удаляется с графа. Обычно задается вопрос, сколько преследователей необходимо, чтобы в конечном итоге обеспечить поимку всех уклоняющихся. Если достаточно одного преследователя, то этот граф называется графом выигрышных копий . В этом случае один убегающий всегда может быть захвачен во времени, линейном по отношению к количеству n узлов графа. Захват г неплательщиков с К преследователей можно взять в порядке гп времени , а также, но точные оценки для более чем одного преследователя до сих пор неизвестны.
Часто правила передвижения изменяются путем изменения скорости убегающих. Эта скорость - максимальное количество ребер, по которым убегающий может пройти за один ход. В приведенном выше примере скорость убегающих равна единице. Другой крайностью является концепция бесконечной скорости, которая позволяет убегающему перемещаться к любому узлу в графе, пока существует путь между его исходной и конечной позициями, который не содержит узлов, занятых преследователем. Точно так же некоторые варианты вооружают преследователей «вертолетами», которые позволяют им в свой ход переместиться в любую вершину.
Другие варианты игнорируют ограничение, согласно которому преследователи и убегающие всегда должны занимать узел, и допускают возможность их расположения где-то вдоль края. Эти варианты часто называют проблемами поиска, тогда как предыдущие варианты подпадают под категорию задач поиска.
Варианты
Несколько вариантов эквивалентны важным параметрам графика. В частности, найти число преследователей , необходимых для захвата одного убегающих с бесконечной скоростью в графе G (когда преследователи и убегающие не ограничены , чтобы перейти от поворота к повороту, но двигаться одновременно) эквивалентны нахождением древесной ширины из G , и выигрышной стратегия убегающего может быть описана в терминах убежища в G . Если этот убегающий невидим для преследователей, тогда задача эквивалентна нахождению ширины пути или разделения вершин. [3] В поисках количество преследователей , необходимых для захвата одного невидимых убегающего в графе G в один ходе (то есть, одно движения по преследователям от их первоначального развертывания) эквивалентно нахождением размера минимального доминирующего множества из G , предполагая, что преследователи могут сначала развернуться, где захотят (это более позднее предположение справедливо, когда предполагается, что преследователи и убегающие перемещаются по очереди).
Настольная игра Скотланд-Ярд - это вариант задачи преследования-уклонения.
Сложность
Сложность нескольких вариантов преследования-уклонения, а именно, сколько преследователей необходимо, чтобы очистить данный граф, и как данное количество преследователей должно перемещаться по графу, чтобы очистить его, либо с минимальной суммой их пройденных расстояний, либо с минимальным временем выполнения задачи , был изучен Нимродом Мегиддо , С.Л. Хакими , Майклом Р. Гэри , Дэвидом С. Джонсоном и Христосом Х. Пападимитриу (J. ACM 1988), а также Р. Бори, К. Тови и С. Кенигом. [4]
Многопользовательские игры с преследованием и уклонением
Решению многопользовательских игр с преследованием и уклонением также уделяется повышенное внимание. См. R Vidal et al., Chung and Furukawa [1] , Hespanha et al. и ссылки в нем. Маркос А.М. Виейра, Рамеш Говиндан и Гаурав С. Сухатме предоставили алгоритм, который вычисляет стратегию минимального времени завершения для преследователей, чтобы захватить всех уклоняющихся, когда все игроки принимают оптимальные решения, основанные на полном знании. Этот алгоритм также можно применить, когда убегающие значительно быстрее преследователей. К сожалению, эти алгоритмы не масштабируются за пределы небольшого числа роботов. Чтобы преодолеть эту проблему, Маркос А.М. Виейра, Рамеш Говиндан и Гаурав С. Сухатме разрабатывают и реализуют алгоритм разделения, в котором преследователи захватывают убегающих, разбивая игру на несколько игр с одним преследователем и одним убегающим.
Непрерывная формулировка
В непрерывной формулировке игр преследования и уклонения среда моделируется геометрически, обычно принимая форму евклидовой плоскости или другого многообразия . Варианты игры могут налагать на игроков ограничения маневренности, такие как ограниченный диапазон скорости или ускорения. Также могут использоваться препятствия.
Приложения
Одним из первых применений проблемы преследования и уклонения были системы наведения ракет, разработанные Руфусом Айзексом из корпорации RAND. [1]
Смотрите также
Заметки
Рекомендации
- Айзекс, Р. (1965). «Дифференциальные игры: математическая теория с приложениями к войне и преследованию, управлению и оптимизации». Нью-Йорк: Джон Вили и сыновья. OCLC 489835778 . Цитировать журнал требует
|journal=
( помощь )CS1 maint: ref дублирует значение по умолчанию ( ссылка ) - Парсонс, Т. Д. (1976). «Преследование-уклонение в графе». Теория и приложения графов . Springer-Verlag. С. 426–441.
- Borie, R .; Тови, С .; Кениг, С. (2009). «Алгоритмы и результаты сложности для задач преследования-уклонения» . В материалах Международной совместной конференции по искусственному интеллекту (IJCAI) . Проверено 11 марта 2010 .
- Ellis, J .; Sudborough, I .; Тернер, Дж. (1994). «Разделение вершин и поисковый номер графа». Информация и вычисления . 113 (1): 50–79. DOI : 10.1006 / inco.1994.1064 .
- Фомин Ф.В. Тиликос, Д. (2008). «Аннотированная библиография по гарантированному поиску графов». Теоретическая информатика . 399 (3): 236–245. DOI : 10.1016 / j.tcs.2008.02.040 .
- Kirousis, M .; Пападимитриу, К. (1986). «Поиск и галька». Теоретическая информатика . 42 (2): 205–218. DOI : 10.1016 / 0304-3975 (86) 90146-5 .
- Новаковски, Р .; Винклер, П. (1983). «Преследование от вершины к вершине в графе». Дискретная математика . 43 (2–3): 235–239. DOI : 10.1016 / 0012-365X (83) 90160-7 .
- Петросян, Леон (1993). «Дифференциальные игры преследования (серия по оптимизации, том 2)». World Scientific Pub Co Inc . 2 .
- Сеймур, П .; Томас Р. (1993). «Поиск в графах и теорема о минимуме и максимуме для ширины дерева». Журнал комбинаторной теории, серии B . 58 (1): 22–33. DOI : 10.1006 / jctb.1993.1027 .
- Видаль; и другие. (2002). «Вероятностные игры преследования-уклонения: теория, реализация и экспериментальная оценка» (PDF) . IEEE Transactions по робототехнике и автоматизации . 18 (5): 662–669. DOI : 10,1109 / TRA.2002.804040 .
- Маркос А.М. Виейра; Рамеш Говиндан и Гаурав С. Сухатме. «Масштабируемое и практичное уклонение от преследования с помощью сетевых роботов». Журнал интеллектуальной сервисной робототехники : [2] .
- Чанг и Фурукава (2008). «Стратегия на основе достижимости для оптимального по времени управления автономными преследователями». Инженерная оптимизация . 40 (1): 67–93. Bibcode : 2008EnOp ... 40 ... 67C . DOI : 10.1080 / 03052150701593133 . S2CID 120015118 .
- Hespanha; и другие. (1999). «Многоагентные вероятностные игры преследования-уклонения». Труды 38-й конференции IEEE по решениям и контролю . С. 2432–2437.