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

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

Собольников Сергей Александрович

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

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

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

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

Москва 2013

005546266

005546266

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Московский государственный технологический университет «СТАНКИН» на кафедре робототехники и мехатроники.

Научный руководитель: Ермолов Иван Леонидович

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

Официальные оппоненты: Афонин Вячеслав Леонидович

доктор технических наук, профессор, заведующий лабораторией управления технологическими процессами и системами ФГБУН Института машиноведения им. A.A. Благонравова Российской академии наук (ИМАШ РАН);

Назарова Анаид Вартановна

кандидат технических наук, доцент кафедры «Робототехнические системы» ФГБОУ ВПО МГТУ им. Н.Э. Баумана

Ведущая организация: ФГАОУ ВПО «Южный федеральный

университет», структурное подразделение Научно-исследовательский институт

многопроцессорных вычислительных

систем имени академика A.B. Каляева

Защита состоится « 2 О » й<2.Ьгс\ ¿)рц 2013 г. в часов на

заседании диссертационного совета Д 212.131.03 при Московском государственном техническом университете радиотехники, электроники и автоматики (МГТУ МИРЭА) по адресу: 119454 г. Москва, проспект Вернадского, дом 78, ауд. Г412.

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

С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА Автореферат разослан « » и о Я 1Гр5| 2013 г.

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

i.A. Тягунов

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

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

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

- использованию неоптимального количества узлов связи,

- присутствию непокрытых зон внутри заданной области,

- избыточному перекрытию заданной области,

- обрыву связи во время перемещения подвижных узлов,

- низкой скорости принятия решений.

Поэтому подвижные узлы должны обладать высоким уровнем автоматизации. Для этого целесообразно использовать автономные мобильные роботы в качестве подвижных узлов связи. В связи с этим актуальной задачей является создание системы планирования действий автономных мобильных роботов-ретрансляторов (АМРР) для обеспечения функционирования ПКС.

Диссертация основывается на результатах исследований в области системного анализа и группового управления, отраженных в трудах И.М. Макарова, Д.Е. Охоцимского, И.А. Каляева, Ю.М. Соломенцева, В.Г. Градецкого, С.Г. Капустяна, В.М. Лохина, C.B. Манько, Е.И. Юревича, Р. Аркина, Т. Балча, В. Кумара, М. Матарик и других отечественных и зарубежных ученых.

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

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

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

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

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

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

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

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

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

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

программирования в средах Visual С++ и Delphi. Исследование работоспособности предлагаемых решений проводилось путем математического и имитационного моделирования с использованием разработанного автором программного обеспечения и натурных экспериментальных исследований.

Научная новизна работы заключается в:

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

позиций для роботов-ретрансляторов на местности, перемещения в целевые позиции с поддержанием коммуникационного соединения;

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

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

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

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

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

Практической ценностью обладают следующие результаты.

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

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

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

4. Построен экспериментальный образец подвижной коммуникационной сети на базе автономных мобильных роботов-

ретрансляторов с использованием разработанного программного обеспечения.

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

Реализация результатов работы. Теоретические и практические результаты работы использованы при выполнении НИР «Проведение проблемно-ориентированных исследований по созданию подвижных реконфигурируемых информационных коммуникационных сетей на основе автономных мобильных мехатронных агентов» Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса на 2007-2013 годы».

Апробация работы. Основные результаты диссертации докладывались и обсуждались на следующих конференциях: Международная научная конференция «Robotics for risky interventions and Environmental Surveillance-Maintenance 5th IARP RISE'2011», 2011 год, Левен, Бельгия.; XXI Международная научно-техническая конференция «ЭКСТРЕМАЛЬНАЯ РОБОТОТЕХНИКА», 2010, Москва; Международная научно-техническая конференция «ЭКСТРЕМАЛЬНАЯ РОБОТОТЕХНИКА», 2011, Санкт-Петербург; Международная научно-техническая конференция «ЭКСТРЕМАЛЬНАЯ РОБОТОТЕХНИКА», 2012, Санкт-Петербург; Международная научно-техническая интернет-конференция молодых ученых «Автоматизация, мехатроника, информационные технологии», 2010, Омск; XV научная конференция «МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И ИНФОРМАТИКА», 2013, Москва.

