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

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

Приемко Андрей Анатольевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ НЕЙРОСЕТЕВЫХ АЛГОРИТМОВ

РЕШЕНИЯ ЗАДАЧ НАВИГАЦИИ ИНТЕЛЛЕКТУАЛЬНЫМИ

МОБИЛЬНЫМИ АГЕНТАМИ В НЕСТАЦИОНАРНЫХ СРЕДАХ

Специальность: 05.13.17 – Теоретические основы информатики

Автореферат

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

кандидата технических наук

Таганрог - 2007

Работа выполнена в Технологическом институте Южного федерального университета в г. Таганроге

Научный руководитель: доктор технических наук, профессор Чернухин Юрий Викторович.

Официальные оппоненты: доктор технических наук, профессор
Ромм Яков Евсеевич

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

Карелин Владимир Петрович.

Ведущая организация: ФГУП НИИ «БРИЗ», г. Таганрог.

Защита диссертации состоится «___» __________ 2007 г. в 1420 на заседании диссертационного совета Д.212.208.21 при федеральном государственном образовательном учреждении высшего профессионального образования «Южный федеральный университет» по адресу: 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке ЮФУ по адресу: г. Ростов на Дону, ул. Пушкинская, 148.

Автореферат разослан « ____ » ___________ 2007 г.

Ученый секретарь

диссертационного совета Д 212.208.21

доктор технических наук, профессор Бабенко Л.К.

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

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

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

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

При этом основной проблемой, стоящей перед ИА, является планирование действий во внешней среде, направленных на достижение поставленной цели, т.е. организация собственного поведения. Работы по созданию интеллектуальных мобильных агентов ведутся во многих научных центрах Японии, США, Великобритании, Франции, Германии и других стран. Однако, несмотря на все усилия, полученные результаты все еще далеки от желаемых. Это связано с тем, что обеспечение автоматической навигации ИА в общем случае связано с необходимостью разработки алгоритмов, позволяющих решать задачи формирования карты проходимости априори неформализованной внешней среды; определения собственного положения на карте по информации, получаемой из среды; планирования траектории движения к цели с использованием карты.

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

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

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

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

Настоящая работа является дальнейшим развитием результатов исследований, проводимых на кафедре вычислительной техники ТТИ ЮФУ под руководством профессора Чернухина Ю.В.

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

Целью работы является разработка и исследование нейросетевых алгоритмов и структур для решения задач формирования карты проходимости внешней среды; определения собственного положения на ней, экстраполяции положения цели на этой карте для ИА типа АМР. Кроме того, исследуются вопросы разработки алгоритмов и структур формирования дискретной модели проходимости внешней среды для решения задачи автоматической навигации ИА типа надводный корабль, а также необитаемый батискаф. Работа выполнена в соответствии с пунктами «…Исследование и когнитивное моделирование интеллекта, включая моделирование поведения…» и «…Применение бионических принципов, методов и моделей в информационных технологиях…» паспорта специальности 05.13.17.

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

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

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

Основные положения, выносимые на защиту. На защиту выносятся следующие положения и результаты:

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

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

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

Практическая ценность работы. Синтезированные в диссертации алгоритмы и структуры могут применяться при разработке нейросетевых систем управления ИА, ориентированных на применение в практически важных сферах деятельности, таких как транспорт, оборона, производство, научные исследования в экстремальных условиях, спасательные и ремонтно-восстановительные работы при ликвидации последствий чрезвычайных ситуаций и террористических актов и т.д. Полученные в работе результаты использовались в хоздоговорной НИР №12237 «Разработка алгоритмического обеспечения задачи отождествления информации от гидроакустических средств поиска подводных объектов», в хоздоговорной НИР №12238 «Разработка и исследование систем автоматизации проектирования проблемно-ориентированных вычислительных устройств на базе ПЛИС», а также в учебном процессе кафедры вычислительной техники ТТИ ЮФУ, что подтверждено соответствующими актами.

Апробация работы. Основные результаты работы докладывались на:

1. Всероссийской научной конференции студентов и аспирантов "ТЕХНИЧЕСКАЯ КИБЕРНЕТИКА РАДИОЭЛЕКТРОНИКА И СИСТЕМЫ УПРАВЛЕНИЯ" (Таганрог, ТРТУ, 2002 г.);
2. Научной конференции ППС ТРТУ ( ТРТУ 2005г.);
3. 14-ой международной конференции по нейрокибернетике "Проблемы нейрокибернетики” (Ростов на Дону, РГУ,2005 г.);
4. Всероссийской научной конференции молодых ученых, аспирантов и студентов “ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, СИСТЕМНЫЙ АНАЛИЗ И УПРАВЛЕНИЕ ” (Таганрог, ТРТУ, 2005 г.);
5. Всероссийской научно-технической конференции “НЕЙРОИНФОРМАТИКА 2006 ” (Москва, 2006 г.);
6. Всероссийской научно-технической конференции “НЕЙРОИНФОРМАТИКА 2007 ” (Москва, 2007 г.).

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

Структура и объем работы. Материал основной части диссертационной работы изложен на 189 страницах машинописного текста. Диссертация состоит из введения, четырех разделов, заключения и списка литературы из 71 наименования, содержит 106 рисунков, 1 таблицу и 4 приложения на 27 страницах.

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

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

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

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

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

Рисунок 1–Формализация задачи, решаемой ИА

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

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

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

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

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

Рисунок 2-Стратегия исследования внешней среды