Преследование-уклонение

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

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

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

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

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

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

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

Варианты

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

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

Сложность

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

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

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

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

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

Если лев преследует человека с одинаковой скоростью, то ясно, что человек может уйти на плоскости или сфере, всегда двигаясь по прямой от льва. Когда оба заключены в круглый диск, казалось вероятным, что лев поймает человека. Безикович доказал в 1952 году, что у этого человека есть стратегия, позволяющая избежать пленения на неопределенный срок вопреки любой стратегии. ^{[ 5 ]}

Приложения

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

См. также

Примечания

^ Jump up to: ^а ^б Айзекс 1965 г.
^ Парсонс 1976
^ Эллис 1994
^ Бори 2009
^ Литтлвуд, Джон Эденсор (1988). Боллобас, Бела (ред.). Сборник Литтлвуда (переиздание, переиздание). Кембридж: Издательство Кембриджского университета. стр. 114–117. ISBN 978-0-521-33702-1 .

Ссылки

Айзекс, Р. (1965). Дифференциальные игры: математическая теория с приложениями к войне и преследованию, управлению и оптимизации . Нью-Йорк: Джон Уайли и сыновья. OCLC 489835778 .
Парсонс, Т.Д. (1976). «Преследование–уклонение в графе». Теория и приложения графов . Спрингер-Верлаг. стр. 426–441.
Бори, Р.; Тови, К.; Кениг, С. (2009). «Алгоритмы и результаты по сложности для задач преследования–уклонения» . В материалах Международной совместной конференции по искусственному интеллекту (IJCAI) . Проверено 11 марта 2010 г.
Эллис, Дж.; Садборо, И.; Тернер, Дж. (1994). «Разделение вершин и номер поиска графа» . Информация и вычисления . 113 (1): 50–79. дои : 10.1006/inco.1994.1064 .
Фомин Ф.В.; Тиликос, Д. (2008). «Аннотированная библиография по гарантированному поиску в графе» . Теоретическая информатика . 399 (3): 236–245. дои : 10.1016/j.tcs.2008.02.040 .
Кирусис, М.; Пападимитриу, К. (1986). «Поиски и камешки» . Теоретическая информатика . 42 (2): 205–218. дои : 10.1016/0304-3975(86)90146-5 .
Новаковски, Р.; Винклер, П. (1983). «Преследование от вершины к вершине в графе» . Дискретная математика . 43 (2–3): 235–239. дои : 10.1016/0012-365X(83)90160-7 .
Петросян, Леон (1993). «Дифференциальные игры преследования (Серия по оптимизации, том 2)». Мировой научный паб Co Inc. 2 .
Сеймур, П .; Томас, Р. (1993). «Поиск по графу и теорема о мин-максе для ширины дерева» . Журнал комбинаторной теории, серия B. 58 (1): 22–33. дои : 10.1006/jctb.1993.1027 .
Видаль; и др. (2002). «Вероятностные игры преследования–уклонения: теория, реализация и экспериментальная оценка» (PDF) . Транзакции IEEE по робототехнике и автоматизации . 18 (5): 662–669. дои : 10.1109/TRA.2002.804040 .
Маркос А.М. Виейра; Рамеш Говиндан и Гаурав С. Сукхатме. «Масштабируемое и практичное преследование-уклонение с помощью сетевых роботов». Журнал интеллектуальной сервисной робототехники : [2] .
Чунг и Фурукава (2008). «Стратегия, основанная на достижимости, для оптимального по времени управления автономными преследователями». Инженерная оптимизация . 40 (1): 67–93. Бибкод : 2008EnOp...40...67C . дои : 10.1080/03052150701593133 . S2CID 120015118 .
Эспанья; и др. (1999). «Многоагентные вероятностные игры преследования–уклонения». Материалы 38-й конференции IEEE по принятию решений и управлению . стр. 2432–2437.

[CITEREFIsaacs1965-1] Jump up to: ^а ^б Айзекс 1965 г.

[2] Парсонс 1976

[3] Эллис 1994

[4] Бори 2009

[5] Литтлвуд, Джон Эденсор (1988). Боллобас, Бела (ред.). Сборник Литтлвуда (переиздание, переиздание). Кембридж: Издательство Кембриджского университета. стр. 114–117. ISBN 978-0-521-33702-1 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]