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

Российская Академия Наук Институт Системного Программирования

УДК 519 7

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

Устюжанин Андрей Евгеньевич

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

Специальность 05 13 11-математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

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

Москва 2007

003061618

Работа выполнена в Институте системного программирования РАН

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

профессор

Жданов Александр Аркадьевич

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

профессор

Зенкевич Станислав Леонидович

доктор физико-математических наук, профессор

Дмитриев Александр Сергеевич

Ведущая организация Институт точной механики и

вычислительной техники им С А Лебедева РАН

Защита диссертации состоится «7» сентября 2007 г на заседании диссертационного совета Д 002 087 01 при Институте системного программирования РАН по адресу

109004, Москва, Б Коммунистическая 25, Институт системного программирования РАН, конференц-зал

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН

Автореферат разослан «7» августа 2007 г

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

/Прохоров СII./

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

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

Темпы развития индустрии мобильной робототехники в наши дни сопоставимы с темпами развития отрасли персональных компьютеров в начале 80-х годов на рынке нет устоявшегося лидера и нет традиционных подходов, которые могли бы считаться безусловными авторитетами Напротив, число проектных решений, архитектур роботов, предлагаемых исследовательскими и производственными коллективами, изобилует разнообразием, но все они, как правило, ориентированы на решение частных задач, отличающихся определенной узостью постановки На сегодняшний день нет общепринятых методов разработки систем управления, подходящих для роботов, особенно если речь идет об адаптивных методах управления, которые пока практически не используются Тем не менее, такие методы существуют, и одним из них является метод Автономного Адаптивного Управления (ААУ)

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

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

Для систем управления важную роль играет «глубина памяти» - объем сохраненной предыстории поведения управляемого объекта Эффективность работы системы управления напрямую зависит от глубины памяти В настоящей работе в рамках метода ААУ предлагается новый подход к построению модуля ассоциативной памяти для систем ААУ - памяти, которая способна идентифицировать протяженные во времени или в пространстве закономерности входных сигналов В работах С Н Гринченко указывается на системы с ассоциативной памятью, как на системы, обладающие большей «глубиной памяти», поскольку они естественным образом приспособлены для работы с более сложными образами В частности, системы ассоциативной памяти способны распознавать сохраненный образ протяженного во времени или в пространстве явления по небольшому фрагменту или по искаженному прообразу Примеры, для которых наличие такой памяти необходимо, можно найти в любой области, требующей эффективного прогнозирования при управлении Например, можно указать на следующие прикладные задачи

• управление мобильным роботом в лабиринте,

• адаптивное управление подвеской автомобиля,

• управление коллективами агентов,

• управление искусственным спутником

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

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

1 Предложен и разработан метод построения ассоциативной памяти для систем управления на основе хаотических процессоров Создание и реализация такой памяти является развитием теории ААУ, позволяющим системам

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

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

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

Одну из ключевых ролей в построении систем автономного адаптивного управления играет подсистема формирования и распознавания образов (ФРО) На сегодняшний день технологии, использованные для реализации этой подсистемы, позволяли работать лишь с образами непродолжительных во времени явлений (например, временных рядов, наблюдаемых в течение не более 5 тактов работы системы) «Глубина» такой памяти невелика, и небольшой объем запоминаемой предыстории обусловлен тем, что основной технологией работы системы ФРО является использование системы нейроноподобных элементов Возможности отслеживать динамику и длинные последовательности наблюдаемых явлений и процессов посредством нейроноподобных структур наталкиваются на серьезные ограничения, вызванные тем, что пока еще не развита технология использования нейроноподобных сетей для работы с образами протяженных пространственно-временных объектов Использование предложенного в данной диссертационной работе подхода к построению ассоциативной памяти на основе хаотических процессоров позволит значительно расширить границы применимости методологии ААУ, охватив, тем самым, более сложные с технологической точки зрения области

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

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

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

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

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

Апробация работы и публикации Результаты работы докладывались на международных конференциях «Интеллектуальные системы» (Дивноморское, 2003 г и 2004 г), «Нейроинформатика-2006» (Москва, 2006 г), 44-й и 48-й научных конференциях МФТИ (Долгопрудный, 2001 г, 2005 г)

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

Структура и объем работы Диссертация состоит из введения, пяти глав, заключения, списка литературы и одного приложения Список литературы включает 94 названия Основной текст диссертации занимает 126 страниц

Содержание работы

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

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

• Методология Автономного Адаптивного Управления,

• Информационные потоки в динамических системах Хаотические

процессоры,

• Меры близости многомерных последовательностей

Методология «Автономного адаптивного управления» (Жданов А А, 1999) - подход, разрабатываемый в Институте системного программирования РАН и нацеленный на проектирование и разработку систем управления, обладающих свойством адаптации к изменениям условий окружающей среды Предлагаемый в данной работе метод построения ассоциативной памяти позволяет существенно повысить эффективность подсистем распознавания образов и памяти образов в системах ААУ Центральным понятием системы распознавания является понятие образа Используется понятие образа, принятого в алгебраических системах, где под образом понимается результат отображения из множества прообразов в множество образов Множеством прообразов в случае систем управления может быть множество объектов, сцен или процессов, наблюдаемых управляющей системой (УС) в окружающей ее среде посредством сенсоров Множество образов расположено в памяти УС (называемой памятью образов) и представлено множеством идентификаторов образов Рассматриваемое отображение реализует некоторое определенное правило, накладывающее ограничения на структуру и статистические свойства прообразов, которым разрешается иметь свои отображения в памяти образов,

т е собственно образы Память образов формируется в процессе автоматического обучения системы распознавания