Внедрение результатов исследования. Ряд теоретических и практических результатов, полученных в диссертации, внедрены в Московском филиале ФГУП «АВАРИЙНО-ТЕХНИЧЕСКИЙ ЦЕНТР МИНАТОМ РОССИИ» (г. Санкт-Петербург) Инженерно-Техническом и Учебном Центре Робототехники (ИТУЦР) и в учебном процессе МГТУ «СТАНКИН», что подтверждается соответствующими актами о внедрении.

Публикации. По тематике диссертации автором опубликовано 10 печатных трудов, из них 5 работ опубликовано в журналах из перечня ВАК РФ. По результатам работы получено 5 свидетельств на владение правами интеллектуальной собственности.

Структура и объем работы. Диссертация общим объемом 169 страниц состоит из введения, четырех глав, заключения, списка сокращений, списка использованных источников из 69 наименований и приложения. Основной текст изложен на 152 страницах, включает 80 рисунков и 11 таблиц.

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

Во введении обоснована актуальность темы диссертационной работы, приведены данные по ее структуре и объему.

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

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

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

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

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

диссертационной работе основное внимание уделяется вопросам планирования групповых действий АМРР для создания ПКС. В последнем разделе главы формулируются цель и задачи диссертации.

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

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

- задание оператором входных параметров;

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

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

-нахождение маршрутов скоординированного движения АМРР в целевые позиции, которое учитывает обход препятствий, предотвращение столкновений между членами группы, а также поддержание радиосвязи между АМРР во время перемещения;

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

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

На рис. 1 изображена структурно-функциональная модель комбинированной стратегии планирования. "Цифровая карта" отображает информацию о местности и о ПКС. Редактирование карты местности и задание параметров ПКС и среды осуществляется оператором с помощью

"Подсистемы ввода". Для хранения различных карт отвечает блок "База карт местности".

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

В блоке "Формирование предварительного маршрута и назначение целевых позиций в группе АМРР" происходит распределение целевых позиций между АМРР и определение предварительного маршрута для их перемещения из начальных позиций в целевые.

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

Далее "Центральное вычислительное устройство" передает план движения каждому АМРР, на которых располагаются локальные системы планирования, обеспечивающие скоординированное движение роботов к целевым позициям.

Для реализации разработанной модели было создано алгоритмическое обеспечение, направленное на решение задач распределения АМРР, назначения целей и скоординированного движения АМРР.

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

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

Перед созданием алгоритмов распределения был принят ряд допущений: зона действия коммуникационного сигнала одного робота-ретранслятора представляется в виде круга радиусом Rampp', все роботы обладают идентичными коммуникационными возможностями. Тогда задача распределения мобильных роботов по заданной области сводится к задаче покрытия плоского многоугольника кругами радиуса Rampp• При этом необходимо рассчитать по возможности минимальное количество АМРР с целью оптимального использование имеющихся роботов, что достигается при минимальной площади взаимного наложения областей покрытия роботов. Кроме этого целевые позиции должны быть вычислены таким образом, чтобы минимизировать площадь избыточного

перекрытия: SA = SnK - So6n, где S„K - суммарная площадь покрытия, So6l -площадь заданной области. Это необходимо для уменьшения вероятности несанкционированного доступа к сети.

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

Первый из разработанных в диссертации алгоритмов основан на

гексагональном покрытии, особенностью которого является

расположение целевых позиций АМРР в узлах гексагональной сетки,

ю

покрывающей всю заданную область. Радиус покрытия одного АМРР

гексагональной структуры рассчитывается по формуле: й = Д™рр, для

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

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

Int\-^- 1 + 1, если Rem\

IV3R) IV3 RJ 2'

Int\-%2-\ + 2, ewuRemi ]>-;

JlRj [j3Rj 2'

m-

lnt\ Л"' +1, если Rem 1 1.5 RJ

<2 1.5R Гз'

Int\-^~ 1 + 2, ecnuRemi-^- |>-2

3

где Int - операция нахождения целой части, Rem(x) = х - Int(x), xw -длина прямоугольника вдоль оси х, yw - длина прямоугольника вдоль оси У-

Координаты центра круга, расположенного в ¿-ой (1 <к<п) строке и /-ом (1 <1<т) можно найти, используя формулу: .3

0.5+(/-1)-Л,(1- 1)л/з R, если1 нечетное, 3 Я

0.5+(/ -1) - Л,—Я + (* -1)>/3 Я, если I четное.

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

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

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

п

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

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

™пХ Е 1К"С1,

;=1 х^К,

где К, - /-ый кластер, к - количество кластеров, г = 1,2,..., к, х] е К, ая точка кластера^,, и с - центр г'-ого кластера.

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

