Чейзинг после движущейся цели?

Предположим, что у вас есть мир с двумя игроками в нем chaser и цель. Предположим, что охотник движется немного быстрее цели. Если вы охотник, и вы знаете, что цель умна и пытается не попасться, что было бы хорошим подходом к преследованию и в конечном счете поймать цель? (Я оставляю детали мира очень расплывчатыми, так как я надеюсь выучить общий алгоритм или семейство методов для решения этой проблемы, а не слишком сильно оптимизировать структуру мира.)

Изначально я полагал, что использование чего-то вроде алгоритма Дейкстры или * и постоянное перерасчет маршрута по мере продвижения цели было бы хорошей идеей, но на самом деле может быть лучшее решение, которое работает, используя более круговой маршрут, чтобы углубиться цель. Это может быть также смоделировано как игра с двумя игроками, которая может быть решена с минимаксным или UCT, но пространство поиска может быть настолько огромным, что было бы совершенно невозможно выполнить любые разумные поиски.

Была ли эта проблема широко изучена? Если да, существует ли набор известных методов, которые можно использовать здесь?

Спасибо!

(Мои извинения, если это дубликат, я, похоже, не нашел другого вопроса, подобного этому, но если он есть, я был бы счастлив закрыть этот).

Ответ 1

Поскольку вы ищете самые разные мнения, я подведу итог тому, что я нашел удивительным из статьи Википедии о ракете Sidewinder: ранние ракеты, стремящиеся к поиску тепла, пытались управлять таким образом, чтобы цель оставалась в центре их детектора. На практике это означало, что ракеты пытались преследовать свои цели. Важной разработкой ракеты Sidewinder является то, что она пытается стабилизировать относительное положение цели на своих датчиках. (Моряки уже давно знают, что корабль на постоянном подшипнике на самом деле находится на курсе столкновения.)

Этот улучшенный алгоритм имеет тенденцию рисовать прямую линию от хищника до добычи и обеспечивает хорошее поведение, когда жертва пытается уклониться. (Каждая кривая, получаемая добычей, дает хищнику еще один ярлык.)

Ответ 2

Отказ от ответственности: у меня нет обширных знаний о литературе по этой теме. Тем не менее, я сделал несколько таких вещей в прошлом (а именно, отслеживание происхождения источника звука).

Простая вещь, когда вы хотите преследовать цель, - это направиться прямо к ней. Это то, что вы сделали. Тем не менее, цель будет двигаться тем временем. Таким образом, алгоритм оптимален только тогда, когда цель не перемещается.

Первый элемент сложности, который мы можем иметь, состоит в том, что цель имеет фиксированную траекторию (неизвестную для chaser). Я уверен, что если траекторией цели может быть любая функция, то нет лучшего алгоритма, чем предыдущий простой. Тем не менее, вы всегда можете сделать некоторые разумные предположения (целевая скорость не может измениться слишком быстро, то есть ее ускорение ограничено), что позволяет вам придумать лучшие алгоритмы.

Итак, я бы сделал первый шаг - реализовать фильтр Kalman. Это дает вам оценку траектории цели. Вы можете сделать несколько быстрых вычислений, и это даст вам траекторию, которую следователь должен предпринять, чтобы перехватить ее в минимальное время.

Теперь, если вам нужно что-то более интересное (на данный момент я не рекомендую), вы можете попытаться узнать траекторию цели (но зачем вам это нужно? Фильтры Кальмана часто оптимальны). Таким образом, вы можете оценить его траекторию с нейронными сетями, с повышающими алгоритмами и т.д. Но я честно не считаю, что это было бы полезно.

Я сказал, что это первый уровень сложности. Второй уровень сложности должен состоять в том, чтобы считать, что цель адаптирует свою траекторию в соответствии с тем, что делает охотник. Это приведет к некоторым состязательным поискам. Это может быть интересно, но я недостаточно уверен в этой теме, чтобы больше поговорить об этом.

Ответ 3

Быстрый поиск "AI chasing" показал этот алгоритм:

http://www.peachpit.com/articles/article.aspx?p=102090&seqNum=4

Это выглядит неплохо. В зависимости от того, насколько эффективно, быстро вы хотите поймать цель, есть другие алгоритмы, на которые вы можете смотреть.

Попробуйте выполнить поиск по Flocking algorithm, и я уверен, что у меня есть некоторые "динамические" алгоритмы A * (но я не могу похоже, найдут их в эту минуту), которые также могут быть полезны.

Кроме того, Neural Networks может работать нормально, предполагая, что в вашем мире не так уж много препятствий. Что-то с 2 входами (расстояние до цели и дельта радианы для достижения цели) и 2 выхода (желаемая скорость и желаемый заголовок)

Ответ 4

Я думаю, что вы смешиваете 2 отдельных вопроса в одной и той же проблеме, которая, скорее всего, будет изолирована.

Предотвращение/предотвращение столкновений
Расчет предполагаемого адресата

Предотвращение/предотвращение столкновений

Это было тщательно изучено, многие конкретные факторы вступают в игру при принятии решения о том, как реализовать это...

Как динамическое перемещение объектов (низкое разрешение стиля RTS сетка или гоночная игра)?
Как перегружается сцена, получаемая с динамическими объектами (Решите, нужно ли учитывать движения толпы оптимизировать путь)?

Результат этих вопросов, скорее всего, приведет вас к некоторому воплощению A *, характерному для ситуации, в которой он будет использоваться, и приведет к тому, что у охотника появится целевая точка в мире и движется к нему в наиболее эффективным способом.

Расчет предполагаемого назначения

Теперь, когда объект может сказать: "Я хочу пойти сюда, дайте мне лучший путь", мы можем независимо смотреть на погоню за мишенью.

Из встроенных алгоритмов самонаведения я использовал следующее:

Оцените время достижения цели (используя несколько эвристических, возможно, просто путь к объекту)
Экстраполируйте положение цели к моменту, когда потребуется, чтобы догнать ее (вдоль текущей скорости/пути)
Сравните расчетное время, на которое нацеливается фактическое время в будущую позицию, если не в пределах некоторого допуска, смещение и повторение процесса до тех пор, пока не будет удовлетворено
Задайте цели цели как экстраполированное положение.

Это будет медленно начать, но некоторые легкие оптимизации можно сделать, отрегулировав допуск времени до целевых оценок и не пересчитывая все дерево путей в каждом кадре.

Вы также можете обнаружить изменения целевой скорости/пути для запуска пересчета