автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Модели и алгоритмы картографирования среды и планирования движений автономных мобильных роботов для мониторинга лабиринтов

На правах рукописи

Кучерский Роман Владимирович

МОДЕЛИ И АЛГОРИТМЫ КАРТОГРАФИРОВАНИЯ СРЕДЫ И ПЛАНИРОВАНИЯ ДВИЖЕНИЙ АВТОНОМНЫХ МОБИЛЬНЫХ РОБОТОВ ДЛЯ МОНИТОРИНГА ЛАБИРИНТОВ

Специальность:

05.13.01 - системный анализ, управление и обработка информации

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

17 АПР 2014

Москва 2014

005547222

Работа выполнена на кафедре «Проблемы управления», факультета «Кибернетика» Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный технический университет радиотехники, электроники и автоматики» (МГТУ МИРЭА).

Научный руководитель: Манько Сергей Викторович,

доктор технических наук, профессор, профессор кафедры «Проблемы управления» МГТУ МИРЭА.

Официальные оппоненты: Ермолов Иван Леонидович,

доктор технических наук, доцент, доцент кафедры «Робототехника и мехатроника» ФГБОУ ВПО МГТУ «СТАНКИН». Синнцын Сергей Владимирович, кандидат технических наук, доцент, начальник отдела ФГУП МОКБ «Марс».

Ведущая организация: Национальный исследовательский

университет «МЭИ».

Защита состоится « 22» мая_ 2014 г. в 13 часов на

заседании диссертационного совета Д 212.131.03 при МГТУ МИРЭА по адресу: г. Москва, пр. Вернадского, д. 78, ауд. Г-412.

С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА.

Автореферат разослан «14» апреля 2014 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу: 119454, г. Москва, пр. Вернадского, д. 78, МГТУ МИРЭА, диссертационный совет Д 212.131.03.

Ученый секретарь Диссертационного совета, д.т.н., профессор

О.А. Тягунов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Одна из ключевых функциональных возможностей автономного мобильного робота, ориентированного на решение широкого спектра прикладных задач в экстремальных условиях, связана с необходимостью точного определения параметров собственного местоположения и построения карты местности. Известные недостатки средств и методов инерциальной и спутниковой навигации, связанные с быстрым накоплением ошибки (в первом случае), а также ограниченной точностью и возможностью подавления (во втором), являются существенным препятствием в обеспечении автономности современных образцов мобильных роботов различных типов и назначения. Возможным решением этих проблем является развитие технологий локальной навигации на основе визуальной обратной связи, позволяющих с высокой степенью достоверности осуществлять оценку координат самого робота и окружающих его объектов.

Одной из важнейших областей применения автономных мобильных роботов в рамках целого ряда различных приложений, включая задачи по борьбе с терроризмом, является обследование полостей строительных конструкций, систем вентиляции зданий и сооружений, коммуникационных каналов и т.д. с целью обнаружения неполадок или несанкционированно установленных потенциально опасных закладок и устройств с нанесением на карту координат обнаруженных объектов.

Исследования, проводимые в России в области разработки технологий локальной навигации и картографирования для создания перспективных образцов автономных робототехнических систем, во многом уступают программам аналогичных работ, активно выполняемых в развитых странах мира.

Таким образом, проблематика развития средств и методов локальной навигации и картографирования, как основополагающих составляющих автономности интеллектуальных мобильных роботов, является крайне важной и актуальной.

Предмет исследования - принципы построения и программно-алгоритмическое обеспечение системы локальной навигации и картографирования полостей строительных конструкций для автономного мобильного робота.

Объект исследования — наземные автономные мобильные роботы.

Цель исследования — повышение степени автономности и функциональной эффективности мобильных роботов с интеллектуальной системой управления за счет разработки программно-алгоритмического обеспечения для обследования и картографирования лабиринтов, необходимого при решении широкого спектра задач специального и гражданского назначения.

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

1. разработка алгоритмов локальной навигации и картографирования полостей строительных конструкций автономным мобильным роботом;

2. разработка алгоритмов нахождения и идентификации ориентиров при обследовании полостей строительных конструкций;

3. разработка структуры данных для представления карты полостей строительных конструкций с возможностью ее использования совместно с программно-алгоритмическими средствами локальной навигации автономного робота;

4. разработка алгоритмов планирования движений автономного мобильного робота для обеспечения полного обхода лабиринта с возможностью возврата на исходную позицию;

5. разработка алгоритмов информационного взаимодействия роботов в задачах кооперативного картографирования;

6. разработка алгоритмов планирования задач и распределения заданий при кооперативном картографировании полостей строительных конструкций.

Методы исследования. Проведенные исследования основаны на использовании методов теории информации, теории управления, математического анализа, математического моделирования и прикладного программирования.

Научная новизна полученных результатов определяется следующими основными положениями:

1. разработаны оригинальная форма представления структуры полостей строительных конструкций и алгоритмы их картографирования, позволяющие обеспечить учет всей совокупности значимых характеристик выявленных ориентиров;

2. разработан алгоритм планирования движений автономного мобильного робота для обследования полостей строительных конструкций, основанный на использовании алгоритма гарантированного обхода лабиринта по методу Люка-Тремо;

3. предложен новый подход к построению робототехнических децентрализованных систем кооперативного картографирования местности, при котором каждый из агентов формирует собственную копию общей карты. Разработан алгоритм формирования обобщенной карты при кооперативном картографировании местности;

