Алгоритм для RC автомобиля
Я ищу алгоритм, и я не знаю, с чего начать!
Я пытаюсь добраться из точки А в точку Б на декартовом графике. Движение ограничено движением автомобиля RC: назад, вперед, вперед-влево и вперед-вправо (постоянный радиус поворота; автомобиль либо полностью поворачивает, либо вовсе не поворачивает).
Как бы я построить алгоритм, который принимает следующее:
turningRadius, initialPosition, initialOrientation, finalPosition
И дает упорядоченный набор шагов, чтобы добраться до finalPosition?
Обратите внимание, что мне все равно, какова окончательная ориентация.
Спасибо!
РЕДАКТИРОВАТЬ: Обратите внимание, что это не на графике с дискретными узлами, а непрерывной системой координат
4 ответа
Как описывается ваша проблема, алгоритм прост и требует только двух простых шагов: 1) двигаться вперед, поворачивая (влево или вправо), пока машина не будет направлена прямо на B, 2) двигаться вперед, пока не нажмете B. Готово.
Единственная относительно сложная часть - это первый шаг. Если B лежит слева от продольной оси автомобиля в исходном положении, естественным подходом будет начать с поворота налево. Это будет работать, если точка B не лежит внутри круговой траектории, образованной таким левым поворотом (радиуса turningRadius). В последнем случае автомобиль будет двигаться по кругу, но никогда не сможет нацелиться непосредственно на B. В таких случаях правильная стратегия состоит в том, чтобы фактически начать с правого поворота и продолжать вращаться, пока вы не нацелите автомобиль на B.
Итак, если у вас нет требований к оптимальности для вашей траектории, самый простой алгоритм для первого шага состоит в том, чтобы безоговорочно повернуть "далеко" от точки: повернуть направо, если B лежит слева от продольной оси автомобиля, и поверните налево, если B лежит вправо. Продолжайте поворачивать, пока машина не будет направлена прямо на B. Это звучит немного неестественно, но это всегда работает, то есть вы всегда сможете прицелиться в машину.
Если вы заботитесь о более оптимальной (более короткой) траектории, то вам нужно проанализировать местоположение B относительно начальной позиции / ориентации автомобиля ("Находится ли B внутри круга поворота или снаружи?") И выбрать направление движения. первый поворот соответственно.
В общем, это не простая проблема. Он подпадает под категорию "Планирование в условиях дифференциальных ограничений". Последние три главы книги LaValle (доступны онлайн здесь) имеют дело с этим. В частности, посмотрите на раздел 14.4.2., Который имеет дело с "машиной Дубинса", которая похожа на вашу машину с радиоуправлением, за исключением того, что она не движется назад.
Также ищите для "Планирование автомобильного пути Дубинс". Вы найдете много бумаг.
Вы пробовали * (звездочку)? также приятно, когда вы предоставляете карту местности. Вы можете назначить веса различным участкам местности, что приведет к разному пути. Я считаю, что алгоритм по умолчанию не предоставляет диагональных направлений, но вы можете добавить это довольно легко.
Также он по умолчанию не имеет дело с "поворотом", но a-star даст полный путь. Что вы можете сделать, это рассчитать радиус поворота на основе 2 точек. Текущая позиция и следующая рассчитанная позиция, ИЛИ последняя позиция и текущая позиция. Затем вы можете добавить или вычесть направление направления с изменением угла. Возможно, вам придется настроить это немного.
Звучит как интересный и веселый проект! Чтобы получить конкретную рекомендацию алгоритма, вам, вероятно, следует предоставить более подробную информацию... Как вы ожидаете буквально запустить это на каком-то встроенном контроллере, подключенном к машине RC? Или это алгоритм для запуска на рабочей станции и удаленного управления автомобилем? (Или это чисто абстрактное упражнение, а машины нет… ауууу.)
Моя общая рекомендация для того, чтобы понять, с чего начать, - это Построение Решателей Проблем, которое является отличным введением в мир методов решения проблем "ИИ". Это может быть немного устаревшим в эти дни... но подождите, что я говорю! Возможно нет.:-)
[Хорошо, я должен объяснить этот последний комментарий: большинство "современных" техник ИИ, которые я видел на практике, на самом деле восходит к идеям, которым уже много лет… Они только что стали практичными благодаря неустанному продвижению закона Мура. Таким образом, книга, написанная в 1993 году, все еще обсуждает довольно современные методы, из того, что я лично видел. Я хотел бы, чтобы меня указали на контрпример!]