Под прообразом, анализируемым разработанной системой управления, понимается последовательность многомерных векторов, заданных в некотором уУ-мерном пространстве Работа датчиков, отображающих информацию о наблюдаемых объектах и процессах в форму входных векторов, во многих случаях описывается тривиальными правилами Например, для мобильного робота, обладающего 10-ю ультразвуковыми датчиками расстояния, поток информации от этих датчиков можно представить как последовательность 10-мерных векторов Характерные длины таких последовательностей определяются спецификой конкретной предметной области

Построение памяти образов базируется на принципе так называемых «хаотических процессоров» (Дмитриев АС, 1997) - систем, работающих с потоками информации, и обладающими следующими свойствами

• итеративность,

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

• адресация элементов по содержанию

«Хаотический процессор» определяется как информационная система, реализующая отображение Р

Х„, = Р(Л:„а),

где X, - я-мерный вектор, а — вектор параметров, размерность которого определяется спецификой задачи Итеративно применяя отображение ^ к начальному вектору Хи, получаем последовательность векторов X/, Х2, , Хт Такую последовательность называют траекторией системы в векторном пространстве Множество последовательностей я-,мерных векторов длиной не большей т будем обозначать Ут"

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

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

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

• Евклидова мера близости - сумма квадратов поэлементных разностей двух сравниваемых последовательностей,

• Мера наибольшей общей посдпоследовательности (Longest Common Subsequence -LCSS), по которой последовательности тем ближе, чем больше максимальная длина общей подпоследовательности двух сравниваемых последовательностей,

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

В главе 2 описывается подход к построению ассоциативной памяти, позволяющей запоминать протяженные во времени и пространстве цепочки данных Здесь и далее рассматриваются два множества множество ключей К, каждый из элементов которого принадлежит VJ\ и множество идентификаторов последовательностей О, каждый из элементов которого являются целым числом Под ассоциативной памятью понимается

Определение 1 Ассоциативной будем называть память, обеспечивающую хранение пар (ключ, идентификатор) и поиск идентификаторов, ключи которых совпадают с поисковым запросом Другими словами память обеспечивает сюръективное отображение между множеством ключей К и множеством значений идентификаторов О, упорядоченных по возрастанию от 0 до N-1 (где N— мощность множества значений О) Извлечение идентификатора из памяти осуществляется по запросу - последовательности Q е V„" т е память реализует операции

• сохранение пары (ключ К„ идентификатор О,'), К, еК, <9, е О,

• поиска идентификатора сохраненных ключей К„ по запросу {QJ е Vmn, При работе с ключами, представленными в виде последовательности

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

Определение 2 Устойчивой ассоциативной памятью назовем такую

ассоциативную память, которая в дополнение к операциям обычной

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

• поиск идентификаторов 0} сохраненных ключей К„ ключи которых

похожи на запрос {QJ е V,,",

• поиск идентификаторов О, сохраненных ключей К„ которые включают

последовательности, похожие на запрос (Qj

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

Далее рассматриваются подсистемы ААУ, для которых использование ассоциативной памяти оказывается оправданным Сравнивая функциональность подсистемы ААУ «ФРО» и «Базы Знаний» с функциональностью ассоциативной памяти, приходим к выводу, что именно для этих подсистем использование ассоциативной памяти может дать значительные преимущества

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

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

Минимальным ограничивающим параллелепипедом или минимальным ограничивающим регионом (МОП или MBR - minimum bounding rectangle) для последовательности {S,}, все элементы которой принадлежат V? (S, е 9?), будем называть «-мерный параллелепипед R = MBR({5,}) минимального объема со сторонами, параллельными осям координат, который целиком содержит точки этой последовательности Расширением параллелепипеда R на величину 8 является параллелепипед R такой что, центр R' совпадает с

центром параллелепипеда Я, а координаты вершин Я' отличаются от координат соответствующих вершин Я на величину <5 вдоль каждой из осей в направлении от центра Я

Алгоритм вычисления МВК меры следующий Пусть даны последовательность {8,} и запрос {0,,}, для которых необходимо вычислить меру близости Для этого разобьем {8,} на подпоследовательности, и для каждой из подпоследовательностей построим минимальный ограничивающий параллелепипед й, Каждый параллелепипед увеличим на <5 (для каждого параллелепипеда построим расширение на величину 5) Таким образом, последовательности {8,} ставим в соответствие последовательность {Я,} Заметим, что между любыми двумя Яь е {/?,} установлено соотношения непосредственного следования - для них можно определить, является ли Я, непосредственным предшественником Я, или нет Тогда процедура вычисления меры близости последовательностей (О,} и {Б,} выглядит следующим образом

1) V = чтт (минимальное значение, которое нужно, чтобы операция деления

на V была всегда допустима)

2) по последовательности {5,} строим {Л,},

3) последовательно для каждого элемента £), е {£),} проверяем

a) принадлежит ли (), какому-либо Я,е {Я,}, и если принадлежит, то запоминаем индексы этих регионов (индексы текущего шага) Если принадлежность найдена, то увеличиваем значение V на величину

b) сравниваем индексы текущего шага с индексами прошлого шага Если оказывается, что индексы текущего следуют за индексами прошлого, то увеличиваем V на величину «г

4) Величина меры близости вычисляется как /Л>

Величина 5 характеризует устойчивость алгоритма к пространственным искажениям Параметрам алгоритма а/ и а2 были присвоены значения 1 и 2 соответственно

Описанный способ сравнения пространственно-временных последовательностей удовлетворяет выдвинутым требованиям и оказывается лучше аналогов (БТ\У и ЬС88) Этот вывод подкрепляется численными

