Методы комбинаторной виртуализации для мобильных роботов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Горбенко, Анна Андреевна

• Горбенко, Анна Андреевна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Горбенко, Анна Андреевна

Оглавление

Введение

Глава 1. Система обработки моторных примитивов

1.1 Математическая модель системы обработки примитивов

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

1.3 Экспериментальные исследования для метода комбинаторной виртуализации системы обработки моторных примитивов

Глава 2. Визуальная система навигации

2.1 Проблема построения панорамного изображения

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

2.1.2 Экспериментальные исследования для метода комбинаторной виртуализации построения

панорамного изображения

2.2 Проблема выбора конкретного множества дорожных знаков

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

2.2.2 Экспериментальные исследования для метода комбинаторной виртуализации выбора

множества дорожных знаков

2.3 Проблема совмещения дорожных знаков на

различных изображениях

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

на различных изображениях

2.3.2 Экспериментальные исследования для метода комбинаторной виртуализации совмещения

дорожных знаков на различных изображениях

Глава 3. Система распознавания изображений

3.1 Оптимизация множества алгоритмов распознавания

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

алгоритмов распознавания

и

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

Глава 4. Программный комплекс

4.1 Система алгоритмов

4.1.1 Обучение на одном примере с помощью имитации

4.1.2 Бортовой ЭАТ-решатель

4.1.3 Система безопасного планирования

4.1.4 Алгоритм самообучения распознаванию объектов

4.2 Исследовательские роботы

4.3 Общее описание программного обеспечения

4.4 Общее тестирование программного обеспечения робота

Заключение

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

Список иллюстративного материала

Введение диссертации (часть автореферата) на тему «Методы комбинаторной виртуализации для мобильных роботов»

Введение

Актуальность темы. Исследование различных вопросов разработки математических моделей, вычислительных методов и алгоритмов для робототехниче-ских систем относится к одному из наиболее актуальных направлений современной математики [5,6,10,12,13,15,117]. Особенно интенсивно в последние годы развивается проблематика, связанная с мобильными роботами [39,45,95,102].

Виртуализация — это общий подход, заключающийся в использовании некоторых методов абстрактного рассмотрения ресурсов. Наиболее интенсивно различные методы виртуализации применяются в программировании (см., например, [24,29,94,159]). Использование виртуализации позволяет выносить связи с конкретными ресурсами за рамки программного, программно-аппаратного или аппаратного комплекса, что делает соответствующий комплекс существенно более универсальным.

Следует отметить, что развитие технологий создания программного обеспечения и соответствующих математических моделей для робототехнических систем во многом повторяет аналогичные процессы для компьютерных систем. Однако эти процессы для роботов на сегодняшний день находятся на существенно более ранней стадии, чем для компьютерных систем (см., например, [22,86,96,139]). Сегодня для роботов нет аналогов ОС Microsoft Windows или ОС Linux. Во многом это обусловлено тем, что в робототехнике математические модели виртуализации разработаны пока очень слабо. Кроме того, робототехника выдвигает значительно большие требования к виртуализации, чем компьютерные системы. В частности, в робототехнике виртуализация необходима не только на уровне чисто вычислительных процессов, но и для мехатрони-ки, сенсорики. Процессы взаимодействия между устройствами, с окружением и пользователями для роботов существенно более сложны и многогранны, чем для компьютерных систем. Несмотря на существенное отставание от компьютерных систем, в робототехнике уже довольно давно считается общепринятой необходимость использования абстрактных понятий и применения некоторых методов виртуализации при разработке комплексного программного обеспечения [84].

Степень разработанности темы. В последние годы при построении различных математических моделей для робототехнических систем появился интерес к использованию закономерностей из области комбинаторики слов. Поиск наибольшей общей подпоследовательности применяется в техническом зрении для склеивания результатов трехмерного лазерного сканирования [121]; в алгоритмах визуальной навигации мобильных роботов для уменьшения неопределенности при мониторинге особенностей [19]; в алгоритмах лазерной навигации мобильных роботов для локализации на карте [16]; при эволюционировании архитектуры системы управления робота [75]; при обучении робота-графопостроителя в качестве меры подобия траекторий [127]; в обучении роботов на уровне задач для обобщения опыта [119]. Модифицированный вариант наибольшей общей подпоследовательности используется в техническом зрении для представления действий траекториями [23,125,164]. Поиск разделяющих подпоследовательностей используется мобильными роботами при распознавании звуковых сигналов [123]. Следует отмстить, что различные иерархические

модели обучения уже давно исследуются в теории искусственного интеллекта. Среди таких моделей можно отметить избирательные модели, параллельные, последовательные, неупорядоченные [124]. Однако в робототехнике иерархические методы стали применять сравнительно недавно. В частности, можно отметить робототехнические симуляторы [37,38], реализации для реальных роботов [35, 36, 91] и программное обеспечение [145] для гуманоидных роботов NAO1 и iCub2. В работе [168] предложен метод иерархического обучения движению гуманоидного робота, основанный на поиске для строки, представляющей собой последовательность действий, минимального покрытия без пересечений подсловами из известного множества. В работе [56] рассмотрен сравнительный анализ трех различных алгоритмов сравнения строк с точки зрения их эффективности при решении задачи локализации робота, использующего визуальную систему навигации по дорожным знакам. В работах [137,138] для строк, представляющих описание траекторий мобильных роботов, рассмотрены мера близости, предложенная в [82], расстояния Хэмминга и Левенштейна, а также кросс-корреляционная мера близости.

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

Несмотря на очевидные преимущества, которые может дать комбинаторная виртуализация в робототехнике, на сегодняшний день существенным препятствием для активного использования этого метода в робототехнике является то, что большинство задач поиска комбинаторных закономерностей относится к классу вычислительно трудных проблем. В частности, в работе [121] применяются наибольшие общие подпоследовательности множества строк. Проблема нахождения наибольшей общей подпоследовательности множества строк является NP-трудной. В работе [121] для ее решения предлагается применять полный перебор (brute force) [154]. В работе [125] при сравнении двух множеств строк рассматриваются наибольшие общие подпоследовательности только пар строк. При эволюционировании архитектуры системы управления робота [75] для измерения генетической конвергенции популяции применяется поиск наибольшей общей подпоследовательности двух случайным образом выбранных генотипов, хотя очевидно, что рассмотрение некоторых множеств генотипов было бы более информативно. Используемая при локализации на карте [16] наибольшая общая подпоследовательность двух строк, представляющих результаты сканирования, дает недостаточно точные результаты, что заставляет применять

1Aldebaran Robotics. URL: http://www.aldebaran-robotics.com/en/

2iCub. URL: http://www.icub.org/

систему из двух дополнительных фильтров. При обучении роботов на уровне задач для обобщения опыта необходимость использования более сложной комбинаторной модели, чем наибольшая общая подпоследовательность двух строк, применявшаяся в [119], отмечена, например, в [42]. В работе [168] не рассматривается возможность изменения последовательности действий. Это, вообще говоря, приводит к факториальному замедлению процесса обучения. Однако рассмотрение возможности изменения последовательности действий потребует решения NP-трудной задачи поиска минимального разбиения множества на подмножества.

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

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

Проблема выполнимости (SAT):

Дано: Булева функция f(xь ..., хп).

вопрос: Существуют ли значения Xi,..., хп такие, что f(xь ..., хп) = 1?

Проблема SAT является ключевой задачей в математической логике и теории вычислений. Доказательство NP-полноты этой проблемы было дано С. Куком в 1971 году [33]. До этого времени понятия NP-полных проблем еще не существовало. На практике проблема выполнимости является основополагающей в решении многих задач в теории автоматического доказательства, системах автоматизированного проектирования, автоматизированном производстве, машинном зрении, теории баз данных, робототехнике, разработке интегральных схем, разработке архитектур компьютеров, разработке компьютерных сетей. Проблема SAT является наиболее изученной NP-полной проблемой [69,97]. Часто SAT рассматривается для булевых функций в конъюнктивной нормальной форме (КНФ). Особенно интенсивно изучается важный частный случай SAT, относящийся к булевым функциям в конъюнктивной нормальной форме, в которой каждая дизъюнкция содержит ровно 3 переменных или их отрицания (3-КНФ).

Проблема 3-выполнимости (3SAT):

дано: Булева функция f(xi,... ,жп) в 3-КНФ.