4. разработаны алгоритмы планирования задач и распределения заданий при кооперативном картографировании полостей строительных конструкций группой роботов на основе динамически формируемого технологического графа.

Достоверность полученных результатов обеспечивается корректным использованием математического аппарата, обоснованными теоретическими выкладками, а также результатами экспериментальных исследований на моделях.

Практическая ценность работы характеризуется следующими пунктами:

1. разработана модель представления исследуемого лабиринта в составе подсистемы планирования движений автономного мобильного робота для мониторинга полостей строительных конструкций;

2. разработано алгоритмическое обеспечение для планирования движений автономного мобильного робота при обследовании полостей строительных конструкций;

3. разработаны алгоритмы кооперативного картографирования протяженных участков полостей строительных конструкций группой автономных мобильных роботов;

4. разработан программно-инструментальный комплекс 81аш81ти1а1ог, позволяющий моделировать процесс обследования полостей строительных конструкций с использованием автономных мобильных роботов, действующих как независимо, так и в составе группы.

Внедрение результатов исследования. Теоретические и практические результаты, полученные в диссертации, использованы при выполнении НИР №8.858.2011 «Поисковые исследования и разработка средств и методов локальной навигации и картографирования для систем управления перспективных образцов полуавтоматических и автономных мобильных роботов на базе комплексного применения современных интеллектуальных технологий визуальной обратной связи и обработки информации»

(проводимой МГТУ МИРЭА по заказу Министерства образования и науки РФ в период 2012 - 2013 гг.), что подтверждается соответствующим актом о внедрении.

Результаты диссертационной работы внедрены в учебный процесс кафедры «Проблемы управления» в виде УМКД и конспекта лекций по курсу «Интеллектуальные технологии локальной навигации» в рамках программы «Интеллектуальные мобильные роботы» магистерской подготовки по направлению 221000.68 «Мехатроника и робототехника». Кроме того, на основе материалов диссертационных исследований поставлены лабораторные работы и подготовлены методические указания по выполнению лабораторных работ «Исследование методов локальной навигации и картографии (SLAM - Simultaneous Localization And Mapping)» и «Исследование подсистемы локальной навигации и картографии на основе алгоритма FastSLAM».

Основные положения, выносимые на защиту:

1. модель и алгоритмы нахождения и идентификации ориентиров в процессе картографирования полостей строительных конструкций;

2. алгоритмы планирования движений автономного мобильного робота при решении задач обследования полостей строительных конструкций на основе модифицированного метода Люка-Тремо по обходу лабиринта произвольной топологии и протяженности;

3. алгоритмы информационного взаимодействия роботов в задачах кооперативного картографирования;

4. алгоритмы планирования действий и распределения заданий на основе динамически формируемого технологического графа в многоагентной робототехнической системе для кооперативного картографирования полостей строительных конструкций.

Апробация работы. Основные положения диссертации доложены, обсуждены и получили положительные отзывы на следующих конференциях: Научно-практическая конференция «Перспективные системы и задачи управления», Домбай 2009 г.; III Всероссийская конференция студентов, аспирантов и молодых ученых, г. Москва, МИРЭА, 11-13 ноября 2009 г.; XIX международный научно-технический семинар «Современные технологии в задачах управления, автоматики и обработки

б

информации», Алушта 2010 г.; XX международный научно-технический семинар «Современные технологии в задачах управления, автоматики и обработки информации», Алушта 2011 г.; VI Всероссийская научно-практическая конференция

«Перспективные системы и задачи управления», Таганрог 2011 г.; VII Всероссийская научно-практическая конференция «Перспективные системы и задачи управления», Домбай 2012г.

Публикации. По тематике диссертации опубликовано 9 печатных работ, в том числе 4 в изданиях, включенных в перечень ВАК РФ. По результатам работы получено 2 свидетельства о государственной регистрации программы для ЭВМ.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и 4 приложений. Объем основного текста составляет 134 печатные страницы, включая 10 таблиц, 71 рисунка и список литературы из 71 наименования.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении дано обоснование актуальности темы диссертации, сформулированы цель работы и задачи исследований, кратко представлены ее структура и содержание, приведены выносимые на защиту результаты, охарактеризованы их научная новизна и практическая ценность.

В первой главе диссертационной работы проведен анализ принципов построения, особенностей применения и проблем разработки автономных мобильных роботов. Показано, что наличие средств навигации и картографирования в составе бортовых систем управления автономными мобильными роботами является необходимым условием для обеспечения надежности и качества их автономного функционирования в априорно неопределенной среде. Таким образом, разработка высокоэффективных средств навигации является крайне важной и актуальной задачей, один из путей решения которой связан с использованием возможностей дальнометрической обратной связи для определения параметров собственного местоположения и построения карт местности.

На основе анализа особенностей построения программно-аппаратных средств современных образцов автономных мобильных роботов сделан вывод о целесообразности модульного наращивания их функциональных возможностей за счет разработки алгоритмов локальной навигации и картографирования.

Показано, что одна из важнейших областей прикладного применения автономных мобильных роботов связана с обследованием полостей строительных конструкций, коммуникационных каналов, систем вентиляции зданий и сооружений при поиске неисправностей или несанкционированно установленных закладок и потенциально опасных устройств. Специфика возникающих задач обусловлена необходимостью построения высокоточных карт исследуемых лабиринтов, а также планирования действий робота в процессе их мониторинга.