экспериментами В качестве тестовых данных для численных экспериментов использовались данные из следующих источников 1) данные, полученные в ходе работы над совместным проектом Института системного программирования и Санкт-Петербургского научно-практического центра медико-социальной экспертизы, протезирования и реабилитации инвалидов им Г А Альбрехта, 2) набор слов австралийского языка глухонемых, который является стандартом де-факто для проверки работы различных алгоритмов с многомерными данными

Из анализа результатов вычислительных экспериментов были сделаны следующие выводы

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

2) мера ЬСББ ведет себя тем хуже, чем больше соотношение длины последовательности к длине запроса,

3) мера МВК. ведет себя в целом не хуже, чем евклидова мера,

4) евклидова мера ведет себя хуже, чем мера МВЛ при увеличении параметра соотношения длины последовательности к длине запроса,

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

Далее предлагается следующий способ построения ассоциативной памяти на основе хаотического процессора Схема хранения данных основана на подходе аппроксимации бассейна аттрактора посредством многомерных геометрических примитивов и хранении этих элементов в многомерной индексной структуре Пример построения МОП-ов разбиения последовательности приведен на Рис 1

Рис, I - Пример разбиения многомерной иоследователы-гости и построения ограничивающих регионов

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

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

• отображение Р обладает хаотическим режимом,

• аттракторами этого отображения являются (X,}

• бассейн аттрактора включает подмножество объединения {Я,}

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

Рис, 2. Бассейны Притяжения аттракторов

Для реализации отображения Р необходимо каждой сохраняемой по с дедо 8 ательно стм (X,} сопоставить последовательность МОП-он {/?,<, Каждому МОП-у поставим в соответствие следующие данные:

• идентификатор всей последовательности 0},

• индекс МОП-а в последовательности /А',,'.

• центр следующего МОП-Ц (или первого, если текущий МОП Является последним в {&,}),

■ признак конца последовательност и, который равен 1, если текущий МОП является последним в последовательности /Л',/, к 0 в противном случае. Последовательность параллелепипедов /У?,/ а связанных с ними данных сохраняется в структуре многомерного индекса - ^дереве с приоритетами.

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

На основании оценки сложности операции поиска по К-дереву

показывается, что сложность операции поиска при использовании

N — „ ,

предложенного подхода составляет 0(тв( —) "), где т длина запроса (), Л

В

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

носителе Эмпирические оценки эффективности работы предложенной памяти приводятся в 5-ой главе

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

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

Программная модель робота, рассматриваемая в этом примере, соответствует современной модели мобильного робота Pioneer II DX Такой робот оснащен следующими датчиками

• лазерные датчики расстояния,

• датчик цвета,

• датчики столкновения,

• датчик направления (компас)

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

Рис. 3. Поспев овательность значений, полученных от лазерных сенсоров.

Для облегчения работы с такими с такими векторами были использованы дискретные вей в лет-преобразован» я по базису вей влетов Хаара. Использование такого преобразования позволило уменьшить аберрации и размерность входных сигналов. Характерная длина прообразов (длина последовательности векторов) препятствий варьировалась от 50 до 100 элементов. Множество идентификаторов последовательностей состоит из чисел от 0 до (Т-1), где Т— число типов препятствий.

Управляющая система (УС) такого мобильного робота была спроектирована с использованием методологии ААУ, схема которой представлена на Рис.4.

Среда I)

СредаШ

Среда $

09

Блек датчиков

Исполняй-

з**88*88»! щий арти

Ж

Формирование, оценкеаннеи

распознавание образов

Фазирование 8азы знаний

1

Принятое

Йдаарат зивиий

Опрслеяенме

