Введение 3
Постановка задачи 5
Обзор литературы 7
Глава 1. Алгоритм построения траектории RRT 8
1.1 RRT 8
1.2 KD-tree 10
Глава 2. Реализация алгоритма 12
2.1. Начальные данные 12
2.2. Генерация очередного положения стоп 12
2.3. Добавление вершин в k-мерное дерево 14
2.4. Добавление вершин в RRT 14
2.5. Оптимизация пути 17
2.6. Расчет положений стоп 17
2.7. Расчет позы робота 18
Глава 3. Эксперименты 21
3.1 Описание работы расчетной программы 21
3.2 Пример работы расчетной программы 22
Заключение 25
Список литературы 26
Разработка аппаратов, перемещающихся с помощью конечностей, стала одним из важных направлений робототехники. Перемещаться по поверхности с неровностями целесообразнее посредством шагания: шагающие объекты используют лишь участки местности, необходимые для постановки ног; благодаря этому, требования к поверхности передвижения снижаются.
Ряд исследований посвящен теоретическим вопросам, а также вопросам конструирования и лабораторного макетирования многоногих шагающих механизмов. Управление ходьбой таких устройств осуществляется на кинематическом уровне - локомоции организуются с помощью последовательности статически устойчивых конфигураций. С увеличением числа ног шагающих роботов проблема структуры управления упрощается; с другой стороны, вследствие растущего числа степеней свободы, их механическая часть становится более сложной.
В случае наличия на пути робота препятствий, задача построения траектории движения механизма значительно усложняется. В этом случае траектории требуется вычислять, основываясь не только на параметрах самого механизма, но и на расположении, форме и состоянии объектов в окружающей среде робота.
В данной работе рассматривается задача построения трехмерной траектории движения двуногого механизма в пространстве с препятствиями. По известной карте местности, определяемой набором прямоугольных препятствий, и заданным начальной и конечной точках искомого маршрута вычисляется последовательность положений механизма в пространстве. В каждый момент времени полный набор обобщенных координат робота вычисляется по положениям ступней.
Для решения задачи применяется алгоритм быстрорасширяющихся деревьев (Rapidly expanding Random Trees, RRT). Рассмотрен способ ускорения работы алгоритма RRT с помощью построения дополнительного поискового k-мерного дерева.
В данной работе была рассмотрена задача построения траекторий антропоморфного механизма для его перемещения по заранее известной карте в аксиальной плоскости. Для решения этой задачи адаптирован и реализован вероятностный алгоритм RRT (rapidly exploring random trees) с оптимизацией посредством k-мерного дерева. Самой затратной частью работы программы стала проверка на существование пути между конфигурациями. Реализация и практическая применимость продемонстрированы в главах 2-3.
