A * дискретизация ориентации

Question

У меня есть пространство с препятствиями, я хочу найти путь. Я могу сделать дискретизацию пространства в сетке и использовать A * (или D * или что-то еще), чтобы найти путь через него. Теперь я хочу добавить ориентацию к алгоритму. Таким образом, теперь местоположение узла становится 3D-вектором (x, y, phi). Вы можете перейти от одного узла к другому только в том случае, если они принадлежат дуге (обе позиции находятся на круге и ориентированы вдоль касательных линий). Как я дискретирую пространство, чтобы углы не взорвались в том смысле, что, пройдя по графику, множество возможных углов становится конечным? Спасибо.

Answer 1

Углы могут быть предотвращены от взрыва, гарантируя, что phi считается по модулю 2pi, то есть phi = phi + 2pi * k для любого целочисленного значения k.

В синтаксисе типа C вы можете завершить обновление phi с помощью fmod.

phi = fmod(phi + deltaphi, 2*pi) 

Где дельтафи - это изменение угла, которое вы вводите (в радианах).

Самый распространенный способ сделать это - ограничить значения угла phi, чтобы взять один из n дискретных углов, который также имеет преимущество в предотвращении проблем с точностью и округлением. Учитывая, что вы знаете, что phi может принимать только один из значений n, вы можете рассматривать его как целое число и сопоставлять значение с реальным, когда это необходимо.

i = (i + deltai) % n 
phi = (2*i*pi)/n) 

Где ваши изменения угла deltai есть (2 * deltai * пи)/п радиан.

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

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

Движение вперед и назад в то же время, когда вы поворачиваете ввод, является более сложным и, как правило, не особенно хорошо работает с дискретными решетками - оно требует некоторой модели автомобиля, с которым вы работаете. Наиболее распространенными являются простые неголономные модели - передний только автомобиль (автомобиль Дубинса) или автомобиль с прямым/обратным (автомобиль Reeds Shepp) - ваша ссылка на касательные к кругам, я предполагаю, что это то, что вы после. Dubins-Curves или аналогичные библиотеки могут быть использованы для создания библиотек возможных путей, которые могут быть объединены с планировщиком A * (или D *).

Differentially Constrained Mobile Robot Motion Planning in State Lattices от Mihail Pivtoraiko, Ross A. Knepper и Alonzo Kelly имеет несколько ярких изображений того, что возможно.

Answer 2

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

• 4-направления: использовать квадратную сетку с перемещением через кромки
• 8-направление использует квадратную сетку с движением по краям и вершин
• 6- направления использовать шестиугольную сетку с перемещением по краям
• 12-направленные использовать шестиугольную сетку с подвижным элементом nt по краям и точкам
• ... и так далее.

Чтобы действительно получить дискретные заголовки, я объявлен enum называется Direction:

public enum Direction { 
    North, 
    NorthEast, 
    East, 
    SouthEast, 
    South, 
    SouthWest, 
    West, 
    NorthWest; 

//additional code below... 
} 

Вы можете поиск правильного заголовка, первым вычисляя XY-смещению между текущим положением и целью позицией:

int dx = currentPosition.x - goalPosition.x; 
int dy = currentPosition.y - goalPosition.y; 

Они были переданы методу getInstance(int,int) (см. Ниже) для получения правильного Direction:

public static Direction getInstance(int dx, int dy) { 
    int count = Direction.values().length; 
    double rad = Math.atan2(dy, dx); // In radians 
    double degree = rad * (180/Math.PI) + 450; 

    return getInstance(((int) Math.round(((degree % 360)/(360/count)))) % count); 
} 

public static Direction getInstance(int i) { 
    return Direction.values()[i % Direction.count]; 
} 

Фактически эти методы вычисляют заголовок в градусах и раундах до ближайшего Direction. Затем вы можете реализовать метод, который перемещает/поворачивает агент в заголовке Direction, например. agent.turnToward(Direction d) или agent.move(Direction d).

Дополнительные ресурсы:

• шестигранной Сетки: http://www.redblobgames.com/grids/hexagons/#distances
• Представляющие сетки с графиками: http://www.redblobgames.com/pathfinding/grids/algorithms.html
• Pathfinding с A *: http://theory.stanford.edu/~amitp/GameProgramming/