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

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

Шека Андрей Сергеевич

Модели, алгоритмы и программный комплекс для обеспечения интеллектуального эксперимента

05.13.18 — Математическое моделирование, численные методы и комплексы программ

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

00554ооо1

2 2 МАП 2014

Екатеринбург — 2014

005548567

Работа выполнена на кафедре алгебры и дискретной математики ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б. Н. Ельцина»

Научный руководитель: Попов Владимир Юрьевич, доктор физико-

математических наук, доцент.

Официальные оппоненты: Корольков Юрий Дмитриевич, доктор физико-

математических наук, профессор, ФГБОУ ВПО «Иркутский государственный университет», заведующий кафедрой прикладной алгебры и защиты информации Института математики, экономики и информатики;

Иванов Дмитрий Иванович, кандидат физико-мате-матичсских наук, доцент, ФГБОУ ВПО «Тюменский государственный университет», доцент кафедры алгебры и математической логики Института математики и компьютерных науки.

Ведущая организация: ФГБУН Институт математики и механики имени

Н. Н. Красовского УрО РАН, Екатеринбург

Защита состоится 20 июня 2014 в 13.30 на заседании диссертационного совета Д 212.285.25 на базе ФГАОУ ВПО «Уральского федерального университета имени первого Президента России Б. Н. Ельцина» по адресу: 620000, Екатеринбург, ир. Ленина, 51, зал диссертационных советов, комн. 248.

С диссертацией молено ознакомиться в библиотеке ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б. Н. Ельцина», http://diiiaovet.ticieiice.urfu.ru/iiews2/.

Автореферат разослан с;<1 2014 г.

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

В. Г. Пименов

Общая характеристика работы

Актуальность темы исследования. Начало активному изучению современной теории искусственного интеллекта было положено в работе [32]. К настоящему времени теория искусственного интеллекта является неотъемлемой частью таких областей знаний, как компьютерные науки, математическое моделирование, теория управления и многие другие.

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

На сегодняшний день основным инструментом для проведения интеллектуального эксперимента принято использовать робототехнический полигон, на котором тестируются интеллектуальные алгоритмы. Исследования в области разработки и использования робототехнических полигонов в последние десятилетия отражены не только в многочисленных научных публикациях (см., например, [20, 24]), но и в крупномасштабных проектах на государственном уровне (см., например, [30, 44]). Большое внимание уделяется различным робототехни-ческим соревнованиям (см., например, Robocup [38], Eurobot [23]). Журналом Artificial Intelligence [21] исследования в области интеллектуальных соревнований и полигонов выделяются в качестве самостоятельного научного направления. Проблематика построения и использования робототехнических полигонов но-ирежнему актуальна, и для неё открыт вопрос разработки высокоэффективных математических моделей и алгоритмов для проведения интеллектуальных экспериментов.

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

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

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

1. Разработка алгоритмов размещения датчиков для исследовательского окружения робота.

2. Разработка алгоритма оптимального решения задачи локализации робота.

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

4. Разработка программного комплекса, обеспечивающего проведение экспериментального тестирования предложенного математического аппарата.

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

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

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

Научная новизна. Все результаты диссертации являются новыми.

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

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

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

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

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

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

Положения, выносимые на защиту.

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

2. Сведение проблемы размещение датчиков для обеспечения навигации к проблемам выполнимости булевой функции и 3-выполнимости булевой функции.

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

4. Сведение проблемы построения плана локализации к проблемам выполнимости булевой функции и 3-выполнимости булевой функции.

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

G. Усовершенствованный генетический алгоритм.

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

Степень достоверности и апробация результатов. Математические результаты снабжены доказательствами. Теоретические положения подтверждены вычислительными экспериментами. Основные результаты диссертации докладывались и обсуждались на следующих конференциях: International Conference on Computer-Aided Design, Manufacturing, Modeling and Simulation (Китай, Хан-чжоу, 2011 г.), International Conference on Computer, Informatics, Cybernetics and Applications (Китай, Ханчжоу, 2011 г.), научная сессия МИФИ (Москва, 2008 г., 2009 г.), Межвузовская научная конференция но проблемам информатики СПИСОК-2009 (Екатеринбург, 2009 г.), 42-я и 43-я Всероссийская молодежная школа-конференция (Екатеринбург, 2011 г., 2012 г.).

Результаты исследований представлены на следующих выставках: Международная выставка вооружения «Уралэкспоармс-2008» (Нижний Тагил, 2008 г.), XIV Российский экономический форум «Уралтехно. Наука. Бизнес» (Екатеринбург, 2009 г.), международных выставках «Иннопром» (Екатеринбург, 2010 г., 2012 г., 2013 г.).

Публикации и личный вклад автора. По теме диссертации опубликовано 11 научных работ, из них — 8 статей в рецензируемых журналах, входящих в список ВАК, 2 — в сборниках научных трудов и тезисов докладов конференций, получено 2 свидетельства о регистрации программ для ЭВМ, 2 патента

на полезные модели. Список работ автора диссертации приведен в конце автореферата. Работы [16-18, 28] не включены в основной список работ, так как в них опубликованы промежуточные результаты. Из работ автора [1, 3—6, 9—14] в диссертацию включены только результаты, принадлежащие диссертанту.

Структура и объём диссертации. Диссертация состоит из введения, четырёх глав основного содержания, заключения, списка цитируемой литературы и списка публикаций. Общий объём диссертации составляет 118 страниц машинописного текста. Она включает 9 рисунков, 14 таблиц и 131 ссылку на литературные источники. Основное содержание работы

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

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

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

Для осуществления внешнего наблюдения необходимо, чтобы каждая точка полигона обозревалась хотя бы одним датчиком. Отметим, что данная задача является классической для современной компьютерной науки и робототехники (см., например, [22, 40, 42]); в работах [22, 40, 42] представлены приближённые методы её решения. В диссертации представлены алгоритмы для получения точного решения на основе логических моделей. В общем случае данная задача может быть описана следующей математической моделью. Проблема размещения датчиков (SP)