времени принятия (Митина

Рис 4 структура управляющей системы (УС) согласно методологии ААУ ОУ - объект управления, Среда Б, Среда и Среда и - обозначения внешней среды с различных точек зрения (Жданов А А , 1999)

Система «Формирования и распознавания образов» такой системы управления построена с использованием системы ассоциативной памяти на основе систем детерминированного хаоса

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

• анализ и распознавание объектов по искаженным входным данным,

• распознавание препятствия по фрагментарной информации,

• прогнозирование штока информации по имеющимся данным

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

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

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

В качестве типов препятствий были выбраны следующие три набора 1 -й набор препятствий содержит два класса препятствий, каждый из которых представляет собой искаженную трапецию Препятствия 2-го набора выбраны из теста на уровень интеллекта (10), в котором необходимо было определить различия между препятствиями Препятствия 3-го набора были взяты с карты мира и представляют собой очертания Багамских островов

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

Первая задача, названная «Слон», должна показать возможности системы управления по распознаванию препятствия, несмотря на преднамеренно создаваемые сложности распознавания Один тип сложностей связан с тем, что масштаб препятствий может варьироваться в заданном диапазоне, т е размер препятствий при управлении роботом отличается от размера препятствия, который они имели при обучении управляющей системы Второй тип сложностей состоит в увеличении скорости перемещения робота в режиме управления Эффективность работы системы управления определяется как соотношение корректно определенных типов препятствий к общему числу попыток распознавания

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

Вторая задача, названная «Сталкер», состоит в «сборе» как можно большего числа полезных препятствий В лабиринт, о котором системе управления известно только то, что в нем присутствуют препятствия двух типов («хорошие» и «плохие»), помещается мобильный робот Ни очертаний препятствий, ни их взаимное расположение системе управления не известны Система управления может отличить препятствия по маячку, установленному на каждом препятствии Но для того, чтобы увидеть маяк, необходимо почти полностью обойти это препятствие Робот должен «научиться» отличать «хорошие» препятствия от «плохих» по выявленным им характерным особенностям очертаний Перемещаясь по лабиринту, робот должен коснуться как можно большего числа «хороших» препятствий, избегая столкновений с «плохими» препятствиями При каждом касании, в зависимости от типа

препятствия, робот приобретает или теряет баллы Число набранных балов за отведенное время является критерием успешности работы системы управления

Лабиринт третьей задачи, условно названной «Колумб», представляет собой полосу препятствий, которую необходимо преодолеть роботу Изначально мобильный робот располагается у нижней кромки полосы, и ему необходимо добраться до верхней стороны за минимальное время В этой задаче роботу не требуется касаться препятствия, но препятствия составляются таким образом, что обход препятствия с одной стороны может занять существенно меньше времени, чем обход с другой стороны То есть при быстром и правильном распознавании типа препятствия робот может изменить направление обхода и сэкономить время Показателем эффективности работы системы управления является зависимость вертикальной координаты положения робота от времени

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

В главе 4 приводится описание практической реализации ассоциативной памяти, системы имитационного моделирования мобильных роботов и системы управления мобильными роботами В описание включены основные компоненты, интерфейсы и протоколы, разработанные в ходе работ Также в этой главе приводится краткое описание библиотек сторонних производителей и программного обеспечения, используемого в ходе работ В качестве платформы для создания системы имитационного моделирования примеров, описанных в 3-ей главе, была выбрана система Player/Stage Эта система ориентирована на исследователей в области робототехники и позволяет разрабатывать системы управления для различных мобильных роботов (Pioneer, Hepera, MIONIX, и тд), предоставляя разработчику удобные программные интерфейсы взаимодействия с основными датчиками и актуаторами роботов Помимо богатого набора устройств, поддерживаемыми Player-ом, на ее выбор оказали влияние следующие немаловажные факторы Во-первых, таким фактором стала расширяемость платформы - при необходимости исследователь может самостоятельно разработать новый тип датчика и драйвер, обеспечивающий взаимодействия с программной системой управления Во-вторых, таким фактором является архитектура системы, позволяющая без изменений в логике программы перейти от управления программной моделью робота к управлению реальным роботом

Для целей исследования все эксперименты проводились с использованеим имитационного сервера Stage Для моделирования использовались два компьютера имитационный сервер и клиент На сервер имитации работала система Player и система имитации Stage под управлением операционной системы Linux Компьютер клиентского приложения работал под операционной системой MS Windows 2003 Professional, на нем выполнялась система управления мобильным роботом, написанная на языке Java и взаимодействующая с сервером имитации посредством библиотеки Java-client

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

Затем даются описание правил обработки входных сигналов системой управления и правила взаимодействия системы управления с актуаторами мобильного робота Приводится способ интеграции данной программной модели в архитектуру ААУ

Таким образом, созданная инфраструктура позволяет загрузить разработанные системы управления мобильным роботом и сравнить их эффективность, исходя из условий, описанных в 3-ей главе

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

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

• объема занимаемой памяти,

• времени сохранения последовательностей,

• времени поиска последовательности

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

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

Результаты проведенных экспериментов показывают преимущества использования памяти на основе хаотического процессора Во-первых, хаотический процессор позволяет реализовать выразительную функцию меры близости (МВЛ меру), предложенную во 2-ой главе Во-вторых, время поиска сохраненных идентификаторов в такой реализации значительно (до 6 раз) меньше времени поиска в альтернативных реализациях Кроме того, время поиска посредством хаотического процессора гораздо меньше зависит от объема сохраненной информации

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

Рис 5 Зависимость результативности системы управления мобильным роботом от времени при скорости движения робота 1000с"1 Квадратные значки - система управления с ФРО на основе евклидовой меры, треугольные значки - на основе меры ЬСББ, ромбовидные - на основе меры МВИ

В ходе испытаний, при движении робота со скоростью в 2 раза превышающей скорость его движения при обучении, результативность системы управления с ассоциативной памятью на основе хаотического процессора превысила на 65% результативность системы управления с ассоциативной памятью на основе евклидовой меры и на 25% - с ассоциативной памятью на основе метода ЬСББ

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

Проведенное сравнение показывает успешность распознавания роботами заданных препятствий

Количественное сравнение эффективности различных систем управления приводится для задач «Сталкер» и «Колумб» Зависимости рейтинга,

набранного различными системами управления, от времени представлены на рис 6, 7

время с

Рис 6 Зависимость рейтинга систем управления мобильным роботом от времени в задаче «Сталкер» Треугольные значки соответствуют системе управления со случайным механизмом принятия решений (Ехр1огег11апск>т), квадратные - с выбором левого пути обхода (Ехр1огегЬей), а ромбовидные - системе управления ААУ

Сравнение эффективности работы системы управления для задачи «Сталкер» проходило с двумя другими типами систем управления 1) Ехр1огег11апс1от - система управления принимает случайное решение по касанию или избеганию препятствия, 2) Ехр1огегЬей - система управления обходит препятствие до тех пор, пока не натолкнется на маяк и тип препятствия не станет известен точно

За время эксперимента около 5 минут показатели системы ААУ превысили показатели Ехр1огег11апс1от в 2 раза, а показатели Ехр1оге1Ьей; в 1,7 раз Сравнение зависимостей говорит об успешности использования подсистемы ассоциативной памяти для системы управления

Рис 7 Зависимость рейтинга систем управления мобильным роботом от времени в задаче «Колумб» Треугольные значки соответствуют системе управления со случайным механизмом принятия решений, квадратные - с выбором левого пути обхода, а ромбовидные - системе управления ААУ

Сравнение эффективности работы системы управления для задачи «Колумб» проходило с двумя другими типами систем управления 1) Ехр1огег!1апс1от - система управления принимает случайное решение по обходу препятствий слева или справа, 2) ЕхрЬгегЬей - система управления принимает одно и то же решение обхода препятствия слева

