Цель работы - разработка программного комплекса для отладки и демонстрации задач управления движением групп роботов, а также наблюдения за группой роботов с использованием нескольких камер с использованием Java в среде «Эльбрус». Показана возможность использования вычислительных средств ряда «Эльбрус» в качестве вычислителей для задач управления и наблюдения за группой роботов. Моделирование движения; поиск пути на графе; моделирование алгоритмов группового управления. The purpose of this work is developing the software for debugging and demonstration of tasks of motion control of robots group and monitoring a robots group using multiple cameras using Java language in the OS «Elbrus» environment. The article displays possibility of using computer systems of «Elbrus» series as computer for robots control and monitoring tasks. Motion modelling; search path on the graph; modelling algorithms of group control.
ABSCTRACT Постановка задачи
В предыдущей работе [2] авторами было проведено моделирование алгоритмов поиска пути отдельным роботом и алгоритмов технического зрения. Движение робота было сведено к поиску пути на графе, соответственно был проведен анализ существующих алгоритмов поиска пути на графе. В качестве используемого алгоритма был выбран алгоритм А* с некоторыми изменениями в эвристической функции для учета дополнительных параметров. Для повышения реалистичности модели в нее был включен учет таких параметров робота, как: скорость, ускорение, радиус поворота, радиус обнаружения препятствий. В данной работе планировалось расширить данную модель для моделирования уже не одного, а группы из нескольких роботов.
Формально, в задаче обрабатываются три множества: множество роботов, множество целей и множество внешних факторов. В разрабатываемой программе должно быть моделирование всех этих множеств. Задача поиска пути
Задача поиска пути была сведена к задаче поиска пути на графе из узла-старта до узлафиниша [3, 4]. Пара (V(G), E(G)) называется графом, если V(G) — непустое конечное множество элементов, называемых узлами, а E(G) — конечное множество неупорядоченных пар различных элементов из V(G), называемых рёбрами [5]. При этом поиск необходимо осуществлять, учитывая проходимость различных опорных поверхностеи и радиус поворота робота.
Для задачи поиска пути роботом также необходимо учитывать длину пути, что можно обозначить через вес рёбер. При этом, если робот может переместиться из точки A в точку B, то не обязательно, что он может и переместиться из точки B в точку A. Например, если точка A — это точка на открытои местности, а точка B — точка у стены с азимутом, направленным прямо в стену. Таким образом, для поставленнои задачи подходит использование взвешенного ориентированного графа.
Узел графа по определению представляет собои элемент графа, обозначающии объект любои природы. В даннои задаче узел графа обозначает область на местности, в которую робот имеет возможность встать. Так как необходимо учитывать радиус поворота робота, то необходимо и учитывать азимут робота при построении пути. Таким образом, узел графа задается не только координатами x, y, но и азимутом.
Ребром графа обозначается траектория между узлами, которые она соединяет, по которои может перемещаться робот. При этом траектория строится с учетом радиуса поворота робота. Так как при поиске пути надо учитывать проходимость различных опорных поверхностеи, то вес ребра обозначим как среднии коэффициент проходимости на всём протяжении траектории данного ребра.
Рисунок 1. Обход окружностей в одном направлении Путь робота проходит от узла к узлу. Но эти узлы не могут быть соединены ребрами, являющимися прямыми траекториями, так как робот не имеет возможность мгновенно развернуться в нужном направлении. Поэтому между узлами необходимо находить траекторию с плавными поворотами, соответствующими радиусу поворота робота. При этом необходимо проверять эти траектории на наличие препятствий на пути.
Учет радиуса поворота происходит при построении траектории от узла к узлу. Соответсвенно, каждый узел, помимо координат, характеризовался еще и азимутом. Итоговая траектория между двумя узлами состоит из трех сегментов - двух дуг и отрезка прямой. При этом могут возникнуть два случая, различающиеся подсчетом основных точек: когда обе окружности обходятся в одном направлении и наоборот. Выбирается та, которая имеет наименьшую длину. Варианты обхода окружностей изображены на рисунках 1 и 2.
Задача поиска наилучшего пути могла бы сводиться к задаче поиска кратчаишего пути. Но в реальности данное решение не всегда приемлемо. Путь может проходить по различным опорным поверхностям. Например, есть более длинныи путь по асфальтированнои дороге и более короткии по песку. Заранее известно, что робот движется по песку намного медленнее, чем по асфальту и поэтому лучшии путь был бы более длинным.
Робот оценивает проходимость двумя методами: посредством анализа загружаемои в него карты и посредством своих датчиков.
Первыи метод формирует карту проходимости на основе загружаемои в робота карты местности. Карта местности отображает виды опорных поверхностеи, а карта проходимости отображает коэффициенты проходимости этих поверхностеи.
Второи метод анализирует реальную проходимость и меняет карту проходимости, если реальныи коэффициент отличен от коэффициента на карте. Расчет карты проходимости
При расчете карты проходимости карта местности в формате OpenStreetMap разбивается на квадраты, соответствующие размерам робота. В каждом таком квадрате считается среднии коэффициент проходимости по каждому пикселю. Если хотя бы один пиксель в этои области окажется непроходимым, тогда вся область считается непроходимои. Иначе, робот помечает эту область рассчитанным средним коэффициентом проходимости.
Но с растровыми картами могут возникнуть некоторые проблемы. Во-первых, между разными областями на карте в результате сглаживания, некоторые пиксели не соответствуют ни одному цвету из легенды. Во-вторых, в результате того же сглаживания, некоторые пиксели могут обозначать непроходимую область, хотя на самом деле это не так. И в-третьих, некоторые пиксели могут немного отличаться от цветов в легенде (обычно не больше чем на 2 в одном из каналов). Эти проблемы решаются путем сглаживания, использование скользящего окна и введения небольшои погрешности. Пример формирования карты местности и сформированнои карты проходимости приведен на рисунке 3. Рисунок 3. Пример карты местности и карты проходимости Алгоритм поиска пути
Алгоритмы поиска пути ищут путь на графе из стартового узла в узел-финиш. При этом, в зависимости от алгоритма, путь может быть кратчаишим. Кроме того, некоторые алгоритмы позволяют учитывать вес узлов.
Алгоритм А* считается одним из лучших алгоритмов поиска пути [6]. Он объединяет в себя достоинства двух алгоритмов: учет длины пути из алгоритма Деикстры и учет эвристическои функции из алгоритма «лучшии первыи».
Алгоритм А* [7] использует формулу эвристики, которои в общем случае имеет вид: f(n)=g(n)+h(n), где f(n) — значение оценки для узла n, g(n) — стоимость пути из узла-старта в узел n, h(n) — эвристическое приближение стоимости пути из узла n в узел-финиш.
Функция h(n) должна быть допустимои эвристическои оценкои, то есть не должна переоценивать расстояние до узла-финиша. Одним из способов задания такои функции является длина прямои, соединяющии узел n и узел-финиш.
Алгоритм работает аналогично алгоритму Деикстры, где вместо длины пути учитывается функция f(n), а когда узлу n1 устанавливается родитель n2, пересчитывается функция g(n) следующим образом:
g(n1) = g(n2) + d(n1, n2), где d(n1, n2) — расстояние между узлами n1 и n2.
Так как подразумевается использование различных опорных поверхностеи с разными коэффициентами проходимости и учет радиуса поворота, то функции g(n) и h(n) были изменены.
Функция g(n) должна учитывать не только длину ребра, но и его вес. При этом желательно внести штраф к поворотам. При указании узлу n1 родителя n2 происходит пересчет функции g(n) следующим образом:
g(n)=g(n2)+d(n1, n2)*w(n1, n2)+r(n1, n2)*w(n1, n2), где d(n1, n2) — длина пути от узла n1 до узла n2, w(n1, n2) — вес ребра, соединяющего узлы n1 и n2, r(n1, n2) — суммарныи угол поворота в радианах ребра, соединяющего узлы n1 и n2.
Оценка h(n) рассчитывается как длина пути от узла n до узла финиша с учетом направлении узла n и узла финиша, умноженная на среднии вес. Среднии вес в данном случае рассчитывается как среднее значение веса в точках узла n и узла финиша. Поиск пути группой роботов
Для разрабатываемои модели было принято использовать схему независимого управления с использованием общих ресурсов. Каждыи робот движется независимо от других в свою целевую точку, считая остальных роботов препятствиями, которые надо объезжать. Общение между роботами происходит через управляющую машину, которая уведомляется обо всех обнаруженных несоответствиях карты местности и карты реальности. Далее, управляющая машина уведомляет всех роботов о необходимости изменении карты проходимости, вследствие чего все роботы имеют одинаковую и актуальную карту проходимости, позволяющую более точно планировать маршрут. На рисунке 4 изображено окно программы с группои из трех роботов.
Рисунок 4. Окно программы с группой из трех роботов Рисунок 5. Окно программы наблюдения за группой роботов
Наблюдение за роботами осуществляется группой камер с такими различными параметрами, как радиус обзора и угол обзора. В данной модели предполагается, что отдельная камера способна отследить в своей области видимости отдельных роботов и вести их от момента въезда в область видимости до момента выезда из области видимости. Если робот выезжает из области видимости на любое время большее минимального кванта, воспринимаемого программой, то считается, что камера его «потеряла» и следующий въезд будет восприниматься как въезд другим роботом. Далее алгоритм поиска соответствий ищет точки въезда и выезда и областей видимости, которые могли бы принадлежать одному роботу. При поиске соответствий помимо местоположения учитываются такие характеристики роботов, как: скорость, ускорение и азимут. Если области видимости камер перекрываются, и робот проехал через это перекрытие хотя бы в одной точке, то соответствие между траекториями с камер определяется отдельно и однозначно. На рисунке 5 изображено окно программы с добавленными камерами, обнаруженными траекториями и некоторыми соответствиями.
Рисунок 6. Временные характеристики алгоритма построения графа проходимости
Рисунок 7. Временные характеристики алгоритма поиска пути Тестирование
Разработанныи программныи стенд позволяет проводить эксперименты для оценки скорости работы алгоритмов поиска пути, как для одиночного робота, так и в составе группы. Было
В статье показано, что вычислительные средства ряда “Эльбрус” могут удовлетворять требованиям, предъявляемым РТК в области планирования маршрута и наблюдения за группои роботов. Показаны временные характеристики для соответствующих алгоритмов.
Использование отечественных вычислительных средств и сертифицированного ОПО “Эльбрус” позволяет говорить о перспективах решения задач импортозамещения в области робототехники.
References