Дано. Дискретное пространство R с Z2, множество N с R возможных мест нахождения робота, множество S С R возможных мест размеще-

ния датчиков, положительное целое число к и функция обзора датчиком F такая: если точка у € R обозрима из точки х, то у £ F(x), где F : S —» 2й.

Задача. Существует ли множество Т с S такое, что Ux€tF(x) = N и \Т\ < к?

Основным результатом первого раздела первой главы является построение логической модели путем явного сведения SP к задачам выполнимости булевых формул, а именно: к задаче выполнимости булевой формулы в конъюнктивной нормальной форме (SAT), задаче выполнимости булевой формулы в 3-конъюнктивной нормальной форме (3SAT) и задаче максимальной выполнимости булевой формулы в конъюнктивной нормальной |}>орме (MAXSAT). Следует отметить, что на практике необходимо однократное решение задачи SP для каждого полигона. При этом экономия на стоимости: даже одного датчика является значимой. Поэтому можно использовать относительно медленные алгоритмы для нахождения оптимального решения.: Для цроблем MAXSAT, SAT и 3SAT существуют достаточно эффективные алгоритмы (см., например, [26, 39]), позволяющие получать точные решения. Поэтому построение явного сведения SP к MAXSAT, SAT и 3SAT можно рассматривать как эффективное решение проблемы SP.

Рассмотрим сведение SP к MAXSAT. Пусть S = {ai, <22,..., am} и N — {Ьь b2l ■ ■ ■, bn}. Без потери общности можно предположить, что для любого i существует j такое, что hi € F(dj). Пусть «¿j = (V;6{p|bie.F(ap)}3;i) V .sj и Pij = (У|б{р|б,бР(%)}:гг) V -.Sj-, где 1 < i < n, 1 < j < m + 1. Пусть с = (Ai<i<n,i<j<m+i(<2«j Л Pij)) Л (Ai<t<m-a;t).

Теорема SP to MAXSAT. Пусть | 1 < 1 < m + 1,1 < j < m} явля-

ются заданными для переменных а такими, что максимальное число операторов сг выполнимы. Пусть Т = {a7- | aj € S,x° = 1}. Тогда \Т\ = min pes И-