Сравнение зависимостей показывает успешность использования подсистемы ассоциативной памяти для системы управления в задаче «Колумб» За время эксперимента показатели системы ААУ превысили показатели Ехр1огег11апс1от в 1,27 раз а показания Ехр1огегЬей в 1,2 раза

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

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

Основные выводы и результаты

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

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

2 Разработан критерий для сравнения пространственно-временных последовательностей, основанный на использовании меры минимальных ограничивающих регионов (Minimum Bounding Region (MBR) меры) В соответствии с предложенным критерием разработан алгоритм эффективного поиска близких пространственно-временных последовательностей, основанный на использовании структур пространственного индексирования Разработаны оценки ресурсоемкости и производительности для сравнения предложенного подхода с альтернативными подходами

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

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

Публикации

По теме диссертации опубликованы следующие работы 1 Жданов А А , Устюжанин А Е, Возможности использования технологии детерминированного хаоса в системах автономного адаптивного управления // Тр Института системного программирования Том 2 М ИСП РАН, 2001 с 141-179

2 Устюжанин А Е, Об использовании многомерного представления данных для анализа документарных источников // XLIV научная конференция МФТИ, 2001

3 Жданов А А, Устюжанин А Е, Использование технологий детерминированного хаоса для построения ассоциативных баз знаний систем автономного адаптивного управления // Тр Конференции ШЕЕ AIS'02 M Физматлит, 2002 С 121-127

4 Жданов А А, Устюжанин А Е, Использование технологий детерминированного хаоса для реализации памяти систем автономного адаптивного управления // МФТИ-2002

5 Устюжанин А Е, Метаповедение как способ динамической конфигурации поведения агента // IEEE AIS-2003, с 57-65

6 Бородин M В , Устюжанин А Е, О возможностях динамического изменения поведения агентов на базе многоагентной платформы JADE // МФТИ, XLVI конференция, 2003 (тезисы)

7 Бородин M В , Устюжанин А Е, Построение обучаемых многоагентных систем на базе платформы JADE // IEEE AIS-2004, с 73-82

8 Жданов А А , Устюжанин А Е , Караваев M В , Липкевич Д Б , 4GN -инструмент для разработки нейроноподобных адаптивных систем управления на основе метода автономного адаптивного управления // Нейроинформатика-2005

9 Жданов А А, Устюжанин А Е, Караваев M В Нейросетевой самообучаемый метод адаптивного управления динамическими объектами // Материалы XXIX Академических чтений по космонавтике, 2005 год M 2005 с 93

10 Устюжанин А Е, Ассоциативная память контурных объектов на основе вейвлет представлений // МФТИ-2005, с 88-101

11 Сурин H В , Устюжанин А Е, Визуализация многомерных данных с помощью самоорганизующихся карт // МФТИ, XLVIII конференция

12 Ющенко А В, Устюжанин А Е, Распознавание и интеграция метаданных разнородных источников // МФТИ, XLVIII конференция, 2005

13 Устюжанин А Е, Метод построения системы памяти для хранения и поиска многомерных пространственно-временных последовательностей // Вестник Московского государственного технического университета им H Э Баумана, серия «Приборостроение», номер 2,2007, с 104-112

Подписано в печать 06 08 2007 г Исполнено 06 08 2007 Печать трафаретная

Заказ № 607 Тираж 100 экз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш, 36 (495) 975-78-56 лууууу аи<:оге1егаг ги

Введение.

Актуальность темы.

Цель работа.

Задачи работы.

Новизна работы.

Практическая значимость работа.

Структура и объем работы.

Глава 1. Современное состояние предметной области.

Имитационный метод автономного адаптивного управления.

Детерминированный хаос. Представление о процессах обработки информации в динамических системах.

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

Глава 2. Построение систем ассоциативной памяти иа основе хаотического процессора. Анализ характеристик ассоциативной памяти.

Функции системы памяти.

Использование ассоциативной памяти в системах ААУ.

Мера близости пространственно-временных последовательностей.

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

База данных ироекга адаптивного протезирования кисти руки.

База данных австралийского языка глухонемых.

Результаты сравнения.

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

Реализация хаотического процессора.

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

Глава 3. Построение системы управления на основе методологии ААУ с использованием ассоциативной памяти. система управления мобильным роботом.

Структура лабиринта.

Критерии эффективности управления мобильноым роботом.

Глава 4. Особенности реализации системы управления мобильным роботом.

Реализация модуля ассоциативной памяти.

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

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

Предобработка сигналов сенсоров.

Управление актуаторами.

Автономная Адаптиваня система управления.

Глава 5. Анализ эффекгивности работа системы управления.

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

Сравнение реализаций ассоциативной памяти для задачи «Слот).

Сравнение систем управления мобильными роботами.

АКТУАЛЬНОСТЬ ТЕМЫ

Развитие способов представления информации как средства эффективного управления искусственными и естественными системами не теряет своей актуальности с начальных этапов становления кибернетики. В наши дни управляющие системы в состоянии контролировать достаточно сложные объекты, масштабы которых варьируются от нанороботов до комплексов атомных электростанций. Значительные темпы развития демонстрирует в наши дни индустрия мобильных роботов, выполняющих разнообразные полезные функции в различных практических сферах. Примером, показавшим принципиальный скачок возможностей автономной робототехники, стал кросс непилотируемых автомобилей но аризонской пустыне в 2005 году [1]. Другими примерами мобильных роботов, завоевавших отдельную пишу па современном рынке, являются роботы, используемые в силовых ведомствах (разведка, разминирование, работы во вредных для человека средах), мобильные автономные роботы-гиды для музеев и выставок [2], роботы-пылесосы [3].

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

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

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

