Недавно я работал над своим собственным мобильным роботом, Тыква, со студентом магистратуры в моей исследовательской лаборатории. Поскольку мы пытаемся заменить некоторые пакеты по умолчанию, которые использует мой робот из библиотеки ROS, мы узнали о различных алгоритмах, используемых в типичном стеке роботов. Как человек, который занимается планированием и обучением с подкреплением, но определенно не робототехникой, мне пришлось пройти через сложную кривую обучения. Робот должен знать, как локализоваться в своей среде - или выяснить, где он находится, построить карту своего окружения на лету, если у него ее еще нет, избегать препятствий, которые могут появиться. случайным образом управляйте его двигателями, чтобы изменить его скорость или направление, придумывайте план, который решает задачу, и так далее.
Как вы догадываетесь, одна действительно важная часть робота - это его способность планировать путь из одного места в другое с учетом карты его окружения. Зачем ему это делать? Может быть, ему нужно пересечь комнату, чтобы доставить какую-то посылку, или, может быть, ему нужно сопроводить человека в какое-то здание. В любом случае, когда роботу нужно перейти из начальной точки в целевую для выполнения задачи, он должен придумать план пути для перемещения по окружающей среде. В статьях по робототехнике вы часто встретите карту, подобную приведенной ниже, с начальным и конечным местоположениями. Это прекрасное изображение классической проблемы мобильной робототехники, которую мы обычно называем планированием пути. Другими словами, как робот может найти путь, ведущий от начальной точки к целевой?
Заявление об ограничении ответственности. Раньше я писал несколько сообщений с красочными диаграммами и длинными пояснениями. По общему признанию, из-за того, что подобные посты требуют огромного количества работы, я так и не опубликовал ничего. В дальнейшем я планирую писать посты без излишеств, более грубые и непринужденные. Почему? Что ж, мне не только легче писать сообщения, которые укрепляют мое собственное понимание концепции, но я также почти уверен, что они могут быть такими же информативными без всех наворотов, которые были в других моих сообщениях. А теперь вернемся к нашему регулярному расписанию ...
Однако, как всегда, следует помнить о некоторых тонкостях:
- План пути действительно должен работать на роботе. Если план пути заставляет робота поворачивать под острыми углами, но робот не может двигаться под острыми углами (как машина), этот план пути не должен позволено, разрешено.
- План пути должен быть как можно ближе к оптимальному. Хотя неплохо найти любой план пути, который приведет робота от начальной точки к конечной точке, этого, к сожалению, недостаточно. Мы хотели бы что-нибудь более эффективное. Это не только поможет роботу выполнить свою задачу как можно быстрее, но и сэкономит драгоценное время автономной работы.
- План пути должен избегать столкновения со стенами. Это само собой разумеется. Роботы могут быть довольно дорогими, и сбой никогда не бывает хорошим. Один только мой маленький робот обошелся мне в тысячу долларов.
Один из самых популярных алгоритмов для составления плана пути, который пытается удовлетворить этим условиям, называется Быстрое изучение случайных деревьев (RRT). Поскольку картинка стоит тысячи слов, посмотрите схему ниже. Предположим, что робот должен перейти от начальной точки (красная точка) к целевой точке (зеленая точка) на простой карте без каких-либо препятствий. По сути, мы начнем с дерева, у которого есть корневой узел, представляющий начальную позицию робота. После этого будем постепенно наращивать дерево. Как? Мы возьмем кучу случайных выборок карты, создадим новый узел для каждой случайной выборки и каким-то образом вставим каждый новый узел в дерево. Как только в дереве появится узел, достаточно близкий к целевой позиции робота, мы закончили.
Поскольку я знаю, что это кажется довольно расплывчатым, давайте добавим некоторые детали к этой приблизительной идее. Для начала давайте рассмотрим каждый параметр, который мы отправим в RRT.
- Карта: карта окружающей среды, разделенная на область препятствий и область без препятствий. Это будет похоже на карту, которую я разместил выше, где область препятствий - это что-то серое, а область без препятствий - любое белое.
- Начальное положение: начальное положение робота в окружающей его среде. Это просто красная точка на карте.
- Целевая область: целевая область робота в его среде. И это просто зеленая точка на карте.
- Количество итераций: количество итераций, выполненных RRT.
Давайте пройдемся по каждому этапу RRT. Сначала мы инициализируем пустое дерево. Затем мы вставим корневой узел, который представляет начальную позицию в дерево. На этом этапе у нас будет просто дерево с единственным узлом, представляющим начальную позицию. Наконец, мы будем повторять эти шаги, пока не достигнем количества итераций или не достигнем цели, в зависимости от того, что наступит раньше.
- Пример случайного местоположения из области карты, свободной от препятствий.
- Создайте узел, связанный со случайной позицией.
- Найдите узел в дереве, ближайший к случайной позиции.
- Рассчитайте путь от случайного положения до положения узла, который действительно может работать на роботе.
- Переходите к следующей итерации, если путь с чем-то сталкивается.
- Вставьте узел, связанный со случайной позицией, в дерево с узлом (ближайшим к нему) в качестве его родительского узла.
- Верните дерево, когда случайная позиция окажется на некотором расстоянии от целевой позиции.
В качестве предупреждения: если дерево не приблизится к целевой области к тому времени, когда мы достигнем количества итераций, мы просто вернем дерево, которое мы построили до сих пор.
Но как нам получить путь от начального местоположения к местоположению цели после того, как мы построили дерево? Все, что нам нужно сделать, это начать с узла, который представляет местоположение цели, и вернуться вверх по tree, пока мы не дойдем до узла, представляющего начальную точку. Это даст нам путь, который приведет робота от начальной точки к целевой. Легкий.
И можно ли повторно использовать дерево для новых местоположений целей на той же карте? Конечно! Если в дереве уже есть узел, который находится рядом с новым местоположением цели, все готово. Однако, если еще нет ничего близкого к этой новой цели, мы можем просто продолжать выборку, пока не дойдем до ближайшего к ней узла. Пока окружающая среда не меняется, вы можете просто продолжать строить на том же дереве для любых новых целевых локаций.
Без лишних слов, вот грубая версия алгоритма RRT!
function RRT(map, startPosition, goalRegion, numIterations):
tree = initializeEmptyTree()
insertRootNode(tree, startPosition)
for i = 1 to numIterations:
randomPosition = sample(map)
randomNode = createNode(tree, randomPosition)
nearestNode = findNearestNode(tree, randomPosition)
path = calculatePath(nearestNode, randomNode)
if (hasCollision(map, path)):
continue
insertNewNode(tree, nearestNode, randomNode)
if (randomPosition is within goalRegion):
return tree
return tree
Есть еще одна вещь, о которой важно рассказать! Ранее я упоминал, что мы ищем путь, который работает на реальном роботе, является оптимальным и избегает препятствий. Хотя этот путь будет работать на реальном роботе и избегать препятствий, оптимален ли он? К сожалению, оказывается, что RRT не гарантирует создание оптимальных путей. В одном из будущих постов блога я расскажу о RRT *, улучшенной версии RRT, которая в конечном итоге создает оптимальный путь. Но это в следующий раз.