Рассмотрим сведение SP к SAT. Пусть С = Л i<i<n СVi6{p|bieFK)}^i) Ai<i<m (V1<i<fc(zii!) V Л !<(<* {->гц V ->Zjti).

1 <i<j<m

Теорема SP to SAT. Пусть {x4,z°j | 1 < i < m, 1 < j < k} являются значениями литералов такими, что £ выполнима. Пусть Т = {щ | ai € S, .т® = 1}. Тогда UxeTF(x) = N и \Т[ < к.

Используя стандартные преобразования из теории вычислительной сложности, из которая представлена в конъюнктивной нормальной форме, можно получить 3-конъюнктивную нормальную форму Таким образом, получаем сведение SP к 3SAT.

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

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

Проблема размещения датчиков для обеспечения навигации на основе триангуляции (SPP)

дано. Дискретное пространство R, функция обзора датчиком F, множество N = {61, &2) • • • ,Ьп} возможных мест нахождения робота, множество S = {аь а.2,..., От} возможных мест размещения датчиков и положительное целое число к.

Задача. Существует ли множество Т Q S такое, что Vfy е N За,-, aj € Т такие, что г ф j, bi € F(ai),bi € F(aj) и \T\<k?

Основной результат второго раздела первой главы — построение явного сведения SPP к SAT и 3SAT. Данный подход использован по тем же причинам, что и для задачи SP.

Рассмотрим сведение SPP к SAT. Пусть

Ч> — A l<t<n {V¡e{p\b<eF(ap)}Xij,l) л 1<г<п (-"^¿д,! V -ixii2,i); l<j<2 1 <(<m

Ф = a l<t<n (Vl<t<k{zi,t) v -'Xijj) Л l<l<k v -'Zj-;);

1<3<2 1 <i<j<m

1 <l<m

£ = tp Лф.

Теорема SPP to SAT. Пусть {х-^,*^ | 1 < i < n, 1 < j < 2,1 < I < m,

1 < t < k} являются значениями литералов такими, что £ выполнима. Пусть Т = {а; | щ € S,3i,j ж?., = 1}. Тогда Щ € N 3сц,а} € Т такие, что i ф j, bi 6 F(a,i), bi € F(a.j) и \T\ < k.

Используя аналогичную технику, что и для задачи SP, получаем З-конъ-юнктивную нормальную форму для задачи SPP, то есть получаем сведение SPP к 3SAT.

Отметим, если робот является источником информации, то задачи SP и SPP получают иную не менее важную интерпретацию. А именно: решение задачи SP обеспечивает покрытие окружения минимальным количеством информационных концентраторов, а решение задачи SPP даёт возможность получения надежного покрытия окружения. Такой подход представляет существенный интерес и активно изучается [29, 48]. В частности, решение каждой из этих задач в таком контексте представляет значительный интерес для разработки робо-тотехнического полигона, поскольку многие задачи искусственного интеллекта непосредственно связаны со сбором информации, а требование надежности информационного обмена является одним из приоритетных для ряда важнейших направлений использования робототехники и интеллектуальных систем (военные технологии, космонавтика, ликвидация чрезвычайных ситуаций и т.д.).

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

и поиск приближённых решений при помощи быстрых интеллектуальных алгоритмов.

Основным результатом третьего раздела первой главы является построение эффективного интеллектуального алгоритма для приближённого решения проблемы ЭР. Предложенное решение основано на алгоритме оптимизации искусственной физики, который имеет три стадии: инициализация, вычисление сил и передвижение [47].

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

В диссертации для вычисления сил использовалась нейронная сеть Рун-ге— Кутты, основанная на многослойном персептроне и идее метода Рунге - Кут-ты. Данные нейронные сети рассматривались в работе [46]. Взаимосвязь входов и выходов нейронной сети Рунге — Кутты 4-го порядка описывается следующими соотношениями: з/(г + 1) = у{г)-\-\Н{кй + 2к\ +2/с2 + &з), гДе = кг = М}{у{г)+\Нк0\ю), к2 = к3 = Л/>(у(г)+Л^2;ги),Л/>(ж;го)-

нейронная сеть, многослойный персептрон с входом х и весами хи. Для обучения использовался алгоритм, который распространяет градиентную ошибку в обратном направлении нейронной сети Рунге — Кутты для минимизации квадратичной ошибки Е — ||.т(г + 1) — у(г + 1)||2 на г-й итерации. Вычислив

— = —2(х(г + 1) - у г + 1 • + 2—I + 2—± + —¿),

дги^ 6 дииу Згу,- дш, дги/

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

Глава 2. Планирование движения для определения местоположения

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

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

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

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

Пусть прямоугольный граф G размера т и те задан матрицей (з[г>^])т+2хп+2, где —í<i<m,—l<j<n. Заметим, что g[i,j] = 1 или g[i,j] = 0. Случай g[i,j] = 1 возможен тогда и только тогда, когда ячейка с координатами i, j принадлежит G. Матрица имеет увеличенный размер, чтобы учесть непроходимость границ графа, то есть g[i, — 1] = 0, g[i, п] = 0 при — 1 < г < т и д[— 1, j] — 0, д[т, j] — 0 при — 1 < j < п. Пусть на г-м шаге di определяет направление движения (север, восток, юг, запад), где 0 < d¿ < 4. Тогда последовательность из i передвижений определим следующим образом: Di = [dQ, ...,di\. Каждый шаг характеризуется некоторым окружением, а именно тем, являются ли соседние ячейки проходимыми или нет. Пусть на г-м шаге w\ показывает проходимость соседних ячеек, где 0 <wt< 16. Значения ui¿ вычисляются с помощью функции t([x, у]) = p[I+1'!'l + + 45'x-!/+1) + 8®1*,1,-11, где 0 < х < т, 0 < у < п. Также определим последовательность проходимости соседних ячеек: W¡ = [и>о,..., tyj. Таким образом, можно задать план локализации с помощью функции f(Wi, Di-i), которая на г-м шаге вычисляет направление движения di. Пусть F(Wi) = F(W{U [f(Wu F{Wi^))} и F(W0) = ¡f(W0, Q)]. Определим функцию q{[x,y], D¡), которая возвращает координаты ячейки при старте из ячейки д[х, у) и выполнении последовательности передвижений Di. Определим функцию Т([х, у], Di) = [í([s, у]), t(q([x, у], D0),..., t{q{[x, у], Di)}, которая возвращает последовательность масок проходимых ячеек при выполнении последовательности передвижений Д-, где D, = D¿_i U di. Таким образом, можно определить функцию h{WuDi-1) = {q([x,y],Di-i)\g[x,y] = 1, T(\x,y],Di-\) = W¡}, которая определяет множество ячеек, где может находиться робот при выполнении последовательности передвижений £>¿_i, наблюдая при этом последовательность проходимость соседних ячеек W¿.

Проблема корректного детерминированного плана локализации (VDLPP)

Дано. Прямоугольный граф G, натуральное число К.

задача. Существует ли /(w¿, Di-1) такой, что для VWk = и WK_! = [wQ,...,wk^]: \h(WK, F{WK^))\ < 1?

Основным результатом второй главы является построение явного сведения VDLPP к SAT. Задача VDLPP на практике требует однократного решения для

каждого полигона и может быть решена заблаговременно до непосредственного использования плана локализации. Построение явного сведения VDLPP к SAT можно рассматривать как эффективное решение проблемы VDLPP.

Рассмотрим сведение VDLPP к SAT. Пусть W = {(х,у)\д[х,у] = 1}, V = {(х,у)\д[х, у] = 0}. Определим функции: fx{d) и fy(d) такие, что ¿(1) = О, /х(2) = 0, fx(3) = -1, Д(4) = 1 и /у(1) = 1, М2) = -1, Ш = 0, / (4) = 0. Определим литералы, истинность которых имеет следующее значение: sXotV„lXuyui - истинно, если робот нри старте из ячейки Хо,уо на шаге I приходит в ячейку x\,yi\ ax0,y„,i,h ~ истинно, если робот при старте из ячейки (ху, уо) на шаге I может находиться в любой ячейке из множества с порядковым номером h; h]gjL - истинно, если на шаге I множество д является подмножеством множества h с шага I - 1; cXoMtitd - истинно, если при старте робота из ячейки (х0, уо) на шаге I выбрано направление движение d, где 1 < d < 4 и направление движения регламентируется функциями: fx(d) и fy(d)\ eX:Vid - истинно, если ячейка (х,у) имеет конфигурацию стенок d, где 0 < d < 24 и конфигурация стенок регламентируется функцией t(x,y). Чтобы литералы удовлетворяли заявленному смыслу и отвечали условиям задачи VDLPP, определим следующую формулу: <р = ац Л а2 А 0\ А 02 А 5 Л 71 Л 72 А щ Л 772 А 773 А А, где

<21 = Ao<5<2,(i„Vg)eH'',(ri,yi)?i(x2,ii2) (-,s»o,K)i«i.У1.< V "^хо.УоЛг.Уг.О; О-г = /\{x0,ya)eW {\/(xi,yi)ew(s*o,yo,xi,Vi,

0)Л (xo,Va)£W (sXO,VOJCO,VO,Q)>

0<1<А;

01 = A(lo>№)e^(Vl<d<4(Cio,S/o,M))A(i-o,yo)eW',0<i<i:(_'Cio,yo,W V "'СжоЛо,',?);

О <l<k 1 <d<q<4

02 = A(i0,3/o),(ii,yi)eW'(_,c®o,!/o,i,<i V ~,s®o,l»a.®ii»i,i V sx0,yo,xi+fx(iI},yi+fv(d),l+'i)'

0<l<k,l<d<4

S - A (xa,Vo)£W (\fo<k<n*m(aXa,Vo,l,h)) A (xa,y0)eWfi<l<k (^.»Д V ^а*о,Уо,1,д)'< О <1<к 0 <h<g<n*m