Проведенный обзор литературы по проблематике построения высокоточных систем локальной навигации и картографирования (именуемой в зарубежных источниках аббревиатурой SLAM) показал, что известные алгоритмы (EKF, FastSLAM, DP-SLAM), в явном виде, не позволяют обеспечить решение задач мониторинга лабиринтов различных типов, ввиду факторов неопределенности, связанных с наличием эффекта проскальзывания, ошибок измерений и вычислений, влекущих за собой неверную оценку длин и углов расхождения коридоров, и приводящих, в свою очередь, к построению неверной карты и, как следствие, дезориентации и потере робота.

Отмечено, что один из путей повышения эффективности и сокращения временных затрат, требуемых для обследования протяженных участков полостей строительных конструкций, связан с разработкой средств и методов кооперативного картографирования лабиринтов на основе использования многоагентных робототехнических систем.

Сформирована обобщенная структура интеллектуальной системы управления автономным мобильным роботом, которая построена по иерархическому принципу и предназначена для решения задачи картографирования полостей строительных конструкций (рис. 1).

Во второй главе проводится детальный сравнительный анализ современных подходов к решению задачи SLAM на основе использования расширенного фильтра Калмана (EKF) и алгоритма FastSLAM с целью выбора наиболее эффективного метода для построения системы локальной навигации и картографирования лабиринтов.

Основываясь на результатах проведенных экспериментальных исследований по сравнению подходов к решению задачи SLAM, в

качестве конструктивной основы для построения системы локальной навигации и картографирования лабиринтов выбран алгоритм Ра518ЬАМ, так как он незначительно уступает по своей точности алгоритму на основе расширенного фильтра Калмана, но при этом обладает значительно более высокой производительностью, что имеет принципиально важное значение при картографировании протяженных участков полостей строительных конструкций.

Задание

Стратегический уровень

Aiiu.hi < карты

Карта

Миформанионно-lUMcpiue.ibiiaH система

IIjcii I ификлюр ориентиров

Обновление состояния

на основе одометрнческих данных

Обновление состояния на

основе повторно обнаруженных ориентиров

Добавление новых ориентиров

SLAM

Интеллектуальная

Интеллектуальная система управления

Приводной уровень

Тактический

уровень Формирование поведения

гНГ

Рис. 1. Структура программного обеспечения системы локальной навигации и картографии для автономного мобильного робота

Показано, что эффективность алгоритмов локальной навигации и картографирования напрямую зависит от точности информационно-измерительной системы, в связи с чем, в настоящей работе в качестве средства дальнометрии предполагается использование сканирующего лазерного дальномера (ЬГОАЯ), а в качестве ориентиров - углы, образованные при пересечении стен коридоров. Выявление углов осуществляется путем выделения и анализа контуров стен. При этом в качестве контура стен рассматриваются информативные прямые, соединяющие концы векторов дальности, полученные с помощью ЬЮАЯа. Основываясь на проведенном обзоре, в качестве метода

9

отыскания информативных прямых, выбран и реализован алгоритм 11атег-Оо1^1а5-Реискег, результат работы которого представлен на рис. 2 а.

а) б) в)

Рис. 2. Выявление и идентификация ориентиров, а) результат работы

подпрограммы для поиска ориентиров; б) фрагмент лабиринта; в) фрагмент построенной карты с окрестностями у углов и перекрестков

Обозначена проблема идентификации ориентиров при построении карты лабиринта, сопряженная со сложностями выявления отличий между ними. В данной работе эта проблема была

решена присвоением каждому углу окрестности £с;, в которой он определен. Модель представления одиночного угла в системе идентификации ориентиров имеет вид:

