Содержание к диссертации
Введение
ГЛАВА 1. Анализ современного состояния систем технического зрения и управления роботами 10
1.1.Анализ параметров среды (зданий) и мобильных роботов существенных с точки зрения решения задачи обнаружения препятствий и управления движением 10
1.2.Современное состояние систем технического зрения, планирования движения и управления роботами в зданиях и сооружениях 14
1.3. Системный анализ характеристик и параметров подвижных и неподвижных объектов в зданиях и сооружениях 32
1.4.Цель и задачи исследования: 36
1.5.Результаты и выводы по главе 1 37
ГЛАВА 2. Разработка алгоритмов распознавания объектов в ближней зоне робота 38
2.1.Задача распознавания объектов в ближней зоне робота 38
2.2.Хранилище объектов 40
2.3. Синтез алгоритма поиска и распознавания известных объектов 42
2.4.Синтез алгоритм распознавания известных и неизвестных объектов и размещения их в хранилище данных 54
2.5.Примеры работы алгоритмов 66
2.6.Результаты и выводы по главе 2 75
ГЛАВА 3. Разработка методики и алгоритмического обеспечения управления роботом 77
3.1.Постановка задачи управления роботом внутри зданий и сооружений 77
3.2.Разработка методики управления движением робота 79
3.3. Разработка алгоритма построения карты препятствий 84
3.4.Предотвращение столкновений с препятствиями 94
3.5.Примеры работы алгоритмов 95
3.6.Результаты и выводы по главе 3 97
ГЛАВА 4. Оценка эффективности разработанных методик и алгоритмов 99
4.1.Оценка эффективности алгоритмов распознавания объектов з
4.2. Оценка эффективности методики создания траекторий робота 105
4.3.Разработка структуры системы управления движением робота 108
4.4.Результаты моделирования движением робота в зданиях и сооружениях 110
4.5.Результаты и выводы по главе 4 114
Заключение 115
Список сокращений 117
Список литературы 118
- Системный анализ характеристик и параметров подвижных и неподвижных объектов в зданиях и сооружениях
- Синтез алгоритма поиска и распознавания известных объектов
- Разработка алгоритма построения карты препятствий
- Оценка эффективности методики создания траекторий робота
Введение к работе
Актуальность темы исследования. Повышение вычислительной мощности ЭВМ, появление новых методов управления и распознавания образов обуславливают в ближайшей перспективе повсеместное внедрение роботов в повседневной жизни человека. Эффективное применение роботов внутри зданий и сооружений сопряжено с рядом трудностей, решение которых позволит обеспечить повышение качества управления ими.
При управлении движением мобильного робота одной из важнейших задач является определение его местоположения. Для этой цели применяются семантические карты, содержащие визуальную информацию об окружающей среде, полученную с применением системы технического зрения (СТЗ) робота.
В настоящее время большинство СТЗ используют несколько видеокамер. Они позволяют получить достаточно точные результаты, но являются критичными по отношению к распознаванию человека или изменению фона изображения. Это приводит к снижению точности распознавания и увеличению вычислительных мощностей, а значит и времени распознавания объекта. Для устранения указанных недостатков могут применяться данные глубин изображений, различающихся по цвету и текстуре и занимающие определенную область в пространстве. Для автономной навигации мобильных роботизированных платформ в зданиях и сооружениях необходимо решить задачу объезда подвижных (человек) и неподвижных (предметы, мебель, оборудование и пр.) препятствий. Для этого СТЗ робота должна обнаруживать и распознавать максимально возможное количество препятствий, обеспечивая перемещение без столкновений.
В прикладном плане внедрение результатов работы создает новые условия и возможности для контроля и управления роботами с применением семантических карт. Кроме того, развитие данного направления позволит создать новые условия для проведения экспериментальных работ и расширить возможности для дальнейших научных исследований.
Степень разработанности темы. Вопросы управления движением робота и распознавания образов для целей планирования траектории его движения представлены в трудах российских и зарубежных ученых: Носков В.П., Дзинько Р., Пурдаков С.Ф., Andrzej Pronobis., Young D. Kwon., Choset H. etal., T. Lozano Perez., R. Bohlin., Y. Hwang., K. Hoff., O. Khatib, M. Sabry Hassouna., Navneet Dalal., Shotton J., Knuth D., Mojtahedzadeh R и др.
Решенные в работе задачи способствуют развитию теории и практики управления мобильными роботами в зданиях и сооружениях. Актуальность темы исследования определяется необходимостью разработки методик управления движением робота и алгоритмов распознавания подвижных и неподвижных препятствий для обеспечения перемещения мобильных робототехнических платформ в заранее неизвестной среде. Разделы диссертационного исследования соответствуют основным положениям «Стратегии развития отрасли информационных технологий в РФ на 2014-2020 годы и на перспективу до 2025 года», в части касающейся развития робототехнических систем и устройств.
Объект исследования – система управления движением робота внутри зданий и сооружений.
Предмет исследования – модели, методы и алгоритмы обнаружения препятствий и управление роботом внутри зданий и сооружений.
Целью диссертационной работы является повышение эффективности управления движением робота за счет разработки алгоритмов распознавания образов.
Научной задачей решаемой в данном исследовании, является разработка взаимосвязанного комплекса методики и алгоритмов, как основы системы управления движением робота внутри зданий и сооружений. Для достижения поставленной цели требуется решить следующие задачи:
-
провести анализ основных параметров и факторов мобильного робота как объекта управления, а также окружающей среды (зданий и сооружений), в которой он функционирует;
-
разработать алгоритм распознавания неизвестных объектов (как подвижных, так и неподвижных) в ближней зоне робота на основе проведенного анализа факторов и применения алгоритма 3D-pointcloud;
-
разработать алгоритм распознавания известных объектов (подвижных и неподвижных препятствий) для предотвращения столкновения с ними робота, основанный на алгоритме поиска ближайших соседей, модифицированный для применения совместно деревьями поиска, алгоритмом SURF (англ. Speeded Up Robust Features) и библиотекой FLANN (англ. Fast Library for Approximate Nearest Neighbors);
-
на основе оригинальных алгоритмов обнаружения препятствий, построения их карты, а также построения траекторий движений, синтезировать методику управления движением мобильного робота в заранее неизвестной среде;
-
разработать систему управления движением робота в зданиях и сооружениях на основе модифицированных алгоритмов SURF, KNN (англ. k-nearest neighbors). Проведена оценка эффективности синтезированных алгоритмов и разработанной методики, подтвердившая повышение эффективности распознавания препятствий и управления движением мобильного робота в заранее неизвестной динамически изменяющейся окружающей среде.
Научная новизна диссертационного исследования состоит в следующем:
-
синтезирован алгоритм распознавания известных объектов, расположенных в ближней зоне мобильного робота, использующий данные, поступающие от датчика СТЗ (совмещающего в себе видеокамеру и инфракрасный сенсор глубины), отличающийся использованием алгоритма поиска ближайших соседей, модифицированного для применения совместно с деревьями поиска, библиотекой FLANN, а также алгоритмом SURF и позволяющий повысить эффективность обнаружения препятствий по сравнению с существующими алгоритмами;
-
синтезирован алгоритм распознавания неизвестных объектов, отличающийся использованием модифицированного алгоритма построения трехмерных облаков точек, обеспечивающий повышение эффективности и снижение времени распознавания препятствий и позволяющий обнаружить любые препятствия в ближней зоне робота при любом освещении без использования дополнительного источника света;
-
разработана методика управления мобильным роботом в заранее неизвестной
среде зданий и сооружений, реализованная в форме трех алгоритмов, а именно: обнаружение препятствий, построение карты препятствий и построение траекторий, отличающаяся использованием алгоритма 3D-pointcloud для повышения эффективности и снижения времени на распознавание образов.
Теоретическая значимость работы состоит в том, что разработаны алгоритмы обнаружения препятствий и методика создания траекторий движения робота для целей управления перемещением мобильных роботов в заранее неизвестной среде зданий и сооружений.
Практическая значимость работы. Разработанная система управления движением робота внутри зданий и сооружений позволяет расширить возможности использования СТЗ роботов построенных на основе любых датчиков, позволяющих получить цветное изображение (кадр), карту глубин изображений, а также 3D-облако точек. Все синтезированные алгоритмы используют данные о расстоянии до препятствия, не зависят от света видимого спектра, позволяют производить распознавание в полной темноте, исключая необходимость дополнительного освещения.
Сформирована структура программного комплекса, разработан программный компонент, зарегистрированный в Федеральной службе по интеллектуальной собственности. Учебный вариант разработанного программного обеспечения используется в ФГБОУ ВПО «АГТУ» для подготовки научных и инженерных кадров.
Результаты внедрены в ООО «АГТУ Роботикс» (г. Астрахань) при разработке системы управления движением робота для проекта «MobileBot».
Методология и методы исследования. В процессе работы использовались методы системного анализа, распознавания образов, теории алгоритмов, математической статистики, теории принятия решений, теории множеств, теории баз данных и объектно-ориентированного программирования.
Положения, выносимые на защиту:
-
алгоритм распознавания известных (подвижных и неподвижных) препятствий в ближней зоне мобильного робота;
-
алгоритм распознавания неизвестных (подвижных и неподвижных) препятствий в ближней зоне мобильного робота;
-
методика управления движением робота внутри зданий и сооружений в заранее неизвестной среде.
Апробация научных результатов. Основные положения докладывались и обсуждались на Всероссийской научно-исследовательской конференции с международным участием молодых ученых, аспирантов, студентов и старшеклассников «Наука, образование, инновации: пути развития» (Петропавловск-Камчатский, 2014 г.); VIII Международной научно-практической конференции «Интеграция теории и практики мирового научного знания в XXI веке» (Казань, 2014 г.); XXVI - Международной научной конференции математические методы в технике и технологиях - ММТТ-27 (Саратов , 2014 г.); Международной научной конференции «Фундаментальные и прикладные исследования в современном мире», Информационный издательский учебно-научный центр «Стратегия будущего» (Санкт-Петербург, 2014г.);Международной научной конференции «CIT&DS Creativity in intelligent technologies & data science»(Волгоград, 2015 г.).
Публикации. Основные положения настоящей диссертационной работы изложены в 10 научных публикациях, среди которых 3 статьи в научных журналах, рекомендованных ВАК РФ, 1 статьи в изданиях, индексируемых в базе данных SCOPUS, 4 публикации в сборнике международных и всероссийских научных конференций, получено 1 свидетельство о государственной регистрации программы для ЭВМ.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка сокращений и условных обозначений, библиографического списка, 6 приложений. Основная часть работы изложена на 144 страницах машинописного текста, содержит 83 рисунка, 22 таблицы. Библиографический список содержит 133 наименований.
Системный анализ характеристик и параметров подвижных и неподвижных объектов в зданиях и сооружениях
В 1969 году Marvin Minsky обладатель премии Тьюринга (Turing Award) и пионер робототехники и искусственного интеллекта обобщил результаты, достигнутые исследователями во второй половине 20-го века: «В пятидесятых годах было предсказано, что через 5 лет роботы будут везде. В шестидесятых годах, было предсказано, что через 10 лет роботы будут везде. В семидесятых годах, было предсказано, что через 20 лет роботы будут везде. В восьмидесятых годах, было предсказано, что через 40 лет роботы будут везде» [1].
Это утверждение показывает, что существующая уверенность и ожидания робототехнического сообщества наталкиваются на непредвиденные проблемы, вытекающие из сложности неструктурированной окружающей среды. Проблемы требуют многолетних исследований во многих областях (например, обработка сигналов, статистика, машинное обучение и техническое зрение) для достижения такого уровня, на котором разработанные алгоритмы могут быть применены в реальном мире для практических целей.
Следующее поколение роботов будет не только отслеживать собственное местоположение, и перемещаться между точками в пространстве, но и «понимать» окружающее пространство и взаимодействовать с людьми, в том числе на естественном языке.
В сфере обслуживания роботы используются для выполнения простых небольших задач. На рынке представлены роботы для уборки помещений (например, «IRobot Roomba»). Эти устройства иногда оснащаются дополнительными функциями, например, визуальная навигация. Простые роботы становятся популярными в образовании и развлечении. В области безопасности роботы являются более сложными и обеспечивают работу в таких условиях, где человек в силу разных причин не может находиться. Эти платформы обеспечивают не только навигацию, но и автономно взаимодействуют с окружающей средой и «общаются» с людьми.
В последнее время большинство достижений в таких областях, как компьютерное зрение и когнитивная робототехника обусловлены
необходимостью создания искусственных когнитивных систем, способных выполнять задачи в реальных условиях. Краеугольным камнем для таких роботов является их понимание о пространстве, в котором они функционируют. Пространственное понимание является предпосылкой для таких базовых задач, как навигация, обход препятствий, автономная разведка или манипуляции. Существует также множество других задач, которые зависят от способности воспринимать и понимать окружающее пространство.
Наиболее существенным требованием к современным мобильным роботам является возможность автономного перемещения без столкновений в реальной недетерминированной среде на основе информации, получаемой от системы технического зрения [23]. Существуют системы навигации на основе дальномеров [96, 109], CCD-камер (видеокамер [7], стереокамер [8] и т.д.), глубинных сенсоров [22] и ряд других. Очень перспективное направление - создание систем навигации роботов в зданиях и сооружениях с применением инфракрасных сенсоров глубины, работающих совместно с видеокамерой, таких как Microsoft Kinect [40] или Asus Xtion [121]. Сферы применения мобильных роботов в зданиях и сооружениях – роботы специального назначения [114], рекламно информационные [96] и пр. CCD-камеры
CCD-камера является достаточно часто используемой и состоит из одной или двух камер [20]. В последнее время проведено значительное число исследований, в которых используют CCD-камеры для обнаружения объектов. Основным недостатком CCD-камер является то, что они работают только на основе видимого спектра.
Основные преимущества CCD-камеры [18]: позволяет получить большой объем информации; обеспечивает получение информации об окружающей среде в трехмерном пространстве; обладают низкой стоимостью по сравнению с аналогами. Однако данный вид технических устройств обладает и рядом недостатков [41], а именно: для обработки изображений требуются значительные вычислительные мощности; на качество получаемой информации существенное влияние оказывает освещенность внутри зданий и сооружений.
Дальномеры Лазерные дальномеры используют лазерный луч, который отражается от вращающегося зеркала к цели [82], а затем возвращается к датчику для выполнения требуемых расчетов. Используются два основных типа дальномеров. Первый тип испускает непрерывный пучок, и данные вычисляются по возвращении к приемнику этого пучка [2]. Второй тип - импульсный лазер, который посылает множество лазерных импульсов и рассчитывает среднее на каждом импульсе для определения расстояния до объекта. Основные преимущества лазерных дальномеров [113]: высокая скорость работы; высокая точность определения расстояния; данные полученные дальномером можно интерпретировать непосредственно как расстояние до препятствия в определенном направлении. Основными недостатками являются высокая стоимость и «прозрачность» некоторых материалов для лазерного дальномера (например, стекло). Сенсоры глубины В отсутствии света использование камер также затруднительно. В последнее время в данной области произошел ряд достижений. Например, Kinect системы применяются для измерения расстояний, обнаружения ориентиров и создания 3D-моделей [40].
Дороговизна сенсоров глубины (в которых применялись лазеры) долгое время препятствовала активному их внедрению. Однако, с появлением Microsoft Kinect, существенным образом может быть повышено качество и скорость распознавания подвижных препятствий [19, 40].
Основные преимущества сенсора глубины типа Microsoft Kinect: низкая стоимость; диапазон глубины и встроенное программное обеспечение позволяют автоматически откалибровать датчик с учтом условий окружающего пространства; высокая скорость работы; возможность получения большого объема информации; возможность получения 3D-информации об окружающей среде и препятствиях; отсутствие зависимости от интенсивности освещения [7].
Основные недостатки устройства – «прозрачность» ряда материалов и ограниченный диапазон измерения расстояния до объекта (от 0,8 м) [40]. Сравнение датчиков Сравнение датчиков выполняется на основе факторов и параметров окружающего пространства на основе следующих критериев: работа при любых условиях освещения (РПЛУО); время обнаружения (ВО); время отклика (БВО); расстояние обнаружения (РО); стоимость (Ст).
Синтез алгоритма поиска и распознавания известных объектов
При движении внутри зданий существуют большое число объектов, окружающих робота, оказывающих влияние на траекторию его движения, в том числе к ним относятся известные объекты. Они не только являются ориентирами, но и определяют способы объезда препятствий. Для распознавания известных объектов используются различные эффективные алгоритмы, большинство из которых функционирует на основе RGB-изображений [16].
Для получения особенностей образа объекта наиболее часто применяются статистические выборки на основе локальных особенностей [65] или методы извлечения особых точек изображения [4, 37]. При этом методы извлечения особых точек изображения реализованы в большинстве библиотек, таких как OPENCV и OPENNI [9]. Обнаружение объектов - алгоритмы SURF [4] и SIFT [72]. Сравнение результатов использования этих двух алгоритмов [37, 67] показывает преимущество SURF над SIFT и его более высокую эффективность. Кроме того, алгоритм SURF реализован в стандартных библиотеках распознавания изображений [42].
Алгоритм распознавания известных объектов Основа работы системы распознавания известных объектов - алгоритм, показанный на рисунке 2.3. Опишем каждый из его блоков. Синтез алгоритма извлечения особых точек изображения «SURF» (блок 2.3.3)
Алгоритм работает на основе матрицы Гессе [49, 56], но использует очень простые аппроксимации. Этот алгоритм опирается на интегральные изображения [85], чтобы сократить вычислительные затраты и уменьшить время. Поэтому он называется детектор «Fast-Hessian» [28]. Дескриптор описывает распределение «Haar-wavelet» [68] в пределах процентных точек. Вход интегрального изображения 1(х,у) при местоположении Х= (х, у) определен как: /=07=0 где 1(х,у) представляет собой сумму всех пикселей в прямоугольной области исходного изображения /, образованном с Х= (х, у). Вычисляется Цх,у) за четыре дополнения, чтобы рассчитать сумму интенсивностей любой вертикальной прямоугольной области [4]. Детектор «Fast-Hessian» Алгоритм базируется на матрице Гессе и обладает высокой производительностью и хорошей точностью. Тогда Гессиан: \Lxx{X,d) LXV(X,G)] (2.2) где, Lxx(x,a) - Гауссова свертка: LJCJC(X,a) = g(a) (2.3) Гауссианы являются оптимальными для пространственного анализа [46]. Однако на практике Гауссова свертка должна быть дискретной и даже с гауссовыми фильтрами сглаживание происходит таким образом, что результирующие изображения являются субдискретными.
Интегральные изображения
Интегральные изображения используется для повышения эффективности вычисления матрицы Гессе. Пусть изображение I - цифровое изображение, определяемое по пиксельной сетке Q = [[0,M]]x[[0,N]], где М и N являются неотрицательными целыми числами, [[А, В]] обозначает интервал целочисленных значений между двумя целыми числами A и B. При этом рассматриваются только серые изображения, являющиеся простыми и устойчивыми к модификациям цвета, в котором изображения всегда нормализованы в пределах от 0 до 255. Интегральное изображение I определяется по формуле (2.1).
Алгоритм SURF обеспечивает определение преобладающей ориентации перепадов особых точек для вычисления инвариантности их дескрипторов. Первоначально SURF вычисляет градиенты в соседних пикселях особой точки с использованием фильтр Хаара [4]. Размер фильтра 4s, где s – масштаб особой точки. Рисунок 2.5 - Пример фильтра Хаара значение черной области:
Точечное значение перепада яркости по оси X и Y получается с помощью фильтра Хаара. Форма фильтра является прямоугольной, значения параметров фильтра рассчитываются с помощью интегральной матрицы и требуют всего 6 операций для вычисления одного фильтра произвольного размера [4].
Фильтры Хаара используют значения dX и dY, которые умножаются на вес для каждой точки. Вес является значением Гауссиана с центром в особой точке и сигмой равной 2s (где s - масштаб особой точки) [97].
Далее используется угловое окно с размером /3 [4] вращающееся вокруг центра координат. Алгоритм выбирает положение окна, в котором получается максимальная длина суммарного вектора точек для уменьшения влияния шумов. Алгоритм не требует инвариантности дескрипторов вращения, в которых не вычисляется ориентация особых точек, а идентифицирует точки, которые вращаются не более чем на ±15 градусов [4]. Конструкция дескрипторов Дескриптор - массив из 64 (или 128) чисел, идентифицирующий особую точку. Прямоугольная область используется для вычисления дескриптора вокруг особой точки размером 20s. Размер первой области равен 40x40 пикселей, она сориентирована вдоль направления, вычисленного для особой точки. Дескриптор - описание градиента 16 квадрантов вокруг особой точки [97].
Рисунок 2.7 - Иллюстрация получения градиента особой точки [4]
Квадрат разделен на 16 субрегионов, образованных регулярной сеткой 5x5, используемой для нахождения градиента на точках сетки с применением фильтра Хаара. Необходимо отметить, что при вычислении фильтра Хаара, изображение не вращается, фильтр обрабатывает обычные координаты изображения. Однако, при этом получаются координаты градиента (dX,dY), вращаемые на соответствующий угол как и ориентация квадрата. Таким образом, 400 фильтров Хаара используются для вычисления дескрипторов особой точки (в каждом из 16 субрегионов вычисляются 25 фильтров Хаара).
После этого, алгоритм вычисляет четыре значения (рис.2.8), которые и являются компонентами дескриптора: YJdx Yidx\ dY YidY\. Где, dx и dY суммируются по каждому субрегиону и Yidxl dY являются абсолютными значениями dX dY. Эти значение показывают поведения разных участков изображений и сохранятся в векторе v.
Дескриптор SURF получается конкатенациями 16 векторов, вычисленных для каждого субрегиона нормализацией соответствующего 64-мерного вектора. Поэтому его Евклидова норма является унитарной. Таким образом, дескриптор является инвариантным к изменению аффинного контраста [66].
Для нахождения объекта в изображении присутствует два набора дескрипторов особых точек, извлекаемых из двух изображений. Дескриптор SURF является 64-мерным вектором с унитарной евклидовой нормой. Дескрипторы хранятся в соответствующих векторах v1 и v2. Нахождение соответствия - сравнение векторов v1 и v2 по методу ближайших соседей [50, 71]. Для этой цели алгоритм SURF имеет несколько версий, наиболее применяемыми являются два алгоритма - «Gpu SURF Detector» и «Match SURF Feature With Feature Tree». Оба алгоритма используются для поиска соответствий между дескрипторными точками образа и изображения с камеры (рисунок 2.9).
Оба алгоритма состоят из основных шагов: извлечение дескрипторов изображения, поиск соответствий между точками, получение результатов. В шаге «Извлечение дескрипторов изображения» для ускорения вычисления дескрипторов алгоритм «Gpu SURF Detector» использует функции, которые поддерживаются графическим процессором. Входные изображения конвертированы в «GpuImage» (формат используемый в графическом процессоре). Функция «Gpu SURF Detector» используется для получения дескрипторов. В Алгоритме «Match SURF Feature With Feature Tree» входные изображения не конвертируют в специальный формат. Для этого используется функция «SURFFeature», обеспечивающая получение дескрипторов.
Поиск соответствий между точками: для поиска соответствий между точками алгоритм «Gpu SURF Detector» выполняет функцию «GpuBruteForceMatcher» с параметром «DistanceType.L2 - квадрат евклидова расстояние». Эта функция работает как линейный поиск. Алгоритм «MatchSURFFeatureWithFeatureTree» используется с деревом принятия решений. Алгоритм работает как поиск ближайшего соседа. В этом алгоритме выполняется функция «MatchSURFFeatureWithFeatureTree». Алгоритм работает быстро, но качество результата не соответствует требованиям решаемой задачи.
Синтез алгоритм поиска ближайших соседей (блок 2.3.5) Для распознавания неподвижных объектов применяются два алгоритма: линейный поиск (требует существенных вычислительных затрат) [45] и приблизительный поиск ближайших соседей (обеспечивают поиск с требуемой точностью за приемлемое время) [54]. В алгоритме поиска ближайших соседей (алгоритм NNS) существует задача оптимизации нахождения ближайших точек. Близость обычно выражается в терминах функции несходства. Однако наиболее часто применяется приблизительный поиск ближайших соседей, в котором существуют три известных алгоритма: FLANN [54], ANN [60], STANN [15]. В робототехнике наиболее часто применяется FLANN, т.к. поддерживается в большинстве библиотек, таких как OPENCV и OPENNI [23].
Разработка алгоритма построения карты препятствий
Управление движением робота является крайне актуальной и сложной задачей. В общем случае окружающая среда очень сложна из-за особенностей ее изменения (освещение и угол обзора) и препятствий. Изменения в окружающем пространстве робота могут происходить очень быстро, что приводит к снижению точности распознавания препятствий.
Кроме того, робот должен обладать всей необходимой информацией о состоянии среды в ближней зоне, в т.ч. данными о наличии, направлении и скорости перемещения препятствий [48], определяющих требования к построению траектории и планированию движения. Это означает, что отсутствует информация о препятствиях, которые блокируют перемещение робота по траектории движения. Если неизвестное препятствие обнаружено, то появляется необходимость использования датчиков системы технического зрения и алгоритма обнаружения препятствий. Кроме того, необходимо идентифицировать препятствие с целью поиска его в хранилище известных объектов и в случае, если оно в нем отсутствует, то добавить, чтобы проложить новый маршрут для решения задачи препятствования столкновению [1, 87]. Для этих целей необходимо решить следующую задачу путем синтеза оригинального алгоритма, реализующего следующие подзадачи (ПоЗ):
Для управления движением мобильного робота в пространстве обычно применяются три метода: планирование глобального пути (globalpathplanning) [89], планирование локального пути (localpathplanning) [89], гибридный метод (hybridmethod) [86]. При этом наиболее эффективным является именно последний метод [86].
На основе вышеизложенного, методика планирования движения робота может быть реализована с использованием трех известных методов: планирование глобального пути (ПГП), планирование локального пути (ПЛП), гибридный метод (ГМ). Метод ПГП - определение траектории от начала до конца для всей карты в целом. Метод ПЛП обеспечивает управление движением в ближней зоне робота и распознавание динамических препятствиями лучше, чем ПГП. Однако, метод ПГП позволяет предотвратить попадание робота в ловушку бесконечного цикла, которая может возникнуть при использовании ПЛП.
Рисунок 3.2 -Конфигурирование пространства
Как правило, первый шаг построения траектории движения робота -преобразование пространства в непрерывные геометрические формы и геометрическая декомпозиция. Это представление называется конфигурирование пространства [80] (рисунок 3.2). 3.2.1. Конфигурирование пространства
Непрерывные геометрические карты. Окружающая среда является непрерывной двухмерной плоскостью, зависящей от структуры препятствий, наполненных множеством точек, отрезков, многоугольников и т.д. Путь, соединяющий текущее местоположение робота и цели формируется сетью одномерных кривых и (или) линий, называется дорожная карта [58]. Существует два подхода к формированию дорожной карты - график видимости [80] и диаграмма Вороного [30]. Более эффективным является метод графика видимости.
График видимости. Стандартный график видимости определен в двухмерной многоугольной конфигурации пространства. Узлы графика видимости включают начальную точку, цель, а также все вершины препятствий в конфигурируемом пространстве. Рисунок 3.3 -Планирование траектории (метод графика видимости) Края графика видимости являются прямолинейными отрезками, соединяющими два узла в прямой видимости. Оптимальная траектория от начальной точки к целевой вычисляется функцией поиска на графе с использованием стандартного метода поиска экстремума [80], например, алгоритм «A-Звезда» [110]. При этом график видимости будет являться оптимальным (рисунок 3.3).
Геометрическое разложение. Если окружающая среда разделена на множество подобластей, то эти подобласти называются клетки или ячейки. Окружающая среда разделяется на свободные и занятые ячейки, для этого применяется декомпозиция на соты и картографирование сетки размещения (Occupancy grid mapping). Декомпозиция на соты. В этом методе свободное окружающее пространство препятствий разделено на множество подобластей. Они называются ячейки.
Оценка эффективности методики создания траекторий робота
Результаты экспериментов показывают, что существует возможность совместного распознавания нескольких подвижных и неподвижных объектов в режиме реального времени с применением Kinect. Однако, для увеличения быстродействия традиционных алгоритмов распознавания, следует применять параллельное программирование. Для удобства сравнения полученных в рамках исследования результатов все полученные данные сведены к одной диаграмме, демонстрирующей эффективность предложенных в работе алгоритмов (рисунок 4.4).
Как показано ранее, появляется ряд трудностей: масштаб, место, фон и помехи, проекция, вращение и угол обзора при обнаружении препятствий. Эксперименты проводились с использованием двух методов обнаружения препятствий: 3D-облако точек [101]; библиотека FLANN и алгоритм SURF [98]. Рассмотрено изменение интенсивности света к качеству обнаружения (для различного времени суток - 10:00, 14:00, 19:00, 23:00) без искусственного освещения, полученные результаты представлены на рисунке 4.6. и в таблице 4.4.
Полученные результаты свидетельствуют о том, что предложенные алгоритмы распознавания объектов удовлетворяют жестким требованиям по обнаружению объектов в режиме реального времени. Это означает, что предложенный подход может применяться в системах технического зрения мобильных робототехнических платформ для получения сенсорной карты внешней среды, используемой системой управления роботом для перемещения в зданиях и сооружениях в заранее неизвестной среде.
Разработанная методика содержит основные шаги: обнаружение препятствий; построение карты препятствий; построение траекторий (рисунок 4.7). Основа обнаружения препятствий - алгоритм 3D- Pointcloud. В шаге «построение карты препятствий» используется метод построения на основе непрерывных геометрических карт (Continuous geometric maps), используемых в методе «планирование глобального пути».
Непрерывные геометрические карты (НГК) описывают среду робота точнее, чем метод геометрического разложения (МГР). НГК характеризуются высоким уровнем затрат вычислительных ресурсов для создания и обновления карты, что является неизбежным условием, например, когда робот движется в неструктурированных средах (в здании и сооружении).
Полученные результаты показаны на рисунках 4.8–4.10.и таблице 4.5. Время управления движением робота разделяется на три основных части: время обнаружения препятствий (ВОП); время построения карты препятствий (ВПК); время создания траектории (ВСТ). Время обнаружения препятствий является основным.
Для ускорения решения задачи управления движением робота внутри зданий и сооружений разработана система, приведенная на рисунке 4.11. Для этих целей разработана программа для ПЭВМ на языке Microsoft Visual C# 2010, которая зарегистрирована в Роспатенте РФ, представленной в Приложение А. Основными модулями системы управления являются: модуль получения и предварительной обработки исходных данных (мд.1); модуль обнаружения известных объектов (мд.2); модуль обнаружения неизвестных объектов и построения карты препятствий (мд.3); модуль создания траектории движения робота (мд.4); модуль применения алгоритма избегания препятствий (мд.5). мд.1 получает все данные от датчика «Kinect» (RGB- изображения, глубинные данные, «Skeleton» данные и т.д). Корректируются все пиксели, которые имеют нулевые значения и дающие ошибочные результаты. В этом блоке используется алгоритм, синтезированный в п.2.4.1. мд.2 обеспечивает обнаружение известных объектов с применением библиотеки FLANN и алгоритма SURF в режиме реального времени. В этом блоке используются библиотеки OPENCV и EmguCV (алгоритм синтезирован в п.2.3). 110 мд.3 предназначен для решения задачи обнаружения неизвестных объектов и построения карты препятствий. В этом блоке вся информация о препятствиях обрабатываются на основе 3D–облака точек. Основная работа алгоритма приведена в п.2.4 и рисунке 2.17. мд.4 получает данные из Бл.2 и Бл.3. Задача этого блока - построение карты препятствий и применение алгоритма «А » для создания траектории движения робота. Этот блок использует методику, разработанную в главе 3. Результаты решения задачи выводятся на экран и сохраняются в хранилище данных.