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

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

КАРПОВ Алексей Владимирович

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

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

АВТОРЕФЕРАТ

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

Москва 2006

Работа выполнена в ГОУ «Московская академия рынка труда и информационных технологий» (МАРТИТ).

Научный руководитель - доктор физико-математических наук,

профессор

Ильин Евгений Михайлович

Официальные оппоненты - доктор технических наук,

заслуженный деятель науки,

зам. ген. директора «НИИ суперЭВМ»

Чудинов Станислав Михайлович

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

Митин Юрий Валентинович

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

специального машиностроения МГТУ им Н.Э.Баумана

Защита диссертации состоится « № » «2006» г. в часов на

заседании диссертационного совета Д 850.001.01 при Московской академии рынка труда и информационных технологий (МАРТИТ) по адресу: 121351, г. Москва, ул. Молодогвардейская, д.46, корп. 1, телефон (495) 149-86-38.

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

Автореферат разослан & & 2006 г.

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

Чересов Ю.И.

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

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

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

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

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

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

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

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

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

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

• системный анализ аппаратных и программных средств, используемых при автономном управлении роботом — охранником, роботом — сторожем и беспилотным летательным аппаратом (БПЛА);

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

• применение алгоритмов и разработка программных средств построения • карты местности и поиска кратчайшего пути;

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

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

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

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

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

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

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

Практическая значимость результатов. Разработанный автором на основе исследованных методов комплекс программ использован для дистанционного и автономного управления серией роботов, созданных в ЗАО НТЦ «РИССА», выполняющих различные функции: робота-сторожа для охраны помещений, домашнего робота-охранника, разведчика в труднодоступных и опасных местах, игрового и обучающего робота, беспилотного летательного аппарата (БПЛА). Практическая значимость диссертации подтверждается актом о внедрении результатов исследования в ЗАО НТЦ «РИССА».

Созданный на основе модульной архитектуры программный комплекс может применяться для управления и, в частности, для обеспечения навигации широкого класса мобильных роботов, так как открытость предлагаемого программного обеспечения и его «независимость» от операционной системы (Windows, Linux) позволяют легко адаптировать его к конкретной задаче.

Апробация работы. Основные результаты работы докладывались на 3-ей Международной научно-технической конференции «Радиотехника и связь»,

г. Саратов, СГТУ, 2006, обсуждались на научных семинарах в Московской академии рынка труда и информационных технологий, а также были опубликованы в Вестнике Московской академии рынка труда и информационных технологий и в сборнике трудов конференции "Радиотехника и связь", г. Саратов, СГТУ, 2006.

Действующие модели многофункционального семейства роботов демонстрировались на выставках: Московская международная выставка «Школа 2001» (2001 г.), «Хобби - планета увлечений'02» (2002 г.), «Робототехника'04» (2004 г.), «Интеллектуальные и адаптивные роботы» (2005 г.), проходивших в городе Москве на ВВЦ и в других выставочных комплексах. Разработанные модели роботов были отмечены следующими наградами: лауреат выставки «Школа 2001» за разработку комплексной обучающей системы на базе семейства минироботов «МуЯо», «Гран — при» в номинации Игрушка XXI века на выставке «Хобби - планета увлечений'02» и медалью 2-ой специализированной выставки Робототехника'04.

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

• разработанная и внедренная модель поведения робота и соответствующее программное обеспечение для построения карты местности с использованием ультразвукового дальномера;

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

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

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

Публикации. Материалы диссертации опубликованы в 7 печатных работах, из них 5 статей, 2 — материалы научно-технических конференций.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка литературы. Объем диссертации составляет 127 страниц, в том числе 64 рисунка, 8 таблиц и библиография из 141 наименования.

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

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

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

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

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

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

GSM/GPRS модуль .

Модуль СРБ

Синтезатор речи

Модуль зарядки аккумуляторов

Датчики обнаружения движения, заряда батареи, крена, : давления и температуры

Центральный контроллер

Модуль управления двигателями M Двигатели -•

Модуль управления видеокамерой Видеокамера

Модуль управления ул ьтразву ков ым дальномером Дальномер i ;

HTTP/WAP - сервер

Управляющий процессор (РСМ-3350 СХ1-300)

Управляющая программа

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

I

m

Ü¡

Модуль управления двигателям м

», скорость, р

______<г

Система ориентации ' 1

Модуль обработки данных Модуль обработки данных Модуль обработки данных

дальномера видеокамер (добряките, двигателей

(расстояние и препятствий) . параметры камеры) (скорость, расстожив)

t

Модуль определения параметров навигации

Модуль планирования движения

Модуль управления видеокамерой