Вопрос: Существуют ли значения ..., хп такие, что f(xь ..., хп) = 1?

Отметим, что как и SAT, проблема 3SAT является NP-полпой [126].

Для SAT разработано много высокоэффективных алгоритмов [69], которые обычно называют SAT-решателями. В частности, разработано много методов оптимизации, параллельных и эвристических алгоритмов (см., например, [69]). Предложено несколько генетических алгоритмов [46,74,92,165]. Также рассмотрены гибридные алгоритмы, в которых подход генетических алгоритмов комбинирован с алгоритмами локального поиска [73]. Современные решатели для

SAT в основном разработаны для булевых функций в КНФ. В частности, для решения задачи выполнимости в КНФ успешно применялись методы стохастического локального поиска. В последнее время решатели, работающие с произвольными булевыми функциями, показали, что существуют преимущества при решении пропозициональной проблемы выполнимости в более выразительном естественном представлении, поскольку преобразование формулы в КНФ может привести к потере структуры проблемы и появлению значительно большего количества переменных для кодирования задачи. Решатели, использущие КНФ, могут проигрывать на проблемах, для которых более естественно кодирование произвольной пропозициональной формулой. Представление формулы в виде КНФ может экспоненциально увеличить размер формулы или значительно уменьшить эффективность использования булевых функций вообще. Перевод может привести к появлению множества новых переменных, которые увеличивают размер пространства поиска решателя. Отметим, что имеется и существенный интерес к разработке алгоритмов, которые способны работать не только с конъюнктами (см., например, [116,149]). Сравнительно высокую эффективность показывают алгоритмы, основанные только на локальном поиске. Конечно, данные алгоритмы в худшем случае требуют экспоненциального времени. Но на основании экспериментальных данных они могут относительно быстро получить решения для большинства булевых функций. Отметим, что у возможности быстро решать NP-полные проблемы есть и теоретическое обоснование, связанное с невозможностью для 3SAT доказательства NP-полноты в среднем относительно естественного сведения [32,70].

Наличие большого количества эффективных SAT-решателей делает естественным использование сведения к различным версиям проблемы выполнимости для решения вычислительно трудных задач. В последнее время большой интерес вызвало кодирование задач проблемой выполнимости и их решение высокоэффективными алгоритмами, разработанными для задачи выполнимости. В частности, алгоритмы локального поиска дали впечатляющие результаты для многих задач. Например, существует несколько вариантов SAT-кодирования проблемы CSP3, клики, задачи планирования и раскраски графов. Задачи нахождения максимального разреза, вершинного покрытия и максимального независимого множества могут быть сведены к MAX-2-SAT4. Существует ряд явных сведений задачи нахождения гамильтонова пути к проблеме 3SAT.

Если существует полиномиальный алгоритм F, который трансформирует произвольные начальные данные х проблемы А б NP в начальные данные F(x) проблемы В € NP так, что для F(x) существует вычисление, возвращающее 1, тогда и только тогда, когда для х существует вычисление, возвращающее 1, то говорят, что проблема А полиномиально сводима к проблеме 5, и пишут А ос В (см. [93]). Если проблема В является NP-полной, то А ос В для любой проблемы В € NP. Поэтому наличие некоторого эффективного алгоритма для решения NP-полпой проблемы означает существование эффективного алгоритма для произвольной проблемы из класса NP (см. [2]). Однако выполнимость соотношения A ос 3SAT сама по себе дает лишь теоретическую возможность использования алгоритмов для 3SAT при решении проблемы А.

3Constraint satisfaction problem

4 Maximum 2-satisfiability problem

Более того, хотя конструктивное доказательство теоремы Кука (см. [126]) даст явное сведение произвольной проблемы из класса NP к SAT, оно требует, чтобы исходная проблема была задана машиной Тьюринга. Поэтому его сложно использовать на практике, поскольку проблемы, которые необходимо решать, редко бывают заданы машиной Тьюринга. Для практического использования алгоритмов для 3SAT при решении некоторой проблемы А нам необходимо не только соотношение А ос 3SAT, но и подтверждение этого соотношения в виде конструктивного полиномиального алгоритма, позволяющего строить в явном виде исходные данные 3SAT по исходным данным А. Такое сведение с подтверждением называется конструктивным полиномиальным сведением [31]. Для обозначения отношения конструктивной полиномиальной сводимости мы будем использовать символ осс. Следует отметить, что для использования конструктивного полиномиального сведения в качестве математического понятия, а не фразеологизма, необходима строгая формализация (см. [31]). Поэтому понятие конструктивного полиномиального сведения, следуя [31], мы будем рассматривать в рамках вычислительной логики предикатов С PL (computational predicate logic), удовлетворяющей системе аксиом Гейтинга [80]. Заметим, что конструктивное полиномиальное сведение проблемы А к проблеме В в качестве теоремы должно быть выводимо не в классической логике, а в логике С PL. Поэтому, используя стандартный в таких случаях формализм (см., например, [7]), конструктивное полиномиальное сведение проблемы А к проблеме В мы в дальнейшем будем обозначать С PL h А осс В. Поскольку для проблемы 3SAT известно большое количество эффективных алгоритмов [97], установление С PL h А схс 3SAT может рассматриваться как эффективное решение проблемы А. Однако для практического использования некоторой комбинаторной проблемы А в робототехнике получения утверждения С PL Ь А осс 3SAT недостаточно. Необходимо для данного сведения С PL 1- А осс 3SAT найти решатель, который будет демонстрировать высокую эффективность на робо-тотехнических данных с использованием вычислительных возможностей, которые доступны робототехническому комплексу. Более того, робототехническим комплексам, кроме решения той или иной комбинаторной проблемы, одновременно необходимо решать и ряд других задач. Поэтому решатель должен быть тем или иным образом интегрирован в общую вычислительную систему робота. Естественно возникает вопрос о разработке некоторого общего метода комбинаторной виртуализации для современных роботов, который включал бы в себя математические модели, вычислительные методы и общие подходы к созданию программного комплекса, обеспечивающие эффективное решение вычислительно трудных комбинаторных проблем.

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

бототсхники отражены в государственных программах многих ведущих держав5'6'7'8'9,10 — США, ЕС, Японии, Китая, Южной Кореи — и программных документах крупнейших робототехнических организаций — RIA11, IFR12. Эти документы позволяют достаточно четко очертить как задачи в области создания самих роботов, так и задачи, связанные с системами управления роботов. Большинство сервисных роботов — это устройства, рассчитанные на массовое внедрение. Они должны быть сравнительно простыми и дешевыми, обладать минимальным набором сенсоров и сравнительно скромными вычислительными ресурсами. Однако в большинстве случаев можно предполагать, что сервисный робот имеет возможность подключения к внешним вычислительным ресурсам. При этом во многих случаях внешние вычислительные ресурсы могут быть весьма значительными (кластеры, суперкомпьтеры, сети суперкомпьютеров).

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

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

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

• визуальная система навигации;

• система распознавания изображений.

Исследование метода комбинаторной виртуализации для мобильного робота с одним визуальным сенсором естественным образом разбивается на разработку

5National Robotics Initiative (NRI). The realization of co-robots acting in direct support of individuals and groups, USA, 2014. URL: http://www.nsf.gov/pubs/2014/nsfl4500/nsfl4500.htm (дата обращения 04.04.2014)

6Robotic visions to 2020 and beyond. The strategic research agenda for robotics in Europe, 2009. URL: http://robotics.h2214467.stratoserver.net/cms/upload/SRA/2010-06_SRA_A4_low.pdf (дата обращения 04.04.2014)

7ATIP14.002: Development of intelligent service robots in China, 2014. URL: http://www.atip.org/atip-publications/atip-reports/2014/8263-atipl4-002-development-of-intelligcnt-scrvicc-robots-in-china.html (дата обращения 04.04.2014)

8Robotics and autonomous systems industry. Final report. National Defense University, USA, 2011. URL: http://www.technologyroadmaps.com/icaf-is-report-robotics-autonomous-systems-2011.pdf (дата обращения 04.04.2014)

9URL: http://robotics .snu.ac.kr/upfiles/papers/Robotics%20in%20Korea.pdf (дата обращения: 04.04.2014)

10URL: http://www.nsftokyo.org/rm06-06.pdf (дата обращения 04.04.2014)

11Robotic Industries Association. URL: http://www.robotics.org/

