Теоретический алгоритм почтенного графа кратчайшего пути A * и последующие усовершенствования (например, Иерархический аннотированный A *), безусловно, являются методом выбора для поиска путей в разработке игр.
Вместо этого мне просто кажется, что RL - более естественная парадигма для перемещения персонажа по игровому пространству.
И все же я не знаю ни одного разработчика игр, который бы реализовал движок поиска путей на основе Reinforcement Learning. (Из этого я не делаю вывод, что применение RL в pathfinding равно 0, просто оно очень мало по сравнению с A * и друзьями.)
Безотносительно причины, это не потому, что эти разработчики не знают о RL, о чем свидетельствует тот факт, что RL часто используется в других местах игрового движка.
Этот вопрос не является предлогом для предложения мнения о RL при поиске путей; на самом деле, я предполагаю, что молчаливое предпочтение A * et al. над RL правильно, но это предпочтение не очевидно для меня, и мне очень любопытно узнать причину этого, особенно от любого, кто пытался использовать RL для поиска пути.
Ответы:
Я полагаю, это потому, что, поскольку вы не получите никакого полезного обобщения политики из ничего, кроме игрушечных проблем, и функция вознаграждения будет выглядеть подозрительно как эвристика A *, перспектива использования RL имеет тенденцию выглядеть действительно перестроенный, неэффективный способ получения результатов, которые в лучшем случае идентичны A *, но, вероятно, не будут такими уж хорошими.
Это может быть несправедливо по отношению к RL, и если так, то мне было бы интересно услышать почему, но я не вижу ничего, чтобы это указывать.
Многие из нас также помнят, каким было нахождение пути в играх до широкого распространения A *, и не стремятся навязать игрокам что-то похожее на те дни, или не страдают от рыночных последствий этого.
источник
Не зная много о RL, я попытаюсь ответить на ваш вопрос с другими вопросами:
Используя RL, можете ли вы определить, возможно ли достичь точки A из точки B?
Может ли RL гарантировать воспроизводимое / последовательное / тестируемое поведение при навигации?
Как соотносятся требования к памяти и времени работы процессора с A *? Точно так же, сколько вы можете предварительно вычислить по сравнению, скажем, с навигационными сетками?
Как RL справедлива в среде с динамическим столкновением?
Насколько сложнее понять и правильно реализовать RL по сравнению, скажем, с поведением рулевого управления?
Есть ли хорошие поставщики промежуточного программного обеспечения для RL?
Возможно, эти вопросы помогут вам с вашим ответом.
источник
Я смущен предположением, что RL - "более естественная парадигма". Я не вижу, как обучение с подкреплением отображает проблемную область почти так же чисто и точно, как поиск по графику. Обычно вы не хотите, чтобы агент учился - вы предполагали, что они уже знают маршрут. Вместо этого вы хотите, чтобы они выбирали и использовали наиболее прямой доступный маршрут, а поиск в графике облегчает его почти оптимальным образом. Если бы вы использовали RL в автономном режиме для расчета наилучшего направления в любом конкретном узле для любого данного пункта назначения, это в конечном итоге принесло бы в целом эквивалент A *, за исключением того, что требовалось бы значительно больше памяти *, а также требовало от разработчиков очень осторожного убедитесь, что все узлы были должным образом исследованы во время обучения. И эта тренировка просто даст значение, которое мы уже можем очень хорошо аппроксимировать уравнением Пифагора, поскольку заранее знаем, что график подчиняется евклидовым правилам расстояния. (Это, конечно, не относится ко всем ситуациям, в которых можно использовать поиск в графе и / или обучение с подкреплением.)
(Что касается проблемы с памятью: если у вас было 1000 возможных квантованных позиций на карте, это 1000 узлов плюс 1000 * M ребер (где M - среднее число узлов, достижимых из любого другого узла.) Этого, плюс эвристика, достаточно для A * для работы. Чтобы обучение с подкреплением работало, по крайней мере так, как я его представляю, вам также понадобится 1000 записей для каждого из этих 1000 * M ребер, чтобы получить значение вознаграждения за это ребро для любого из 1000 Возможные пункты назначения. Это много данных - и каждый их бит должен быть достаточно точным, чтобы избежать петель, обходов или тупиков.
источник
Поиск пути - это относительно «решенная» проблема, а RL - нет.
С помощью A * разработчики могут быстро создавать эвристики и улучшать их с течением времени. RL (я говорю о Q-Learning, когда ссылаюсь на RL здесь), требуется время, чтобы вычислить лучшие показатели обучения и факторы дисконтирования (время, которое стоит потратить на другие аспекты игры).
источник
Это действительно зависит от типов игры. Если в игре все статично, лучше использовать поиск A *. Однако, если в той же области находятся другие игроки-люди, поиск A * гарантированно провалится. A * search не знает, куда направляются другие игроки. С другой стороны, RL может моделировать поведение других игроков и найти лучший путь, который учитывает движение других игроков.
источник