{ыамсчаиив.упы ПГЛорО!»^

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

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

Рис. 2. Робот на гусеничном шасси

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

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

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

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

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

• определение правил и алгоритмов поведения в автономном режиме;

• управление роботом через Интернет (с помощью компьютера или мобильного телефона (WAP 1.2/2.0));

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

• настройка параметров робота;

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

Предлагаемое программное обеспечение должно также обеспечить:

• построение карты местности;

• определение параметров навигации;

• реализацию системы автономного управления роботом.

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

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

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

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

• управляющая программа — производит управление остальными модулями системы;

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

Модуль

Двигатели управления

двигателями

1 Модуль управления у л ьтразву ковы м —э Дальномер

Получение данных с дальномером

видеокамер, _

двигателей Модуль управления Камера

видеокамерой

Рис. 3 Блок-схема комплекса алгоритмов системы ориентации в пространстве • модуль обработки данных двигателей — осуществляет обработку, накопление и анализ данных, поступающих с двигателей (количество оборотов);

• модуль управления видеокамерами — отвечает за выполнение команд управления видеокамерой: поворот, приближение, включение/выключение и т.д.;

• модуль обработки данных видеокамер — отвечает за обработку, накопление и анализ данных, поступающих с видеокамеры: первичная обработка изображения (яркость, контраст), выделение объектов на изображении, распознавание объектов, определение параметров объектов (дальность, угол поворота камеры по отношению к объекту и т.д.);

• модуль управления дальномером - отвечает за выполнение команд управления ультразвуковым дальномером: поворот, включение/выключение и т.д.;

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

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

• модуль планирования движения — рассчитывает оптимальный маршрут с

учетом параметров ориентации в пространстве и отклонения от расчетного маршрута; • интерфейс пользователя - данный блок предназначен для обеспечения взаимодействия робота с пользователем и включает в себя функции работы через различные каналы связи: Интернет (с помощью компьютера или мобильного телефона (WAP 1.2/2.0)) или локальная сеть. Во второй главе проанализированы такие виды датчиков робота, как дальномеры и видеокамеры. Оцениваются возможности их использования для решения задачи автономного управления роботом. Показано, что совместное использование видеокамеры (моно или стерео) и ультразвукового дальномера является наиболее предпочтительным для решения задачи определения параметров навигации. Применение ультразвуковых дальномеров оправдано их невысокой стоимостью (по сравнению с лазерными аналогами), малыми габаритами и спецификой одного из видов разрабатываемых роботов (детские игрушки) при достаточно высокой точности измерений (менее 1 мм на 300 -4000 мм). Отмечено, что для получения достоверной работы описанных датчиков необходима их точная калибровка (определение параметров), алгоритм которой зависит от вида устройства.

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

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

Процедура калибровки заключается в вычислении внутренних и внешних параметров камеры. Внутренние параметры описывают свойства самой камеры и не изменяются при перемещении камеры в пространстве. В приближении тонкой линзы и геометрической оптики, матрица внутренних параметров (3 х 3) определяется четырьмя величинами: двумя координатами оптической оси на экране ис, ус и выраженными соответственно в размерах пикселей вертикального и горизонтального направления величинами фокусного расстояния /и,,/у Эта матрица определяет связь между координатами (и, V) изображения на экране в пикселях и координатами (X\ У, 2) точки наблюдения в декартовой системе координат с началом в центре линзы и осями X, У, лежащими в плоскости линзы, а осью X направленной наружу. Соответствующее матричное соотношение имеет вид:

(X

О)

Г-Л 0 ис О -/, О О 1 _ ч

Если для описания положения точки используется некоторая произвольная декартова система координат, то необходимо записать формулы преобразо-

вания координат при переходе к системе координат, связанной с камерой. Соответствующее преобразование системы координат сводится к ее вращению, описываемому ортогональной матрицей Я = {гу}, и переносу начала координат системы на вектор сдвига V.

гс = Иг+1 (2)

или в матричном виде:

'х* (г 12 1з '0

У = Г2\ г12 Г21 'г

/31 гзг гзз

чЬ

(3)

Матрица вращения, которая сводится в данном случае к вектору вращения г, и вектор сдвига - это внешние параметры видеокамеры.

Определение параметров камеры по результатам наблюдения — одна из задач компьютерной обработки изображений. Предложенные алгоритмы оптимизированы и реализованы на языке С++.

Для калибровки камеры вводится матрица //= {1ги}, представляющая собой произведение матриц внутренних и внешних параметров. Эта матрица связывает между собой координаты {х,у,г) точек в пространстве с координатами (м,у) их изображений:

и= ^х + ЪгУ + Ь Зг + /г,4

/г2,* + /г22>> + /г2:,г + /г24

¿и* + ^2у + + Аз4

В матричном виде эти два уравнения имеют вид:

V

Кг Кг

К. К К Кг

К

к к к

К)

(4)

Схуг10000 -их —иу -иг —и IО О О О л _у г 1 -гх -уу -У2 -V

= 0

(5)

Поиск параметров камеры выполняется в два этапа. На первом этапе оцениваются значения элементов матрицы Иу, а на втором этапе по этим элементам находятся внутренние и внешние характеристики камеры.

Пусть в результате измерений нам известно положение в пространстве N точек (х;, уи г,) и их изображений («,, V;). Так как каждое измерение дает 2 соотношения между координатами точек и их изображений (5), то получаем однородную (с нулевой правой частью) систему из 2Ы уравнений для 11

неизвестных вида Ах = О ^У!", аИх, =0, 1 <к<п с т неизвестными, п >т

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

п / т т ^^

где ь„ =

Будем искать минимум функции Р{х1,х2,...,хт) при условии нормировки Блок - схема алгоритма калибровки камеры для трехмерного объекта изображена на рис. 6.

Далее приводится запрограммированный на С++ алгоритм решения всей задачи.

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

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

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

ф = £(Сч - Ч)2 + ((V, - V,)2) (6)

1=1

Функция Ф нелинейно зависит от внутренних и внешних параметров: ис, Ус» А> /«

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

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

/^2у + ^3)у'+ (/=>+ /^У + ^з) = 0 (7)

либо