12Internationa 1 Federation of Robotics. URL: http://www.ifr.org/

соответствующих методов для трех его основных систем.

Отмстим, что рассмотрение мобильного робота с одним визуальным сенсором является типичным для робототехнических исследований. В частности, как роботы с одним визуальным сенсором можно рассматривать исследовательские роботы Nomad13, Rovio14, Khepera15, Pioneer16, Scout,17 и т.д. Кроме того, можно отметить ряд серийных роботов (см., например, iClebo Arte18, Roomba19, Neato20), которые также могут быть рассмотрены как мобильная платформа с одним визуальным сенсором для проведения исследований.

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

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

13Общее описание, URL: http://www.ida.liu.se/cxt/robocup/middle/Dutch-Team/paper.html. Пример применения: Chopra A., Obsniuk М., Jenkin М. The Nomad 200 and the Nomad SuperScout: reverse engineered and rcsurrcctcd // Proceedings of the 3rd Canadian conference on computer and robot vision. -2006. -P.55.

14Общее описание, URL: http://www.wowwee.com/en/support/rovio. Пример применения: Lera F., Garcia J., Fernández С., Matellán V. Augmented reality to improve teleoperation of mobile robots // Proceedings of the XII Workshop de Agentes Físicos. -2011. P.105-110. Отметим, что в этой статье дан обзор роботов-телеприсутствия, каждый из которых с точки зрения навигации является мобильным роботом с одним визуальным сенсором.

15Общсе описание, URL: http://www.k-team.com/mobile-robotics-products. Пример применения: Siegwart R., Saucy P. Interacting mobile robots on the web // Proceedings of the IEEE International conference on robotics and automation. -Piscataway: IEEE Press, 1999. и Burlacu A., Mihai 0., Tiganas V. An image based visual servoing scheme for wheeled mobile robots // Proceedings of the 15th international conference on system theory, control, and computing. — Piscataway: IEEE Press, 2011. -P.l-5.

16Общее описание, URL: http://www.mobilerobots.com/ResearchRobots.aspx. Пример применения: Salim A., Fuentes O., Muñoz A. Development of local vision-based behaviors for a robotic soccer player // Proceedings of the 5th Mexican international conference in computer science. -Piscataway: IEEE Press, 2004. -P.275-281.

17Общее описание, URL: http://distrob.cs.umn.edu/scout.php. Пример применения: Rybski P., Stoeter S., Gini M., Hougcn D., Papanikolopoulos N. Performance of a distributed robotic system using shared communications channels // IEEE transactions on robotics and automation. -2002. -V.18, N.5. -P.713-727.

18URL: http://iclebo.com.ru

19URL: www.irobot.ru

20URL: www.neatorobotics.com

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

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

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

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

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

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

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