Для систем ААУ важную роль играет «глубина памяти» — объем сохраненной предыстории поведения управляемого объекта. Эффективность работы системы управления напрямую зависит от глубины памяти. В настоящей работе в рамках метода ААУ предлагается новый подход к построению модуля ассоциативной памяти для систем ААУ - памяти, которая способна идентифицировать протяженные во времени или в пространстве закономерности входных сигналов. В работе [3] С.Н. Гринченко указывает на системы с ассоциативной памятью, как на системы, обладающие большей «глубиной памяти». Это системы, способные эффективно распознавать сохраненный образ протяженного во времени или в пространстве явления но небольшому фрагменту, например, для того, чтобы прогнозировать ход развития ситуации в целом, обладая лишь выборочными данными о ней. Примеры, для которых наличие такой памяти необходимо, можно найти в любой области, требующей эффективного прогнозирования при управлении. Например, можно указать на следующие прикладные задачи:

• управление мобильным роботом в лабиринте,

• адаптивное управление подвеской ав томобиля,

• управление коллективом агентов

• и другие.

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

ЦЕЛЬ РАБОТЫ

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

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

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

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

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

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

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

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

X, пиксел

220 г

200

180

160

140

120

100 б)

0 500 1000 1500 2000 2500 3000 3500 t, мс а) в)

Рисунок 1. (а) Зависимость координаты пера от времен при написании букв ang. Темная линия - траектория X(t) для буквы а (б). Светлая линия - X(t) для буквы g (в). Стрелкой отмечена точка, до которой траектории похожи друг на друга, и после которой они перестают повторять друг друга.

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

ЗАДАЧИ РАБОТЫ

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

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

• критериев сравнения последовательностей многомерных данных,

• алгоритма поиска информации,

• способа кодирования и хранения информации,

• практических критериев качественной применимости ассоциативном памяти.

Практическая часть работы состоит в реализации:

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

• систем ассоциативной памяти, альтернативных предложенному подходу,

• демонстрационных примеров - модельных систем мобильного робота,

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

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

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

НОВИЗНА РАБОТЫ

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

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

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

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

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

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

ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ РАБОТЫ

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

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

СТРУКТУРА И ОБЪЕМ РАБОТЫ

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

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

• Информационные потоки в динамических системах. Хаотические процессоры;

• Меры близос ти многомерных последовательностей.

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

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

• умения работать с искаженными данными,

• умения распознавать препятствия по фрашентарной информации,

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

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

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

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

Общий объем работы составляет 129 страниц. Список литературы включает 94 наименования.

1. DARPA Grand Challenge, http://www.darpa.mil/grandchallenge/index.asp

2. Гринченко C.H. Системная память живого (как основа его метаэволюции и периодической структуры). М.: ИПИРАН, Мир, 2004

3. Жданов А. А., Метод автономного адаптивного управления // Известия Академии Наук. Теория и системы управления, 1999, № 5, с. 127-134

4. Жданов А.А. Об одном имитационном подходе к адаптивному управлению. Сб. "Вопросы кибернетики". Научный совет по комплексной проблеме "Кибернетика" РАН. Вып. 2. М., 1996.

5. Жданов А.А. О понятии автономного искусственного интеллекта // Сб. научи, тр. Искусственный интеллект в технических системах. М.: Гос.ИФТП. 1997.

