Аннотация: При создании мобильных роботов одной из центральных проблем является автоматическое планирование маршрута. Эта задача состоит в том, чтобы при заданных начальном и конечном положениях робота по карте местности построить маршрут, по которому робот может попасть в целевую точку, не столкнувшись с препятствиями. Существуют два подхода к решению этой задачи. В одном из них используется понятие конфигурационного пространства, идея которого состоит в том, чтобы стянуть объект (робот) в точку, одновременно расширив препятствия в соответствии с его формой. Кратчайший маршрут отыскивается путем просмотра графа «прямой видимости», в котором представлены все прямолинейные отрезки пути, обходящие препятствия в конфигурационном пространстве. Основным недостатком данного подхода являются трудности, возникающие при поворотах робота, и, кроме того, кратчайший маршрут проходит очень близко к препятствиям.
Ключевые слова: Робот, декомпозиция, планирование маршрута, проходимая область.
Технические науки
УДК 681.3.06:007.52
Чудинов Владислав Александрович
Chudinov Vladislav Alexandrovich
студент, кафедра Автомобили технологические машины, автодорожный факультет,
Пермский национальный исследовательский политехнический университет
г.Пермь, Российская Федерация
Бруданов Антон Михайлович
Brudanov Anton Mikhailovich
студент, кафедра Автомобили технологические машины, автодорожный факультет,
Пермский национальный исследовательский политехнический университет
г.Пермь, Российская Федерация
ЕСТЕСТВЕННАЯ ДЕКОМПОЗИЦИЯ СВОБОДНОГО ПРОСТРАНСТВА ПРИ ПЛАНИРОВАНИИ МАРШРУТА
NATURAL DECOMPOSITION OF FREE SPACE FOR PATH PLANNING
Аннотация: При создании мобильных роботов одной из центральных проблем является автоматическое планирование маршрута. Эта задача состоит в том, чтобы при заданных начальном и конечном положениях робота по карте местности построить маршрут, по которому робот может попасть в целевую точку, не столкнувшись с препятствиями. Существуют два подхода к решению этой задачи. В одном из них используется понятие конфигурационного пространства, идея которого состоит в том, чтобы стянуть объект (робот) в точку, одновременно расширив препятствия в соответствии с его формой. Кратчайший маршрут отыскивается путем просмотра графа «прямой видимости», в котором представлены все прямолинейные отрезки пути, обходящие препятствия в конфигурационном пространстве. Основным недостатком данного подхода являются трудности, возникающие при поворотах робота, и, кроме того, кратчайший маршрут проходит очень близко к препятствиям.
Аnnotation: When creating a mobile robot one of the central problems is the automatic route planning. This problem is that, when given the initial and final positions of the robot on the map area to build the route by which the robot can get to the destination point, not when faced with obstacles. There are two approaches to solving this problem. In one of them uses the concept of the configuration space, the idea of which is to pull the object (robot) to the point at the same time extending the obstacles in accordance with its shape. The shortest route is searched by viewing a graph "line of sight", in which all segments of straight path, bypassing the obstacles in the configuration space. The main disadvantage of this approach is the difficulty encountered when turning the robot, and, in addition, the shortest route is very close to obstacles.
Ключевые слова: Робот, декомпозиция, планирование маршрута, проходимая область.
Keywords: Robot, decomposition, planning the route traversed area.
Альтернативный подход состоит в том, чтобы непосредственно представить свободное пространство совокупностью некоторых элементов, таких, как выпуклые многоугольники или обобщенные конусы. В рамках такого подхода удается построить маршруты обхода препятствий на более безопасном расстоянии (участки маршрута складываются из осей обобщенных конусов). Предложен также смешанный подход, в котором свободное пространство описывалось в терминах двух элементарных форм: обобщенные конусы и выпуклые многоугольники. Обобщенные конусы хорошо описывают узкие участки свободного пространства между двумя препятствиями. Однако при представлении больших открытых областей они часто оказываются неудобными, так как оси конусов искусственно ограничивают положение участка траектории внутри конуса. С другой стороны, выпуклые многоугольники удобны как раз при описании больших областей, а в случае узких коридоров описание оказывается слишком громоздким.
Для того чтобы пользоваться таким смешанным представлением свободного пространства, необходимо ответить на вопрос о том, в каком месте пространства нужно строить эти элементарные формы, чтобы получить структуру, удобную для планирования маршрута. Для человека кажется естественным строить «канал» между двумя соседними препятствиями, имеющими форму многоугольника, и многоугольник для представления свободного пространства, ограниченного несколькими препятствиями («проходимая область»). Предлагаемый подход к планированию маршрута состоит в том, чтобы попарно проанализировать пространственные соотношения между соседними препятствиями и построить граф «соседства препятствий». После этого по дуальному (по отношению к построенному) графу из обобщенных конусов и выпуклых многогранников можно сформировать соответственно каналы и проходимые области. Таким образом все свободное пространство разбивается на неперекрывающиеся элементарные формы: проходимые области и каналы. В этих терминах алгоритм планирования маршрута выглядит следующим образом.
Многоугольные препятствия могут быть выпуклыми или невыпуклыми. Выпуклые препятствия обладают некоторыми свойствами, которые облегчают процесс построения каналов. В частности, для таких препятствий легче рассчитывать минимальную ширину канала и определять положение наиболее узкого места. Чтобы иметь однородное представление препятствий с сохранением полезных свойств выпуклых фигур, было предложено представлять все препятствия выпуклыми многоугольниками. Невыпуклые препятствия разбиваются на неперекрывающиеся выпуклые части. Алгоритм декомпозиции довольно прост. На невыпуклом многоугольнике выбирается «вогнутая» вершина с максимальным углом. Затем осуществляется просмотр вершин вправо и влево от нее и выбирается максимальное подмножество соседних вершин, образующих выпуклый многоугольник. Этот многоугольник отсекается от исходной фигуры, и при необходимости процесс повторяется вновь с оставшейся частью. Получившиеся в результате процесса декомпозиции препятствия, имеющие общие ребра, обозначаются как соприкасающиеся. Граница карты местности представляется четырьмя прямоугольными препятствиями, которые ограничивают свободное пространство.
Чтобы провести естественную декомпозицию свободного пространства, в первую очередь необходимо ответить на вопрос о том, где следует строить каналы и проходимые области, и определить их отношения связности. Эта информация представляется в виде графа связности, который является удобным средством для описания свободного пространства. В принципе элементы свободного пространства можно было бы описывать единственной элементарной формой – каналом, который всегда можно построить между двумя препятствиями. Однако такой подход ведет к образованию большого количества ложных каналов, не имеющих реального смысла. Эта проблема решается путем выявления соседних препятствий и формирования каналов только между ними.
Известны несколько методов определения отношений соседства для элементарных геометрических фигур, однако все они ориентированы на какой-либо сравнительный узкий класс препятствий. Был предложен также эвристический подход к определению отношений соседства между выпуклыми препятствиями. Для каждой пары выпуклых препятствий определяются те их ребра, которые не находятся на выпуклой оболочке этих препятствий. После этого минимальное расстояние между данными препятствиями может быть найдено путем перебора всех попарных расстояний между вершинами выделенных ребер и расстояний «вершина - ребро». После расчета всех минимальных расстояний между препятствиями и построения соответствующих минимальных отрезков, каждому из которых отвечает своя дуга на графе соседства, производится удаление ложных дуг. Если минимальный отрезок пересекает какое-либо препятствие, то соответствующая ему дуга удаляется из графа. Если два отрезка пересекаются, то удаляется наибольший из них. После завершения этого процесса только соседние препятствия будут соединены отрезками. В результате граф соседства приобретает вид, показанный на (рис.1), где обозначено: 1 – узел, отвечающий проходимости области; 2 – узел, соответствующий препятствию; 3 – дуга, соответствующая каналу; 4 – дуга, связывающая соседние препятствия. На основе этого графа можно проводить планирование маршрута.
На графе соседства каждая дуга отвечает каналу, а каждый цикл представляет проходимую область. Для того чтобы явно показать это свойство, на (рис.1) показан также и дуальный граф, названный графом связности. Узлы этого графа представляют проходимые области, а дуги – каналы.
Рисунок 1 – Граф соседства Рисунок 2 - Многоугольник
Граф связности позволяет определить критические зоны при построении каналов и проходимости областей, а также дает описание связности различных зон свободного пространства. Чтобы провести планирование маршрута, необходимо располагать подробной геометрической информацией о каждой зоне. В рамках описываемого подхода такая информация обеспечивается представлением зон свободного пространства двумя элементарными формами – обобщенными конусами и выпуклыми многоугольниками.
Первоначально обобщенные конусы использовались для представления объектов в некоторых системах технического зрения. В последнее время их применяют и для представления областей свободного пространства при планировании маршрута подвижного робота. В последнем случае конус строят следующим образом. Вначале строится его ось как перпендикуляр к минимальному отрезку, соединяющему два препятствия, проходящий через центр этого отрезка. Эта ось задает положение возможного отрезка маршрута при прохождении робота через наиболее узкое место между данными двумя препятствиями. Однако начало и конец этого отрезка, т.е. места, где робот может войти в канал и выйти из него, на данном этапе определить нельзя – для этого нужно знать форму проходимых областей, связанных рассматриваемым каналом.
В графе связности каждый узел связан с набором (из трех или более) выпуклых препятствий. Эти препятствия образуют цикл на графе соседства, и между любыми двумя соседними препятствиями этого цикла можно построить обобщенный конус. Область свободного пространства, ограниченную циклом, можно представить выпуклым многоугольником. Такое представление позволяет упростить процесс планирования маршрута через проходимые области, так как внутри выпуклого многоугольника любые две точки можно соединить прямой, не пересекающей границы этого многоугольника. Процесс построения такого выпуклого многоугольника поясняется на рис.2. Вначале формируется многоугольник из ребер препятствий и минимальных отрезков, соединяющих эти препятствия. Этот многоугольник в общем случае не является выпуклым. Для формирования выпуклого многоугольника применяется следующий алгоритм, позволяющий удалить вогнутости:
Повторяя эту процедуру для всех вогнутых вершин, можно построить искомый выпуклый многоугольник. Есть два аспекта, на которые следует обратить внимание. Во-первых, в окончательном списке вершин построенного многоугольника необходимо сохранить, по крайней мере, по одной вершине каждого многоугольного препятствия. Во-вторых, если подмножество вершин какого-либо препятствия, входящее в список вершин проходимости области, содержит более одной вогнутой вершины, то из этого подмножества вначале следует удалить концевые вершины. Эти эвристические правила позволяют построить максимально возможный выпуклый многоугольник, описывающий проходимую область.
В некоторых случаях построить выпуклый многоугольник внутри группы препятствий, состоящей более чем из трех объектов, оказывается невозможным. В этом случае алгоритм разбивает соответствующую группу на две путем добавления дополнительного минимального отрезка и соответственно новой дуги в графе соседства. Затем производятся рекурсивные попытки построить выпуклые многоугольники внутри каждой из полученных групп. Рекурсия прекращается после того, как такие многоугольники удается построить для каждой из дочерних групп. После этого для каждой новой дуги в графе соседства строится канал.
Процесс построения выпуклых многоугольников не только дает геометрическое представление проходимых областей, но и завершает представление каналов. Прямолинейные отрезки AB, CD и EG (рис.2), сформированные при построении выпуклого многоугольника, ограничивающего проходимую область, являются входами в три канала. Точка пересечения оси канала с входным отрезком является критической при входе робота в данную проходимую область канала. В принципе канал может выродиться в минимальный отрезок, так как при построении проходимой области выбирается наибольший из возможных выпуклых многоугольников.
Критические точки играют важную роль при построении окончательного маршрута. Каждый канал имеет две точки входа, которые соединяются прямолинейным отрезком – осью канала. Информация о минимальной ширине прохода используется при определении того, может ли робот пройти через данный канал или нет. Каждая проходимая область имеет несколько критических точек. При планировании маршрута любая пара из них может быть соединена отрезком. Совокупность критических точек проходимой области позволяет примерно определить ее площадь (точнее площадь вписанного круга). Эта информация нужна при планировании разворотов робота.
Для упрощения процесса планирования маршрута граф связности свободного пространства преобразуется в рабочий граф, в котором учтена информация о возможности прохода каналов и разворотов внутри проходимых областей. При заданных начальной и конечной точках маршрута алгоритм преобразования вначале определяет, в каких зонах (каналах или проходимых областях) они находятся. Затем он формирует начальный и целевой узлы рабочего графа и соединяет их дугами с критическими точками соответствующих зон. Эти дуги проверяются на пересечение с препятствиями и при наличии пересечений исключаются из графа.
При поиске оптимального маршрута на построенном рабочем графе используется функция локальных затрат, представляющая собой расстояние между двумя узлами, и эвристическая оценка оставшихся затрат – расстояние по прямой до целевой точки. В связи с тем, что свободное пространство представлено явно, границы проходимых областей и каналов вдоль спланированного маршрута могут использоваться при сенсорном контроле отработки маршрута.
Представленный подход к планированию маршрута имеет ряд преимуществ перед известными альтернативными подходами. Эти преимущества связаны с тем, что свободное пространство представляется явно в терминах неперекрывающихся выпуклых многоугольников (проходимых областей) и обобщенных конусов (каналов). Проходимые области являются естественными местами для маневров робота, а каналы – это критические коридоры, которые должны быть достаточно широкими, чтобы робот мог через них пройти.
Литература
1. Поезжаева Е.В//Теория механизмов и механика систем машин. Промышленные роботы: учеб. пособие: в 3 ч. / Е.В. Поезжаева. – Пермь: Изд-во Перм. Гос. техн. ун-та, 2009.-Ч.2-185.
2. Поезжаева Е.В//Теория механизмов и механика систем машин. Учеб. Пособия/Е.В. Поезжаева.- Пермь: Изд-во Пермского национального исследовательского политехнического университета. 2014.-400
3. Поезжаева Е.В//Теория механизмов и механика систем машин. Промышленные роботы: учеб. пособие: в 3 ч. / Е.В. Поезжаева. – Пермь: Изд-во Перм. Гос. техн. ун-та, 2009.-Ч.3-164.