достоверность и обоснованность, полученных в диссертации результатов, подтверждена вычислительными и робототехническими экспериментами. Апробация работы. Результаты диссертации были представлены на следующих конференциях: 9-я Международная конференция "Высокопроизводительные параллельные вычисления на кластерных системах" (Владимир, 2009 г.); Межвузовская научная конференция по проблемам информатики "СПИСОК -2009" (Екатеринбург, 2009 г.); Итоговая конференция XIV областного конкурса научно-исследовательских работ студентов учреждений высшего и среднего профессионального образования Свердловской области (НИРС) "Научный Олимп" (Екатеринбург, 2011 г.); 42-ая Всероссийская молодежная конференция "Современные проблемы математики" (Екатеринбург, 2011г.); The 4th International Conference on Advanced Computer Control (Shanghai, China, 2012); Научно-технический семинар "Робототехника и безлюдные технологии. Перспективы развития и возможности УрФУ"(Екатеринбург, 2013); The 2nd International Conference on Machine Design and Manufacturing Engineering (Jeju Island, South Korea, 2013); The 3rd International Conference on Computer-Aided Design, Manufacturing, Modeling and Simulation (Chongqing, China, 2013); The 11th International Conference of Numerical Analysis and Applied Mathematics (Rhodes, Greece, 2013); The 3rd International Conference on Advanced Materials and Engineering Materials (Singapore, 2013). Также результаты диссертации регулярно докладывались на научном семинаре отдела интеллектуальных систем и робототехники РУНЦ "Интеллектуальные системы и информационная безопасность" института математики и компьютерных наук УрФУ. Результаты были представлены на Уральской международной выставке и форуме промышленности и инноваций ИННОПРОМ-2010 и третьей международной выставке и форуме промышленности и инноваций ИННОПРОМ-2012. Публикации. По теме диссертации опубликовано 13 научных работ (см. [178]

Список литературы диссертационного исследования кандидат наук Горбенко, Анна Андреевна, 2014 год

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

Гасфилд Д. Строки, деревья и последовательности в алгоритмах / Д. Гас-филд. -СПб.: Невский Диалект, 2003. -654 с.

Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. -М.: Мир, 1982. -419 с.

Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. Проблемы кибернетики / Ю.И. Журавлев. - М.: Наука, 1978. -33 вып. -С.5 -68.

Журавлев Ю.И. Распознавание образов и распознавание изображений / Ю.И. Журавлев, И.Б. Гуревич // Ежегодник "Распознавание. Классификация. Прогноз. Математические методы и их применение". -М.: Наука, 1989. -2 вып. -С.5 -72.

Игнатьев М.Б. Алгоритмы управления роботами-манипуляторами / М.Б. Игнатьев, Ф.М. Кулаков, A.M. Покровский. -Л.Машиностроение, 1972. -248 с.

Каляев И.А. Модели и алгоритмы коллективного управления в группах роботов / И.А. Каляев, А.Р. Гайдук, С.Г. Капустян. -М.: ФИЗМАТЛИТ, 2009. -280 с.

Кейслер Г. Теория моделей / Г. Кейслер, Ч. Чэн. -М.: Мир, 1977. -616 с.

Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов / В.И. Левенштейн // Доклады Академий Наук СССР. -1965. -Т. 163, Ш. -С.845 -848.

Окуловский Ю.С. Программный комплекс обеспечения интеллектуальных вычислений: дис. ... канд. физ.-мат. наук: 05.13.18 / Окуловский Юрий Сергеевич. -Екатеринбург: Издательство уральского государственного университета, 2009. -111 с.

Попов Э.В. Алгоритмические основы интеллектуальных роботов и искусственного интеллекта / Э.В. Попов, Г.Р. Фирдман. -М.: Наука, 1976. -455 с.

Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилиньский, Л. Рутковский. -М.: Горячая линия — Телеком, 2006. -452 с.

Тимофеев A.B. Адаптивные робототехнические комплексы / A.B. Тимофеев. -Л.: Машиностроение, 1988. -320 с.

Тимофеев A.B. Роботы и искусственный интеллект / A.B. Тимофеев. -М.: Наука, 1978. -190 с.

Хайкин С. Нейронные сети: полный курс, 2-е издание / С. Хайкин. — М.:Вильямс, 2006. -1104 с.

[15] Черноусько Ф. J1. Манипуляционные роботы: динамика, управление, оптимизация / Ф.Л. Черноусько, Н.Н. Болотник, В.Г. Градецкий. -М.: Наука, 1989. -368 с.

[16] Adluru N. Robot mapping for rescue robots / N. Adluru, L. Latccki, R. Lakaemper, R. Madhavan // CD proceedings of IEEE international workshop on safety, security and rescue robotics, 2006. [Электронный ресурс]. URL: http://www.cis.temple.edu/~latecki/Papers/SSRR2006print.pdf (дата обращения: 04.04.2014)

[17] Andrcopoulos A. 50 Years of object recognition: directions forward / A. Andreopoulos, J. Tsotsos // Computer vision and image understanding. -2013. -V.117, N.8. -P.827 -891.

[18] Argall B. A survey of robot learning from demonstration / B. Argall, S. Chernova, M. Veloso, B. Browning // Robotics and autonomous systems. -2009. -V.57, N.5. -P.469 -483.

[19] Argyros A. Robot homing by exploiting panoramic vision / A. Argyros, K. Bekris, S. Orphanoudakis, L. Kavraki // Autonomous robots. -2005. -V.19, N.l. -P.7 -25.

[20] Bookstein F. Principal warps: thin-plate splines and the decomposition of deformations / F. Bookstein // IEEE transactions on pattern analysis and machine intelligence. -1989. -V.ll, N.6. -P.567 -585.

[21] Brown M. Automatic panoramic image stitching using invariant features / M. Brown, D. Lowe // International journal of computer vision. -2007. -V.74, N.l. -P.59 -73.

[22] Brown M. The virtual node layer: a programming abstraction for wireless sensor networks / M. Brown, S. Gilbert, N. Lynch, C. Newport, T. Nolte, M. Spindel // ACM SIGBED review. -2007. -V.4, N.3. -P.7 -12.

[23] Buzan D. Extraction and clustering of motion trajectories in video / D. Buzan, S. Sclaroff, G. Kollios // Proceedings of the 17th international conference on pattern recognition. -Piscataway: IEEE CS Press, 2004. -V.2. -P.521 -524.

[24] Campbell S. Applied virtualization technology / S. Campbell, M. Jeronimo. -Hillsboro: Intel Press, 2006. -266 p.

[25] Cardoso I. Noise tolerance in a ncocognitron-like network / I. Cardoso, A. Wichert // Neural networks. -2014. -V.49. -P.32 -38.

[26] Cartwright B. Landmark learning in bees / B. Cartwright, T. Collett // Journal of comparative physiology A: neuroethology, sensory, neural,behavioral physiology. -1983. -V.151, N.4. -P.521 -543.

[27] Cartwright B. Landmark maps for honeybees / B. Cartwright, T. Collett // Biological cybernetics. -1987. -V.57, N.l-2. -P.85 -93.

[28] Choset H. Topology in motion planning / H. Choset, A. Rizzi // Springer tracts in advanced robotics. -2005. -V.15. -P.90 -99.

[29] Chowdhury N. A survey of network virtualization / N. Chowdhury, R. Boutaba // Computer networks. -2010. -V.54, N.5. -P.862 -876.

[30] Cintra M. A study on techniques for the automatic generation of membership functions for pattern recognition / M. Cintra, H. Camargo, M. Monard // CD proceedings of the III congresso da academia trinacional de ciencias, 2008. [Электронный ресурс]. URL: http://www.labic.icmc.usp.br/pub/mcmonard/CintraC3N08.pdf (дата обращения: 04.04.2014)

[31] Constable R. Formalizing decidability theorems about automata / R. Constable // Computational logic. NATO ASI Series. Series F: computer and systems sciences. -1999. -V.165. -P.179 -213.

[32] Cook S. Finding hard instances of the satis ability problem: a survey / S. Cook, D. Mitchell // DIM ACS series in discrete mathematics and theoretical computer science. -1997. -V.35. -P.l -16.

[33] Cook S. The complexity of theorem proving procedures / S. Cook // Proceedings of the 3rd annual ACM symposium on theory of computing. -New York: ACM, 1971. -P. 151 -158.

[34] Dayan P. Using expectation-maximization for reinforcement learning / P. Dayan, G. Hinton // Neural computation. -1997. -V.9, N.2. -P.271 -278.

[35] Demiris Y. Content-based control of goal-directed attention during human action perception / Y. Demiris, B. Khadhouri // Interaction studies. -2008. -V.9, N.2. -P.353 -376.

[36] Demiris Y. Distributed, predictive perception of actions: a biologically inspired robotics architecture for imitation and learning / Y. Demiris, M. Johnson // Connection science. -2003. -V.15, N.4. -P.231 -243.

[37] Demiris Y. Imitation as a dual-route process featuring predictive and learning components: a biologically-plausible computational model / Y. Demiris, G. Hayes // Imitation in animals and artifacts. Cambridge: MIT Press, 2002. -P. 327 -361.

[38] Demiris Y. Movement imitation mechanisms in robots and humans. PhD thesis, University of Edinburgh, 1999. -99 p.

[39] Dudek G. Computational principles of mobile robotics / G. Dudek, M. Jenkin. -Cambridge: Cambridge University Press, 2010. -381 p.

[40] Efe M. A comparative study of neural network structures in identification of nonlinear systems / M. Efe and O. Kaynak // Mechatronics. -1999. -V.9, N.l. -P.287 -300.

[41] Efe M. A comparative study of soft-computing methodologies in identification of robotic manipulators / M. Efe and O. Kaynak // Robotics and autonomous systems. -2000. -V.30, N.3. -P.221 -230.

[42] Ekvall S. Robot learning from demonstration: a task-level planning approach / S. Ekvall, D. Kragic // International journal of advanced robotic systems. -2008. -V.5, N.3. -P.223 -234.

[43] Elmogy M. Landmark manipulation system for mobile robot navigation / M. Elmogy // Proceedings of the 2010 international conference on computer engineering and systems. -Piscataway: IEEE Press, 2010. -P.120 -125.

[44] Farber M. Topology of robot motion planning / M. Farber // NATO science series II: mathematics, physics and chemistry. -2006. -V.217. -P. 185 -230.

[45] Fernández-Madrigal J. Simultaneous localization and mapping for mobile robots: introduction and methods / J.-A. Fernández-Madrigal, J. Claraco. -Hershey: IGI Global, 2012. -497 p.

[46] Fleurent C. Genetic and hybrid algorithms for graph coloring / C. Fleurent, J. Ferland // Annals of operations research. -1996. -V.63, N.3. -P.437 -461.

[47] Fomcna R. Coarsely calibrated visual servoing of a mobile robot using a catadioptric vision system / R. Fomena, H. Yoon, A. Cherubini, F. Chaumette, S. Hutchinson // Proceedings of the 2009 IEEE/RSJ international conference on intelligent robots and systems. -Piscataway: IEEE Press, 2009. -P.5432 -5437.

[48] Frances M. On covering problems of codes / M. Frances, A. Litman // Theory of computing systems. -1997. -V.30, N.2. -P.113 -119.

[49] Fukushima K. Artificial vision by multi-layered neural networks: neocognitron and its advances / K. Fukushima // Neural networks. -2013. -V.37. -P. 103 -119.

[50] Fukushima K. Neocognitron: a self-organizing neural network model for a mechanism of pattern recognition unaffected shift in position / K. Fukushima // Biological cybernetics. -1980. -V.36, N.4. -P. 193 -202.

[51] Gan Z. Visual sensing and its applications. Integration of laser sensors to industrial robots / Z. Gan, Q. Tang. -Berlin: Springer, 2011. -259 p.

[52] Gent I. Towards an understanding of hill-climbing procedures for SAT / I. Gent, T. Walsh // Proceedings of the 11th national conference on artificial intelligence. -Cambridge: MIT Press, 1993. -P.28 -33.

[53] Gerbush M. Approximating minimum reset sequences / M. Gerbush, B. Heeringa // Lecture notes in computer science. -2011. -V.6482. -P.154 -162.

[54] Goedeme T. Robust vision-only mobile robot navigation with topological maps / T. Goedeme, L. Van Gool // Motion planning. -Rijeka: InTech, 2008. -Chapter 4. -P.63 -88.

[55] Goedeme T. Vision-based intelligent wheel chair control: the role of vision and inertial sensing in topological navigation / T. Goedeme, M. Nuttin, T. Tuytelaars, L. Van Gool // Journal of robotic systems. -2004. -V.21, N.2. -P.85 -94.

[56] Gonzalez-Buesa C. Solving the mobile robot localization problem using string matching algorithms / C. Gonzalez-Buesa, J. Campos // Proceedings of the 2004 IEEE/RSJ international conference on intelligent robots and systems. -Piscataway: IEEE Press, 2004. -V.3. -P.2475 -2480.

[57] Gorbenko A. A real-world experiments setup for investigations of the problem of visual landmarks selection for mobile robots / A. Gorbenko, V. Popov // Applied mathematical sciences. -2012. -V.6, N.96. -P.4767 -4771.

[58] Gorbenko A. Computational experiments for the problem of selection of a minimal set of visual landmarks / A. Gorbenko, V. Popov // Applied mathematical sciences. -2012. -V.6, N.116. -P.5775 -5780.

[59] Gorbenko A. Hamiltonian alternating cycles with fixed number of color appearances / A. Gorbenko, V. Popov // Applied mathematical sciences. -2012. -V.6, N.135. -P.6729 -6731.

[60] Gorbenko A. On the problem of placement of visual landmarks / A. Gorbenko, V. Popov // Applied mathematical sciences. -2012. -V.6, N.14. -P.689 -696.

[61] Gorbenko A. SAT solvers for the problem of sensor placement / A. Gorbenko, V. Popov // Advanced studies in theoretical physics. -2012. -V.6, N.25. -P.1235 -1238.

[62] Gorbenko A. Task-resource scheduling problem / A. Gorbenko, V. Popov // International journal of automation and computing. -2012. -V.9, N.4. -P.429 -441.

[63] Gorbenko A. The hamiltonian alternating path problem / A. Gorbenko, V. Popov // IAENG international journal of applied mathematics. -2012. -V.42, N.4. -P.204 -213.

[64] Gorbenko A. The problem of finding two edge-disjoint hamiltonian cycles / A. Gorbenko, V. Popov // Applied mathematical sciences. -2012. -V.6, N.132. -P.6563 -6566.

[65] Gorbenko A. The set of parameterized k-covers problem / A. Gorbenko, V. Popov // Theoretical computer science. -2012. -V.423. -P.19 -24.

[66] Gotthilf Z. Constrained LCS: hardness and approximation / Z. Gotthilf, D. Hermelin, M. Lewenstein // Lecture notes in computer science. -2008. -V.5029. -P.255 -262.

[67] Gourichon S. Estimating ego-motion using a panoramic sensor: comparison between a bio-inspired and a camera-calibrated method / S. Gourichon, J.-A. Meyer, S. Ieng, L. Smadja, R. Benosman // Proceedings of the symposium

on biologically-inspired machine vision, theory and application. -Aberystwyth: University of Wales, 2003. -P.91 -101.

[68] Grollman D. Robot learning from failed demonstrations / D. Grollman, A. Billard // International journal of social robotics. -2012. -V.4, N.4 -P.331 -342.

[69] Gu J. Algorithms for the satisfiability (SAT) problem: a survey / J. Gu, P. Purdom, J. Franco, B. Wah // DIMACS series in discrete mathematics and theoretical computer science. Providence: American Mathematical Society, 1996. -P.19 -152.

[70] Gurevich Y. Average case completeness / Y. Gurcvich // Journal of computer and system sciences. -1991. -V.42, N.3. -P.346 -398.

[71] Hada Y. Trajectory tracking control of a nonholonomic mobile robot using igps and odometry / Y. Hada, E. Hemeldan, K. Takase, H. Gakuhari // Proceedings of IEEE international conference on multisensor fusion and integration for intelligent systems. -Piscataway: IEEE Press, 2003. -P.51 -57.

[72] Han J. Adaptive unscented kalman filter and its applications in nonlinear control / J. Han, Q. Song, Y. He // Kalman filter: recent advances and applications. -Rijeka: InTech, 2009. -Chapter 1. -P.l -24.

[73] Hao J. A hybrid genetic algorithm for the satisfiability problem / J. Hao, F. Lardeux, F. Saubion // Proceedings of the 1st international workshop on heuristics. -Cambridge: MIT Press, 2002. -P. 102 -109.

[74] Hao J. A new population-based method for satisfiability problems / J. Hao, R. Dome // Proceedings of 11th european conference on artificial intelligence. -New York: John Wiley k Sons Ltd., 1994. -P.135 -139.

[75] Harvey I. Genetic convergence in a species of evolved robot control architectures / I. Harvey, P. Husbands, D. Cliff // Proceedings of the 5th international conference on genetic algorithms. -San Francisco: Morgan Kaufmann Publishers Inc., 1993. -P.636 -649.

[76] Haupt R. Practical genetic algorithms / R. Haupt, S. Haupt. -New York: John Wiley & Sons Inc., 2004. -272 p.

[77] Havangi R. Adaptive neuro-fuzzy extended kalman filtering for robot localization / R. Havangi, M. Nekoui, M. Teshnehlab // International journal of computer science issues. -2010. -V.7, N.2. -P.15 -23.

[78] Hayet J. A visual landmark framework for indoor mobile robot navigation / J. Hayet, F. Lerasle, M. Devy // Proceedings of the IEEE international conference on robotics and automation. -Piscataway: IEEE Press, 2002. -V.4. -P.3942 -3947.

[79] Hayet J. A visual landmark framework for mobile robot navigation / J. Hayet, F. Lerasle, M. Devy // Image and vision computing. -2007. -V.25, N.8. -P. 1341 -1351.

[80] Heyting A. Mathematische grundlagenforschung. Intuitionismus. Beweistheorie / A. Heyting // Bulletin of the american mathematical society. -1935. -V.41, N.7. -P.476 -477.

[81] Hillis W. Co-evolving parasites improve simulated evolution as an optimization procedure / W. Hillis // Physica D: nonlinear phenomena. -1990. -V.42, N.l-3. -P.228 -234.

[82] Hong I. Image-based homing / I. Hong // Proceedings of the IEEE international conference on robotics and automation. -Piscataway: IEEE Press, 1991. -P.620 -625.

[83] Hong J. Image-based homing / J. Hong, X. Tan, B. Pinette, R. Weiss, E. Riseman // IEEE control systems. -1992. -V.12, N.l. -P.38 -45.

[84] Hsieh M. Adaptive teams of autonomous aerial and ground robots for situational awareness: field reports / M. Hsieh, C. Cowley, J. Keller, L. Chaimowicz, B. Grocholsky, V. Kumar, C. Taylor, Y. Endo, R. Arkin, B. Jung, D. Wolf, G. Sukhatme, D. MacKenzie // Journal of field robotics. -2007. -V.24, N.11-12. -P.991 -1014.

[85] Ishiguro H. Baseline detection and localization for invisible omnidirectional cameras / H. Ishiguro, T. Sogo, M. Barth // International journal of computer vision. -2004. -V.58, N.3. -P.209 -226.

[86] Ishikawa J. Object dynamics virtualization by robotic assistance for cooperative object handling with human / J. Ishikawa, A. Sakai, K. Furuta // Proceedings of the IEEE/RSJ international conference on intelligent robots and systems. -Piscataway: IEEE Press, 2009. -P4238 -4244.

[87] Jiang M. Approximability of constrained LCS / M. Jiang // Journal of computer and system sciences. -2012. -V.78, N.3. -P.689 -697.

[88] Jiang Y.-G. Towards optimal bag-of-fcaturcs for object categorization and semantic video retrieval / Y.-G. Jiang, C.-W. Ngo, J. Yang // Proceedings of the 6th ACM international conference on image and video retrieval. -New York: ACM Press, 2007. -P.494 -501.

[89] Jogan M. Panoramic eigenimages for spatial localization / M. Jogan, A. Leonardis // Lecture notes in computer science. -1999. -V.1689. -P.558 -567.

[90] Jogan M. Robust localization using an omnidirectional appearance-based subspace model of environment / M. Jogan, A. Leonardis // Robotics and autonomous systems. -2003. -V.45, N.l. -P.51 -72.

[91] Johnson M. Abstraction in recognition to solve the correspondence problem for robot imitation / M. Johnson M., Y. Demiris // Technical report series: department of computer science, University of Essex. -2004. -V. 415. -P.63 -70.

[92] Jong K. Using genetic algorithms to solve np-complete problems / K. Jong, W. Spears // Proceedings of the 3rd international conference on genetic algorithms. -San Francisco: Morgan Kaufmann Publishers Inc., 1989. -P.124 -132.

[93] Karp R. Reducibility among combinatorial problems / R. Karp // Proceedings of a symposium on the complexity of computer computations. -Berlin: Springer, 1972. -P.85 -103.

[94] Kedia P. A survey on virtualization service providers, security issues, tools and future trends / P. Kedia, R. Nagpal, T. Singh // International journal of computer applications. -2013. -V.69, N.24. -P.36 -42.

[95J Kelly A. Mobile robotics: mathematics, models, and methods / A. Kelly. -Cambridge: Cambridge University Press, 2013. -808 p.

[96] Kernbach S. Re-embodiment of honeybee aggregation behavior in an artificial micro-robotic system / S. Kernbach, R. Thenius, O. Kernbach, T. Schmickl // Adaptive behavior. -2009. -V.17, N.3. -P.237 -259.

[97] Kilani Y. A survey of the satisfiability-problems solving algorithms / Y. Kilani, M. Bsoul, A. Alsarhan, A. Al-Khasawneh // International journal of advanced intelligence paradigms. -2013. -V.5, N.3. -P.233 -256.

[98] Kober J. Learning motor skills: from algorithms to robot experiments / J. Kober, J. Peters. -Cham: Springer, 2014. -201p.

[99] Kober J. Learning motor primitives for robotics / J. Kober, J. Peters // Proceedings of the IEEE international conference on robotics and automation. -Piscataway: IEEE Press, 2009. -P.2112 -2118.

[100] Lambrinos D. A mobile robot employing insect strategies for navigation / D. Lambrinos, R. Moller, T. Labhart, R. Pfeifer, R. Wehner // Robotics and autonomous systems. -2000. -V.30, N.l-2. -P.39 -64.

[101] Lamon P. Deriving and matching image fingerprint sequences for mobile robot localization / P. Lamon, I. Nourbakhsh, B. Jensen, R. Siegwart // Proceedings of the IEEE international conference on robotics and automation. -Piscataway: IEEE Press, 2001. -P.1609 -1614.

[102] LaValle S. Planning algorithms / S. LaValle. -Cambridge: Cambridge University Press, 2006. -842 p.

[103] Lee T. Finding consensus and optimal alignment of circular strings / T. Lee, J. Na, H. Park, K. Park, J. Sim // Theoretical computer science. -2013. -V.468. -P. 92 -101.

[104] Lee T. Finding optimal alignment and consensus of circular strings / T. Lee, J. Na, H. Park, K. Park, J. Sim // Lecture notes in computer science. -2010. -V.6129. -P.310 -322.

105] Lcniowski R. Predictive feedback approach to structural vibration suppression / R. Leniowski, L. Leniowska // Archives of control sciences. -2006. -V.16, N.l. -P.35 -50.

106] Lienhart R. An extended set of haar-like features for rapid object detection / R. Lienhart, J. Maydt // Proceedings of the international conference on image processing. -Piscataway: IEEE Press, 2002. -V.l. -P.900 -903.