727 ^

где - площадь круга, обозначающего зону действия

коммуникационного сигнала робота-ретранслятора.

^_Г—--Целевые позиции

4 I—роботов-ретрансляторов

Границы области

Кластер

Рис. 2. Метод кластеризации к-средних.

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

12

позиция, и процедура кластеризации повторяется, пока не останется непокрытых участков.

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

алгоритма кластеризации k-средних равна о{пЛ'Л log«). При этом случайное начальное расположение и итерационная процедура добавления целевых позиций существенно увеличивают время расчета и снижают точность решения.

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

В третьем разделе главы приводятся алгоритмы решения задачи скоординированного движения и назначения целевых позиций мобильным роботам. Данные задачи соответствуют блокам "Формирование предварительного маршрута и назначение целевых позиций в группе АМРР" и "Локальные системы планирования движения АМРР" структурно-функциональной модели.

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

графа О = (V, Е), в котором вершинами V являются позиции, которые могут занимать АМРР, ребра Е графа обозначают переходы из одной позиции в другую, а веса ребер с соответствуют стоимости этих переходов. Необходимо найти кратчайший путь от заданной вершины , обозначающей исходную позицию мобильных роботов, до целевой позиции г е V при условии, что такой путь существует.

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

= С (я, V,) + Н(\>!, где Н(х>„ 0 — эвристическая функция оценки стоимости перемещения из текущей вершины у, в целевую

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

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

Сформируем двудольный граф о,=(5иГ,л), где 5 — множество исходных позиций АМРР, Т — множество целевых позиций, причем пГ = 0 , А — множество ребер, соединяющих вершины графа так, что каждое ребро а, (А: )е А соединяет вершину ^ е 5, с вершиной Ц е Т и имеет вес с]. Тогда необходимо найти совершенное паросочетание графа 01 с минимальным весом.

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

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

Внутригрупповые взаимодействия представляются в виде графа 02=(У2,Е2,С2), где У2 - множество вершин графа, представляющих мобильные роботы группы; Е2 — множество ребер графа, отражающих

коммуникационные связи между роботами; С-2 - множество ограничительных функций, которые описывают условия сохранения связей Е2. Ограничительные функции можно представить в виде = (х, ~хк? +(у,-укГ-К, где Я,(х,. у,) и цк(хК ук) -координаты соседних г'-ого и ¿-ого роботов соответственно. Ограничение становится активным, когда дк) = ¿х, где 5Х отрицательное число, которое рассматривается как пороговое значение. Положение относительно соседних АМРР группы налагает на каждый робот два вида ограничений: поддержание коммуникационной связи и уклонение от столкновений.

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

При формировании управляющих воздействий для режимов управления была использована методика группового управления роботами на основе метода потенциалов. При этом предполагается, что на АМРР накладываются только голономные связи. Модель г'-ого робота может быть представлена в виде: <7,= и,, где и, - управляющее воздействие. Суть метода заключается в предположении, что целевая позиция робота имеет некоторый положительный заряд, а сам робот и препятствия среды отрицательный. Тогда робот под действием сил будет притягиваться к целевой позиции и отталкиваться от препятствий и других роботов. В качестве закона движения в этой работе была использована так называемая навигационная функция особенностью которой является отсутствие локальных минимумов, присущих другим реализациям метода:

(¿Ч<7„<7Г) + П ¿(ЯпО^У

;=о

где <1(<у,, ) - расстояние от до д„ ¿(дпО- расстояние от с/, до препятствия О,, М - количество препятствий, к - параметр, зависящий от геометрии рабочего пространства.

В этом случае управляющее воздействие для г'-ого робота может быть определено следующим образом: ",(<?,) = -^У,(д1).

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

1. «Достижение соединения» и, = ia^ga + ),

где Vga и ^gh - градиенты ограничительных функций, связанных с соседними AMPP Ra и Rb, коэффициенты а и Ъ принимают значения 0 или 1 в зависимости от активности ограничений, kj - коэффициент пропорциональности.

2. «Движение к целевой позиции» = '

„ =

где НИМ1-

3. «Поддержание соединения» = (a^Sa + ,

где fo - коэффициент пропорциональности такой, что k2>2ki.

Таким образом каждый АМРР в составе ПКС на основании

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

Третья глава посвящена моделированию работы ПКС на базе группы АМРР. Разработанные модели и алгоритмы были реализованы в виде прикладного программного обеспечения на платформе Microsoft Win32.

Моделирование распределения целевых позиций для АМРР по заданной области проводилось для следующих параметров: площадь заданной области 116590 м2, радиус действия радиосигнала робота-ретранслятора 50 м. Конфигурация области и целевые позиции после

распределения изображе1 ibi на рис. 3.

^ Целез tt^fcНУУ ffibl^F) \ |ые позиции^.. j Щжш Граница заданной области ж: *0Ш............

а) б) в)

Рис. 3. Моделирование распределения АМРР: а) на основе гексагонального покрытия; б) на основе кластеризации к-средних; в) комбинированный алгоритм

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