С, = (Х(, у„ £с() (1)

где X;, у( — оценки координат ьго угла, а ЕС| - окрестность его определения. Таким образом, после обнаружения очередного угла, производится проверка попадания оценок координат его положения в окрестности уже известных углов. Отрицательный результат проверки говорит о том, что этот угол, возможно, является новым. Показано, что, несмотря на коррекцию погрешностей измерений с помощью алгоритма Раз18ЬАМ, величина ошибки может накопиться до такой степени, что превысит величину окрестности определения угла и повлечь за собой его повторное включение в перечень обнаруженных ориентиров.

Решение проблемы заключается в дополнении состава значимых характеристик исследуемых лабиринтов не только окрестностями

углов £сь но и соответствующих перекрестков. В этом случае модель перекрестка представляет собой совокупность углов и окрестности

определения самого перекрестка (2), как показано на рис. 2 б, в.

ю

Центром перекрестка является точка пересечения прямых, проходящих через диагонально противоположные углы, входящих в его состав.

Т = (С,£() (2)

где С = - совокупность углов, входящих в перекресток.

Таким образом, анализ новизны ориентира сводится к проверке, попадания найденного угла в окрестность какого-либо уже известного перекрестка. При отрицательном ответе угол считается новым, а его положение должно быть отражено на карте.

При этом, структура полостей строительных конструкций (рис.3) представляется в виде графа, модель которого может быть описана как:

О = (Т, И) (3)

где Ь - коридор, а Т - модель перекрестка (2).

Рис. 3. Модель лабиринта

Для удобства хранения и использования карты лабиринта разработана структура базы данных (рис. 4), в основе которой лежит предложенная модель (3).

В соответствии с поставленными задачами разработан алгоритм планирования движений автономного мобильного робота для обследования полостей строительных конструкций (с возможностью возврата на исходную позицию), основанный на использовании алгоритма гарантированного обхода лабиринта по методу Люка-Тремо. Использование алгоритма Люка-Тремо для решения поставленной задачи предполагало создание такой его модификации, которая способна функционировать совместно с подсистемой локальной навигации и картографирования на основе Рав18ЬАМ. Блок-схема алгоритма гарантированного обхода на основе

модифицированного метода Люка-Тремо для разработанной модели представления лабиринта изображена на рис. 5. Проведенные экспериментальные исследования доказали работоспособность и эффективность созданного алгоритмического обеспечения.

Коридоры-Перекрестки

[индекс коридора] [индекс перекрестка]

=6®

Углы

те®

Коридоры

$ [индекс коридора] [начальный коридор] [текущий коридор] [количество прохождении] тупик длина

9 [индекс угла] X Y

[величина угла]

Углы-Коридоры

[индекс угла] [индекс коридора]

Перекрестки

У [индекс перекрестка]

X У

[начальный перекресток] [последний посещенный] тупик

Углы-Перекрестки

[индекс угла] [индекс перекрестка]

Рис. 4. Структура базы данных, отражающая модель лабиринта

Третья глава посвящена разработке концепции построения многоагентных робототехнических систем для кооперативного картографирования протяженных участков лабиринтов.

Показано, что одним из путей повышения эффективности и сокращения временных затрат, требуемых для обследования протяженных участков полостей строительных конструкций, является использование системы кооперативного картографирования. Однако возможность ее применения сопряжена с необходимостью разработки эффективного алгоритма планирования задач и распределения заданий между роботами.

Предложен новый подход к кооперативному картографированию полостей строительных конструкций, при котором все роботы функционируют в единой системе координат, постоянно обмениваются пакетами данных, и имеют информацию о взаимном расположении друг друга. При этом индивидуальная карта, формируемая каждым из роботов, дополняется информацией об ориентирах, найденных другими членами многоагентной системы. Таким образом, в произвольный момент времени, у каждого из роботов есть свой прототип глобальной карты местности, что значительно повышает надежность системы за счет децентрализации. В процессе обхода лабиринта роботы обмениваются сообщениями посредством широковещания (broadcast).

12

Начало

I

Характер! ictiikii робота ii ИИС

-

Иннцналиаацпя Ра&й1.АМ к

картографической БД; соддапне начального коридора и перекрестка

1

Двигаться вперед

I

Поиск и идентификация углов

I ~~~

Инициализация нового перекрестка, сохранение я картографической БД

Ра^ЬАМ. Оценка состояния системы

I

Добавление упав в картографическую БД, привязка к ориентирам из Ра51$ЬЛМ

Установить у коридора п перекрестка свойство «тупик» = true. Развернуться па 180 градусов

Выбор любого го не пройденных коридоров

Развернуться на 180 градусов

Выбор любого из 1 раз пройденных коридоров, кроме начального

Выбор начального коридора

Увеличить количество прохождений текущего _коридора на 1_

Рис. 5. Блок-схема алгоритма планирования движений робота при обследовании лабиринта по методу Люка-Тремо

При таком подходе усреднение оценок положения ориентиров является необходимой операцией для формирования единого, общего для всех, экземпляра карты.

Показано, что обобщение оценок положений ориентиров, произведенных различными агентами, может быть реализовано с помощью следующих алгоритмов усреднения:

• Среднее арифметическое

Хо = (х,у)> гДе * = > y =

(4)

Минимум среднеквадратического отклонения

х° = Хо,, где i такой, что шах( /ЦО.О], /Ц1,1]) = min(max( PJ0,0], />„,[1,1])) (5)

/е(1л)

• Минимум определителя ковариационной матрицы

X0=Xoj , где i такой, что det(P„,) = min(det(Po;)) (6)

На основе проведенных экспериментальных исследований показано, что наилучшим критерием получения усредненной оценки является "Минимум определителя ковариационной матрицы" (6).

Для планирования задач и распределения заданий при кооперативном картографировании полостей строительных конструкций группой роботов предложено использовать динамически формируемый технологический граф лабиринта. Оперируя понятиями технологического графа, можно представить процесс обхода лабиринта в качестве совокупности задач по исследованию коридоров между перекрестками. В условиях априорно неизвестной структуры лабиринта формирование его модели в виде графа осуществляется динамически в процессе обхода. При этом обнаружение нового коридора рассматривается в качестве новой задачи, отображаемой на синтезируемом графе.

Показано, что организация процесса планирования заданий на основе динамически формируемого технологического графа имеет целый ряд преимуществ, основным из которых является развитый математический аппарат теории графов, применение которого позволило использовать стандартные алгоритмы обхода и поиска кратчайшего пути при решении задачи оптимального перехода робота из одного коридора в другой, что в понятиях технологического графа означает переход к выполнению задачи, соответствующей обследованию выбранного коридора.

Четвертая глава посвящена разработке программно-инструментального комплекса 81аш81ши1аШг для моделирования задач кооперативного картографирования лабиринтов группой автономных мобильных роботов, и проведению модельных экспериментальных исследований. Блочно-модульная структура комплекса представлена на рис. 6.

где п - количество роботов в системе,

Х<п = [хо1 У о,Т Р . =

л»

Ol

(7)

Среди основных функциональных возможностей 81аш81ши1а1ог следует отметить:

• моделирование естественных возмущающих факторов, оказывающих влияние на процесс движения мобильного робота, включая проскальзывание, погрешности измерений и др.;

• осуществление гарантированного обхода лабиринта автономным мобильным роботом в режиме одиночного картографирования;

• моделирование процесса кооперативного картографирования полостей строительных конструкций группой автономных мобильных роботов;

• возможность автоматической оценки точности построения карты и времени, затраченного на осуществление полного обхода лабиринта.

Рис. 6. Структурная схема программного моделирующего комплекса

$1ат51ти1а1ог

Разработанный программный моделирующий комплекс позволил провести комплексные экспериментальные исследования по оценке эффективности разработанных алгоритмов кооперативного картографирования протяженных участков полостей строительных конструкций (рис. 7). Подсистема статистики и оценки точности построения карты позволила проверить возможность практического применения разработанных алгоритмов картографирования при различных точностных характеристиках информационно-измерительной системы робота.

Рис. 7. Интерфейс программного моделирующего комплекса 81ат81тиЫог

Проведенные исследования в полной мере подтвердили работоспособность разработанных алгоритмов локальной навигации, картографирования и планирования движений автономных мобильных роботов для обследования протяженных участков полостей строительных конструкций, а оценка эффективности алгоритмов планирования задач и распределения заданий на основе динамически формируемого технологического графа показала, что использование многоагентной системы позволяет значительно сократить время построения карты.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

В диссертационной работе решена совокупность актуальных научно-технических задач, связанных с разработкой высокоточных систем локальной навигации, картографирования и планирования движений интеллектуальных автономных мобильных роботов для решения задач мониторинга лабиринтов. Получены следующие научные результаты:

1. разработано программно-алгоритмическое обеспечение для решения задач локальной навигации и картографирования полостей строительных конструкций автономным мобильным роботом на

основе алгоритма FastSLAM;

2. разработаны алгоритмы выявления и идентификации ориентиров при картографировании полостей строительных конструкций. Для формирования и хранения карты лабиринта разработана структура данных, отражающая взаимосвязи между углами, коридорами и перекрестками. Предложена модель представления перекрестков в составе графового описания лабиринтов, предотвращающая неверную идентификацию углов в качестве ориентиров;

3. разработан алгоритм планирования движений автономного мобильного робота для обследования полостей строительных конструкций, основанный на использовании алгоритма гарантированного обхода лабиринта по методу Люка-Тремо;

4. сформирован подход к построению многоагентных робототехнических систем кооперативного картографирования местности, основанный на непрерывной информационной интеграции между агентами. Разработаны алгоритмы планирования действий и распределения заданий на основе динамически формируемого технологического графа лабиринта при кооперативном картографировании протяженных участков полостей строительных конструкций группой роботов.

5. разработан программно-инструментальный комплекс SlamSimulator, позволяющий моделировать процесс обследования полостей строительных конструкций с использованием автономных мобильных роботов, действующих как независимо, так и в составе группы;

Основные положения диссертации опубликованы в следующих работах:

в изданиях, входящих в перечень ВАК РФ:

1. Р.В. Кучерский, C.B. Манько. Алгоритмы локальной навигации и картографии для бортовой системы управления автономного мобильного робота // "Известия ЮФУ. Технические науки" - Таганрог: Изд-во ТТИ ЮФУ, №3,2012, — с.13-22.

2. Макаров И. М., Лохин В. М., Манько С. В., Романов М. П., Крюченков Е. Н., Кучерский Р.В., Диане С. А. Мультиагентные робототехнические системы: примеры и перспективы применения // "Мехатроника, Автоматизация, Управление" - Москва: Изд-во «Новые технологии», №2,2012, - с.22-32.

3. Макаров И. М., Лохин В. М., Манько С. В., Романов М. П., Крюченков Е. Н., Худак Ю.И., Кучерский Р.В. Модели и алгоритмы планирования действий и распределения заданий в мультиагентных робототехнических системах // "Мехатроника, Автоматизация, Управление" -Москва: Изд-во «Новые технологии», №5, 2012, - с.44-50.

4. Кучерский Р.В., Манько C.B. Модель многоагентной робототехнической системы для кооперативного картографирования

протяженных участков полостей строительных конструкций // "Естественные и технические науки" - Москва: Изд-во «Спутник +», №6,2013, - с.ЗОЗ-311.

в других изданиях:

5. Макаров И.М., Лохин В.М., Манько C.B., Романов М.П., Худак Ю.И., Крюченков E.H., Юрин А.Д., Кучерский Р.В. Принципы построения, разработка и моделирование мультиагентных робототехнических систем // Материалы IV Всероссийской научно-практической конференции «Перспективные системы и задачи управления» - Таганрог: Изд-во ТТИ ЮФУ, 2009, - с.58-59.

6. Манько C.B., Трипольский П.Э, Кучерский Р.В. Картография полостей строительных конструкций автономным мобильным роботом // Труды XIX международного научно-технического семинара «Современные технологии в задачах управления, автоматики и обработки информации. - М.: Издательский дом МЭИ, 2010, - с.36.

7. Лохин В.М., Манько C.B., Романов М.П., Худак Ю.И., Крюченков E.H., Юрин А.Д., Кучерский Р.В. Принципы построения, разработка и моделирование мультиагентных робототехнических систем // МЕХАТРОНИКА И РОБОТОТЕХНИКА. // Итоговый сборник статей. - Санкт-Петербург: Изд-во «Потитехника-сервис», 2010, - с.88-89.

8. Лохин В.М., Манько C.B., Яшунский В.Д., Кучерский Р.В. Модель среды и обобщение сенсорной информации в интеллектуальных системах управления автономными роботами // Тезисы докладов XX международного научно-технического семинара «Современные технологии в задачах управления, автоматики и обработки информации. - Пенза: Изд-во ПГУ, 2011, — с.22- 23.

9. Манько C.B., Александрова Р.И., Кучерский Р.В. Алгоритмы локальной навигации и картографии для бортовой системы управления автономного мобильного робота // Материалы VI Всероссийской научно-практической конференции «Перспективные системы и задачи управления» -Таганрог: Изд-во ТТИ ЮФУ, 2011, - с. 144-145.

в свидетельствах о государственной регистрации программ для ЭВМ:

10. Кучерский Р.В., Манько C.B. Программа для моделирования процесса кооперативного картографирования протяженных участков местности группой автономных мобильных роботов. Свидетельство о государственной регистрации программы для ЭВМ №2013610474, 2013.

11. Кучерский Р.В., Манько C.B. Программа для моделирования процесса кооперативного картографирования полостей строительных конструкций группой автономных мобильных роботов. Свидетельство о государственной регистрации программы для ЭВМ №2013661068, 2013.

Личный вклад автора в написание статей [1], [4] заключается в изложении алгоритмов локальной навигации и картографирования лабиринтов автономными мобильными роботами, действующими как независимо, так и в составе группы. В работах [6], [8], [9] автором представлены результаты моделирования задачи мониторинга лабиринтов автономными мобильными роботами. Роль автора в регистрации программ для ЭВМ [10], [11] заключается в непосредственной разработке соответствующего программного обеспечения. В публикациях [2], [3], [5], [7] участие автора характеризуется неразделимым соавторством.

Научное издание

Кучерский Роман Владимирович

МОДЕЛИ И АЛГОРИТМЫ КАРТОГРАФИРОВАНИЯ СРЕДЫ И ПЛАНИРОВАНИЯ ДВИЖЕНИЙ АВТОНОМНЫХ МОБИЛЬНЫХ РОБОТОВ ДЛЯ МОНИТОРИНГА ЛАБИРИНТОВ

Специальность: 05.13.01 — системный анализ, управление и обработка информации

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 24.03.2014 Формат 60 х 90 '/|6. Бумага 80 г Усл.-печ.л. 1,25. Тираж 120 экз. Заказ 473

Отпечатано в редакционно-издательском отделе Федерального государственного бюджетного образовательного Учреждения высшего профессионального образования «Московский государственный технический университет радиотехники, электроники и автоматики» 119454 Москва, пр. Вернадского, 78

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования "Московский государственный технический университет радиотехники, электроники и автоматики" (МГТУ МИРЭА)

04201457838 На правах рукописи

Кучерский Роман Владимирович

Модели и алгоритмы картографирования среды и планирования движений автономных мобильных роботов для мониторинга

лабиринтов

Специальность 05.13.01 - системный анализ, управление и обработка

информации

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель -доктор технических наук, профессор Манько С.В.

Москва 2014

Содержание

Введение...............................................................................................................4

Глава 1. Принципы построения, особенности применения и проблемы разработки автономных мобильных роботов...................................................9

1.1. Области применения автономных мобильных роботов......................12

1.2. Современные подходы к решению задач локальной навигации и картографирования в системах управления автономными мобильными роботами..........................................................................................................37

1.2.1. Использование алгоритма расширенного фильтра Калмана (EKF) для решения задачи локальной навигации и картографии.....................41

1.2.2. Использование алгоритма FastSLAM для решения задачи локальной навигации и картографии........................................................49

1.2.3. Использование алгоритма DP-SLAM для решения задачи локальной навигации и картографии........................................................53

Выводы по 1 главе и постановка задачи......................................................55

Глава 2. Развитие методов и алгоритмов локальной навигации, картографирования и планирования движений автономного мобильного робота для обследования лабиринтов.............................................................59

2.1. Сравнительный анализ подходов к решению задачи локальной навигации и картографии..............................................................................59

2.2. Разработка алгоритмов построения карты лабиринта произвольной топологии........................................................................................................66

2.2.1. Разработка модели и алгоритмов нахождения и идентификации ориентиров...................................................................................................66

2.2.2. Разработка структуры данных для представления карты полостей строительных конструкций.......................................................................75

2.2.3. Алгоритм гарантированного обхода лабиринта произвольной протяженности и топологии автономным мобильным роботом...........81

2.3. Оценка эффективности разработанных алгоритмов картографирования

полостей строительных конструкций..........................................................86

Выводы по 2 главе..........................................................................................95

Глава 3. Разработка алгоритмов кооперативного картографирования протяженных участков полостей строительных конструкций.....................96

3.1. Разработка алгоритмов информационного взаимодействия роботов в задачах кооперативного картографирования..............................................97

3.2. Планирование задач и распределение заданий на основе динамически

формируемого технологического графа....................................................105

Выводы по 3 главе........................................................................................112

Глава 4. Экспериментальные исследования и оценка эффективности разработанных алгоритмов картографирования лабиринтов с использованием автономных мобильных роботов...................................................................113

4.1. Разработка программного моделирующего комплекса 81ат81пш1а1;ог. ........................................................................................................................113

4.2. Проведение комплексных экспериментальных исследований........118

Выводы по 4 главе........................................................................................122

Заключение.......................................................................................................123

Литература........................................................................................................127

Приложение А..................................................................................................135

Приложение Б..................................................................................................136

Приложение В..................................................................................................137

Приложение Г..................................................................................................139

Введение

Многообразие потенциальных применений интеллектуальных мобильных роботов охватывает огромный спектр различных прикладных задач, связанных с проведением работ в неопределенных и экстремальных условиях - от космических и глубоководных исследований, обслуживания атомных станций, ликвидации последствий техногенных аварий и катастроф, борьбы с терроризмом и использования в интересах вооруженных сил, полицейских и других спецподразделений, до выполнения сложнейших медицинских операций (по целевой доставке требуемым органам необходимых доз медикаментозных препаратов), автоматизации коммунально-хозяйственной сферы, организации быта и досуга и т.д.

Создание интеллектуальных мобильных роботов, способных обеспечить выполнение требуемых функций в автономном режиме, является крайне сложной проблемой, требующей проведения глубоких исследований по целому ряду важнейших вопросов - от принципов построения и способов технической реализации, до этики поведения искусственных систем по отношению к человеку и их взаимного сосуществования. Комплексное решение этой проблемы предполагает последовательный переход от стадии теоретических и экспериментальных разработок к этапу их опытного внедрения с проверкой эффективности развиваемых подходов, анализом их целесообразности и т.д. Подобное положение вещей обусловливает то пристальное внимание, которое повсеместно придается фундаментальным и прикладным исследованиям в области управления и искусственного интеллекта в приложении к задачам робототехники.

В ряду основных функциональных возможностей, которыми должен обладать автономный мобильный робот, ориентированный на решение широкого спектра различных прикладных задач по сбору разнородной информации и выполнению сложных технологических операций в экстремальных средах, на открытой местности или в сложных городских

условиях, одна из ключевых связана с необходимостью точного определения параметров собственного местоположения и построения карт местности. Известные недостатки средств и методов инерциальной и спутниковой навигации, связанные с быстрым накоплением ошибки, в первом случае, а также ограниченной точностью и возможностью подавления во втором, являются существенным препятствием в обеспечении автономности современных образцов мобильных роботов различных типов и назначения.

В данной связи, развитие технологий локальной навигации на основе визуальной обратной связи, позволяющих с высокой степенью достоверности осуществлять оценку не только координат самого робота, но и окружающих его объектов представляет собой крайне важную и актуальную задачу , специфика которой во многом определяется необходимостью учета различных факторов неопределенности, связанных с погрешностями информационно-измерительных средств, проскальзыванием и т.д.

Одной из важнейших областей применения автономных мобильных роботов в рамках целого ряда различных приложений, включая задачи по борьбе с терроризмом, является обследование полостей строительных конструкций, систем вентиляции зданий и сооружений, коммуникационных каналов и т.д. с целью обнаружения неполадок или несанкционированно установленных потенциально опасных закладок и устройств с нанесением на карту координат обнаруженных объектов.

Исследованию этой проблематики, связанной с разработкой технологий локальной навигации и картографирования для создания перспективных образцов автономных робототехнических систем и именуемой в зарубежной литературе обобщенной аббревиатурой SLAM (Simultaneous Localization And Mapping), во всем мире уделяется приоритетное внимание, а реальные практические результаты, полученные в США, странах Европы и Юго-Восточной Азии носят опережающий характер.

В настоящее время существует несколько основных подходов к

решению этих задач, включая расширенный фильтр Калмана, FastSLAM, DP-

5

SLAM. Тем не менее, у каждого из этих методов есть свои ограничения и недостатки, что еще раз подчеркивает необходимость совершенствования алгоритмов картографии местности автономными мобильными роботами.

Таким образом, учитывая современные тенденции и необходимость создания автономных мобильных роботов, принципиально важным аспектом является развитие методов и средств локальной навигации и картографии, как основополагающих составляющих автономности интеллектуального мобильного робота.

Объектом исследования являются наземные автономные мобильные роботы.

Предмет исследования - принципы построения и программно-алгоритмическое обеспечение системы локальной навигации и картографирования полостей строительных конструкций для автономного мобильного робота.

Целью диссертационной работы является повышение степени автономности и функциональной эффективности мобильных роботов с интеллектуальной системой управления за счет разработки программно-алгоритмического обеспечения для обследования и картографирования лабиринтов, необходимого при решении широкого спектра задач специального и гражданского назначения. Для достижения поставленной цели в диссертации решаются следующие задачи:

1. разработка алгоритмов локальной навигации и картографирования полостей строительных конструкций автономным мобильным роботом;

2. разработка алгоритмов нахождения и идентификации ориентиров при обследовании полостей строительных конструкций;

3. разработка структуры данных для представления карты полостей строительных конструкций с возможностью ее использования совместно с программно-алгоритмическими средствами локальной навигации автономного робота;

4. разработка алгоритмов планирования движений автономного мобильного робота для обеспечения полного обхода лабиринта с возможностью возврата на исходную позицию;

5. разработка алгоритмов информационного взаимодействия роботов в задачах кооперативного картографирования;

6. разработка алгоритмов планирования задач и распределения заданий при кооперативном картографировании полостей строительных конструкций.

Изложение материалов исследований в диссертационной работе построено следующим образом. В первой главе рассматриваются принципы построения и проблема разработки высокоточных средств локальной навигации и картографирования местности для интеллектуальных систем управления автономными мобильными роботами на основе дал ьнометрической обратной связи. Приводится обзор современных образцов автономных мобильных роботов и обосновывается возможность повышения степени их автономности за счет использования алгоритмов локальной навигации и картографии. На основе проведенного обзора сформирована постановка задач диссертационной работы.

Вторая глава посвящена сравнительному анализу существующих алгоритмов решения задач локальной навигации и картографирования местности. Проводится оценка возможности и эффективности практического применения алгоритма ГазгЗЬАМ для решения задачи картографирования полостей строительных конструкций. По результатам проведенных модельных экспериментов обосновывается выбор алгоритма Раз18ЬАМ, как основы для подсистемы локальной навигации и картографии. Разрабатываются алгоритмы выявления и идентификации ориентиров в условиях полостей строительных конструкций. Предлагаются алгоритмы управления движением автономных мобильных роботов на основе модификации алгоритма Люка-Тремо для обеспечения гарантированного

обхода полостей строительных конструкций.

7

В третьей главе сформирован подход к построению многоагентной робототехнической системы для кооперативного картографирования протяженных участков местности на основе непрерывной информационной интеграции. Разработан алгоритм усреднения оценок положения ориентира, сделанных различными агентами, на основе минимума определителя ковариационной матрицы. Предлагаются алгоритмы решения задач планирования действий и распределения заданий в многоагентной робототехнической системе для кооперативного картографирования протяженных участков полостей строительных конструкций на основе динамически формируемого технологического графа.

Четвертая глава посвящена разработке программно-алгоритмического обеспечения для моделирования задачи кооперативного картографирования протяженных участков полостей строительных конструкций группой автономных мобильных роботов, приводятся результаты экспериментальных исследований.

В заключение представлены общая характеристика выполненных исследований и основные выводы по результатам диссертационной работы.

На защиту выносятся:

1. модель и алгоритмы нахождения и идентификации ориентиров в процессе картографирования полостей строительных конструкций;

2. алгоритмы планирования движений автономного мобильного робота при решении задач обследования полостей строительных конструкций на основе модифицированного метода Люка-Тремо по обходу лабиринта произвольной топологии и протяженности;

3. алгоритмы информационного взаимодействия роботов в задачах кооперативного картографирования;

4. алгоритмы планирования действий и распределения заданий на основе динамически формируемого технологического графа в многоагентной робототехнической системе для кооперативного картографирования полостей строительных конструкций.

Глава 1. Принципы построения, особенности применения и проблемы разработки автономных мобильных роботов

В настоящее время робототехника является одной из самых актуальных и быстро развивающихся прикладных наук, охватывающей практически все сферы человеческой деятельности, нуждающиеся в автоматизации [1, 2, 3, 4].

Особую роль играют автономные мобильные роботы, так как они позволяют решать целый спектр разнородных прикладных задач без участия человека непосредственно в процессе функционирования. В первую очередь необходимость использования автономных мобильных роботов возникает в экстремальных условиях. Характерным примером может послужить исследование поверхности других планет, ликвидация последствий техногенных аварий и катастроф, проведение специальных мероприятий по борьбе с терроризмом и т.д.

Автономность мобильного робота во многом определяется эффективностью средств навигации. Среди основных способов навигации, широко применяемых в современной робототехнике можно отметить спутниковую, инерциальную и локальную навигацию.

> Спутниковая - навигация - использование совокупности наземного и космического оборудования для определения местоположения (географических координат и высоты) и точного времени, а также параметров движения для наземных, водных и воздушных объектов.

Основные недостатки:

• Сравнительно невысокая точность

• Возможность подавления сигнала

• Зависимость от внешних источников информации (спутники)

> Инерциальная навигация - определение координат и параметров движения различных объектов и управления их движением, основанный на свойствах инерции тел и являющийся автономным, то

есть не требующим наличия внешних ориентиров или поступающих извне сигналов.

Основные недостатки: • Накопление ошибки, обусловленное интегрирующими свойствами самой системы ^ Локальная навигация - использование дальнометрической обратной связи для определения положения робота и окружающих его объектов Из перечисленных способов особый интерес вызывает локальная навигация, ввиду своей независимости от внешних источников информации и потенциальной возможности обеспечения достаточно высокой точности, обусловленной исключительно характеристиками системы дальнометрии. Оба этих качества, в свою очередь, имеют неоспоримое значение при построении высокоточной системы навигации для автономного мобильного робота.

Другой не менее важной способностью, которой должен обладать автономный мобильный робот при функционировании в незнакомой среде является картографирование местности. Решение задачи картографирования местности тесно сопряжено с навигацией, так как для нанесения на карту новых объектов необходимо максимально точно определить их положение относительно робота и других объектов, уже нанесенных на карту. Учитывая тот факт, что для построения карты требуется достаточно точный способ определения положений объектов, в то время как для локальной навигации необходима актуальная карта, задачи локальной навигации и картографирования местности принято решать совместно. Наличие подсистемы локальной навигации и картографирования местности в составе бортовой системы управления мобильного робота позволяет значительно повысить степень автономности, благ