6. Zhdanov A. A. About an Autonomous Adaptive Control Methodology. ISIC/CIRA/(ISAS'98), NIST, Gaithersburg, Maryland. September 14-17, 1998.

7. Жданов А. А., Метод автономного адаптивного управления // Известия Академии Наук. Теория и системы управления, 1999, № 5, с. 127-134

8. Рядовиков А. В., Жданов А. А., О некоторых формальных моделях нейронов. // Сб. научн. тр. Всероссийской научн.-техн. конференции "Нейроинформатика-99", ч. 1. М.: МИФИ. 1999.

9. Жданов А.А., Беляев Б.Б., Мамаев В.В. Использование принципа автономного адаптивного управления в системе угловой стабилизации космического аппарата «Спектр РГ» // Сб. научи, тр. Информационная бионика и моделирование. М.: ГосИФТП, 1955. - С. 87 -114.

10. Wiegerinck W. and Tennekes Н. On the information flow for one-dimensional maps. Phsy. Lett. A, 1990, vol. 144, no 3

11. Шустер Г. Детерминированный хаос. Введение. М: Мир, 1988

12. Atmanspacher Н., Scheingraber Н. Global scaling properties of the chaotic attractor reconstructed from the experimental data. — Phys. Rev. A, 1988, vol. 37, pp 1314-1322

13. Дмитриев А.С. Запись и восстановление информации в одномерных динамических системах. — Радиотехника и электроника. 1991, т. 36, N1, С101-108

14. Dmitriev A.S., Panas A.L., and Strakov S.O. Storing and recognition information based on stable cycles of one-dimensional maps. Phys. Lett. A., 1991, vol.155, pp 494-499

15. Andreev Yu.V., Dmitriev A.S. and Starkov S.O. Information processing in 1-D systems with chaos. IEEE Transaction on circuit and systems, 1997, vol. 44, pp. 21-28

16. Андреев Ю.В., Вельский Ю.Л., Дмитриев А.С. Запись и восстановление информации с использованием устойчивых циклов двумерных и многомерных отображений. Радиотехника и электроника, 1994, т.39, с. 114-123

17. Шустер Г. Детерминированный хаос. Введение. М: Мир, 1988

18. Шарковский А.Н., Майстренко Ю.Л., Романенко Е.Ю. Разностные уравнения и их приложения. Киев: Наукадумка, 1986

19. Edward Ott, Tim Sauer, James A. Yorke. Coping with Chaos: Analysis of Chaotic Data and The Exploitation of Chaotic Systems, Wiley-Interscience, 1994

20. RAgrawal, C.Faloutsos, A.Swami. Efficient Similarly Search in Sequence Databases. In Proc. Of the 4th FODO, pages 69-84, Oct.1993.

21. A.Gionis, P. Indyk, R. Motwani. Similarity search in high dimensions via hashing. In Proc. Of 25th VLDB, pages 518-529,1999.

22. B.-K. Yi, C. Faloutsos. Fast Time Sequence Indexing for Arbitrary Lp Norms.

23. Proceedings of VLDB, Cairo Egypt, Sept. 2000.118

24. K.Chuand, M.Wong. Fast Time-Series Searching with Scaling and Shifting. ACM Principles of Database Systems, pages237-248,June 1999.

25. D.Rafiei, A.Mendelzon. Querying Time Series Data Based on Similarity. IEEE Transactions on Knowledge and Data Engineering, Vol.12, No 5, pages 675-693,2000.

26. D.Goldin, P.Kanellakis. On Similarity Queries for Time-Series Data. In Proceedings of CP'95, Cassis, France, Sept. 1995.

27. C. S. Myers, L. R. Rabiner. A comparative study of several dynamic time-warping algorithms for connected word recognition. The Bell System Technical Journal, 60(7):1389-1409, September 1981.

28. H.Sakoe, S.Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. Acoustics, Speech and Signal Processing, ASSP-26(1):43^9, Feb. 1978.

29. D.Berndt, J.Clifford. Using Dynamic Time Warping to Find Patterns in Time Series. InProc. Of KDD Workshop, 1994.

30. S.Park, W.Chu, J.Yoon, C.Hsu. Efficient Searches for Similar Subsequences of Different Lengths in Sequence Databases. In Proceedings of ICDE, pages 23-32,2000.

31. E.Keogh, M.Pazzani. Scaling up Dynamic Time Warp-ing for Datamining Applications. In Proc. 6th Int. Conf. on Knowledge Discovery and Data Mining, Boston, MA, 2000.

32. R.Agrawal, K.Lin, H.S.Sawhney, K.Shim. Fast Similarity Search in the Presence of Noise, Scaling and Translation in Time-Series Databases. In Proc of VLDB, pages 490-501, Sept. 1995.

33. B.Bollobas, G.Das, D.Gunopulos, H.Mannila. Time-Series Similarity Problems and Well-Separated Geometric Sets. In Proc of the 13th SCG, Nice, France, 1997.

34. T.Bozkaya, N.Yazdani, M.Ozsoyoglu. Matching and Indexing Sequences of Different Lengths. InProc. Of the CIKM, Las Vegas, 1997.

35. G.Das, D.Gunopulos, H.Mannila. Finding Similar TimeSeries. InProc. Of the first PKDD Symp., pages 88-100, 1997.

36. C.Faloutsos, H.Jagadish, A.Mendelzon, T.Milo. Signature technique for similarity-based queries. In SEQUENCES 97, 1997.

37. S.Perng, H.Wang, S.Zhang, D.S.Parker. Landmarks: a New Model for Similarity-based Pattern Querying in Time Series Databases. In Proceedings of ICDE, pages33-42,2000.

38. Y.Qu, C.Wang, X.Wang. Supporting Fast Search in Time Series for Movement Patterns in Multiple Scales. In Proc of the ACMCIKM, pages 251-258,1998.

39. H.V.Jagadish, A.O.Mendelzon, T.Milo. Similarity-based queries. InProc. Of the 14th ACMPODS, pages36-45, May 1995.

40. S.-L.Lee, S.-J.Chun, D.-H.Kim, J.-H.Lee, C.W.Chung. Similarity Search for Multidimensional Data Sequences. In Proceedings of ICDE, pages 599-608, 2000.

41. C.Faloutsos, M.Ranganathan, I.Manolopoulos. Fast Subsequence Matching in Time Series Databases. In Proceedings of ACMSIGMOD, pages419^29, May 1994.

42. T.Bozkaya, N.Yazdani, M.Ozsoyoglu. Matching and Indexing Sequences ofDifferent Lengths. InProc. Of the CIKM, Las Vegas, 1997.120

43. S.Gaffncy, P.Smyth. Trajectory Clustering with Mix-tures of Regression Models. InProc. Of the 5th ACMSIGKDD, SanDiego, CA, pages63-72, Aug.1999.

44. P.KAgarwal, L.Arge, J.Erickson. Indexing moving points. InProc. Of the 19th ACM Symp.on Principles of Database Systems (PODS), pages 175-186,2000.

45. G.Kollios, D.Gunopulos, V.Tsotras. On Indexing Mo-bile Objects. InProc. Of the 18th ACM Symp. On Principles of Database Systems (PODS), pages261-272, Junel 999.

46. S.Saltenis, C.Jensen, S.Leutenegger, M.A.Lopez. Indexing the Positions of Continuously Moving Objects. In Proceedings of the ACMSIGMOD, pages 331-342, May 2000.

47. D.Pfoser, C.Jensen, Y.Theodoridis. Novel Approaches in Query Processing for Moving Objects. In Proceedings of VLDB, CairoEgypt, Sept. 2000.

48. The First Computers: History and Architectures, edited by Raul Rojas and Ulf Hashagen, MIT Press, 2000.

49. From Dits to Bits.: A Personal History of the Electronic Computer, Herman Lukoff, 1979. Robotics Press

50. John Bayko, Great Microprocessors of the Past and Present, 2003 (http://www.sasktelwebsite.net/jbayko/cpu.html)

51. Jeffrey Richter, Advanced Windows, Microsoft Press 2000

52. Ершова Н.Ю., Соловьев A.B., Организация вычислительных систем, ИНТУИТ.ру, 2006

53. D. Berndt and J. Clifford. Using Dynamic Time Warping to Find Patterns in Time Series. In Proc. of KDD Workshop, 1994

54. M. Vlachos, G. Kollios, and D. Gunopulos. Discovering similar multidimensional trajectories. In Proc. of ICDE, 2002.

55. G. Das, D. Gunopulos, and H. Mannila. Finding Similar Time Series. In Proc. of the First PKDD Symp., pages 88-100,1997.

56. S. Park, W. Chu, J. Yoon, and C. Hsu. Efficient Searches for Similar Subsequences of Different Lengths in Sequence Databases. In Proceedings of ICDE, pages 23-32,2000.

57. Ю.В. Андреев, А.С. Дмитриев, ДА. Кумииов, Хаотические процессоры, Москва. Успехи современной радиоэлектроники, N10,1997

58. А. А. Жданов, А.Е. Устюжанин, Возможности использования технологии детерминированного хаоса в системах автономного адаптивного управления, Москва, сборник трудов ИСП РАН, с141-180, 2001

59. Yu. V. Andreyev, A. S. Dmitriev, D. A. Kuminov, V. V. Pavlov. Information processing in 1-d and 2-d map: recurrent and cellular neural networks implementation, CNNA'96, Seville, Spain, 1996

60. Guttman A., 'R-trees: A Dynamic Index Structure for Spatial Searching', Proc. ACM SIGMOD Int. Conf. on Management of Data, Boston, MA, 1984, pp. 47-57.

61. Eamonn J. Keogh, Shruti Kasetty. On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration. In International Conference on Knowledge Discovery and Data Mining, pages 102-111, Edmonton, Canada, July 2002.

62. База данных слов австралийского языка глухонемых, http://kdd.ics.uci.edu/databases/auslan/auslan.html

63. Chen, L. and R. Т. Ng, On The Marriage of Lp-norms and Edit Distance, Proc. Ind. Conf. on Very Large Data Bases (VLDB). pp. 792—803,2004

64. Chen L., Ozsu M., Oria V., Robust and fast similarity search for moving object trajectories, Proc. of ACM SIGMOD international conference on Management of data, pp 491-502,2005

65. S. Thurn, Robotic mapping: a survey, Technical report, CMU-CS-02-111, School of computer science, Carnegie Mellon University, Pittsburg, PA, 2002

66. I.J. Cox and J.J. Leonard. Modeling a dynamic environment using a Bayesian multiple hypothesis approach. Artificial Intelligence, 66:311-344, 1994.

67. M. Bosse, P. Newman, M. Soika, W. Feiten, J. Leonard, and S. Teller. An adas framework for scalable mapping. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2003.

68. T. Bailey. Mobile Robot Localization and Mapping in Extensive Outdoor Environments. PhD thesis, University of Sydney, Sydney, NSW, Australia, 2002.

69. AIBO (Artificial Intelligent roBOt), http://en.wikipedia.org/wiki/Aibo

70. RoboCup official site, http://robocup.org/

71. Micromouse Maze Competition, http://www.np.edu.sg/~adp-alpha/micromouse/micemain.htm

72. Российская олимпиада роботов, http://www.robosport.ru/

73. Соревнование роботов-пожарников, Trinity College, Hartford, Connecticut, http://www.trincoll.edu/events/robot/

74. Часто задаваемые вопрос и ответы по робототехнике, http://robots.net/rcfaq.html

75. А.В. Сыцко, Система управления автономным мобильным роботом на основе адаптивного резонанса Материалы XXIX Академических чтений по космонавтике, 2005 год. М.: 2005. с. 93.

76. А.А. Жданов, М.В. Крьгжаиовский, Н.Б. Преображенский. Бионическая интеллектуальная автономная адаптивная система управления мобильным роботом (часть 1): Мехатроника, 2004, N1, С. 21-30.

77. Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссндес, Приемы объектно-ориентированного проектирования. Паттерны проектирования, Питер, 2001

78. Thomas Seidl, Hans-Peter Kriegel, 'Optimal Multi-Step k-Nearest Neighbor Search', Proceedings of the ACM SIGMOD, 1998

79. King Lum Cheung, Ada Wai-chee Fu:, 'Enhanced nearest neighbor search on the R-tree', SIGMOD Record, vol. 27, num. 3,1998

80. Marioh Hadjieleftheriou, Spatiallndex Library, http://u-foria.org/marioh/spatialindex/

81. Brian Gerkey, Kasper Stoy, Richard T. Vaughan, Player Robot Server. Technical Report IRIS-00-392, Institute for Robotics and Intelligent Systems, School of Engineering, University of Southern California, November 2000

82. Проект моделирования мобильных роботов Player/Stage, http: / / playerstage.sourceforge.net/

83. Библиотека Java-player, проект взаимодействия с сервером player для пользовательских приложений на языке Java. http://java-player.sourceforge.net/

84. Устюжанин А.Е., Ассоциативная память контурных объектов на основе вейвлет представлений // Процессы и методы обработки информации. М., 2005.

85. Библиотека управления мобильными роботами в среде Player/Stage па языке Java: http://java-player.sourceforge.net/

86. Anargyos Krikelis, Charles С. Weems (editors) (1997) Associative Processing and Processors, IEEE Computer Science Press. ISBN 0-8186-7661-2