Таким образом, алгоритм на основе гексагонального покрытия обладает наименьшим временем расчета, однако при невыпуклой конфигурации зоны дает неоптимальное количество используемых роботов и наибольшую площадь избыточного перекрытия. Количество роботов при использовании алгоритма на основе кластеризации к-средних со случайным начальным распределением для данного примера равно 31, что на одного робота больше, однако площадь избыточного перекрытия при этом в 2,6 раза меньше. Комбинированный алгоритм позволяет повысить эффективность решения задачи для рассматриваемого примера за счет сокращения времени в 7,8 раз в сравнении с предыдущим алгоритмом, а также за счет уменьшения количества роботов на 3 единицы и снижения площади перекрытия на 2404 м2.

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

Алгоритм Время выполнения, мс. Количество необходимых роботов Покрываемая площадь, м2. Площадь избыточного перекрытия, м2.

гексагональное покрытие 1 30 180571 63981

кластеризация к-средних 2354 31 142220 25630

комбинированный 301 28 139816 23226

Моделирование работы алгоритмов назначения и перемещения было проведено с помощью двух созданных в рамках диссертации программных пакетов, реализующих различные уровни систем планирования. В первом происходит предварительное планирование перемещения с помощью алгоритма А*. Во втором - локальное планирование с помощью алгоритма скоординированного перемещения.

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

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

17

потенциалов. Назначение целевых позиций проходило с помощью

венгерского алгоритма.

б)

Рис. 4. Результаты моделирования движения группы АМРР: а) глобальное планирование с помощью алгоритма А*; б) с помощью метода потенциалов

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

Четвертая глава посвящена созданию экспериментального образца ПКС и исследованию его функционирования.

Экспериментальный образец подвижной коммуникационной сети был создан на базе трех подвижных платформ MD050 с ретрансляторами ASUS RT-N10. Взаимодействия системы с оператором осуществлялось с помощью переносной ЭВМ с разработанным программным обеспечением.

На рис. 5 показаны движение экспериментальных образцов АМРР и изображения перемещений моделей АМРР на цифровой карте.

Рис. 5. Экспериментальное исследование работы ПКС

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

роботам-ретрансляторам необходимо было обеспечить ,

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

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

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

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

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

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

19

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

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

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

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

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

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

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

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

1. Градецкий В.Г., Ермолов И.Л., Князьков М.М., Собольников С.А., Построение подвижных коммуникационных сетей на базе наземных автономных мобильных роботов, "Мехатроника. Автоматизация. Управление", № 11, 2011, — с.27-32.

2. Ермолов И.Л., Илюхин Ю.В., Собольников С.А. Планирование траекторий движения в группе автономных мобильных коммуникационных роботов. "Вестник МГТУ "Станкин"" №4, 2012, — с.102-106.

3. Ермолов И.Л., Собольников С.А. Решение задачи планирования скоординированных движений группы мобильных роботов для

обеспечения работы подвижной коммуникационной сети. "Вестник МГТУ "Станкин"" №4, 2012, — с. 117-121.

4. Ермолов И.Л., Собольников С.А. Решение задачи распределения группы мобильных роботов для обеспечения работы подвижной коммуникационной сети. "Вестник МГТУ "Станкин"" №4, 2012, —с.142-146.

5. Ермолов И.Л. Никитин В.Н. Собольников С.А., Интерактивный тренажер для операторов мобильных роботов с элементами актуальной адаптации, "Мехатроника, автоматизация, управление", №9, 2010, — с.45-51.

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