107] Lin P. Feature selection: a preprocess for data perturbation / P. Lin, N. Thapa, I. Omer, L. Liu, J. Zhang // IAENG international journal of computer science. -2011. -V.38, N.2. -P. 168 -175.

108] Loganathan C. Cancer classification using adaptive neuro fuzzy inference system with Runge Kutta learning / C. Loganathan, K. Girija // International journal of computer applications. -2013. -V.79, N.4. -P.46 -50.

109] Lowe D. Distinctive image features from scale-invariant keypoints / D. Lowe // International journal of computer vision. -2004. -V.60, N.2. -P.91 -110.

110] Martinelli A. Multi-resolution SLAM for real world navigation / A. Martinelli, A. Tapus, K. Arras, R. Siegwart // Springer tracts in advanced robotics. -2005. -V.15, N.l. -P.442 -452.

111] Meyer-Delius D. Using artificial landmarks to reduce the ambiguity in the environment of a mobile robot / D. Meyer-Delius, M. Beinhofer, A. Kleiner, W. Burgard // Proceedings of the IEEE international conference on robotics and automation. -Piscataway: IEEE Press, 2011. -P.270 -275.

112] Mitchell M. An introduction to genetic algorithms / M. Mitchell. -Cambridge: MIT Press, 1998. -162 p.

