Автор : Nikolaus Correll
Автор перевода: Деньгуб Ю.О.
Источник: Nikolaus Correll. Introduction to Robotics #4: Path–Planning/ Nikolaus Correll.– September 14, 2011
Путь–планирование является важной задачей для автономных мобильных роботов, который позволяет роботам найти кратчайший – или иначе оптимальный – путь между двумя точками. В противном случае оптимальные пути могут быть пути, которые сводят к минимуму количество поворота, количество торможения или независимо от того требует конкретного применения. Алгоритмы, чтобы найти кратчайший путь важны не только в робототехнике, но и в сетевой маршрутизации, видеоиграх и секвенирование гена.
Путь–планирование требует карту окружающей среды и робота , чтобы быть в курсе его расположения по отношению к карте. Будем считать , пока что робот способен локализовать себя, оборудована картой, и способны избежать временных препятствий на пути. Как создать карту, как локализовать робота, и как бороться с неопределенной информацией о местоположении будет основными очагами напоминанием этого класса.
Для того , чтобы спланировать путь, мы так или иначе должны представлять среду в компьютере. Мы различаем два взаимодополняющих подхода: дискретных и непрерывных приближений. В дискретном приближении отображение подразделена на куски равной (например, сетка или шестиугольной карта) или различные размеры (например, комнаты в здании). Последние карты также известны кактопологическими картами . Дискретные карты хорошо поддаются на графике представления. Здесь, каждый кусок карты соответствует вершине (также известный как "узел"), которые соединены между собой ребрами, если робот может перемещаться от одной вершины к другой. Например, дорожная карта является топологическим карта, с пересечениями в качестве вершин и дорог как краев.Вычислительном, график может быть сохранен как смежности или частота списка / матрицы .Непрерывное приближение требует определения внутренних (препятствий) и внешние границы, какправило , в виде многоугольника, в то время как пути могут быть закодированы в виде последовательностей действительных чисел. Дискретные отображения являются доминирующим представлением в робототехнике.
В настоящее время наиболее
распространенной карты является размещение на карте сетки . В карте сетки, среда дискретизируется на
квадраты произвольного разрешения, например , 1 см х
Там существуют также все возможные комбинации дискретного и непрерывного представления.Например, дорожные карты для систем GPS сохраняются в виде топологических карт, которые хранят географические координаты каждой вершины.
Задача найти «кратчайший путь» от одной вершины к другой через связного графа представляет интерес в нескольких областях, наиболее важное место в Интернете, где он используется, чтобы найти оптимальный маршрут для пакета данных. Термин "кратчайший путь" относится здесь к минимальной совокупной стоимости края, который может быть физическое расстояние (в роботизированной приложения), задержка (в приложении сети) или любой другой показатель, который имеет важное значение для конкретного приложения.
Один из самых ранних и простейших алгоритмов является алгоритм Дейкстры . Начиная с начальной вершины , где должна начинаться путь, алгоритм отмечает все непосредственные соседи начальной вершины с ценой , чтобы получить там. Затем он переходит из вершины с самой низкой стоимости для всех его смежных вершин и помечает их стоимость , чтобы добраться до них через себя , если эта стоимость ниже. После того, как все соседи вершины были проверены, алгоритм переходит к вершине со следующей наименьшей стоимостью. Более подробное описание этого алгоритма обеспечивается здесь . После того , как алгоритм достигнет цели вершины, она заканчивается , и робот может следить за края направлен в сторону низкой стоимости края.
Глядя на анимации справа показывает , что алгоритм выполняет много вычислений, которые "очевидно" не идет в правильном направлении. Они очевидны , потому что у нас есть вид с высоты птичьего полета окружающей среды, видя расположение препятствия, и мы знаем приблизительное направление цели.Последние дополнительные знания , которые мы имеем могут быть закодированы с помощьюэвристического функции , любитель слово для "правило". Например, мы могли бы отдать приоритет узлов , которые имеют более низкую оценочное расстояние до цели , чем другие. Для этого мы будем отмечать каждый узел не только с фактическим расстоянием, которое потребовалось нам , чтобы получить там (как и в алгоритме Дейкстры), но и с оценочной стоимостью " , как ворон летит", например , путем вычисления евклидова расстояния или тому Манхэттен расстояние между вершиной мы смотрим на и цель вершины. Этот алгоритм известен как A * . В зависимости от среды, A * может выполнить поиск гораздо быстрее , чем алгоритм Дейкстры.
Расширение A * , что решает проблему дорогого перепланировки ,когда препятствия появляются на пути робота, известен как D * . В отличие от A *, D * начинается с вершины цели и имеет возможность изменять затраты на части пути , которые включают препятствие. Это позволяет D * повторно план вокруг препятствия, сохраняя при этомбольшую часть уже рассчитанной траектории.
А * и D * становится в вычислительном отношении дорогим когда либо пространство поиска велико, например, из – за разрешением мелкозернистой необходимого для выполнения этой задачи, или размеры задачи поиска высоки, например , при планировании кронштейну с несколькими степенями свобода. Более недавнее развитие известный как быстро Изучение случайных деревьев (RRT) решает эту проблему с помощью рандомизированное подход , который направлен на быстро исследовать большую область пространства поиска с итерационным уточнением. Для этого, алгоритм выбирает случайную точку в окружающей среде и связывает его с начальной вершины. Последующие случайные точки затем соединяются с ближайшей вершины в формирующейся графике. График затем подключается к узлу цели, когда точка в дереве приходит достаточно близко , учитывая некоторый порог.Несмотря на то, как правило , алгоритм покрытия (смотри также ниже), РРТ можно использовать для пути планирования, поддерживая старт затрат к на каждой добавленной точке, и смещает выбор точек ,чтобы время от времени падает близко к цели. RRT также может быть использован для учета неголономное контрсилами конкретной платформы при создании следующего случайным образом точку. Один из способов реализации этого является вычисление следующего случайную точку, применяя случайные значения для приводов робота и использовать кинематику вперед , чтобы вычислить следующую точку. Совсем недавно, вариации РРТ было предложено , что в конечном итоге найти оптимальное решение. Тем не менее, хотя РРТ быстро находит некоторое решение, гладкие пути , как правило , требуют дополнительных алгоритмов поиска , которые начинаются от первоначальной оценки , предоставленной РРТ.
Для того , чтобы иметь дело с физического воплощения робота, что усложняет процесс путь–планирования, робот сводится к точечной массы и все препятствия в окружающей среде выращивают половину самого длинного расширения робота от его центра , Это представление называетсяконфигурационного пространства , как это уменьшает представление робота к его х и у координат на плоскости. Большинство алгоритмов планирования также не учитывают ориентацию робота. Если это желательно, дополнительное измерение должно быть введено в пространство конфигурации.
Для того , чтобы увидеть , как найти кратчайший путь может быть применен к 2–ссылка на манипуляторе, и как препятствия в пространстве ху получить проецируется в конфигурационном пространстве такого робота, проверить Кена Гольдберга конфигурации пространства Java – апплет .
После того , как окружающая среда была дискретизируется в графе (обратите внимание, график толькоодин возможный представление), мы можем использовать другие алгоритмы из теории графов для планирования желаемых траекторий роботов. Например, покрытие пола может быть достигнуто путем выполнения поиска в глубину (DFS) или ширину первого поиска (BFS) на графике , где каждая вершина имеет размер инструмента покрытия робота. "Покрытие" интересен не только для чистки пола: одни ите же алгоритмы могут быть использованы для выполнения исчерпывающего поиска конфигурационного пространства, например , как в примере видели в лекции № 3, где мы построили ошибку манипулятором в достижении нужное положение над его конфигурации пространства.Нахождение минимума в этом участке , используя исчерпывающий поиск решает проблему обратной кинематикой. Кроме того , тот же алгоритм может быть использован для систематического следовать все ссылки на веб – сайт до сих нужной глубины (или на самом деле извлечения всей всемирной паутине).
Выполнение DFS или BFS может генерировать эффективные пути охвата, но они далеки от оптимального, много вершин может посетить дважды. Путь , который соединяет все вершины в графе ,но проходит каждую вершину только один раз известен как гамильтонова пути . Гамильтоновым путь ,который возвращается в исходную вершину известен как гамильтонов цикл . Эта проблема также известна как задача коммивояжера (TSP), в котором нуждается маршрут , чтобы подсчитать , что посещает каждый город на его тур только один раз