6. Градецкий В.Г. Ермолов И.Л. Князьков М.М. Собольников С.А. Создание подвижных коммуникационных сетей на базе автономных мобильных роботов, Труды международной научно-техническая конференция «ЭКСТРЕМАЛЬНАЯ РОБОТОТЕХНИКА», Санкт-Петербугр, 2011, — с.93-94.

7. Ермолов И.Л., Подураев Ю.В., Собольников С.А. Система планирования действий в группе мобильных роботов при создании подвижной коммуникационной сети, Труды международной научно-техническая конференция «ЭКСТРЕМАЛЬНАЯ РОБОТОТЕХНИКА», Санкт-Петербугр, 2012, — с.85-90.

8. Ермолов И.Л. Никитин В.Н. Собольников С.А., Интерактивный тренажер для операторов мобильных роботов с элементами актуальной адаптации // Труды XXI международной научно-техническая конференция «ЭКСТРЕМАЛЬНАЯ РОБОТОТЕХНИКА», Москва, 2010, — с.159-168.

9. Ermolov I.L., Nikitin V.N., Sobolnikov S.A., Adaptive Simulator for Training Mobile Robots' Operators, Труды международной научной конференции «Robotics for risky interventions and Environmental Surveillance-Maintenance 5th IARP RISE'2011», Левен, Бельгия, 2011.

10. Собольников C.A., Система распределения мобильных коммуникационных роботов на местности, Труды XV научной конференций «Математическое моделирование и информатика», 2013, Москва, —с. 182-184.

в свидетельствах на владение правами интеллектуальной собственности:

11. Градецкий В.Г., Ермолов И.Л., Князьков М.М., Собольников С.А., Гибридная подвижная реконфигурируемая коммуникационная сеть. Патент на полезную модель № 125005. 2012.

12. Ермолов И. Л., Собольников С.А. Программа коммуникационного покрытия произвольных областей мобильными

роботами. Свидетельство о государственной регистрации программы для ЭВМ №2012615241. 2012.

13. Ермолов И.Л., Собольников С.А. Программа распределения целей в группе мобильных роботов. Свидетельство о государственной регистрации программы для ЭВМ № 2012615248. 2012.

14. Ермолов И.Л., Собольников С.А. Программа моделирования движения мобильных роботов. Свидетельство о государственной регистрации программы для ЭВМ № 2012615249. 2012.

15. Агапов Д.Г., Никитин В.Н., Омельченко Д.В., Погорелов Д.Ю., Рослякова H.A., Ковалев Р.В., Кузнецов A.M., Михайлюк М.В., Михеев Г.В., Собольников С.А., Торгашев М.А., Чулкова И.Г. Многофункциональный компьютерный тренажер «Робсим-5». Свидетельство о государственной регистрации программы для ЭВМ № 2012660448. 2012.

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

Собольников Сергей Александрович

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

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

Подписано в печать 07.11.2013 Формат 60х 90 1/16. Бумага 80 г. Усл. печ. л. 1,5. Тираж 110 экз. Заказ 199.

Отпечатано в Издательском центре ФГБОУ ВПО Московский государственный технологический университет <<СТАНКИН» 127055, Москва, Вадковский пер., За Тел.: 8(499) 973-31-93

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ "СТАНКИН"

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

04201451796

Собольников Сергей Александрович

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

СЕТИ

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

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель д.т.н., доц. Ермолов И.Л.

Москва 2013

Содержание

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

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

1.1. Подвижные коммуникационные сети на базе автономных мобильных роботов-ретрансляторов...............................................................14

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

1.3. Цель и задачи диссертационной работы...........................................44

Глава 2. Разработка системы планирования движений группы автономных мобильных роботов-ретрансляторов...........................................46

2.1. Методика планирования движений мобильных роботов-ретрансляторов ..................................................................................................46

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

2.3. Решение задачи распределения группы автономных мобильных роботов-ретрансляторов по местности...........................................................54

2.4. Решение задачи планирования скоординированных движений автономных мобильных роботов-ретрансляторов в составе группы...........80

2.5. Выводы по второй главе...................................................................104

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

3.1. Описание разработанного программного обеспечения для

моделирования работы ПКС..........................................................................110

3.2. Результаты моделирования...............................................................117

3.3. Выводы по третьей главе..................................................................132

Глава 4. Разработка экспериментального образца и исследование подвижной коммуникационной сети на базе автономных мобильных роботов-ретрансляторов.......................................................................................133

4.1. Описание разработанного экспериментального образца подвижной

