Оптимальная стратегия погони
Аннотация. Для решения многих задач в различных областях необходимо применять теорию дифференциальных игр. В статье проведен сравнительный анализ различных стратегий решения игр преследования, находящих наибольшее применение на практике, сделаны общие выводы о целесообразности каждой стратегии.
Ключевые слова: игры преследования, стратегия, кратчайший путь, оптимальное решение, неравномерность движения, алгоритм решения.
Содержание не найдено
ЛИТЕРАТУРА
1. Nahin, Paul J. (2012). Chases and Escapes: The Mathematics of Pursuit and Evasion, Princeton: Princeton University Press, ISBN 978-0-691-12514-5.
2. Borie, R.; Tovey, C.; Koenig, S. (2009). "Algorithms and Complexity Results for Pursuit–Evasion Problems". In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
3. Дубанов А. А. Задача преследования. Решение в системе вычислительной математики MathCAD // Информационные технологии, 2018. Т. 24. № 4. C. 251-255.
4. Айзекс Р. Дифференциальные игры. — М. : Мир, 1967.-480c.
5. Понтрягин Л. С. Линейная дифференциальная игра убегания // Тр. МИАН СССР. 1971. Т. 112. С. 30-63.
6. Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. — М. : Наука, 1974.-456c.
7. Бурдаков С. В., Сизов П. А. Алгоритмы управлением движения мобильным роботом в задаче преследования // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление. 2014. № 6 (210). С. 49–58.
8. Желнин Ю. Н. Линеаризованная задача преследования и уклонения на плоскости // Ученые записки ЦАГИ. 1977. Т. 8. № 3. С. 88–98.
9. Симакова Э. Н. Об одной дифференциальной игре преследования // Автоматика
В любой момент времени движение хищника происходит в направлении текущей позиции жертвы. Иными словами, для любого τ точка L(τ) лежит на касательной к кривой F(t) в точке t=τ.
Движение на опережение
Выбирается некоторый вектор единичной длины d, в направлении которого движется хищник до тех пор, пока не пересечётся с жертвой. Формально, ищутся такие вектор d и момент времени τ, что F(0)+Wτd=L(τ) .
Оптимальная стратегия
Докажем, что стратегия 'движение на опережение' оптимальна:
Пусть хищник, следуя иной стратегии, может догнать жертву в точке L(t0) за время t=t0. Тогда ему следует отправиться сразу в эту точку, потратив время . Следуя иной стратегии, хищник бежал бы по кривой, соединяющей точки F(0) и L(t0), в то время как сейчас он движется по отрезку, соединяющему эти точки. Поскольку пространство евклидово, длина кривой не меньше длины отрезка, потому и времени на движе