71 = Л 1<'<* i\Io<h<ntm(b',1,h)) A l<l<kfi<g<n*m V ->6ii9iP);

0<g<n*m 0<h<p<n*m

l<l<k 0 <g,h<n*m

vi = A(

d=i(xu,y0) 0<ti<16 (»i,»i)6V-

<tyt(x„,yo) 0<l<k

_ д ((^ХамМ V ,!rt,г,Л V Cx0,y0,W v -.с*, ,1,й)А

772 " V V V

0<i<i;,l<d<4,0</i<mtn

_ Д (("^а.уо.гл v ",аХ|,»1,1Л v его,уо,<гv ",eI1,Vl ¿)Л

% " V V V ew));

0<l<k,0<d<10,0<h<m*n

^ — A(^o,yo)ew (Oi„,yo,i,d) A (io,yi>),(®byi)eiV (-^aro.yo.fc.ft v паил-У')-d=t(xn ,yo) (xi ,У1 ,У(|)1>X(I ,yi >yu

1=0 0 <h<n*m

о<i<k } U )<1<к \ , , <d< 4 / U

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

Таким образом, получаем сведение задачи VDLPP к SAT. Используя аналогичную технику, что и для задачи SP, получаем 3-конъюнктивную нормальную форму для задачи VDLPP, то есть получаем сведение VDLPP к 3SAT. Глава 3. Самосознание

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

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

В диссертации предложен принципиально новый подход, позволяющий компактно представлять элементы данного пространства. Рассмотрим модель, предложенную в диссертации. Пусть X = {ц \ ж,- является переменной, г е /}, где 7 — некоторое индексное множество. Рассмотрим временные ряды х= (а;ь...,Х|/|).

Как правило, существует некоторый временной интервал, который определяет смысловые границы всех событий. Соответственно, можно предположить, что существует некоторое положительное целое число п такое, что для любого t значение где s > t + п или s < t — п, не влияет на осведомленность о ситуации в момент t. Теперь можно дать новое определение временной связи. Любые временные отношения могут быть определены как временные ряды у такие, что у = {уиу2,.. ..Ущ), где ¿ф] = 0, если аф] = 0; = 0, если s > t + n или s < t — п\ 2/;[s| 6 {0,1}, если Xi[s] = 1 и i-n < s < t + n для некоторого t.

Предложенная модель наследуют все хорошие свойства временных отношений из работ [19, 33], но при этом компенсирует их недостатки. Однако данная модель имеет много временных отношений. Чтобы уменьшить влияние количества временных отношений на производительность системы управления роботом, в исследованиях использовалась алгебра на множестве временных отношений для структурирования особенностей и объединения элементарных событий.

Определим алгебраические операции * на множестве временных отношений следующим образом. Пусть и * v = z, где z;[f] = 1 тогда и только тогда, когда Uj[i] = 1 или Vi[i] = 1 для всех t. Для произвольных временных рядов Xi можно рассмотреть x;[i] как элементарное событие. Результат работы учитывает все элементарные события, которые принимаются во внимание хотя бы одним из операндов.

Пусть 1Z — множество всех временных отношений. Пусть R Ç1Z. Легко проверить, что S = (R | -к) является полугруппой для любого Теперь вместо множества всех временных отношений можно рассматривать только набор системообразующих генераторов полугруппы S. Оставшиеся отношения можно получить с помощью операции *. В частности, при использовании на роботе можно определить семантику только для генераторов полугрупп. Семантика оставшихся отношений будет непосредственно следовать из семантики генераторов и разложения. Такой подход позволяет использовать понятия «статус» и «диаметр» алгебры, чтобы регулировать отношение между числом предустановленной информации и сложностью представления (см., например, [25, 37]).

Дальнейшее сокращение числа временных отношений, семантика которых определена, возможно при объединении элементарных событий. Например, робот оснащен двумя веб-камерами. Рассмотрим следующие элементарные события: «робот находится не на столе» и «человек находится рядом с роботом».

Для первой веб-камеры определим события щ и «2, а для второй — события vi и V2 соответственно. Чтобы быть уверенным, что одно из представленных событий происходит в момент времени t, достаточно, чтобы выполнялось одно из следующих отношений: щ\р\ = 1, Vi[t] = 1. Такая ситуация довольно распространена. Соответственно, возможно использование следующей операции объединения элементарных событий: и * v = 1 тогда и только тогда, когда и = 1 или v = 1.

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

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

общей подпоследовательностью для всех последовательностей в множестве последовательностей.

Определение наибольшей общей подпоследовательности с максимальной последовательностью возможно несколькими способами. Длина последовательности 5" — количество букв в ней — обозначается как |(. Дано множество последовательностей ¿> = {Б^ | 1 < г < т} и последовательность Т в каком-то фиксированном алфавите Е, последовательность Т является подпоследовательностью последовательности £>г, если Т может быть получена из путём удаления некоторых букв из £",■. Последовательность Т является наибольшей общей подпоследовательностью множества последовательностей если Т может быть получена из Б, путем удаления некоторых букв из для всех таких г, что 1 < г < т. Последовательность Т является наибольшей общей подпоследовательностью если Т является общей подпоследовательностью 5, и если и является общей подпоследовательностью то |{/| < |Т|. Последовательность ТбТ является наибольшей общей подпоследовательностью 5 над множеством Т, если Т является общей подпоследовательностью Я, и если V 6 Т является общей подпоследовательностью Б, то |С| < |Т|. В частности, ясно, что наибольшей общей подпоследовательностью ¿> является наибольшая общая подпоследовательность £ над множеством 7", где Т = £*.

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

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

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

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

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

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

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

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

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

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

Во втором разделе четвертой главы проведено тестирование математических моделей для проблемы SP с помощью различных эвристических алгоритмов: fgrasp [39], posit [39], GA [4], SGA [27], OA [27], AI [26], A2 [3G], A3 [35], A4 [34]. Результаты тестирования представлены в таблице 1. Для SAT сведения проблемы SPP в таблице 2 представлено сравнение алгоритмов. Также было проведено тестирование приближённого интеллектуального алгорит-

^ or, ,/ / б-102<ЛГ<103 1 / 5 103<iV<104 ч „

ма для проблемы SP при различных условиях КЦ 102<£<5~;102), Щ io^^sss^io3 / и ^(lo^fi^iQi )• В таблице 3 представлена оценка качества алгоритмов Ма = где T0Dt - количество датчиков наилучшего решения задачи SP, по-

iopt ^ riT-k

лученного SAT-решателем, а. Та - количество датчиков решения задачи SP алгоритмом А. В качестве алгоритмов выступают: закон негативной экспоненциальной силы (NEFL) [47], закон унимодальной силы (TJFL) ¡47], закон линейной силы (LFL) [47] и предложенный в диссертации закон общей силы (E.KFL) на

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

Таблица 1 - Экспериментальные результаты Таблица 2 — Экспериментальные результаты для SP для SPP

Алгоритм Среднее Макс. Лучшее

3SAT

fgrasp 38,1 мин 11,27 ч 2,12 мин

posit 42,32 мин 8,26 ч 2,97 мин

SGA 1,14 ч 21,84 ч 2,17 мин

ОА 17,77 мин 8,18 ч 19 с

А2 19,44 мин 6,38 ч 11,2 с

A3 4,07 мип 41,62 мип 1,1 мип

A4 6,15 мин 4,2 ч 6 с

MAXSAT

AI 6,19 мин 12,74 м 1,5 мин

SGA 52,1 мин 21,3 ч 53 с

OA 32,16 мин 17,6 ч 11 с

Алгоритм Среднее Макс. Лучшее

fgrasp 2,56 ч 7,11 ч 22,3 мин

posit 2,43 ч 9,48 ч 28,7 мин

GA 2,19 ч 6,2 ч 53,55 с

А2 39,72 мин 3,79 ч 15,88 с

A3 5,7 мин 26,1 м 45,9 с

A4 14,55 мин 1,78 ч 7,41 с

Таблица 3 — Результаты тестирования приближённого интеллектуального алгоритма

vt v2 V3

•Mnefl 1,542 1,789 2,116

Mufl 1,873 2,442 3,715

•Mlfl 2,292 3,788 5,204

mßkfb 1,076 1,138 1,157

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

Таблица 4 — Экспериментальные Таблица 5 — Экспериментальное сравнение алгебр результаты для УОЬРР отношений

Время Среднее Макс. Лучшее

fgrasp 3,24 ч 26,73 ч 18,9 мин

posit 4,G1 ч 19,57 ч 9,44 мин

A2 1,33 ч 3,72 ч 5,3 с

A3 11,25 мин 56,43 мин 2,81 м

A4 22,5 мип 37,8 мип 3,4 с

Используемая алгебра А|19| CA |33| РА

Достижение конечной точки маршрута, % 74 52 98

Среднее время прохождения дистанции, мин 7,43 11,8 4

Кол-во достигпутых контрольных точек 97 56 186

Средняя длина пройденного маршрута, м 63 47 97

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

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

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

1. Разработаны алгоритмы размещения датчиков для исследовательского окружения робота. Для проблемы размещения датчиков, осуществляющих внешнее наблюдение (SP), предложены сведения к проблемам SAT, 3SAT и MAXSAT. Для задачи размещения навигационных датчиков (SPP) предложены сведения к проблемам SAT и 3SAT. Предложенные сведения позволяют с помощью эвристических алгоритмов получать точные решения за разумное время. Для решения проблемы (SP) в ограниченное время разработан интеллектуальный алгоритм, основанный на: использовании модели искусственной физики и нейронных сетей Рунге — Кутты. |

2. Разработан алгоритм построения оптимального плана локализации. В частности, представлены сведения проблемы построения корректного детерминированного плана локализации (VDLPP) к проблемам SAT и 3SAT, позволяющие получать оптимальные решения с помощью эвристических алгоритмов.

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

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

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

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

определенных ВАК РФ

1. Брусянин Д. А., Вихарев С. В., Шека А. С. Интеллектуальная система анализа пассажиропотоков с использованием технического зрения // Транспорт Урала. 2012. Т. 2(33). С. 86-89.

2. Шека А. С. Экспериментальный анализ алгебр отношений для идентификации отказов мобильных роботов // Транспорт Урала. 2013. Т. 3(38). С. 53-57.

3. Gorbenko A., Mornov М., Popov V., Sheka A. The problem of sensor placement // Advanced Studies in Theoretical Physics. 2012. Vol. 6. No. 20. P. 965-967.

4. Gorbenko A., Mornev M., Popov V., Sheka A. The problem of sensor placement for triangu-lation-based localisation // International Journal of Automation and Control. 2011. Vol. 5. No. 3. P. 245-253.

5. Gorbenko A., Popov V., Sheka A. Robot self-awareness: Exploration of internal states // Applied Mathematical Sciences. 2012. Vol. 6. No. 14. P. 675-688.

6. Gorbenko A., Popov V., Sheka A. Robot self-awareness: Temporal relation based data mining // Engineering Letters. 2011. Vol. 19. No. 3. P. 169-178.

7. Sheka A. On the Valid Deterministic Localization Plan Problem // Applied Mathematical Sciences. 2013. Vol. 7. No. 97. P. 4829-4838.

8. Sheka A. Problems of Sensor Placement for Intelligent Environments of Robotic Testbeds // International Journal of Mathematical Analysis. 2013. Vol. 7. No. 47. P. 2333-2339.

Другие публикации

9. Брусянин Д. А., Вихарев С. В., Горбенко А. А., Попов В. Ю., Шека А. С. Интеллектуальная система мониторинга пассажиропотока транспортного комплекса региона // Инновационный транспорт. 2012. Т. № 2(3). С. 41-43.

10. Горбенко А. А., Морнев М. Л., Попов В. Ю., Шека А. С. Об организации стационарного визуального наблюдения // Материалы всероссийской молодежной школы-конференции «Современные проблемы математики» (31.01.2011 - 6.02.2011). С. 311-314.

11. Горбенко А. А., Попов В. Ю., Шека А. С. Автономное подключение к источникам питания для мобильных роботов // Материалы всероссийской молодежной школы-конференции «Современные проблемы математики» (29.01.2012 - 5.02.2012). С. 214-216.

Патенты и свидетельства о регистрации программ

12. Брусянин Д. А., Вихярев С. В., Горбенко А. А., Попов В. Ю., Шека А. С. Интеллектуальная система мониторинга пассажиропотока с использованием технического зрения // Патент на полезную модель №121628 (РФ) от 27.10.2012.

13. Вихарев С. В., Шека А. С. Система управления мобильным роботом // Патент на полезную модель №123302 (РФ) от 27.12.2012.

14. Горбенко А. А., Шека А. С. Управляющая программа гусеничного робота Kuzma-II // Свидетельство о государственной регистрации программы для ЭВМ №2012616119 от 4.06.2012.

15. Шека А. С. Управляющая программа колесного робота Kuzma-I // Свидетельство о государственной регистрации программы для ЭВМ №2012611028 от 24.01.2012.

Литература

16. Бабиков А. В., Морнев М. Л., Окуловский Ю. С. и др. Об интеллектуальных алгоритмах управления роботами // Информационно-математические техноологии в экономике, технике и образовании. Вып. 4. Екатеринбург. УГТУ-УПИ. 2008. С. 169-175.

17. Морнев М. Д., Окуловский Ю. С., Попов В. Ю., Шека А. С. Проблемы интеллектуального моделирования колесных роботов // Международная научная конференция «Информационно-математические технологии в экономике, технике и образовании». Тезисы докладов. Екатеринбург. УГТУ-УПИ. 2007. С. 229-231.

18. Окуловский Ю. С., Шска А. С. Об архитектуре роботов и интеллектуальном управлении ими // Научно-технический вестник СПбГУ ИТМО. 2008. Т. 48. С. 143-150.

19. Allen J. F. An Interval-Based Representation of Temporal Knowledge // Proceedings of the 7th international joint conference on Artificial intelligence - Volume 1. 1981. Vol. 1.

20. Andersen G., Burnheimer A., Cicirello V. et al. Intelligent systems demonstration: The Secure Wireless Agent Testbed (SWAT) // Proceedings of the National Conference on Artificial Intelligence. 2004. P. 1004-1005.

21. Artificial Intelligence Journal. URL: http://www.journals.elsevier.com/artificial-intelligence/ (дата обращения: 17.09.2012).

22. Efrat A., Har-Peled S., Mitchell J. Approximation algorithms for two optimal location problems in sensor networks // Proceedings of the 2nd International Conference on Broadband Networks, Boston, Massachusetts, USA. 2005. Vol. 1. P. 714-723.

23. Eurobot. URL: http://www.eurobot.org/ (дата обращения: 16.03.2012).

24. Fernanda В., Garcia F., Takada I. et al. Development of a testbed to intelligent systems on software defined radio // SBMO/IEEE MTT-S International Microwave and Optoelectronics Conference Proceedings. 2005. P. 259-262.

25. Gorbenko A., Lutov A., Mornev M., Popov V. Algebras of stepping motor programs // Applied Mathematical Sciences. 2011. Vol. 5. No. 33-36. P. 1679-1692.

26. Gorbenko A., Popov V. A genetic algorithm with expansion and exploration operators for the maximum satisfiability problem // Applied Mathematical Sciences. 2013. Vol. 7. No. 21—24. P. 1183-1190.

27. Gorbenko A., Popov V. SAT solvers for the problem of sensor placement // Advanced Studies in Theoretical Physics. 2012. Vol. 6. No. 25-28. P. 1235-1238.

28. Gorbenko A., Popov V., Sheka A. Localization on discrete grid graphs // Lecture Notes in Electrical Engineering. 2012. Vol. 107. P. 971-978.

29. Han X., Cao X., Lloyd E.v Shen C.-C. Fault-tolerant relay node placement in heterogeneous wireless sensor networks // IEEE Transactions on Mobile Computing. 2010. Vol. 9. No. 5. P. 643-656.

30. ISHM Testbeds and Prototypes. URL: http://csrp.psu.edu/files/ishm2005/ishm_duncava.ge. pdf (дата обращения: 15.01.2010).

31. Lee-Johnson С., Carnegie D. Mobile robot navigation modulated by artificial emotions // IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics. 2010. Vol. 40. No. 2. P. 469-480.

32. McCulloch W., Pitts W. A logical calculus of the ideas immanent in nervous activity // The Bulletin of Mathematical Biophysics. 1943. Vol. 5. No. 4. P. 115-133.

33. Oates Т., Cohen P. Learning planning operators with conditional and probabilistic effects // Planning with Incomplete Information for Robot Problems: Papers from the 1996 AAAI Spring Symposium. 1996. P. 86-94.

34. Popov V. A genetic algorithm with expansion operator for the 3-satisfiability problem // Advanced Studies in Theoretical Physics. 2013. Vol. 7. No. 5-8. P. 359-361.

35. Popov V. Genetic algorithms with exons and introns for the satisfiability problem // Ad-

P. 221-226.

vanced Studies in Theoretical Physics. 2013. Vol. 7. No. 5-8. P. 355-358.

36. Popov V. GSAT with adaptive score function // Advanced Studies in Theoretical Physics. 2013. Vol. 7. No. 5-8. P. 363-366.

37. Popov V. Sorting by prefix reversals // IAENG International Journal of Applied Mathematics. 2010. Vol. 40. No. 4. P. 1-4.

38. Robocup. URL: http://www.robocup.org/ (дата обращения: 07.06.2013).

39. SAT solvers. URL: http://people.cs.ubc.ca/~hoos/SATLIB/index-ubc.html (дата обращения: 12.08.2010).

40. Spletzer J., Taylor C. Dynamic sensor planning and control for optimally tracking targets // International Journal of Robotics Research. 2003. Vol. 22. No. 1. P. 7-20.

41. Sumpeno S., Hariadi M., Purnomo M. Facial emotional expressions of life-like character based on text classificr and fuzzy logic // IAENG International Journal of Computer Sciencc. 2011. Vol. 38. No. 2. P. 122-133.

42. Susca S., Bullo F., Martinez S. Monitoring environmental boundaries with a robotic sensor network // IEEE Transactions on Control Systems Technology. 2008. Vol. 16. No. 2. P. 288-296.

43. Tekdas O., Isler V. Sensor placement for triangulation-based localization // IEEE Transactions on Automation Science and Engineering. 2010. Vol. 7. No. 3. P. 681-685.

44. The Connected Vehicle Test Bed. URL: http://www.its.dot.gov/factsheets/connected_ vehi(:Ui_test.bed_ffu:tsheet.htin (дата обращения: 08.04.2012).

45. Tovey С., Koenig S. Gridworlds as testbeds for planning with incomplete information // Proceedings of the seventeenth national confcrcncc on artificial intclligcncc. 2000. P. 819-824.

46. Wang Y.-J., Lin C.-T. R.unge Kutta Neural Network for identification of continuous systems // Proceedings of the IEEE International Conference on Systems, Man and Cybernetics. 1998. Vol. 4. P. 3277-3282.

47. Xie L., Zeng J. The performance analysis of artificial physics optimization algorithmdriven by different virtual forces // ICIC Express Letters. 2010. Vol. 4. No. 1. P. 239-244.

48. Zhang W., Xue G., Misra S. Fault-tolerant relay node placement in wireless sensor networks: Problems and algorithms // Proceedings - IEEE INFOCOM. 2007. P. 1649-1657.

Подписано в печать 16.04.2014 г. Формат 60 х 84 1/16 Усл. печ. л. 1,16. Тираж 100 экз. Заказ Ш 248

Копировальный центр «Копи-А» 620027, Екатеринбург, ул. Мамина-Сибиряка, 71

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина»

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

0%2014602^1 Шека Андрей Сергеевич

Модели, алгоритмы и программный комплекс для обеспечения интеллектуального эксперимента

05.13.18 — Математическое моделирование, численные методы

и комплексы программ

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

Научный руководитель д-р физ.-мат. наук Попов Владимир Юрьевич

Екатеринбург — 2014

Содержание

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

Глава 1. Расстановка датчиков..........................................16

1.1. Проблема размещения датчиков......................................19

1.2. Размещение датчиков для обеспечения навигации на основе триангуляции ..............................................................22

1.3. Приближённое решение проблемы размещения датчиков..........25

Заключение к главе 1........................................................30

Глава 2. Планирование движения для локализации................33

2.1. Локализация в решетчатом графе....................................34

2.2. Логическая модель планирования движения........................37

Заключение к главе 2........................................................43

Глава 3. Самосознание......................................................45

3.1. Идентификация внешних аномалий..................................51

3.1.1. Временные отношения Аллена ..............................52

3.1.2. Ограниченность временных отношений Аллена............56

3.1.3. Новые временные отношения................................61

3.1.4. Алгебра временных отношений..............................62

3.1.5. Изучение последствий действий мобильного робота и самоопределения ................................................64

3.2. Исследование внутренних состояний ................................71

3.2.1. Интроны и экзоны в генетическом алгоритме..............72

3.2.2. Использование интронов и экзонов для конфигурирования систем......................................................76

Заключение к главе 3........................................................78

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

4.1. Бортовой компьютер — управляющий компьютер — суперкомпьютер ........................................................................82

4.2. Размещение датчиков..................................................83

4.2.1. SAT-решатели для проблем SP и SPP ....................84

4.2.2. Алгоритм оптимизации искусственной физики для проблемы размещения датчиков..................................86

4.2.3. Применение на транспорте....................................87

4.3. Планирование движения..............................................89

4.4. Самосознание ..........................................................91

4.4.1. Алгебра временных отношений..............................91

4.4.2. Расширенный генетический алгоритм ......................95

Заключение к главе 4........................................................97

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

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

Список публикаций .............................116

Патенты и свидетельства о регистрации программ.........118

Введение

Начало активному изучению современной теории искусственного интеллекта было положено в работе [80]. К настоящему времени теория искусственного интеллекта является неотъемлемой частью таких областей знаний, как компьютерные науки (см., например, [35]), математическое моделирование (см., например, [38]), теория управления (см., например, [26]), теория приближения (см., например, [12]), численные методы (см., например, [60]), компьютерная графика (см., например, [94]), философия (см., например, [23]) и многие другие.

Исследования в области интеллекта неразрывно связаны с исследованиями носителей интеллекта и коммуникационной среды. Необходимым фундаментом исследования интеллекта является всестороннее изучение носителей интеллекта и коммуникационной среды их взаимодействии. В случае исследований естественного интеллекта очевидными носителями являются люди, а коммуникационной средой — их среда обитания. При рассмотрении искусственного интеллекта естественно возникает вопрос о создании как носителей искусственного интеллекта, так и подходящей среды для этих носителей. При этом, учитывая эффект Маугли [8], необходимо принимать во внимание, что разработка носителей и среды — это не элемент удобства изучения, а неотъемлемая часть создания искусственного интеллекта.

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

кациях (см., например, [13, 37, 40]), но и в крупномасштабных проектах на государственном уровне (см., например, [18, 65, 121]). Большое внимание уделяется различным робототехническим соревнованиям (см., например, Robocup [105], Eurobot [36]). Журналом Artificial Intelligence исследования в области интеллектуальных соревнований и полигонов выделяются в качестве самостоятельного научного направления [16].

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

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

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

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

1. Разработка алгоритмов размещения датчиков для исследовательского окружения робота.

2. Разработка алгоритма оптимального решения задачи локализации робота.

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

4. Разработка программного комплекса, обеспечивающего проведение экспериментального тестирования предложенного математического аппарата.

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

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

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

Для осуществления внешнего наблюдения необходимо, чтобы каждая точка полигона обозревалась хотя бы одним датчиком. Эта задача является классической для современной компьютерной науки и робототехники (см., например, [33, 112, 115]). В работах [33, 112, 115] представлены приближённые методы её решения. В диссертации представлены алгоритмы для получения точного решения на основе логических моделей. В общем случае данная задача может быть описана следующей математической моделью. Проблема размещения датчиков (SP)

дано. Дискретное пространство R с Ъ2, множество NCR возможных мест нахождения, множество S С R возможных мест размещения датчиков, положительное целое число к и функция обзора датчиком F такая, что если точка у <Е R обозрима с точки х, то у 6 F(x), где F : S —> 2R.

Задача. Существует ли множество Т с S такое, что Ux<=tF(x) = N и \Т\ < к?

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

датчиков. В работе [120] предлагается приближённый алгоритм для решения данной проблемы; в диссертации же представлен алгоритм для получения точного решения на основе логической модели. В общем случае рассматриваемая задача может быть описана следующей математической моделью.

Проблема размещения датчиков для обеспечения навигации на основе триангуляции (SPP)

ДАНО. Дискретное пространство R, функция обзора датчиком F, множество N = {6i, 62,..., bn} возможных мест нахоэ/сдения, множество S = {0,1,0,2,... ,аш} возможных мест размещения датчиков и положительное целое число к.

задача. Существует ли множество Т с S такое, что v6; g N 3ai, aj е Т такие, что г j, bi Е F(aj), bi G F(aj) и \T\ < k?

Основной результат раздела 1 главы 1 — построение явного сведения SP к MAXSAT, SAT и 3SAT. На практике необходимо однократное решение задачи SP для каждого полигона, при этом экономия каждого датчика имеет существенное значение. Поэтому для обеспечения нахождения оптимального решения можно позволить использование довольно медленного алгоритма. Отметим, что для проблем MAXSAT, SAT и 3SAT разработаны достаточно эффективные алгоритмы (см., например, [48,107]), позволяющие получать точные решения. Поэтому построение явного сведения SP к MAXSAT, SAT и 3SAT можно рассматривать как эффективное решение проблемы SP.

Основной результат раздела 2 главы 1 — построение явного сведения SPP к SAT и 3SAT. Задача SPP на практике также требует однократного решения для каждого полигона. При этом экономия каждого датчика по-прежнему существенна. Также как и для задачи SP, построение явного сведения SPP к SAT и 3SAT можно рассматривать как эффективное решение проблемы SPP.

Если робот является источником информации, то задачи SP и SPP получают иную, но не менее важную интерпретацию. А именно: решение задачи SP обеспечивает покрытие окружения минимальным количеством информаци-

онных концентраторов, а решение задачи SPP дает возможность получения надежного покрытия окружения. Такой подход представляет существенный интерес и активно изучается [59, 131]. В частности, решение каждой из этих задач в таком контексте представляет значительный интерес для разработки робото-технического полигона, поскольку многие задачи искусственного интеллекта непосредственно связаны со сбором информации, а требование надежности информационного обмена является одним из приоритетных для ряда важнейших направлений использования робототехники и интеллектуальных систем (в военных технологиях, космонавтике, чрезвычайных ситуациях и т.д.). Однако решение задачи обеспечения информационного обмена при сборе информации при решении прикладных задач не всегда опирается на хорошо известное постоянно используемое окружение. Довольно часто в прикладных задачах окружение претерпевает существенные изменения. Поэтому с точки зрения прикладных задач большой интерес представляет не только нахождение точных решений задачи расстановки датчиков, но и поиск приближённых решений при помощи быстрых интеллектуальных алгоритмов.

Основной результат раздела 3 главы 1 — построение эффективного интеллектуального алгоритма для приближенного решения проблемы SP. Предложенное решение основано на алгоритме оптимизации искусственной физики, имеющий три стадии: инициализация, вычисление сил и передвижение [129], в котором для вычисления сил использовалась нейронная сеть Рунге — Кут-ты [126].

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

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

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

Пусть прямоугольный граф (7 размера тип задан матрицей (д[{, ^)т+2хп+2, где — 1 < г < т, — 1 < ] < п. Заметим, что д[г^] = 1 или д[г,э) = 0. Случай д[г,= 1 возможен тогда и только тогда, когда ячейка с координатами г, принадлежит (7. Матрица имеет увеличенный размер, чтобы учесть непроходимость границ графа, то есть определим р[г, — 1] = 0, д[г, п] = 0 при — 1 < г < т и д[—1,^'] = 0, д[тл] = 0 при —1<]< п. Пусть на г-м шаге ^ определяет направление движения (север, восток, юг, запад), где 0 < с^ < 4. Тогда последовательность из г передвижений определим следующим образом: Д = [с?0, Каждый шаг характеризуется некоторым окружением, а именно тем, являются ли соседние ячейки проходимыми или нет. Пусть на г-м шаге и>1 показывает проходимость соседних ячеек, где 0 < и^ < 16. Значения г^- вычисляются с помощью функции 1([х,у]) = + 2д[х~1,у] + 4+ ^у-Ц^ Где 0 < х < т, 0 < у < п. Определим последовательность проходимости соседних ячеек: 1¥{ = [ги0,...,

Итак, можно задать план локализации с помощью функции /(1Уг-,£)г_х), которая на г-м шаге вычисляет направление движения Пусть

F(Wi) = F(Wi-1) U {f(Wi:F(Wi-1))] и F(W0) = [/(Wo, [])]. Определим функцию q([x,y], Di), которая возвращает координаты ячейки при старте из ячейки д[х,у] и выполнении последовательности передвижений Д-. Определим функцию Т([х, у], Di) = [t([x, у]), t(q([x, у], D0), t(q([x, у], А)], которая возвращает последовательность масок проходимых ячеек при выполнении последовательности передвижений Di, где Di = Д_х U di.

Таким образом, можно определит