Как адаптировать алгоритмы поиска пути к ограниченному движению?

Представьте себе автомобильное движение, в котором сущности не могут включить десятину. Скажем, ради обсуждения, что при скорости они могут поворачиваться на 90 градусов в секунду. Это во многих случаях изменило бы оптимальный путь и, следовательно, путь. Это может даже сделать «обычные» пути полностью невозможными для прохождения.

Есть ли алгоритмы поиска или алгоритмы планирования движения, которые могут иметь это в виду, или есть простые способы адаптировать популярные?

9 голосов | спросил Weckar E. 9 42017vEurope/Moscow11bEurope/MoscowThu, 09 Nov 2017 12:03:19 +0300 2017, 12:03:19

4 ответа


7

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

 введите описание изображения здесь>> </a> </p>

<p> Вот как это работает. </p>

<p> <strong> Государство </STRONG> </p>

<p> Конфигурация вашего автомобиля  q  на самом деле представляет собой трехмерное состояние, содержащее x, y позицию  и  автомобиля, его ориентацию  t . Узлы в вашем алгоритме A * фактически представляют собой 3D-векторы. </p>

<pre><code>---- +: = 0 = + ----</code></pre>

<p> <STRONG> Действия </STRONG> </p>

<p> А как насчет краев? </p>

<p> Это немного сложнее, потому что ваш автомобиль действительно может выбрать количество  бесконечных  способов поворота колеса. Таким образом, мы можем сделать это доступным для планировщика сетки решетки, ограничив количество действий, которые автомобиль может взять на дискретный набор,  A . Для простоты предположим, что автомобиль не ускоряется, а может мгновенно изменить свою скорость. В нашем случае  A  может быть следующим: </p>

<pre><code>---- +: = 1 = + ----</code></pre>

<p> Теперь мы можем создать дискретный набор действий, которые автомобиль может принять в любое время. Например, жесткое правое нажатие на газ в течение 0,5 секунды будет выглядеть так: </p>

<pre><code>---- +: = 2 = + ----</code></pre>

<p> Ввод автомобиля в обратную сторону и резервное копирование будет выглядеть так: </p>

<pre><code>---- +: = 3 = + ----</code></pre>

<p> И ваш список действий будет выглядеть следующим образом: </p>

<pre><code>---- +: = 4 = + ----</code></pre>

<p> Вам также нужен способ определения того, как действие, предпринятое на узле, приводит к новому узлу. Это называется динамикой  вперед  системы. </p>

<pre><code>---- +: = 5 = + ----</code></pre>

<p> <strong> Дискретные сетки </strong> </p>

<p> Теперь, чтобы построить решетчатую сетку, все, что нам нужно сделать, это  hash  состояние автомобиля в дискретные ячейки сетки. Это превращает их в дискретные узлы, за которыми может следовать A *. Это очень важно, потому что в противном случае A * не мог бы знать, действительно ли два состояния автомобиля одинаковы для их сравнения. Посредством хэширования значений целых сеточных ячеек это становится тривиальным. </p>

<pre><code>---- +: = 6 = + ----</code></pre>

<p> Теперь мы можем выполнить план A *, где GridCells - это узлы, Actions - это ребра между узлами, а Start и Go выражаются в терминах GridCells. Эвристика между двумя GridCells - это расстояние по x и y плюс угловое расстояние в тете. </p>

<p> <strong> По пути </strong> </p>

<p> Теперь, когда у нас есть путь с точки зрения GridCells и Actions между ними, мы можем написать дорожку для автомобиля. Поскольку ячейки сетки дискретны, автомобиль будет прыгать между ячейками. Поэтому нам придется сгладить движение машины по пути. Если ваша игра использует физический движок, это можно сделать, написав рулевой контроллер, который пытается максимально приблизить автомобиль к пути. В противном случае вы можете анимировать путь с использованием кривых Безье или просто путем усреднения ближайших нескольких точек пути. </p></body></html>

ответил mklingen 9 42017vEurope/Moscow11bEurope/MoscowThu, 09 Nov 2017 21:45:19 +0300 2017, 21:45:19
4

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

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

ответил ratchet freak 9 42017vEurope/Moscow11bEurope/MoscowThu, 09 Nov 2017 17:00:29 +0300 2017, 17:00:29
1

Мои мысли, не протестировали их!

  1. Запустите A * от начала до пункта назначения, верните путь.
  2. Прокрутите путь, когда вы обнаружите поворот, используйте безье (или любой другой), который использует текущую скорость искателей для прогнозирования узлов, которые создадут плавный поворот. Убедитесь, что он пытается вернуться к ближайшему узлу пути.
  3. Если поворот может быть выполнен, отличный, если нет, повторите с более низкой скоростью, делая более резкий поворот.
  4. Как только правильный путь будет создан, вернитесь по пути, который регулирует скорость искателя до того, как будет сделан поворот, чтобы он замедлялся до нужной скорости, прежде чем он начнет поворот.
  5. Если поворот не может быть выполнен вообще, снова запустите все. Просто убедитесь, что все обработанные узлы поворота, которые не могут быть сделаны, находятся в закрытом списке, поэтому они игнорируются. И вы можете начать с того, где начался поворот, поэтому вы можете пропустить успешную часть пути, однако в некоторых случаях это может привести к менее оптимальному пути.

Вы также должны сделать это, не выполняя сначала путь: ergo: обработка поворотов во время A *, которая, вероятно, будет намного лучше оптимизирована, но может также оказаться проблематичной и глючной, я действительно не знаю и, к несчастью, у меня нет времени, чтобы проверить его сам.

 Pathfinding

ответил Dennis 9 42017vEurope/Moscow11bEurope/MoscowThu, 09 Nov 2017 17:29:33 +0300 2017, 17:29:33
0

Если ваш агент имеет полный контроль над автомобилем, сделайте это наоборот. Сначала подключите линию от начала до конца, затем выясните, на какой скорости вы можете перемещаться в каждом повороте, как и ответ Денниса.

Не рисуйте кривые Безье из неподвижных точек. Чтобы свести к минимуму потерю скорости, вам нужно перемещать всю линию вокруг, поэтому начните с вставки дополнительных узлов на более или менее равномерном расстоянии, а затем перейдите затем для минимизации энергии или аналогичных стратегий. Для получения дополнительной информации вам нужно посмотреть на создание линии AI в (например, сима или полуси) гоночных играх.

После того, как вы запустили систему линий AI, запустите свой поиск A * и для каждого пути пойдите хотя бы на один угол вперед, а затем вычислите линию AI, которая дает вам оценку времени. Это будет ваша функция затрат.

ответил BECD9A66 9 42017vEurope/Moscow11bEurope/MoscowThu, 09 Nov 2017 20:22:04 +0300 2017, 20:22:04

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132