(*;,«'+ рп)и+(*;,«•+ ^22у+гм)у+(/>•+ ^23у'+ = о, (8) где совокупность коэффициентов называется фундаментальной матрицей. Геометрически эти соотношения означают, что точке (ы,у) левого изображения

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

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

ний. На рис. 7 приводится блок-схема работы этого алгоритма.

Программная реализация алгоритмов на языке С++ проиллюстрирована

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

вычислены вручную координаты 14 точек, отмеченных на рисунке. В результате работы процедуры робастного алгоритма НАИБАС рассчитаны значения элементов фундаментальной матрицы. Для вычисленных значений элементов матрицы условия (7) и (8) выполняются лишь приблизительно. Если рассматривать эти условия как уравнения эпилиний, то отклонение точек от соответствующих прямых характеризует уровень погрешности (шума). Из рис. 8, где показаны также эпилинии выбранных точек, видно, что для некоторых точек (2, 3, 11) эти отклонения достаточно велики.

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

Рис. 8. Левое (а) и правое (б) стереоизображения и соответствующие эпилинии

предметы могут загораживать другие. Считается, что для каждого пикселя определена его интенсивность (яркость) 1{и,\). В качестве энергии строится выражение, учитывающее меру отклонения яркостей и используется принцип «гладкости»: близким пикселям на левом изображении соответствуют близкие пиксели правого изображения:

Здесь первая сумма берется либо по пикселям одной строки, либо по пикселям всего изображения, либо по пикселям некоторой области, вторая сумма берется по всем парам (р, q) соседних пикселей ц левого изображения, функция Кр положительна, если расхождения с[р и с1ч этих пикселей различа-

ются, а Л - весовой коэффициент, определяющий вес энергии сглаживания. Для минимизации энергии (9) в диссертации используется метод динамического программирования. Его реализация на языке С++ проиллюстрирована на практическом примере стереофотографий шахматной доски.

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

/Г р х л г%< г

Рис. 9. Триангуляция при наличии ошибок измерения

В третьей главе проанализированы и реализованы в виде программ на языке С++ алгоритмы расчета параметров навигации и определения маршрута

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

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

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

алгоритмов, позволяет с наименьшими затратами вычислительных ресурсов (сложность 0(п21пи), где п — число ребер препятствий) определить кратчайший путь между начальной и конечной точками траектории движения робота. Данный алгоритм, реализованный в виде программы на языке С++, позволяет анализировать данные, поступающие с различных датчиков и в

реальном масштабе времени принимать решение относительно оптимального выбора маршрута движения.

Алгоритм поиска минимального пути с помощью графа видимости применяется, если окружение робота не изменяется со временем и нужно находить пути для различных начальных и конечных состояний. В этом случае удобно вначале построить граф видимости разрешенной области. Чтобы вычислить граф видимости, нужно найти все пары узлов (вершин) препятствий, которые могут "видеть" друг друга. Это означает, что для каждой пары нужно проверить, не пересекается ли отрезок, их соединяющий, с каким-нибудь препятствием. Отрезок, соединяющий такие узлы, называется ребром видимости. Чтобы получить кратчайший путь, необходимо в графе видимости к множеству узлов препятствий добавить начальную р,ю, и конечную р^,, точки траектории движения робота. После этого каждой дуге графа видимости приписывается вес, равный расстоянию между точками на плоскости. Поиск в этом графе пути с минимальным суммарным весом дает искомый кратчайший путь (рис. 11).

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

3$

Рис. 11. Кратчайший путь в графе видимости Рис. 12. Конфигурационное пространство (СР), II — робот, Р — препятствие

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

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

Сначала реализовано решение задачи построения карты местности с помощью мобильного робота и ультразвукового дальномера. Алгоритм построения карты приведен на рис. 13. Данный алгоритм реализован на языке

С++ и использовался при практической реализации программного обеспечения робота.

В этой же главе представлена работа блока обработки видеосигнала и определения параметров навигации на примере ориентации робота по маякам. Задача решена в три этапа:

1. распознавание маяков на изображении, полученном с видеокамеры;

2. определение параметров маяка: номера маяка, расстояния до него и угла наклона маяка на изображении;

3. вычисление параметров навигации робота по карте местности и параметрам, полученным на втором этапе.

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

• изображение маяка должно быть контрастным (например, черно-белым);

• кодировка номера маяка должна быть проста для распознавания и

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

Алгоритм распознавания маяков и определения их параметров показан на рис. 14.

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

Все программные модули написаны на С++ с использованием отдельных функций дополнительных библиотек: Qt 4.0.0 (интерфейсная часть) и OpenCV (обработка видео). За счет «платформонезависимости» используемых программных средств стало возможным применение данного программного обеспечения не только для Windows (2000, ХР), но и для таких платформ, как Linux и им подобных.

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

• робот-сторож,

• домашний робот-охранник,

• робот-разведчик в труднодоступных и опасных местах,

• робот в учебном процессе,

• БПЛА - беспилотный летательный аппарат.

ЗАКЛЮЧЕНИЕ

Основные результаты выполненной работы заключаются в следующем:

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

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

Реализован в виде программ алгоритм определения параметров (диаграмммы направленности) ультразвукового дальномера.

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

Проведен анализ, обоснованы и реализованы в виде программ на языке С++ три алгоритма нахождения фундаментальной матрицы, определяющей связь между стереопарой изображений и точкой реального объекта: восьмиточечный, семиточечный и алгоритм ИАКБАС, использующий восьми- и семиточечные алгоритмы в комплексе и осуществляющий согласованность по случайным выборкам из всего набора данных координат точек стереоизображений с большим количеством точек. Проведенный анализ и сравнение показали, что оптимальным для практической реализации является алгоритм КАЫБАС по критерию исключения «плохих» точек из выборки, на основе которой получен конечный результат.

Разработана программная реализация алгоритма восстановления трехмерной «сцены» по ее стереоизображению - триангуляции.

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

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

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

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

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

Разработано открытое к модернизации и «платформонезависимое» (Windows (2000, ХР), Linux) программное обеспечение с модульной структурой для дистанционного и автономного управления многофункциональным семейством роботов.

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

• робот - сторож,

• домашний робот - охранник,

• робот - разведчик в труднодоступных и опасных местах,

• робот в учебном процессе,

• БПЛА - беспилотный летательный аппарат.

Проведенные исследования позволили успешно решить поставленные задачи, а именно:

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Карпов A.B. Построение карты местности с помощью мобильного робота и дальномера // Вестник Московской академии рынка труда и информационных технологий. - 2005. - № 20. - С. 110 - 114.

2. Карпов A.B. Ориентация в пространстве по маякам // Вестник Московской академии рынка труда и информационных технологий. -2005. - № 20. - С. 89 - 93.

3. Карпов A.B. Алгоритмы поиска пути робота // Радиотехника и связь: Материалы 3-ей Международной научно-технической конференции. -СГТУ. - Саратов. - 2006. - С. 23 - 30.

4. Карпов A.B. Задача наблюдения за системой помещений // Радиотехника и связь: Материалы 3-ей Международной научно-технической конференции. - СГТУ. - Саратов. - 2006. - С. 17 - 23.

5. Карпов A.B. Обработка изображений, полученных с помощью стереокамер // Вестник Московской академии рынка труда и информационных технологий. - 2006. - № 25. — С. 92 — 97.

6. Карпов A.B., Топехин А.Г. Использование стереоизображений для ориентации робота // Вестник Московской академии рынка труда и информационных технологий. - 2006. - № 27 - С. 86 - 92.

7. Карпов A.B., Топехин А.Г. Установление соответствия между точками стереоизображений // Вестник Московской академии рынка труда и информационных технологий. - 2006. - № 27 — С. 111 - 119.

Заказ № 236/06/06 Подписано в печать 23.06.2006 Тираж 50 экз. Усл. п.л. 1,17

ООО "Цифровичок", тел. (495) 797-75-76; (495) 778-22-20 -www.cfr.ru; е-таИ:т/о@с/г.ги

Введение

1. Анализ построения программного управления роботами

1.1 Основные компоненты робота

1.2 Описание модулей (компонентов) робота

1.3 Архитектура программного обеспечения

1.4 Описание основных модулей программы управления роботами 24 Выводы

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

2.1 Алгоритмы обработки информации, полученной от ультразвукового дальномера

Определение параметррв дальномера

Обработка показаний дальномера

2.2 Калибровка цифровой видеокамеры: теория и алгоритмы 33 Параметры камеры 33 Определение параметров камеры

2.3 Алгоритмы определения геометрии стереоизображений и реконструкции трехмерного объекта

Эпиполярная геометрия

Фундаментальная матрица 44 Установление соответствий между точками стереоизображений 49 Реконструкция трехмерной сцены по системе изображений

Выводы

3. Алгоритмы и программное обеспечение поиска оптимального пути робота 65 3.1 Задача поиска оптимального пути робота

Волновой алгоритм

Трапецеидальный план

Модель движения точечного робота

Модель движения робота-многоугольника

Алгоритм поиска кратчайшего пути

Алгоритм вычисления графа видимости

Алгоритм нахождения кратчайшего пути

3.2 Задача размещения маяков в системе помещений

Разбиение многоугольника на монотонные части

Триангуляция монотонного многоугольника

Выводы 86 4. Предложения по практическому использованию разработанного программного обеспечения для управления роботами

4.1 Построение карты местности с помощью мобильного робота и дальномера

4.2 Ориентация в пространстве по маякам 92 Распознавание маяка 94 Определение параметров маяка

4.3 Примеры разработанных роботов 100 Выводы

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

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

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

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

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

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

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

• системный анализ аппаратных и программных средств, используемых при автономном управлении роботом - охранником, роботом - сторожем и беспилотным летательным аппаратом (БПЛА);

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

• применение алгоритмов и разработка программных средств построения карты местности и поиска кратчайшего пути;

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

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

Научная новизна работы:

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

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

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

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

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

Практическая значимость результатов. Разработанный автором на основе исследованных методов комплекс программ использован для дистанционного и автономного управления серией роботов, созданных в ЗАО НТЦ «РИС-СА», выполняющих различные функции: робота-сторожа для охраны помещений, домашнего робота-охранника, разведчика в труднодоступных и опасных местах, игрового и обучающего робота, беспилотного летательного аппарата (БПЛА). Практическая значимость диссертации подтверждается актом о внедрении результатов исследования в ЗАО НТЦ «РИССА».

Созданный на основе модульной архитектуры программный комплекс может применяться для управления и, в частности, для обеспечения навигации широкого класса мобильных роботов, так как открытость предлагаемого программного обеспечения и его «независимость» от операционной системы (Windows, Linux) позволяют легко адаптировать его к конкретной задаче.

Апробация работы. Основные результаты работы докладывались на 3-ей Международной научно-технической конференции «Радиотехника и связь», г. Саратов, СГТУ, 2006, обсуждались на научных семинарах в Московской академии рынка труда и информационных технологий, а также были опубликованы в Вестнике Московской академии рынка труда и информационных технологий и в сборнике трудов конференции "Радиотехника и связь", г. Саратов, СГТУ, 2006.

Действующие модели многофункционального семейства роботов демонстрировались на выставках: Московская международная выставка «Школа 2001» (2001 г.), «Хобби - планета увлечений'02» (2002 г.), «Робототехника'04» (2004 г.), «Интеллектуальные и адаптивные роботы» (2005 г.), проходивших в городе Москве на ВВЦ и в других выставочных комплексах. Разработанные модели роботов были отмечены следующими наградами: лауреат выставки «Школа 2001» за разработку комплексной обучающей системы на базе семейства минироботов «MyRo», «Гран - при» в номинации Игрушка XXI века на выставке «Хобби - планета увлечений'02» и медалью 2-ой специализированной выставки Робототехника'04.

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

• разработанная и внедренная модель поведения робота и соответствующее программное обеспечение для построения карты местности с использованием ультразвукового дальномера;

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

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

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

Публикации. Материалы диссертации опубликованы в 7 печатных работах, из них 5 статей, 2 - материалы научно-технических конференций.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка литературы. Объем диссертации составляет 127 страниц, в том числе 64 рисунка, 8 таблиц и библиография из 141 наименования.

Основные результаты выполненной работы заключаются в следующем:

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

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

Реализован в виде программ алгоритм определения параметров (диаграмммы направленности) ультразвукового дальномера.

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

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

Разработана программная реализация алгоритма восстановления трехмерной «сцены» по ее стереоизображению - триангуляции.

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

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

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

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

Разработано открытое к модернизации и «платформонезависимое» (Windows (2000, ХР), Linux) программное обеспечение с модульной структурой для дистанционного и автономного управления многофункциональным семейством роботов.

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

• робот - сторож,

• домашний робот - охранник,

• робот - разведчик в труднодоступных и опасных местах,

• робот в учебном процессе,

• БПЛА - беспилотный летательный аппарат.

Проведенные исследования позволили успешно решить поставленные задачи, а именно:

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

1. Карпов А.В. Построение карты местности с помощью мобильного робота и дальномера, М.: Вестник МАРТИТ, 2005, № 20.

2. Карпов А.В. Ориентация в пространстве по маякам, М.: Вестник МАРТИТ, 2005, №20.

3. Карпов А.В. Алгоритмы поиска пути робота, «Радиотехника и связь»: Материалы 3-ей Международной научно-технической конференции. Саратов, СГТУ, 2006.

4. Карпов А.В. Задача наблюдения за системой помещений, «Радиотехника и связь»: Материалы 3-ей Международной научно-технической конференции. Саратов, СГТУ, 2006.

5. Карпов А.В. Установление соответствия между точками стереоизображений, М.: Вестник МАРТИТ, 2006, № 27.

6. Карпов А.В. Использование стереоизображений для ориентации робота, М.: Вестник МАРТИТ, 2006, № 27.

7. Карпов А.В. Обработка изображений, полученных с помощью стерео-камер, М.: Вестник МАРТИТ, 2006, № 25.

8. Бронштейн И.Н., Семендяев К.А. Справочник по математике, М.: Наука, 1967.

9. Вентцель Е.С. Элементы динамического программирования. Москва, "Наука", 1964.

10. Голуб Дж., Ван Лоун Ч. Матричные вычисления Москва, «Мир», 1999

11. Калиткин Н.Н. Численные методы, М.: Наука, 1978.

12. Предко М. Устройства управления роботами: схемотехника и программирование, М.: ДМК-пресс, 2004.

13. Препарата Ф., Шеймос М., Вычислительная геометрия. Введение. Москва, «Мир», 1989.

14. Форсайт Д., Понс Ж. Компьютерное зрение. Современный подход, Издательский дом «Вильяме», 2004.

15. Хори Б.К.П. Зрение роботов, Москва, "Мир", 1989.

16. Betke, Gurvits L. Mobile robot localization using landmarks. IEEE Transactions on Robotics and Automation, 13(2): P. 251-263,1997.

17. Birchfield S., Tomasi C. "Depth Discontinuities by Pixel-to- Pixel Stereo," Technical Report STAN-CS-TR-96-1573, Stanford Univ., 1996.

18. Birchfield S., Tomasi C. Multiway cut for stereo and motion with slanted surfaces. In ICCV99, P. 489^95,1999.

19. Blake A. Comparison of the efficiency of deterministic and stochastic algorithms for visual reconstruction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(1): P. 2-12, January 1989.

20. Borenstein J., Everett H., Feng L. Navigating mobile robots. Wellesley, Massachusetts: A.K. Peters, Ltd., 1996.

21. Bougnoux S. From projective to euclidean space under any practical situation, a criticism of self-calibration. In Proceedings of the 6th International Conference on Computer Vision, P. 790-796, Jan. 1998.

22. Boykov Y., Veksler O., Zabih R. Markov random fields with efficient approximations. In IEEE Conference on Computer Vision and Pattern Recognition, P. 648-655,1998.

23. Boykov Y., Veksler O., Zabih R. Fast Approximate Energy Minimization via Graph Cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23: P. 1222-1239,2001.

24. Boykov Y., Kolmogorov V. Computing geodesies and minimal surfaces via graph cuts. In International Conference on Computer Vision, volume I, P. 2633,2003.

25. Boykov Y., Kolmogorov V. An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(9): P. 1124-1137, September 2004.

26. Boykov Y., Veksler O. Graph Cuts in Vision and Graphics: Theories and Applications, in "Handbook of Mathematical Models in Computer Vision", edts. N. Paragios, Y. Chen, 0. Faugeras, P. 100 118.

27. Brooks R.A., Solving the Find-Path Problem by a Good Representation of Free Space, IEEE Trans, on Systems, Man and Cybernetics, SMC-13 No.3, P. 190197, March 1983.

28. Brooks R.A., Aspects of Mobile Robot Visual Map Making, Proceedings of 2nd International Symposium of Robotics Research, P. 287-293, August 1984.

29. Brooks R.A., T. Lozano-Perez, A Subdivision Algorithm in Configuration Space for Find Path with Rotation, IEEE Trans, on Systems, Man and Cybernetics, SMC-15 No.2, P. 224-233, March/April 1985.

30. Brown M.Z., Burschka D., Hager G.D. Advances in Computational Stereo, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, No 8 (2003) P. 993- 1008.

31. Burgard W., Fox D., Thrun S. Active mobile robot localization. In Proc. of the Fifteenth International Conference on Artificial Intelligence (IJCAI-97), 1997.

32. Caprile В., Torre V. Using Vanishing Points for Camera Calibration. The International Journal of ComputerVision,4(2): P. 127-140, Mar.1990.

33. Castellanos J.A., Tardos J.D. Mobile Robot Localization and Map Building: A Multisensor Fusion Approach. Kluwer Academic Publishers, Boston, MA, 2000.

34. Chatila R. Path Planning and Environment Learning, European Conference on Artificial Intelligence, P. 211-215, July 1982.

35. Chatila R., Laumond J-P. Position Referencing and Consistent World Modelling for Mobile Robots, Proceedings of IEEE International Conference on Robotics and Automation, P. 138-145, March 1985.

36. Chen J. Computational Geometry: Methods and Applications. Texas University, 1996.

37. Clarke Т. A., Fryer F. G. The development of camera calibration methods and models. In Photogrammetric Record, volume 16(91), P. 51-66, April 1998.

38. Cochran S. D., Medioni G. 3-D surface description from binocular stereo. IEEE Trans, on Pattern Analysis and Machine Intell., 14 (10): P. 981-994,1992.

39. Cormen H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms, McGraw-Hill Book Company, 2001.

40. Cox I.J. Blanche: An experiments in guidance and navigation of an autonomous mobile robots, IEEE Transactions Robotics and Automations, vol. 7, no. 3, P. 193-204,1991.

41. Cox I., Hingorani S., Rao S., Maggs B. A maximum likelihood stereo algorithm. Computer Vision, Graphics and Image Processing, 63(3): P. 542-567, 1996.

42. Crowley J.L. Navigation for an Intelligent Mobile Robot, IEEE Journal of Robotics and Automation, Vol. RA-1 No. 1, P. 31-41, March 1985.

43. Csorba M. Simultaneous Localization and Map Building. PhD thesis, University of Oxford, 1997.

44. Davison A.J. Mobile Robot Navigation Using Active Vision. PhD thesis, University of Oxford, 1998.

45. Dhond U., Aggarwal J. Structure from stereo — a review. IEEE Transactions on Systems, Man and Cybernetics, 19(6), 1989.

46. Dissanayake M.W.M.G., Newman P., Durrant-Whyte H.F., Clark S., Csorba M. An experimental and theoretical investigation into simultaneous localization and map building. In: Sixth International Symposium on Experimental Robotics. (1999) P. 265-274.

47. Dissanayake G., Durrant-Whyte H., Bailey T. A computationally efficient solution to the simultaneous localization and map building (SLAM) problem. Working notes of ICRA'2000 Workshop W4: Mobile Robot Navigation and Mapping, April 2000.

48. Drumheller M. Mobile robot localization using sonar, IEEE Transactions on Pattern Analysis and Machine Intel ligence, 9(1987), P. 325-331.

49. Elfes A. Sonar-Based Real World Mapping and Navigation, IEEE Journal of Robotics and Automation, P. 249-265, June 1987.

50. Faugeras 0., Toscani G. The calibration problem for stereo. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, P. 15-20, Miami Beach, FL, June 1986.

51. Faugeras O., Toscani G. Camera calibration for 3D Computer Vision, Proc. Int'l Workshop Industrial Applications of Machine Vision and Machine Intelligence, P. 240 247, Feb. 1987.

52. Faugeras 0. What can be Seen in Three Dimensions with an Uncalibrated Stereo Rig, Proc. ECCV'92,1992.

53. Faugeras O., Luong Т., Maybank S. Camera self-calibration: theory and experiments. In G. Sandini, editor, Proc 2nd ECCV, volume 588 of Lecture Notes in Computer Science, P. 321-334, Santa Margherita Ligure, Italy, May 1992. Springer-Verlag.

54. Faugeras 0. Three-Dimensional Computer Vision: a Geometric Viewpoint. MIT Press, 1993.

55. Faugeras O., Luong Q.T., Papadopoulo T. The Geometry of Multiple Images. MIT Press (2001).

56. Faugeras 0., Lustman F. Motion and structure from motion in a piecewise planar environment," Int. Journ. Pattern Recognition and Artificial Intelligence, vol. 2, no. 3, P. 485-508,1988.

57. Fischler M., Bolles R. "RANdom SAmpling Consensus: a paradigm for model fitting with application to image analysis and automated cartography", Commun. Assoc. Сотр. Mach., 24: P. 381-95,1981.

58. Geiger D., Ladendorf В., Yuille A. Occlusions and binocular stereo. International Journal of Computer Vision, 14 (3): P. 211-226,1995.

59. Giralt G., Chatila R., Vaisset M. An Integrated Navigation and Motion Control System for Autonomous Multisensory Mobile Robots, The First International Symposium of Robotics Research, MIT Press, P. 191-214,1984.

60. Grewal M.S., Weil L.K., Andrews A.P. Global Positioning Systems, Inertial Navigation and Integration, John Willey & Sons, Inc., 2001.

61. Gouzenes L. Strategies for Solving Collision-free Trajectory Problems for Mobile and Manipulator Robots, International Journal of Robotics Research, Vol.3 No. 4, P. 51-65,1984.

62. Guibas L., Motwani R., Raghavan P. The robot localization problem in two dimensions, Proceedings 3rd ACM-SIAM Symposium on Discrete Algorithms, 1992, P. 259-268.

63. Guivant J., Nebot E. Optimization of the simultaneous localization and map building algorithm for real time implementation. IEEE Transactions on Robotic and Automation 17 (2001) P. 242-257.

64. Hartley R., Gupta R., Chang T. Stereo from uncalibrated cameras, in Proc. IEEE Conf. on Computer Vision and Pattern Recognition, 1992, P. 761-764.

65. Hartley R.I. An algorithm for self calibration from several views. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, P. 908-912, Seattle, WA, June 1994.

66. Hartley R. Indefence of the 8-point algorithm. In Proceedings of the 5th International Conference on Computer Vision, pages 1064-1070, Boston, MA, June 1995. IEEE Computer Society Press.

67. Hartley R., Sturm P. Triangulation. Computer Vision and Image Understanding, 68 (2): P. 146-157, November 1997.

68. Hartley R.I., Zisserman A. Multiple View Geometry in Computer Vision. Cambridge University Press, ISBN: 0521623049, 2000.

69. Heikkila J., Silven O. A four-step camera calibration procedure with implicit image correction. Proc. IEEE Comput. Soc. Conf. Comput. Vision and Pattern Recogn., 1997.

70. Heikkila J. Geometric Camera Calibration Using Circular Control Points, IEEE Transactions of Pattern Analysis and Machine Intelligence, vol. 22, No 10, October 2000.

71. Intille S.S., Bobick A.F. Disparity-space images and large occlusion stereo. In Proc. of the 3rd European Conf. on Сотр. Vision, P. 179-186, Stockholm, Sweden, May 1994. Springer-Verlag.

72. Ishikawaand H., Geiger D. Occlusions, discontinuities, and epipolar lines in stereo. In Fifth European Conference on Computer Vision (ECCV'98), P. 332— 248, Freiburg, Germany, June 1998. Springer-Verlag.

73. Iyengar S.S., Jorgensen C.C., Rao S.V.N., Weisbin C.R. Robot Navigation Algorithms using Learned Spatial Graphs, Robotica, Vol. 4, P. 93-100,1986.

74. Jarvis R.A., Byrne J.C. Robot Navigation: Touching, Seeing and Knowing, Proceedings of 1st Australian Conference on Artificial Intelligence, November 1986.

75. Kambhampati S., Davis L.S. Multiresolution Path Planning for Mobile Robot, IEEE Journal of Robotics and Automation, Vol. RA-2 No. 3, P. 135-145, September 1986.

76. Kortenkamp D., Weymouth T. Topological mapping for mobile robots using a combination of sonar and vision sensing. In Proc. of the Twelfth National Conference on Articial Intelligence, P. 979-984,1994.

77. Kuan D.T., Zamiska J.C., Brooks R.A. Natural Decomposition of Free Space for Path Planning, Proceedings of IEEE International Conference on Robotics and Automation, P. 168-173, March 1985.

78. Langer D. A Behavior-based system for off-road navigation, IEEE Transactions on Robotics and Automation, vol. 10, no. 6, P. 776-783,1994.

79. Lee K.M., Kuo C.-C.J. Shape reconstruction from photometric stereo. IEEE Intl. Conf. Computer Vision, P. 479-484,1992.

80. Leonard J.J., Durrant-Whyte H.F., Cox I.J. Dynamic map building for an autonomous mobile robot. International Journal of Robotics Research, 11(4): P. 89-96,1992.

81. Lepetit V., Fua P. Monocular Model-Based 3D Tracking of Rigid Objects: A Survey, Foundation and Trends in Computer Graphics and Vision Vol. 1, No. 1 (2005) P. 1-89.

82. Lenser S., Veloso M. Visual sonar: Fast Obstacle Avoidance using Monocular Vision. In Proc. of the IEEE/RSJIROS 2003, Las Vegas, NV, October 2003.

83. Levitt T. S., Lawton D. T. Qualitative Navigation for Mobile Robots. Artificial Intelligence, 44: P. 305-360,1990.

84. Longuet-Higgins H. A computer algorithm for reconstructing a scene from two projections, Nature, 293: P. 133-135,1981.

85. Longuet-Higgins H. The reconstruction of a plane surface from two perspective projections," Proc. Royal Society London, vol. B227, P. 399^10,1986.

86. Lorigo L.M., Brooks R.A., Grimson W. E. L. Visually-Guided Obstacle Avoidance in Unstructured Environments. In Proc. of the IEEE/RSJ IROS 1997, P. 373-379,1997.

87. Lozano-Perez Т., Wesley M.A. An Algorithm for Planning Collision Free Paths among Polyhedral Obstacles, Communications of the ACM, Vol. 22 No. 10, P. 560-570, October 1979.

88. Lozano-Perez T. Spatial Planning: A Configuration Space Approach, IEEE Trans, on Computers, C-32 No. 2, P. 108-120, February 1983.

89. Lumelsky V.J., Stepanov A. A. Path Planning Strategies for a Point Mobile Automaton Moving Amidst Unknown Obstacles of Arbitrary Shape, Algorith-mica, Vol. 2, No. 4, P. 403-430, 1987.

90. Luong Q., Faugeras O. The fundamental matrix: theory, algorithms, and stability analysis, International Journal of Computer Vision, 17(1): P. 43-76, 1996.

91. Luong Q., Faugeras O. "Self-calibration of a Moving Camera from Point Correspondences and Fundamental Matrices, International Journal of Computer Vision, 1(1): P. 5-40,1997.

92. Mahajan A., Walworth M. 3D position sensing using the difference in the time-of-flights from a wave source to various receivers, IEEE Transactions on Robotics and Automation, vol. 17, no. 1, February 2001.

93. Maybank S. J., Faugeras O. A theory of self-calibration of a moving camera. The International Journal of Computer Vision, 8(2): P. 123-152, Aug. 1992.

94. Moravec H.P. Obstacle Avoidance and Navigation in the Real World by a Seeing Rover, PhD dissertation, Stanford University, September 1980.

95. Moravec H.P., Elfes A. High Resolution Maps from Wide Angle Sonar, Proceedings of IEEE International Conference on Robotics and Automation, P. 116-121, March 1985.

96. Neus M., Maouche S. Motion Planning using the Modified Visibility Graph, Proceedings of IEEE 1999 International Conference. 1999.

97. Newman P. On the Structure and Solution of the Simultaneous Localization and Map Building Problem. PhD thesis, Australian Centre for Field Robotics, University of Sydney, Sydney, Australia, 2000.

98. Ohta Y., Kanade T. Stereo by intra- and interscanline search using dynamic programming. IEEE Trans, on PAMI, 7(2): P. 139-154,1985.

99. Oommen B.J. Robot Navigation in Unknown Terrains Using Learned Visibility Graphs. Part I: The Disjoint Convex Obstacle Case, IEEE Journal of Robotics and Automation, Vol. RA-3, No. 6, December 1987.

100. Intel Corporation, (http://www.intel.com/technology/computing/opencv).

101. Papadimitriou C., Yannakakis M. Shortest paths without a map, Theoretical Computer Science, 84, P. 127 -150,1991.

102. Rao S.V.N., Iyengar S.S., Jorgensen C.C., Weisbin C.R. Robot Navigation in an Unexplored Terrain, Journal of Robotic Systems, Vol.3 No.4, P. 389-407, 1986.

103. Roy S., Cox I. J. A maximum-flow formulation of the n-camera stereo correspondence problem. In Sixth International Conference on Computer Vision (ICCV'98), P. 492-499, Bombay, January 1998.

104. Scharstein D., Szeliski R. Stereo matching with nonlinear diffusion. International Journal of Computer Vision, 28(2): P. 155-174, July 1998.

105. Scharstein D., Szeliski R. A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms, Technical Report MSR-TR-2001-81, November 2001.

106. Se S., Lowe D., Little J. Vision-based mobile robot localization and mapping using scale-invariant features. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), P. 2051-2058,2001.

107. Shatkay H. Learning Models for Robot Navigation. PhD thesis, Computer Science Department, Brown University, Providence, Rl, 1998.

108. Sim R., Dudek G. Learning and evaluating visual features for pose estimation. In ICCV, P. 1217-1222,1999.

109. Simmons R., Koenig S. Probabilistic robot navigation in partially observable environments. In Proc. International Joint Conference on Artificial Intelligence, 1995.

110. Stein G. Accurate internal camera calibration using rotation, with analysis of sources of error. In Proc. Fifth International Conference on Computer Vision, P. 230-236, Cambridge, Massachusetts, June 1995.

111. Middlebury Stereo Vision, (http://www.middlebury.edu/stereo).

112. Strecha C., Van Gool L. J. Motion-stereo integration for depth estimation. In ECCV, volume 2, P. 170-185,2002.

113. Sun C. Fast stereo matching using rectangular subregioning and 3d maximum-surface techniques. Int. J. Comput. Vision, 47(1-3): P. 99-117,2002.

114. Szeliski R., Zabih R. An Experimental Comparison of Stereo Algorithms & Vision Algorithms: Theory and Practice", B. Triggs, A. Zisserman, and R. Szeliski, eds., pp. 1-19, Sept. 1999.

115. Szeliski R. Prediction error as a quality metric for motion and stereo. In Seventh International Conference on Computer Vision (ICCV'99), P. 781-788, Kerkyra, Greece, September 1999.

116. Thrun S., Burgard W., Fox D. A real-time algorithm for mobile robot mapping with applications to multi-robot and 3D mapping. In Proceedings of the

117. EE International Conference on Robotics and Automation (ICRA), San Francisco, CA, 2000.

118. Thrun S. An online mapping algorithm for teams of mobile robots. Int. J. Robotics Research 20 (2001) P. 335-363.

119. Thrun S. Mapping: A survey. Technical Report CMU-CS-02-111, Carnegie Mellon University, 2002.

120. Thrun S. An Approach to learning Mobile Robot Navigation, Robotics and Autonomous Systems, P. 301-319,1995.

121. Triggs В., Zisserman A., Szeliski R. Vision algorithms, theory and practice: International Workshop on Vision. Springer-Verlag (1999).

122. Trucco E., Verri A. Introductory Techniques for 3-D Computer Vision. Prentice Hill, Upper Saddle River, 1998.

123. Ulrich I., Borenstein J. VFH: Local Obstacle Avoidance with Look-ahead Verification. In Proc. of the 2000 IEEE International Conference on Robotics and Automation, P. 2505-2511, San Fransisco, CA, April 2000.

124. Veksler O. Efficient Graph-based Energy Minimization Methods in Computer Vision. PhD thesis, Cornell University, Ithaca, NY, August 1999.

125. Weng J., Huang Т., Ahuja N. Motion and Structure from Two Perspective Views: Algorithms, Error Analysis, and Error Estimation, IEEE Trans. On PAMI, 11(5): P. 451-476, May 1989.

126. Weng J., Cohen P., Herniou M. Camera calibration with distortion models and accuracy evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(10): P. 965-980, Oct. 1992.

127. Wie G., Ma S. A complete two-plane camera calibration method and experimental comparisons. In Proc. Fourth International Conference on Computer Vision, P. 439-446, Berlin, May 1993.

128. Wie G., Ma S. Implicit and explicit camera calibration: Theory and experiments. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5): P. 469-480,1994.

129. Winters N., Santo-Victor J. Mobile robot navigation using omnidirectional vision. InProc. 3rdlrish Machine Vision and Image Processing Conference (IMVIP'99), 1999.

130. Wixson L. E. Detecting occluding edges without computing dense correspondence. In Proceedings of the DARPA Image Understanding Workshop, 1993.

131. Wolberg G., Pavlidis T. Restoration of binary images using stochastic relaxation with annealing. Pattern Recognition Letters, 3: P. 375-388,1985.

132. Ye C., Wang D.W. A novel navigation method for autonomous mobile robots, Journal of Intelligent and Robotic Systems, vol. 32, no. 4, P. 361-388,2001.

133. Young S., Scanion M. Robotic vehicle uses acoustic array for detection and localization in urban environments, Proceedings of the 2001 SPIE Unmanned Ground Vehicle Technology III, P. 147-158, (Orlando, USA), April 2001.

134. Zhang Z. A Flexible New Technique for Camera Calibration, Technical Report MSR-TR-98-71,1998.

135. Zelinsky A. Environment Exploration and Path Planning Algorithms for a Mobile Robot using Sonar", PhD dissertation, University of Wollongong, Department of Computer Science, October 1991.

136. Zhang Z., Faugeras О. A 3d world model builder with a mobile robot. International Journal of Robotics Research, 11(4): P. 269-285,1992.

137. Zhang Z. Motion and structure from two perspective views: From essential parameters to euclidean motion via fundamental matrix. Journal of the Optical Society of America A, 14(11): P. 2938-2950,1997.

138. Zhang Z. Flexible camera calibration by viewing a plane from unknown orientations. Int. Conf. on Computer Vision, 1999.

139. Zitnick C., Kanade T. A cooperative algorithm for stereo matching and occlusion detection. Technical Report CMU-RI-TR-99-35, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, October 1999.