113] Michel D. Horizon matching for localizing unordered panoramic images / D. Michel, A. Argyros, M. Lourakis // Computer vision and image understanding. -2010. -V.114, N.2. -P.274 -285.

114] Moller R. Insect visual homing strategies in a robot with analog processing / R. Moller // Biological cybernetics. -2000. -V.83, N.3 -P231 -243.

115] Morioka K. Human-following mobile robot in a distributed intelligent sensor network / K. Morioka, J. Lee, H. Hashimoto // IEEE transactions on industrial electronics. -2004. -V.51, N.l. -P.229 -237.

116] Muhammad R. A stochastic non-CNF SAT solver / R. Muhammad, P. Stuckey // Lecture notes in computer science. -2006. -V.4099. -P. 120 -129.

117] Murray R. A mathematical introduction to robotic manipulation / R. Murray, Z. Li, S. Sastry. -Boca Raton: CRC Press, 1994. -480 p.

118] Nanayakkara T. Fuzzy self-adaptive radial basis function neural network-based control of a seven-link redundant industrial manipulator / T. Nanayakkara, K. Watanabe, K. Kiguchi, K. Izumi // Advanced robotics. -2001. -V.15, N.l. -P. 17-43.

[119] Nicolcscu M. Natural methods for robot task learning: instructive demonstrations, generalization and practice / M. Nicolescu, M. Mataric // Proceedings of the 2nd international joint conference on autonomous agents and multiagent systems. -New York: ACM, 2003. -P.241 -248.

[120] Nie F. Fuzzy partition and correlation for image segmentation with differential evolution / F. Nie, P. Zhang // IAENG international journal of computer science. -2013. -V.40, N.3. -P. 164 -172.

[121] Niichtcr A. Skyline-based registration of 3D laser scans / A. Niichter, S. Gutev, D. Borrmann, J. Elseberg // Geo-spatial information science. -2011. -V.14, N.2. -P.85 -90.

[122] O'Connor R. Classical mathematics for a constructive world / R. O'Connor // Mathematical structures in computer science. -2011. -V.21. -P.861 -882.

[123] Oates T. Identifying distinctive subsequences in multivariate time series by clustering / T. Oates // Proceedings of the 5th ACM SIGKDD international conference on knowledge discovery and data mining. -New York: ACM, 1999. -P.322 -326.

[124] Ognibenc D. Hierarchies for embodied action perception / D. Ognibene, Y. Wu, K. Lee, Y. Demiris // Computational and robotic models of the hierarchical organization of behavior. -Berlin: Springer, 2013. -Part 1. -P.81 -98.

[125] Oikonomopoulos A. Trajectory-based representation of human actions / A. Oikonomopoulos, I. Patras, M. Pantic, N. Paragios // Lecture notes in computer science. -2007. -V.4451. -P.133 -154.

[126] Papadimitriou C. Computational complexity / C. Papadimitriou. -Boston: Addison Wesley, 1994. -540 p.

[127] Park C. Transfer of skills between human operators through haptic training with robot coordination / C. Park, J. Yoo, A. Howard // Proceedings of the IEEE international conference on robotics and automation. -Piscataway: IEEE Press, 2010. -P.229 -235.

[128] Penrose L. Impossible objects: a special type of visual illusion / L. Penrose, R. Penrose // British journal of psychology. -1958. -V.49, N.l. -P.31 -33.

[129] Pizarro D. Mobile robot geometry initialization from single camera / D. Pizarro, M. Mazo, E. Santiso, H. Hashimoto // Springer tracts in advanced robotics. -2008. -V.42. -P.93 -102.

[130] Popov V. A genetic algorithm with expansion operator for the 3-satisfiability problem / V. Popov // Advanced studies in theoretical physics. -2013. -V.7, N.8. -P.359 -361.

[131] Popov V. Building the panoramic image for mobile robot localization / V. Popov, A. Gorbenko // Applied mechanics and materials. -2013. -V.365-366. -P.967 -970.

[132] Popov V. Genetic algorithms with exons and introns for the satisfiability problem / V. Popov // Advanced studies in theoretical physics. -2013. -V.7, N.8. -P.355 -358.

[133] Popov V. GSAT with adaptive score function / V. Popov // Advanced studies in theoretical physics. -2013. -V.7, N.8. -P.363 -366.

[134] Popov V. The approximate period problem / V. Popov // IAENG international journal of computer science. -2013. -V.36, N.4. -P.268 -274.

[135] Popov V. The approximate period problem for DNA alphabet / V. Popov // Theoretical computer science. -2003. -V.304, N.l-3. -P.443 -447.

[136] Popov V. The problem of selection of fingerprints for topological localization / V. Popov // Applied mechanics and materials. -2013. -V.365-366. -P.946 -949.

[137] Pradel G. Symbolic trajectory description in mobile robotics / G. Pradel, C. Caleanu // Mobile robots: perception & navigation. -Rijeka: InTech, 2007. -P.543 -570.

[138] Pradel G. Symbolic trajectory description in mobile robotics / G. Pradel G., P. Hoppenot // Journal of intelligent and robotic systems. -2006. -V.45, N.2. -P.157 -180.

[139] Raj H. Spirits: using virtualization and pervasiveness to manage mobile robot software systems / H. Raj, B. Scshasayce, K. O'Hara, R. Nathuji, K. Schwan, T. Balch // Lecture notes in computer science. -2006. -V.3996. -P.116 -129.

