Я вычисляю кратчайший путь робота на плоскости с многоугольными препятствиями. Все работает хорошо и быстро, никаких проблем нет. Но, как сгладить путь, чтобы он стал соблазнительным? Ниже приведено изображение пути, соединяющего вершины с прямой. P.S Робот - это всего лишь круг.
Эта статья может быть полезна. Похоже, это нетривиальная проблема. Аннотация:
Автоматические ящики для графов должны вычислять пути среди вершин простого многоугольника, которые помимо остального в интерьере должны обладать определенными эстетическими свойствами. Некоторые из них требуют включения некоторой информации о многоугольной форме, не слишком далеко от самого кратчайшего пути. Мы представляем алгоритм вычисления локально выпуклой области, которая "содержит" кратчайший евклидовой путь среди двух вершин простого многоугольника. Область имеет граничную форму, которая "следует" кратчайшей форме пути. Кубический сплайн Безье в области внутри обеспечивает "короткую и плавную" коллизионную свободную кривую между двумя заданными вершинами. Полученные результаты оказываются эстетически приятными, и используемые методы могут представлять самостоятельный интерес. Они являются элементарными и реализуемыми. Рисунок 7 - это выборочный результат, полученный нашей текущей реализацией.
Я часто играл с методами расчета пути, пытаясь сделать реалистичные последовательности полетов в Teragen. Сначала я попытался использовать кривые Безье.
Но обнаружили, что (для по крайней мере лета) они не так полезны. Причина в том, что кривизна между кривыми прерывистая и поэтому не может быть использована для расчета непрерывного правильного угла поворота для пролета. Кроме того, трудно быть уверенным, что кривая не пересекает гору.
Я отвлекаюсь. То, как я в конце концов обосновался, это простой массовый путь spring и расслабить его в подчинении.
Разделите путь на множество маленьких сегментов, тем веселее. Для каждой точки передвиньте ее немного в направлении, чтобы уменьшить угол между ним и его соседями и путь от препятствий. Повторяйте много раз, пока путь не опустится.
k = 0.01 // Adjust the values of k and j to your liking.
j = 0.01 // Small values take longer to settle. Larger values are unstable.
For each point P
normal_vector = vector_to_previous_point + vector_to_next_point
obstacle_vector = vector_to_nearest_obstacle
obstacle_distance = magnitude(obstacle_vector)
obstacle_vector *= obstacle_distance^2
P += (normal_vector * k) - (obstacle_vector * j)
Преимущество такого рода методов релаксации конечных элементов заключается в том, что вы можете запрограммировать в нем всевозможные ограничения, и путь будет соглашаться на некоторый компромисс между ними, в зависимости от веса (j и k в этом случае).
Если вы попали в робототехнику, почему бы не прийти и не присоединиться к Robotics Proposal?
Не можете ли вы просто сделать путь пытливым при фактическом выполнении алгоритма следующего пути? Если вы оставите путь как есть (т.е. Подключены прямые линии), реализуя расстояние вперед до ~ 1 метра (это значение будет зависеть от скорости вашего робота и суммы, которую вы заполняли конфигурационным пространством, чтобы избежать препятствий) в алгоритм управления, который вычисляет скорость каждого колеса, автоматически сглаживает путь без необходимости предварительной обработки.
Вот быстрые изображения того, что я имею в виду... красная пунктирная линия - это путь, который фактически выполняется роботом, когда вы управляете точкой, основанной на расстоянии взгляда. Расстояние взгляда просто вычисляет точку дальше по пути на какое-то произвольное расстояние.
Опять же, единственное, что вам нужно беспокоиться, - это то, насколько вы набиваете препятствия, чтобы не допустить их удара. Обычно я полагаю, что область препятствия дополняется радиусом робота на половину, но если вы контролируете расстояние взгляда, вам может потребоваться сделать это немного больше.
В случае робота мы не можем знать будущее. Мы должны нарисовать каждый пункт, зная только расположение робота и препятствий. Обычный способ создания кривых путей минимальной длины состоит в том, чтобы моделировать робота с кругом и перемещать круг, чтобы он оставался в контакте с препятствиями. Просто держите один радиус и повороты будут кривыми.
Если вы хотите кривые и НЕ минимальное расстояние, попробуйте сделать вышеуказанный радиус пропорциональным расстоянию, которое вы находитесь от вершины многоугольника.
Идея кривых Безье работает только для того, чтобы сделать путь изогнутым в ретроспективе. Он меняется, когда робот был. Обычно с роботами, изменяющими прошлое, называется "обман". Один из способов избежать изменения пути, по которому вы уже шли, - это смотреть вперед. Но разве робот может видеть вокруг углов? Вы должны лучше определить правила.