Алгоритм для RC автомобиля

Question

Я ищу алгоритм и понятия не имею, с чего начать!

Я пытаюсь перейти из точки A в точку B на декартовом графе.Движение ограничено движением автомобиля RC: назад, вперед, вперед-влево и вперед-вправо (постоянный радиус поворота; автомобиль либо полностью поворачивает, либо вовсе не поворачивает).

Как быЯ строю алгоритм, который принимает следующее:

turningRadius, initialPosition, initialOrientation, finalPosition

И дает упорядоченный набор шагов, чтобы добраться до finalPosition?

Заметьте, что мне все равно, какова конечная ориентация.

Спасибо!

---

РЕДАКТИРОВАТЬ: Обратите внимание, что это не график с дискретными узлами, а непрерывная система координат

Answer 1

Как описывается ваша проблема, алгоритм прост и требует только двух простых шагов: 1) двигайтесь вперед, поворачивая (влево или вправо), пока машина не будет направлена ​​прямо на B, 2) двигайтесь прямо, пока не нажмете B . Готово.

Единственная относительно сложная часть - это первый шаг. Если B лежит слева от продольной оси автомобиля в исходном положении, естественным подходом было бы начать с поворота влево . Это будет работать, если точка B не лежит внутри круговой траектории, образованной таким левым поворотом (радиус turningRadius). В последнем случае автомобиль будет двигаться по кругу, но никогда не сможет нацелиться непосредственно на B. В таких случаях правильная стратегия состоит в том, чтобы фактически начать с поворота вправо и вращаться, пока вы не нацелите машину у Б.

Итак, если у вас нет требований к оптимальности для вашей траектории, самый простой алгоритм для первого шага будет безоговорочно поворачивать «далеко» от точки: поверните вправо , если B лежит на влево от продольной оси автомобиля и поворот влево , если B лежит на вправо . Продолжайте поворачивать, пока машина не будет направлена ​​прямо на B. Это звучит немного неестественно, но это всегда работает, то есть вы всегда сможете нацелить машину.

Если вы заботитесь о более оптимальной (более короткой) траектории, то вам необходимо проанализировать местоположение B относительно начальной позиции / ориентации автомобиля («Находится ли B внутри круга поворота или снаружи?») И выбрать направление первого поворота соответственно.

Answer 2

В общем, это не простая проблема.Он подпадает под категорию «Планирование в условиях дифференциальных ограничений».Последние три главы книги ЛаВалля (доступны онлайн здесь ) имеют дело с этим.В частности, посмотрите на раздел 14.4.2., Который имеет дело с «машиной Дубинса», которая похожа на вашу RC-машину, за исключением того, что она не движется назад.

Также ищите "Планирование автомобильного пути Дубинс".Вы найдете много бумаг.

Answer 3

Звучит как интересный и веселый проект!Чтобы получить конкретную рекомендацию алгоритма, вам, вероятно, следует предоставить более подробную информацию ... Как вы ожидаете буквально запустить это на каком-то встроенном контроллере, подключенном к машине RC?Или это алгоритм для запуска на рабочей станции и удаленного управления автомобилем?(Или это чисто абстрактное упражнение, а машины нет… ауууу.)

Моя общая рекомендация для получения справки о том, с чего начать, будет Построение проблем , что является отличнымвведение в мир методов решения проблем "ИИ".Это может быть немного устаревшим в эти дни ... но подождите, что я говорю!Возможно нет.: -)

[Хорошо, я должен объяснить этот последний комментарий: большинство "современных" техник ИИ, которые я видел на практике, на самом деле восходит к идеям, которым много лет ... Они просто стали практичными теперь благодаря неустанному продвижению закона Мура.Таким образом, книга, написанная в 1993 году, все еще обсуждает довольно современные методы, из того, что я лично видел.Я хотел бы, чтобы меня указали на контрпример!]

Answer 4

Вы пробовали * (звездочку)? также приятно, когда вы предоставляете карту местности. Вы можете назначить веса различным участкам местности, что приведет к другому пути. Я считаю, что алгоритм по умолчанию не предоставляет диагональных направлений, но вы можете добавить это довольно легко.

Также он по умолчанию не имеет дело с "поворотом", но звездочка даст полный путь. Что вы можете сделать, это рассчитать радиус поворота на основе 2 точек. Текущая позиция и следующая рассчитанная позиция, ИЛИ последняя позиция и текущая позиция. Затем вы можете добавить или вычесть направление направления с изменением угла. Возможно, вам придется немного подправить это.