[140] Raiha K. The shortest common supersequence problem over a binary alphabet is NP-coinplete / K. Raiha, E. Ukkonen // Theoretical computer science. -1981. -V.16, N.2. -P. 187 -198.

[141] Ramachandran D. Bayesian inverse rcinforccmcnt learning / D. Ramachandran, E. Amir // Proceedings of the international joint conference on artificial intelligence. -San Francisco: Morgan Kaufmann Publishers Inc., 2007. -P. 2586 -2591.

[142] Ramisa A. Bioinspired robot homing using ALV and visual features / A. Ramisa, A. Goldhoorn, D. Aldavert, R. Toledo, R. Lopez de Mantaras // ERCIM newsletter. -2011. -V.84, N.l. -P.25 -26.

[143] Rensink R. Visual sensing without seeing / R. Rensink // Psychological science. -2004. -V.15, N.l. -P.27 -32.

[144] Sagues C. Localization with omnidirectional images using the radial trifocal tensor / C. Sagues, A. Murillo, J. Guerrero, T. Goedeme, T. Tuytelaars, L. Van Gool / / Proceedings of the IEEE international conference on robotics and automation. -Piscataway: IEEE Press, 2006. -P.551 -556.

[145] Sarabia M. Towards an open-source social middleware for humanoid robots / M. Sarabia, R. Ros, Y. Demiris // Proceedings of the IEEE/RAS international conference on humanoid robotics. -Piscataway: IEEE Press, 2011. -P.670 -675.

11461 Schaffalitzky F. Multi-view matching for unordered image sets, or "How do I organize my holiday snaps?" / F. Schaffalitzky, A. Zisserman // Lecture notes in computer science. -2002. -V.2350. -P.414 -431.

[147] Se S. Mobile robot localization and mapping with uncertainty using scale-invariant visual landmarks / S. Se, D. Lowe, J. Little // International journal of robotics research. -2002. -V.21, N.8. -P.735 -758.

[148] Se S. Vision-based global localization and mapping for mobile robots / S. Se, D. Lowe, J. Little // IEEE transactions on robotics. -2005. -V.21, N.3. -P.364 -375.

[149] Sebastiani R. Applying GSAT to non-clausal formulas / R. Sebastiani // Journal of artificial intelligence research. -1993. -V.l -P.309 -314.

[150] Selman B. A new method for solving hard satisfiability problems / B. Selman, H. Levesque, D. Mitchell // Proceedings of the 10th national conference on artificial intelligence. -Palo Alto: AAAI Press, 1992. -P.440 -446.

[151] Shi J. Good features to track / J. Shi, C. Tomasi //Proceedings of the IEEE computer society conference on computer vision and pattern recognition. -Piscataway: IEEE Press, 1994. -P.593 -600.

[152] Sim J. Approximate periods of strings / J. Sim, C. Iliopoulos, K. Park, W. Smyth // Theoretical computer science. -2001. -V.262, N.l-2. -P.557 -568.

[153] Snavely N. Photo tourism: exploring photo collections in 3D / N. Snavely, S. Seitz, R. Szeliski // ACM transactions on graphics. -2006. -V.25, N.3. -P.835 -846.

[154] Stephens R. Essential algorithms: a practical approach to computer algorithms / R. Stephens. -New York: Wiley, 2013. -624 p.

[155] Svoboda T. Central panoramic cameras, design, geometry, cgomotion. PhD Thesis, Czech technical university, 1999. -116 p.

[156] Svoboda T. Motion estimation using panoramic cameras / T. Svoboda, T. Pajdla, V. Hlava // Proceedings of the IEEE conference on intelligent vehicleson intelligent vehicles. -Piscataway: IEEE Press, 1998. -P.335 -340.

[157] Szeliski R. Image alignment and stitching / R. Szeliski // Handbook of mathematical models in computer vision. -2006. -Part 4. -P.273 -292.

[158] Toh S. A face recognition system using neural networks with incremental learning ability / S. Toh, S. Ozawa // Proceedings of the 8th Australian and New Zealand conference on intelligent information systems, 2003. -P.389 -394. [Электронный ресурс]. URL: http://www2.kobe-u.ac.jp/~ozawasei/pub/ anziis03.pdf (дата обращения: 04.04.2014)

[159] Tulloch M. Understanding Microsoft virtualization R2 solutions / M. Tulloch. -Redmond: Microsoft Press, 2010. -466 p.

[160] Vardy A. Anatomy and physiology of an artificial vision matrix / A. Vardy, F. Oppacher // Lecture notes in computer science. -2004. -V.3141. -P.290 -305.

[161] Vardy A. Low-level visual homing / A. Vardy, F. Oppacher // Lecture notes in computer science. -2003. -V.2801. -P.875 -884.

[162] Veres G. Automatic workflow monitoring in industrial environments / G. Veres, H. Grabner, L. Middleton, L. Van Gool // Lecture notes in computer science. -2011. -V.6492. -P.200 -213.

[163] Viola P. Rapid object detection using a boosted cascade of simple features / P. Viola, M. Jones // Proceedings of the 2001 IEEE computer society conference on computer vision and pattern recognition. -Piscataway: IEEE Press, 2001. -P.511 -518.

[164] Vlachos M. Discovering similar multidimensional trajectories / M. Vlachos, D. Gunopoulos, G. Kollios // Proceedings of the 18th international conference on data engineering. -Piscataway: IEEE Press, 2002. -P.673 -684.

[165] Voorn R. Finding simplest pattern structures using genetic programming / R. Voorn, M. Dastani, E. Marchiori // Proceedings of the genetic and evolutionary computation conference. -San Francisco: Morgan Kaufmann Publishers Inc., 2001. -P.3 -10.

[166] Wang Y.-J. Runge-Kutta neural network for identification of dynamical systems in high accuracy / Y.-J. Wang, C.-T. Lin // IEEE transactions on neural networks. -1998. -V.9, N.2. -P.294 -307.

[167] Weber K. Insect-inspired robotic homing / K. Weber, S. Venkatesh, M. Srinivasan // Adaptive behavior. -1999. -V.7, N.l. -P.65 -97.

[168] Wu Y. Hierarchical learning approach for one-shot action imitation in humanoid robots / Y. Wu, Y. Demiris // Proceedings of the 11th international conference on control, automation, robotics and vision. -Piscataway: IEEE Press, 2010. -P.453 -458.

[169] Wu Y. Towards one shot learning by imitation for humanoid robots / Y. Wu, Y. Demiris // Proceedings of the IEEE international conference on robotics and automation. -Piscataway: IEEE Press, 2010. -P.2889 -2894.

[170] Yano T. 1 MHz ultrasonic transducer operating in air / T. Yano, M. Tone, A. Fukumoto // Acoustical imaging. -1985. -V.14. -P.575 -584.

[171] Ying X. Walkthrough in large environments using concatenated panoramas / X. Ying, K. Peng, H. Zha // Proceedings of the IEEE international conference on robotics and biomimetics. -Piscataway: IEEE Press, 2009. -P.286 -291.

[172] Zhang J. Local features and kernels for classification of texture and object categories: a comprehensive study / J. Zhang, M. Marszalek, S. Lazebnik, C. Schmid // International journal of computer vision. -2007. -V.73, N.2 -P.213 -238.

[173] Zhang W. Learning non-redundant codebooks for classifying complex objects / W. Zhang, A. Surve, X. Fern, T. Dictterich // Proceedinge of the 26th annual international conference on machine learning. -New York: ACM, 2009. -P. 1241 -1248.

[174] Zhang Y. An new modified automatic panoramic image stitching model in fabric defect inspecting area / Y. Zhang, C. Yuen, W. Wong, C. Kan // Applied mechanics and materials. -2013. -V.389. -P.781 -788.

[175] Zhang Y. Repetitive motion planning and control of redundant robot manipulators / Y. Zhang, Z. Zhang. -Heidelberg: Springer, 2013. -201 p.

[176] Zhao Y. Automatic panorama recognition and stitching based on graph structure / Y. Zhao, Y. Xia // Advances in intelligent systems research. -2013. -V.42. -P.261 -263.