коммуникационной сети.................................................................................133

4.2. Результаты натурного эксперимента...............................................143

4.3. Выводы по четвертой главе..............................................................150

Выводы и заключение..........................................................................................151

Список сокращений..............................................................................................153

Список литературы...............................................................................................154

ПРИЛОЖЕНИЕ 1..................................................................................................161

ПРИЛОЖЕНИЕ 2..................................................................................................162

ПРИЛОЖЕНИЕ 3..................................................................................................164

ПРИЛОЖЕНИЕ 4..................................................................................................165

ПРИЛОЖЕНИЕ 5..................................................................................................166

ПРИЛОЖЕНИЕ 6..................................................................................................167

ПРИЛОЖЕНИЕ 7..................................................................................................168

ПРИЛОЖЕНИЕ 8..................................................................................................169

ВВЕДЕНИЕ

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

В основе функционирования коммуникационных радиосетей лежит принцип ретрансляции сигнала, для реализации этого принципа требуются специальные узлы связи (ретрансляторы). В роли таких узлов обычно выступают стационарные радиостанции. Однако решение ряда специальных задач, например проведение военных или аварийно-спасательных операций, требует создания подвижных коммуникационных сетей (ПКС), способных не просто обеспечивать коммуникационное соединение, но и изменять форму области покрытия в ходе выполнения задачи путём изменения конфигурации мобильных узлов связи. Для построения таких сетей необходимо иметь мобильные узлы связи, в качестве которых применяют переносные радиостанции, специально оборудованные автомобили, самолеты и т.д. Пример осуществления реконфигурируемой тактической оперативной связи представлен на рисунке 1. Между тем подобные средства имеют общий недостаток - присутствие человека - оператора. Использование же в качестве мобильных узлов связи автономных мобильных роботов-ретрансляторов (АМРР) позволит минимизировать участие человека в создании коммуникационной сети и сосредоточиться на выполнении основных задач, а также снизить риск потери мобильных узлов связи и повысить незаметность средств связи и уровень защиты от несанкционированного доступа [4].

Зоново-трассоеь* ретранслятор

Зои оео-трассовый ретранслятор

Ретрансляция с временным делением

10-15 КМ

10-15 км

Абоненте

(5 ^-телефоном

Рис. 1. Осуществление реконфигурируемой тактической оперативной связи [4]

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

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

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

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

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

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

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

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

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

Научным руководителем работы выступил д.т.н. доц. И.Л. Ермолов (МГТУ «СТАНКИН»).

Диссертационная работа основывается на результатах исследований в области робототехники и мехатроники, отраженных в трудах И.М. Макарова, Д.Е. Охоцимского, И.А. Каляева, Ю.М. Соломенцева, В.Г. Градецкого, С.Г. Капустяна, В.М. Лохина, C.B. Манько, Е.И. Юревича, Р. Аркина, Т. Балча, В. Кумара, М. Матарик и других отечественных и зарубежных ученых.

Основные результаты данной работы были реализованы в рамках государственного контракта от «19» апреля 2011 г. № 16.513.11.3052 «Разработка принципов построения подвижных реконфигурируемых коммуникационных сетей» в рамках ФЦП «Исследования и разработки по

приоритетным направлениям развития научно-технологического комплекса на 2007-2013 годы».

Автор хочет выразить благодарность Е.В. Алпатовой, Борисову А.Д., Кузину H.A., Чеканину В.А, оказавшим в различной форме помощь в работе над диссертацией.

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

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

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

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

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

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

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

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

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

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

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

Научная новизна работы заключается в:

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

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

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

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

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

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

Практической ценностью обладают следующие результаты.

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

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

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

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

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

Реализация результатов работы. Теоретические и практические результаты работы использованы при выполнении НИР «Проведение проблемно-ориентированных исследований по созданию подвижных реконфигурируемых информационных коммуникационных сетей на основе автономных мобильных мехатронных агентов» Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса на 2007-2013 годы».

Апробация работы. Основные результаты диссертации докладывались и обсуждались на следующих конференциях: Международная научная конференция «Robotics for risky interventions and Environmental Surveillance-Maintenance 5th IARP RISE'2011», 2011 год, Левен, Бельгия.; XXI Международная научно-техническая конференция «ЭКСТРЕМАЛЬНАЯ РОБОТОТЕХНИКА», 2010, Москва; Международная научно-техническая конференция «ЭКСТРЕМ