NP-hardness of collective pursuiting optimization problems

S.V. Pashko

Abstract


The differential pursuitevasion games on a plane are considered. A group of pursuers is created for every evader in a game. The optimization problem of group composition has been formulated. The theorems about NP-completeness and NP-hardness of pursuit optimization problems are proved. Numerical methods for solving such optimization problems are constructed. Numerical experiments have demonstrated high efficiency of the methods.

Prombles in programming 2014; 2-3: 44-51


References


Айзекс Р. Дифференциальные игры. – М.: Мир, 1967. – 480 с.

Parsons T.D. Pursuit – Evasion in a graph. Theory and Applications of Graphs. Springer-Verlag, 1976. – P. 426–441.

Благодатских А.И., Петров Н.Н. Конфликтное взаимодействие групп управляемых объектов. – Ижевск: Удмуртский университет,

– 266 с.

Чикрий А.А. Конфликтно управляемые процессы. – Киев: Наук. думка, 1992. – 384 с.

Borie R., Tovey C., Koenig S. Algorithms and Complexity Results for Pursuit-Evasion Problems // Proceedings of the International Joint

Conference on Artificial Intelligence (IJCAI), 2009. – P. 59–66.

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416 с.

Ибрагимов Г.И., Рихсиев Б.Б. О некоторых достаточных условиях оптимальности времени преследования в дифференциальной игре со многими преследующими // Автоматика и телемеханика. – 2006. – № 4. – С. 16–24.

Иванов Р.П., Ледяев Ю.С. Оптимальность времени преследования в дифференциальной игре многих объектов с простыми движениями // Труды МИАН СССР. Том 158. – М.: МИАН СССР, 1981. – С. 87–97.

Пашко С.В. Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости // Проблемы управления и информатики. – 2012. – № 6. – С. 30–43.

Петросян Л.А., Томский Г.В. Геометрия простого преследования. – Новосибирск: Наука, 1983. – 140 с.

Рихсиев Б.Б. Дифференциальные игры с простыми движениями. – Ташкент: ФАН, 1989. – 232 с.

Гордон А.Я. Один алгоритм решения минимаксной задачи о назначениях // Исследования по дискретной оптимизации. – М.: Наука, 1976. – С. 327–333.

Пашко С.В. Сложность задач оптимизации преследования на плоскости // Проблемы управления и информатики. – 2013. – № 3. – С. 27–39.

Пашко С.В., Яловец А.Л. Численные методы решения задач оптимизации преследования // Проблеми програмування. – 2013. – № 4. – С. 74–85


Refbacks

  • There are currently no refbacks.