[177] Zhu M. Efficient video panoramic image stitching based on an improved selection of Harris corners and a multiple-constraint corner matching / M. Zhu, W. Wang, B. Liu, J. Huang // PLoS ONE. -2013. -V.8, N.12. [Электронный ресурс]. URL: http://www.plosone.org/article/fetchObject.action?uri=info%3Adoi%2F10.13 71%2Fjournal.pone.0081182&rcprcscntation=PDF (дата обращения 04.04.2014)

Работы автора по теме диссертации

[178] Gorbcnko A. A graph-based model of object recognition self-learning / A. Gorbenko // Advanced studies in theoretical physics. -2013. -V.7, N.3. -P. 115 -120.

[179] Gorbenko A. A system of intelligent algorithms for a module of onboard equipment of mobile vehicles / A. Gorbenko // International journal of mathematical analysis. -2013. -V.7, N.47. -P.2317 -2331.

[180] Gorbenko A. Automatic generation of modules of object categorization for autonomous mobile robots / A. Gorbenko // AIP confercncc proceedings. -2013. -V.1558. -P.2087 -2090.

[181] Gorbenko A. Automatic generation of modules of visual recognition / A. Gorbenko // Applied mechanics and materials. -2013. -V.416-417. -P.748 -752.

[182] Gorbenko A. Graph-theoretic models for the module of safe planning for control systems of mobile robots / A. Gorbenko // Advanced materials research. -2013. -V.683. -P.737 -740.

[183] Gorbenko A. On the approximate period problem / A. Gorbenko // IAENG international journal of applied mathematics. -2014. -V.44, N.l. -P.I -9.

[184] Gorbenko A. On the constrained longest common subsequence problem / A. Gorbenko // IAENG international journal of computer science. -2013. -V.40, N.4. -P.266 -273.

[185] Gorbenko A. The problem of fingerprints selection for topological localization / A. Gorbenko // Engineering letters. -2013. -V.21, N.4. -P.212 -217.

[186] Gorbenko A. The shortest common ordered supersequence problem / A. Gorbenko // Applied mathematical sciences. -2013. -V.7, N.97. -P.4813 -4819.

[187] Gorbenko A. An intelligent self-learning algorithm for safe cooperation in industrial environments / A. Gorbenko // CD proceedings of the 3rd international conference on advanced materials and engineering materials. -Singapore, 2013.

[188] Горбенко А.А. Программный комплекс обработки робототехнической видеоинформации для построения трехмерных координат объектов / А.А. Горбенко // Труды межвузовской научной конференции по проблемам информатики "СПИССЖ-2009". -Екатеринбург: Издательство Уральского государственного университета, 2009. -С.53 -55.

[189] Горбенко А.А. Автоматическое порождение специализированных нейронных сетей / А.А. Горбенко // Труды 42-ой всероссийской молодежной школы-конференции "Современные проблемы математики". -Екатеринбург: Издательство института математики и механики УрО РАН, 2011. -С.308 -310.

[190] Горбенко А.А. Система управления гусеничного робота Kuzma-II / А.А. Горбенко// Тезисы студенческих научных работ XIV Областного конкурса научно-исследовательских работ студентов "Научный Олимп". Направление "Естественные науки". -Екатеринбург: Издательство Уральского федерального университета, 2011. -С.7 -8.

[191] Шека А.С., Горбенко А.А. Свидетельство о государственной регистрации программы для ЭВМ №2012616119 "Управляющая программа гусеничного робота Kuzma-II". Федеральная служба по интеллектуальной собственности. Зарегистрировано 4 июля 2012 г.

[192] Вихарев С.В., Шека А.С., Брусяшш Д.А., Попов В.Ю., Горбенко А.А. Пат. 121628 Российская Федерация, МПК G07C. Интеллектуальная система анализа пассажиропотоков с использованием технического зрения; заявитель и патентообладатель общество с ограниченной ответственностью "Брейн-Крафт" (RU). - ^2012110674; заявл. 20.03.2012; опубл. 27.10.2012, Бюл. №30. — 2 е.: ил.

Список иллюстративного материала

1. Рисунок 1 - Пример типичного окружения мобильного сервисного робота.

2. Рисунок 2 - Графическое изображение примера траектории для обучения на основе демонстрации.

20

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

21

4. Рисунок 4 - Пример демонстрации и реально выполненной последовательности команд.

22

5. Таблица 1 - Пример фрагмента матрицы штрафов.

26

6. Рисунок 5 - Усреднение данных с использованием проблемы АР. 47

7. Рисунок 6 - Пример избегания препятствия.

8. Рисунок 7 - Задачи обобщения в реальном времени.

48

49

9. Таблица 2 - Экспериментальные результаты для ДНК данных Test[ 1 ]. 51

10. Таблица 3 - Экспериментальные результаты для ДНК данных Test[2]. 51

11. Таблица 4 - Экспериментальные результаты для ДНК данных Test[3]. 51

12. Рисунок 8 - Робот Neato XV-11 с бортовым компьютером и камерой. 52

13. Таблица 5 - SAT-решатели для последовательностей

примитивов двигателя Test[4], 52

14. Таблица 6 - SAT-решатели для последовательностей

примитивов двигателя Test[5]. 52

15. Таблица 7 - Экспериментальные результаты для различных рекуррентных нейронных сетей. 53

16. Таблица 8 - Экспериментальные результаты для Nqр с различными К и \U\. 53

17. Рисунок 9 - Панорама при благоприятных условиях съемки. 57

18. Рисунок 10 - Искажения навигационных особенностей. 57

19. Рисунок 11 - Панорама при наличии помех. 58

20. Рисунок 12 - Пример исходных изображений

низкого разрешения [131]. 58

21. Рисунок 13 - Варианты порождения панорам. 59

22. Рисунок 14 - Пример нарушения порядка изображений. 59

23. Таблица 9 - Экспериментальные результаты для

0А[2], 0А[5], и 0А[6]. 64

24. Таблица 10 - Экспериментальные результаты для различных генетических алгоритмов и количества поколений. 65

25. Рисунок 15 - Пример серии панорамных изображений [136]. 66

26. Таблица 11 - Экспериментальные результаты для различных генетических алгоритмов. 72

27. Таблица 12 - Качество генетических алгоритмов для различного количества поколений. 73

28. Таблица 13 - Производительность генетических алгоритмов для различного количества поколений. 73

29. Таблица 14 - Среднее количество правильных предсказаний N

для различного количества поколений. 73

30. Рисунок 16 - Треугольник Пеироуза. 74

31. Рисунок 17 - Использование неразличимых дорожных знаков. 75

32. Рисунок 18 - Сенсор с неустойчивым креплением. 75

33. Рисунок 19 - Типичный пример данных для наблюдения за пассажирскими потоками. 76

34. Рисунок 20 - Пример потери информации. 76

35. Рисунок 21 - Области интереса. 77

36. Таблица 15 - Среднее количество кадров в процессе отслеживания. 81

37. Таблица 16 - Экспериментальные результаты для различных тестовых множеств для наблюдения за

пассажирскими потоками. 82

38. Рисунок 22 - Схема самообучающегося алгоритма. 86

39. Таблица 17 - Время решения для различных генетических алгоритмов и тестового множества 11\¥1. 92

40. Таблица 18 - Время решения для различных генетических алгоритмов и тестового множества К\¥2. 92

41. Таблица 19 - Сравнение алгоритмов обработки сцены. 92

42. Таблица 20 - Зависимость аугК[Л] от количества пространственных особенностей р для

различных алгоритмов. 98

43. Таблица 21 - Количество решенных формул для бортовых SAT-решателей.

44. Таблица 22 - Производительность бортовых SAT-решателей.

45. Таблица 23 - Экспериментальные результаты для MP.

46. Рисунок 23-NeatoXV-11.

47. Рисунок 24 - Робот Johnny 5.

48. Рисунок 25 - Робот Kuzma-II.

49. Рисунок 26 - Робот Spy-C Tank.

50. Рисунок 27 - Графический интерфейс робота Spy-C Tank при использовании смартфона.

51. Рисунок 28 - Графический интерфейс робота Spy-C Tank при использовании ноутбука.

52. Рисунок 29 - Пример конфигурационного файла.

53. Таблица 24 - Формат конфигурационного файла.

54. Рисунок 30 - Окно автономной навигации.

55. Рисунок 31 - Окно телеуправляемого режима.

56. Таблица 25 - Среднее значение S для различных значений L и