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

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

Приемко Андрей Анатольевич ООЗОБЗЭБ2

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

Специальность 05 13 17-Теоретические основы информатики

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

Таганрог - 2007

1 4 Ш 2007

003063962

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

Научный руководитель Официальные оппоненты.

доктор технических наук, профессор Чернухин Юрий Викторович

доктор технических Ромм Яков Евсеевич

наук, профессор

доктор технических наук, профессор Карелин Владимир Петрович

Ведущая организация

ФГУП НИИ «БРИЗ», г. Таганрог

Защита диссертации состоится «28» ¿¿¿ОА'ьуС 2007 г в 1420 на заседании диссертационного совета Д 212 208 21 при федеральном государственном образовательном учреждении высшего профессионального образования «Южный федеральный университет» по адресу 347928, Таганрог, пер Некрасовский, 44, ауд Д-406

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

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

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

диссертационного совета Д 212 208 21 доктор технических наук, профессор

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

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

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

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

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

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

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

Целью работы является разработка и исследование нейросетевых алюритмов и структур для решения задач формирования карты проходимости внешней среды, определения собственного положения на ней, экстраполяции положения цели на этой карте для ИЛ типа AMP Кроме того, исследуются вопросы разработки алгоритмов и структур формирования дискретной модели проходимости внешней среды для решения задачи автоматической навигации ИА тина надводный корабль, а также необитаемый батискаф. Работа выполнена в соответствии с пунктами « Исследование и когнитивное моделирование интеллекта, включая моделирование поведения. » и « Применение бионических принципов, методов и моделей в информационных технологиях » паспорта специальности 05 13 3 7. Методы исследований Экспериментальные исследования разработанных алгоритмов проводились на программных моделях. При разработке а га оритмов применялись элементы теории дискретной математики, численных методов, теории множеств, адаптивного управления и языков программирования Достоверность полученных результатов подтверждена экспериментами на специально разработанных программных моделях, прошедших официальную регистрацию программ для ЭВМ

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

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

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

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

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

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

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

"НЕЙРОИНФОРМАТИКА 2006 " (Москва, 2006 г.), Всероссийской научно-технической конференции

"НЕЙРОИНФОРМАТИКА 2007 " (Москва, 2007 г). Публикации. По теме диссертации опубликовано 14 печатных работ, в которых отражены основные результаты диссертации

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

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

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

планирование траектории перемещения к цели в условиях навигационных опасностей

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

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

OYi Y2, а также в жестко связанной с его корпусом системе ОХхХг как

показано на рисунке 1

положения стационарных и подвижных препятствий, а вектора У1 -положение промежуточных целей, лежащих на кратчайшей траектории Т], ведущей к основной цели движения (Ц) Вектор УА задает положение агента В системе координат ОХхХ2 вектор Х0 определяет положение ИА, а вектора X ¡, , X1,

и Х0 задают положение свободных для перемещения, целевых и содержащих

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

У г, У о, У р и У а В этой сети отыскивается градиент функционала, определяемого множеством траекторий движения к цели После этого нейропроцессорной подсистемой принятия решений (СПР) определяется вектор

7

Y

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

2

В координатной системе ОУ{ У2 вектора

Ур определяют участки, свободные для перемещения ИА в некоторый момент дискретного времени tl (время изменяется квантами А(, причем t|+l =t| + &), вектор У 1 определяет положение цели в этот же момент времени, вектора У0 определяют

о

¥I направления на промежуточную цель, который направлен вдоль вектора антиградиента функционала, найденного ПНС

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

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

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

24« —г 3« -22и 214 -20 *

9-е ! 3-« -7-е -б А ?

к ы 1 -0 I I ?

— л 1 1 2- в»3_ »4 т ?

1 НЗ- Н4- Н5- ив

Тогда стратегия исследования среды интеллектуальным агентом состоит в следующем Участки с номерами 1-8 считаются потенциально проходимыми Для уточнения их проходимости ИА осуществляет последовательное сканирование данных участков при помощи дальномеров Сканирование начинается с участка номер 1 Если данный участок свободен, то выполняется перемещение на центр этого участка и занесение информации о нем в карту После этого ИА определяет проходимость участков 2-8, двигаясь против часовой стрелки по периметру участка О, как показано на рисунке 2 Если какой-то из данных участков оказывается занятым объектом, то ИА определяет, находится ли на нем препятствие либо цель и заносит соответствующую информацию в карту. После обследования участков 1-8 ИА расширяет зону исследований и переходит к сканированию участков 9-24, двигаясь по периметру исследованной зоны, как показано на рисунке 2. Данный процесс продолжается до тех пор, пока во

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

внеган

ей среде не останется ни одного неисследованного участка

2 (М)=0,{С}-0,

3 (Яг, ЛР, Кг) - СакГ&пШа, Р,с, П, Ус. Ту Гг, Тл, У6),

4 есяи }^Х=0,то€яеду1омийвиг,ияотепер«хонкл 12,

5 если ) - (шг, то

6 если , то скедую^ иит, кнача-нерехоак п. 13,

7 Даг=90,

8

9 Л,),

10 М><Ц#Я1&((М},(С},Ц,),

11 переход ^п.ЗЗ,

12 есга , ^) - /а)5«, то Лб?<ЖёИ({ЛО, ^) ,

13 ест Р.р Г-0 то спецутхкйшаг,ихгапереход^п 20,

14 есяи К,) = ти, то , Я, ),

15 если = ./ЭДзе.тоспаиуюшкйшаг, икаче-яереходхп.24,

16 Да« 0, И

18 ,

19 переход $пЗЗ

20 «ПК /дке,то ,й„),

21 есяи Xшй, то свдцгощкй аиг, ия&че переходов. 29,

22 «спи ШХ&>((С)

23 если = /Ег^г, то слевдющкй шаг, шаче-ле|юхояхп27,

24 Да»-90,

25

26 переход$:п.ЗЗ,

27 Я, - Р&ИР1апОпМар((М},(СУ)

28 пгреходкп35,

29 есяи ,то спещгащкн шаг, 1ш&че-переходхп.31,

30 АМВ&аЩЯ^,

31 ^ = РсйЬР1апОпМар((М),(С))

32 переход х1135,

33 Ш<Яе(Аа),

34 «спи » , то следующий шаг, шдое переход х п 39

35

36 если {С} О,то следующий шаг, ик&че КъОМар гоегиюх,

37 =

38 переход &пЗ,

39 ВасЦИс),

40 п/п/а^Я,),

41 АааК&ЦМ) Лг),переходхя4

Ус-

Каждому участку среды ставится в соответствие

структура данных ,

содержащая следующую

информацию

двумерный вектор

координат центра участка в системе координат создаваемой карты, ОС -значение курсового угла ИА при нахождении на данном участке, Т -признак проходимости участка, равный 0, если участок свободен для перемещения иди 1,если участок занят объектом Для уточнения типа объекта введем признак V, равный 1, если объект является целевым и 0, если он является препятствием Пусть

Яс - структура данных,

содержащая информацию о текущем участке нахождения ИА;

Я ИР, К к -структуры, хранящие информацию об участках,

находящихся слева, спереди и справа от

текущего, Кт - структура,

Рисунок З-Алгоритм формирования карты внешней среды

содержащая информацию о целевом участке движения ИА на текущем шаге, Дог - величина приращения курсового угла ИА Тогда алгоритм формирования карты внешней среды имеет вид, показанный на рисунке 3 Данный алгоритм построен таким образом, что в пункте 1 выполняется

инициализация структуры Лс, определяющей начальное положение ИА в системе координат создаваемой карты оператором ЕМК^1п/о следующим

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

!//, ,У),, V], ,7'к,¥/{) оператором Са1сК%п1п}о. Далее в пункте 4,

происходи! проверка проходимости участка Яг, находящегося слева от 1екущего Нели он является проходимым, то в пункте 5 происходит проверка на принадлежность информации об эгом участке множеству С оператором )н11£п1п$е1 В случае принадлежности Я^ удаляется из этого множества оператором ])е1Щгп Операция удаления необходима для предотвращения дублирования информации об участках, находящейся в множествах М и С. После этою в иункге б проверяется принадлежность Иг множеству М Если Яг не входит в данное множество, то ИА может осуществить попытку перемещения на участок, описываемый структурой Я,. Для этого в пункте 7 выполняется инициализация Д(X значением, соответствующим повороту влево, а и иушис 8 И; выбирается в качестве целевого участка перемещения агента

Кроме юга, в пунктах 9-10 происходит модификация множеств М и С на основе данных об участках, находящихся прямо по курсу и слева от текущего шхождения ИА оператором Мос1$у8&$ После этого предпринимается

участка и

поныика перемещения ИА в центр целевого участка (в данном случае R¡ ). Для этою в пункте 33 осуществляется поворот корпуса агента на угол А а оператором Roíate и его перемещение в п. 34 оператором Move . Если перемещение на целевой участок произошло успешно, то в пункте 35 происходит добавление информации о нем (в данном случае об участке R¡)» множество М операюром AddRgn После этого в пункте 36 происходит проверка множества

С Ко|ш оно пустое, то неисследованных участков больше нет Процесс исследования среды заканчивается и на основе данных, содержащихся во множестве М, выполняется формирование карты оператором Fill Re CtMap

hcjffl множество С не пустое, то в пункте 37 в качестве текущей позиции ИА принимается ioi участок, на который он переместился и происходит переход к определению проходимости участков, соседних с текущим положением ИА Если в процессе перемещения ИА к целевому участку произошло столкновение с

препятствием, которое не было распознано ДСП, то в пункте 39 осуществляется возврат агента в центр предыдущего участка оператором Back После этого в пункте 40 происходит обновление информации о проходимости участка, на который было предпринято перемещение оператором ModifyRgnlnfa. При этом данный участок считается содержащим препятствие и в пункте 41 информация о нем добавляется в множество М, после чего осуществляется переход к пункту 4 алгоритма

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

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

информации, хранящейся в Rvh, с информацией о среде, окружающей каждый из

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

коюрого затем сравнивается с Rvh . Пусть {<9}- множество участков вероятного

нахождения ИА, Rf -очередной элемент этою множества, RA - участок

нахождения ИА; Mrect - карта среды, сформированная в прямоугольной системе

координат; Rvh - план внешней среды, у - угол поворота Mrad. Тогда алгоритм

определения собственного положения ИА может быть представлен так, как показано на рисунке 4 В первом пункте алгоритма выполняется обнуление у

Далее в пункте 2 происходит выборка очередного участка Rj из множества О

оператором GetK&gion, который исключает выбранный участок из {О} После этого в пункте 3 осуществляется сдвиг центра вращения радиального плана на

позицию участка Rj оператором Translate, а в пункте 4 - определение

\ элементов массива Мrad оператором CalcPlan.

Далее в пункте 5 вычисляется

значени

1 Г = 0,

2 R, = GetKzgi0!{{O]),

3 TranslatiR^M««),

4 Мш = CalcPlayi,Rj, M„cl, у),

5 D=СотраЫ^Мш),

6 если £)<£}щд то следующий шаг, иначе-переход хп.9,

7 Ц^гО,

8 Ra=R

9 f = Normalize {у + Ay),

10 если у = 0, тэ спедукхдяй шаг, иначе переход к п 4,

11 если {С1} ф 0, то переход кп I,

12 остагог.

Рисунок собствен

Если D

значение меры различия D между Rvh и Mrad оператором

Compare на основе следующего выражения:

d -¿¿ijuom-AOMM

j.i

В пункте 6 происходит сравнение значений D и £)„,„ Если

D <D„

то в пункте 7

4-Алгоритм ного положения

определения

Ш1П '

значение _Отш обновляется, а в пункте 8 участок, описываемый Я становится текущей

позицией ИА на карте среды — ^шт ' то в пункте 9 увеличивается угол поворота радиального плана

и его нормализация оператором Normalize для приведения полученного значения пунктах

к диапазону [0,359°] Если в результате выполнения цикла, описанного в 4-9, осуществлен полный поворот радиального плана вокруг центра,

находящегося в участке RJ, то в пункте 11 происходит проверка наличия

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

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

которой хранит информацию о координатах (, У2) участка, в котором

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

1 Yr-QetJhrstPosstKM,

2 ptr,Xo}~Percept(Xr,Xgy,

З.есда Хг*0,то переход к п.12, иначе • следующий шаг, 4 {¥¡,?0)=МарШпфгт(Хт,То);

Jo.Xo),

1.2,

Работа данного алгоритма начинается с выбора наиболее вероятного положения цели на карте из БД в пункте 1 оператором GetFirstPosition Далее в пункте ? формируется дискретный план проходимости среды в связанной с корпусом ИЛ системе координат оператором Percept Коли цель присуютвует на этом плане (Xj •/• О, пункт }), то в пункте I? определяется вектор направления очередного шага траектории, ведущей к ней В пунктах 11,14 происходи! ею отработка

5

6 ArA=$tk;

I.Yy^hY/,

tYA^Correct(R„„Mr<aJA)),

9 если Ya~Yt , то следующий шаг, иначе -

10 Yi-QetNexlPoslmn;

II. если Fr=fl, то переход кп.1, шине - переход кп.2; 12. U = Рв&Р1ая(Хг,Хо)', 13 hY^pWht, W YA~YA+iYA;

15 1 а =Comct{KA,МЮ,,¥Л);

16 если YA=YT, то останов, иначе - переход к п.2 Рисунок 5 -Алгоритм экстраполяции положения

нестационарной цели на карте среды

В пункте 15

осуществляется локализация агента на карте оператором Correct В пункте 16 проверяется, достиг ли ИА цели. Если это так, то работа алгоритма завершается В противном случае снова происходит построение плана проходимости среды и описанные действия повторяются до достижения цели Если цель отсутствует на плане среды, то в пунктах 4-8 осуществляется преобразование карты ш прямоугольного представления в радиальное оператором MapTransfo rm, а также определение направления вектора перемещения к выбранному из БД участку оператором MapPathPlan. Далее в пунктах 6-7 выполняется перемещение в определенном направлении, а в пункте 8-локализация теша оператором Correct Если цель не обнаруживается, на выбранном участке, /о к пункте 10 из БД выбирается очередная запись, имеющая меньшее значение Р оператором GetNextPosihon, и выполняется цикл движения к соответствующему ей участку. Если предыдущая запись была последней в БД (оператор

GetNextPosihon вернул значение Y i равное 0), а цель не найдена, to в пункте 11 осущес* .ляется переход к первой записи и описанный процесс экстраполяции повторяется Таким образом, в начале работы алгоритма из БД выбирается участок, на котором цель находилась чаще всего на этане изучения ее поведения и осуществляется движение к нему Если в процессе движения цель

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

В третьей главе описана программная моделирующая среда МР8е^Ас!ар(, прошедшая процедуру государственной регистрации программ для ЭВМ. Она предназначена для проведения экспериментальных исследований разработанных алгоритмов решения навигационных задач.

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

Эксперименты ¡го исследованию алгоритма экстраполяции положения нестационарной цели с использованием БД и карты среды показали, что с его помощью удается в 5-8 раз сократить время поиска пели по сравнению с алгоритмом, основывающимся на движениях в случайно выбранном направлении. Результаты одного из этих экспериментов показаны на рисунке 6.

Как видно из данного рисунка, агент достиг цель, перемещающуюся во

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

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

Рисунок 6- Результаты эксперимента по экстраполяции положения нестационарной цели

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

каждый из которых задан координатами вершин Pt- Pl+3 Координаты вершин

каждого участка хранятся в массиве DiskrModel Пусть Т -двумерный массив той же размерности, хранящий информацию о проходимости этих участков Элементы этого массива принимают значение true, если соответствующие им участки являются безопасным для движения корабля и false в противном случае, у,к,1-переменные алгоритма, / -количество элементарных участков, на которые дискретизируется среда, по вертикали, J - количество элементарных участков

по горизонтали, К -количество элементов списка Izohnes, хранящих координаты естественных навигационных опасностей; BNO -массив, хранящий координаты искусственных объектов и радиусы зон поражения вокруг них, L - количество элементов данкого массива Тогда алгоритм формирования дискретной модели внешней среды можно представить так, как показано на рисунке 7

1 i=0, 2. J—0,

3 к=0,

4 если Intersect! <M(bolmes[k], DiskxModel[i][)]) = true, ТО T[i][j]= false

переход к п 11, ииаяе-следующий шаг,

5 к=к+1,

6 если к<К, то переход к п 4, и наче-следующи й шаг,

7 1=1,

8 если Intersecüon(BNO[l], DiskrModel (i¡[)])= truc„ TO T[i]|j]=&lse, переход кп 11, иначе-следующий шаг,

9 1=1+1,

10 если 1<L, то переход к п.8, иначе-следующий шаг, llj=j+l,

12 если j<J, то переход к п 3, иначе-следующий шаг,

13 1=1+1,

14 если i<I, то переход к п 2, иначе - останов

Рисунок 7- Алгоритм формирования дискретной модели проходимости внешней среды

среды считаться опасным для прохождения (T[i][j] = false ) и происходит переход к

Перед началом работы алгоритма все элементарные участки считаются свободными для прохождения В пунктах 1-3 выполняется инициализация переменных алгоритма, а в пунктах 4-6 проверка на попадание очередного элементарного участка в области, содержащие естественные навигационные опасности оператором Intersection Если результат этой проверки положителен, то соответствующий участок

рассмотрению очередного участка, В противном случае в пунктах 7-10 происходи-]' проверка па попадание участков и области поражения ¡¡округ искусственных навигационных опасностей путем анализа расстояний от центра

проекции каждой опасной зоны па поверхности коды до каждой ш вершин Р! -Рм участка. Сформированная дискретная модель проходимости вне ¡пней среды

отображается в состояние ГШС, где происходит определение направления шага траектории, позволяющей обойти навигационные опасности. Далее происходит перемещение корпуса корабля и определенном направлении. После перемещения вновь формируется дискретная модель среды и т.д. Описанные действия повторяются до выхода из зоны, содержащей навигационные опасности. С целью определения работоспособности предложенных алгоритмов была сшггеэирована программная моделирующая среда, прошедшая процедуру государственной регистрации. Внешний вид главного окна этой программы показан на рисунке 8. Опа включает в себя: модель под водного рельефа с возможностью задания положения естестве иных навигационных опасностей, а также размещения искусственных опасностей па дне; модель корабля, включающую ГАС, ноле приема которой состоит из двух ярусов (каждый ярус которой имеет ширину 90" и состоит из дискретных лучей), а также модель описанной пейр о процессорной навигационной подсистемы.

Рисунок 8-! дявное окно программной моделирующей среды

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

Для ТС типа необитаемый батискаф, траектория движения к целевому объекту планируется на основе карты подводного рельефа. Однако, если карта является

неточной или в районе погружения батискафа имеются объекты, отсутствующие на ней, то возникает задача формирования кратчайшей траектории обхода возникших навигационных опасностей в автоматическом режиме. Эта задача также решается при помощи бионического метода Формирование дискретной модели внешней среды в данном случае происходит на основе расстояний до элементов подводного рельефа, получаемых при помощи гидроакустической станции (ГАС) батискафа Трехмерная среда дискретизируется на фрагменты, расположенные в пяти элементарных секторах ло курсу движения батискафа. Для каждого элементарного сектора рассчитывается минимальное расстояние от корпуса батискафа до элементов подводного рельефа и сохраняются в массиве Б, В битовом массиве В хранятся признаки проходимости фрагментов среды Пусть МтЬ-длина элементарного фрагмента, а СигЬ- расстояние от корпуса батискафа на котором происходит проверка наличия элементов подводного рельефа Тогда алгоритм формирования дискретной модели проходимости внешней среды можно представить в виде, показанном на рисунке 9 Данный алгоритм построен таким образом, что массив В[1]^] заполняется по столбцам, каждый из которых соответствует элементарному сектору Определение проходимости фрагментов происходит по результатам сравнения величин СигЬ и Э[}]. Если СигЬ<0[)], то фрагмент, соответствующий элементу В[)][;] свободен для перемещения батискафа (В[1][)]=0), иначе он занят рельефом

1 М

2 1=0,

3 СигЬ'МшЬ,

4 если СигЬ <0[Ц,то ВДЯ = 1,иначе В[1]Ц] -0,

5 1=ч+1,

6 Сш1=СигЬ+МтЬ,

7 если К10, то переход к п4, иначе - следующий шаг,

8 я«,

9 если]<5,то переход к п.2, иначе - останов

Рисунок 9-Алгоритм формирования дискретной модели среды

угла поворота корпуса батискафа

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

С целью внедрения результатов, полученных в работе, в рамках учебного процесса разработана программная среда AgentSelfAdapt Эта программа позволяет студентам в интерактивном режиме выбирать тип среды функционирования агента, задавать взаимное расположение агента, препятствий и цели в ней, а также создавать и исследовать программные реализации алгоритмов решения навигационных задач С применением этой программной среды на кафедре вычислительной техники ТТИ ЮФУ поставлены 4 лабораторные работы, используемые при организации учебного процесса

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

Ь Оценки быстродействия разработанных алгоритмов показали, что скорость их рабочьг в случае полной аппаратной реализации в среднем в 50 раз выше, чем при нр :>! раммной Приведенные оценки дают возможность сделать вывод о том, что аппаратная реализация предлагаемых алгоритмов позволяет управлять ИА в условиях нестационарной внешней среды не только в реальном масштабе времени, но и с ел о опережением.

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

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

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

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

батискафа при отработке этой траектории

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

1 Chernukhin. Yu V, Priemko A A Method of an environment mapping in neural network control system of adaptive mobile robot Optical Memory and Neural Networks, Vol 15, №1,2006, p 45-49

2 Чернухин Ю В , Приемко А А Методика формирования карты внешней среды в системе управления адаптивного мобильного робота. Материалы III всероссийской научной конференции молодых ученых, аспирантов и студентов "ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, СИСТЕМНЫЙ АНАЛИЗ И УПРАВЛЕНИЕ " Таганрог Изд-во ТРТУ 2005, с 20-23

3 Чернухин Ю В , Приемко А А Формирование и использование карты внешней среды в задаче навигации адаптивного мобильного робота Материалы VIII всероссийской научно-технической конференции "НЕЙРОИНФОРМАТИКА 2006" Сборник трудов Часть 2 Москва Изд-во МГУ Л. 2006 с 8-12

4. Чернухин Ю В , Приемко А А Об одном методе локализации положения адаптивного мобильного робота при навигации по карте Материалы IX всероссийской научно-технической конференции "НЕЙРОИНФОРМАТИКА 2007 " Сборник научных трудов Часть 2 Москва Изд-во МГУЛ 2007, с 129-137.

5 Чернухин Ю В, Приемко А А Алгоритм навигации адаптивных мобильных роботов по автоматически формируемой карте в условиях динамически изменяющейся внешней среды Известия ТРТУ, Тематический выпуск "Интеллектуальные САПР", №1 2007 , с 46-51

6. Чернухин Ю В, Приемко А А Алгоритм самообучения

интеллектуальных мобильных роботов с нейросетевым управлением Материалы 14-ой международной конференции по нейрокибернетике "Проблемы нейрокибернетике" Сборник трудов Том 2 Ростов на Дону. Изд-во ООО "ЦВР" 2005, с 193-198

7 Чернухин Ю В , Писаренко С Н , Приемко А А Нейросетевая система навигационной безопасности транспортных объектов в наземной, подводной, надводной, и воздушной средах Международный научно-теоретический журнал "Искусственный интеллект" №3,2006, с 331-339

8 Чернухин Ю В , Приемко А А Особенности классификации подводных объектов в условиях неопределенности. Материалы научной конференции ППС ТРТУ Таганрог- Изд-во ТРТУ 2003, с 63

9 Чернухин Ю В, Приемко А А Метод отождествления подводных объектов на основе нечеткой логики Известия ТРТУ №8 Тематический выпуск "Интеллектуальные САПР" Таганрог, Изд-во ТРТУ 2006, с 5-10

10 Чернухин Ю В , Приемко А А Нейросетевая система навигационной безопасности судовождения Известия ТРТУ Специальный выпуск Материалы LII Научно-технической конференции, Таганрог, Изд-во ТРТУ 2006 с 83-87

Ill Чернухин ЮВ, Приемко А.А Трехмерная нейросеть адаптивного подводного робота. Известия ТРТУ. Тематический вьшуск. "Компьютерные технологии в науке инженерии и управлении"; Таганрог, 2006.C.100-103

12. Чернухин Ю.В , Приемко А.А. Авторское свидетельство об официальной регистрации программы «Программный комплекс моделирования самообучающихся нейросетевых систем управления мобильных роботов в условиях наземной среды», №2007611017, б марта, 2007 г.

13 Чернухин Ю В, Гузик В Ф Приемко А А. Авторское свидетельство об официальной регистрации программы «Программный комплекс моделирования нейросетевых систем обеспечения навигационной безопасности интеллектуальных агентов в различных средах», №2007611198,21 марта 2007г

14L Чернухин Ю В , Приемко А А. Программная, модель распознающей подсистемы адаптивного мобильного робота Материалы всероссийской научной конференции студентов и аспирантов "ТЕХНИЧЕСКАЯ КИБЕРНЕТИКА РАДИОЭЛЕКТРОНИКА И СИСТЕМЫ УПРАВЛЕНИЯ" Таганрог- Изд-во ТРТУ 2002,с 128.

В работах, опубликованных в соавторстве, лично автору принадлежат следующие результаты- в работах [1,2,3] - алгоритм формирования карты внешней среды интеллектуального агента, в работах [4,5] -алгоритм определения собственного положения интеллектуального агента на созданной карте, в работе [6] - алгоритм экстраполяции положения нестационарной цели во внешней среде на основе изучения ее поведения; в работах [7,8,9,10,11] - алгоритмы формирования модели внешней среды для интеллектуальных агентов типа надводный корабль и необитаемый батискаф, в работах [12-14] - программная реализация алгоритмов формирования карты среды, определения собственного положения на ней, а также формирования дискретной модели внешней среды

Аспирант

Приемко А А

Тип ТТИ ЮФУ Заказ №Жтир^экз

ВВЕДЕНИЕ.

1. АНАЛИЗ МЕТОДОВ НАВИГАЦИИ ИНТЕЛЛЕКТУАЛЬНЫХ

МОБИЛЬНЫХ АГЕНТОВ.

1.1 Интеллектуальные агенты мобильного типа и проблемы их навигации во внешней среде.

1.2. Традиционные методы решения навигационных задач.

1.3. Некоторые представления о решении навигационных задач живыми организмами.

1.4. Бионический метод решения навигационных задач.

1.5. Использование бионического метода при навигации по карте внешней среды.

1.6. Выводы.

2. РАЗРАБОТКА НЕЙРОСЕТЕВЫХ АЛГОРИТМОВ И СТРУКТУР ДЛЯ РЕШЕНИЯ НАВИГАЦИОННЫХ ЗАДАЧ ИНТЕЛЛЕКТУАЛЬНЫМИ МОБИЛЬНЫМИ АГЕНТАМИ.

2.1. Синтез алгоритма формирования карты проходимости внешней среды.

2.2. Синтез алгоритма масштабирования карты внешней среды.

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

2.4. Алгоритм навигации интеллектуального агента по карте внешней среды.

2.5. Синтез алгоритма экстраполяции положения цели на карте среды на основе изучения ее поведения.

2.6. Выводы.

3. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ РЕШЕНИЯ НАВИГАЦИОННЫХ ЗАДАЧ НА ПРОГРАММНЫХ МОДЕЛЯХ.

3.1. Программная моделирующая среда.

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

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

3.4. Выводы.

4. ИСПОЛЬЗОВАНИЕ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ ДЛЯ РЕШЕНИЯ ПРАКТИЧЕСКИХ ЗАДАЧ.

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

4.1.1. Алгоритм работы подсистемы.

4.1.2. Формирование дискретной модели проходимости внешней среды.

4.1.2.1. Локализация естественных навигационных опасностей на карте среды.

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

4.1.3. Отображение сформированной модели внешней среды в подсистему планирования безопасного маршрута движения.

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

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

4.2.1. Формирование модели внешней среды.

4.2.2. Определение скорости движения батискафа.

4.2.3. Экспериментальное исследование навигационной подсистемы управления батискафом.

4.3. Назначение программной среды AgentSelfadapt и основные приемы работы с ней.

4.3.1. Общая характеристика программной среды.

4.3.2. Интерфейс программной среды и основные приемы работы с ним для сред различных типов.

4.3.2.1. Интерфейс программы для работы с наземной средой.

4.3.2.2. Интерфейс программы для случая надводной и подводной сред.

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

4.3.4. Написание и отладка программ.

4.3.4.1. Результаты выполнения программ.

4.4. Выводы.

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

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

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

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

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

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

Эти обстоятельства приводят к необходимости синтеза специализированных многопроцессорных вычислительных систем нейросетевого типа на основе бионических подходов к управлению интеллектуальными агентами [7-10]. Естественным прообразом бионических управляющих систем служат нейронные сети мозга. Некоторые концептуальные представления о нейронных механизмах управления в живых организмах сформулированы П.К. Анохиным в виде функциональной системы [11]. Подобные механизмы использовались ранее при разработке однородных управляющих структур [8] AMP. В них восприятие внешней среды и обработка информации реализуется подобно тому, как это происходит в живых организмах. Для эффективной работы с такой информацией нейроэлементы в системе управления AMP организуются в виде параллельных вычислительных структур - нейропроцессорных сетей. Анализ показывает, что в большинстве случаев математические операции, выполняемые такими сетями, крайне просты и могут быть сведены к элементарным логическим операциям [7-9].

На основании описанных представлений был создан бионический метод управления AMP. В рамках этого метода разработаны нейросетевые алгоритмы планирования траектории движения к цели в условиях двумерной и трехмерной сред [9]. Синтезированные на основании этих алгоритмов системы управления были экспериментально проверены на специально изготовленных макетных образцах. Однако, в рамках данного метода остались недостаточно исследованными вопросы: формирования карты проходимости внешней среды на основе комплексного анализа информации, получаемой от дистантных и тактильных датчиков; определения собственного положения на карте на основе этой информации; поиска цели во внешней среде; экстраполяции положения цели на карте внешней среды на основе изучения ее поведения.

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

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

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

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

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

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

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

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

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

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

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

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

1. Всероссийской научной конференции студентов и аспирантов "ТЕХНИЧЕСКАЯ КИБЕРНЕТИКА РАДИОЭЛЕКТРОНИКА И СИСТЕМЫ УПРАВЛЕНИЯ" (Таганрог, ТРТУ, 2002 г.);

2. Научной конференции ППС ТРТУ (ТРТУ 2005г.);

3. 14-ой международной конференции по нейрокибернетике "Проблемы нейрокибернетики" (Ростов на Дону, РГУ,2005 г.);

4. Всероссийской научной конференции молодых ученых, аспирантов и студентов "ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, СИСТЕМНЫЙ АНАЛИЗ И УПРАВЛЕНИЕ " (Таганрог, ТРТУ, 2005 г.);

5. Всероссийской научно-технической конференции "НЕЙРОИНФОРМАТИКА 2006 " (Москва-, 2006 г.);

6. Всероссийской научно-технической конференции "НЕЙРОИНФОРМАТИКА 2007 " (Москва, 2007 г.).

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

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

71 наименования, содержит 106 рисунков, 1 таблицу и 4 приложения на 27 страницах.

4.4. Выводы

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

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

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

4. Для исследования алгоритмов решения навигационных задач интеллектуальными агентами в рамках учебного процесса была разработана среда AgentSelfAdapt. Эта программа позволяет студентам в интерактивном режиме выбирать тип среды функционирования агента, задавать взаимное расположение агента, препятствий и цели в среде, а также создавать и исследовать программные реализации алгоритмов решения навигационных задач. С применением этой программной среды на кафедре вычислительной техники ТТИ ЮФУ поставлены 4 лабораторные работы, используемые при организации учебного процесса.

181

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

183

1. Weiss G. Multiagent Systems. A Modern approach to distributed artificial intelligence. - Ma: M1. Press, 1996. - 585 p.

2. Юревич Е.И. Робототехника. СПб.: Изд-во СПбГТУ, 2001. - 300 с.

3. Jean-Paul Laumond. Robot motion planning and control, 1998. 343 p.

4. Козлов Ю.М. Адаптация и обучение в робототехнике- М.гНаука,1990. -248 с.

5. Интегральные роботы //Под ред. Поздняка Г.Е. М.:Мир, 1973. - 419 с.

6. От моделей повеления к искусственному интеллекту // Под ред. Редько В.Г. M.:URSS, 2006. - 447 с.

7. Чернухин Ю.В. Микропроцессорное и нейрокомпьютерное управление адаптивными мобильными роботами. Таганрог: ТРТИ, 1993. - 90 с.

8. Каляев А.В., Чернухин Ю.В., Носков В.П. Однородные управляющие структуры адаптивных роботов // Под ред. А.В. Каляева и Ю.В. Чернухина. -М.: Наука, 1990. 152 с.

9. Чернухин Ю.В. Нейропроцессорные сети. Таганрог: ТРТУ, 1999. -439 с.

10. Ю.Чернухин Ю.В. Искусственный интеллект и нейрокомпьютеры.

11. Таганрог: ТРТУ, 1999. 273 с. П.Анохин П.К. Принципиальные вопросы общей теории функциональных систем // Принципы системной организации функций. - М.: Наука, 1973. - С. 5-61.

12. Arleo A., Millan J., Floreano D. Efficient learning of variable-resolution cognitive maps for autonomous indoor navigation. IEEE Transactions on Robotics and Automation, 1999, Vol 15, No 6. P. 990-1000.

13. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы построение и анализ. -М: МЦНМО, 2001. 955 с.

14. Borenstein J., Feng L., Measurement and correction of systematic odometry errors in mobile robots. IEEE Transactions on Robotics and Automation,1991, Vol 7, №4.-P. 535-539.

15. Borenstein J., Karen Y., The vector field histogram fast obstacle avoidance for mobile robots. IEEE journal of Robotics and Automation, 1991, Vol 7, №3. - P. 278-288.

16. Borenstein J., Koren Y. Histogramic in-motion mapping for mobile robot obstacle avoidance. ШЕЕ Transactions on Robotics and Automation, 1991, Vol 7, No 4.-P. 535-539.

17. Filliat D., J.A. Meyer. Map based navigation in mobile robots. A review of localization strategies. Journal of Cognitive Systems Research, 2003, №4. -P. 243-282.

18. Filliat D., Meyer J-A. Global localization and topological map-learning for robot navigation. In Proceedings of the Six Conferences on Simulation of Adaptive Behavior, 2000. P. 140-150.

19. Mataric M. Integration of representation into goal-driven behavior-based robots. IEEE Transactions on Robotics and Automation, 1992, Vol 8, No 3. -P. 304-312.

20. Meyer J-A, Guillot A, Girard В., Khamassi M., Pirim P., Berthoz A. The Psikharpax project: Towards building an artificial rat. Robotics and autonomous Systems, 2005, Vol 50, №4, p.211-223.

21. Filliat D., J.A. Meyer. Active perception and map learning for robot navigation. Proceedings of the Sixth International Conference on Simulation of Adaptive Behavior. Cambridge: MIT Press, 2000. - P. 246-255.

22. Golovko V, Klimovich D. Neural system simulation for autonomous control of the mobile robot Proceedings of the Fifth International Conference of Advanced Computer Systems. Silesian Technical University. Szczecin, 1998.

23. Golovko V, Dimakov V. Architecture of Neural System for control of autonomous vehicles. In preprints of third IF AC symposium of intelligent autonomous vehicles. Madrid, Spain: Elsevier science Ltd.

24. Golovko V, Schilling K, Roth H, Sadykhov R, Albertos P, Dimakov V. The architecture of neural system for control of a mobile robot. In Proceedings of ICCNAI'99. Brest, Belarus, 1999. - P.57-61.

25. Tolman E.C. Cognitive maps in rats and men. Psychological Review, 1948, №55.27.0'Keefe, J. Dostrovsky. The hippocampus as spatial map, preliminary evidence from unit activity in the freely moving rat. Experimental brain research, 1971, №34.

26. Borghi G., Brugali D. Autonomous map learning for a multi-sensor mobile robot using dictiometric representation and negotiation mechanism. In Proceedings of the international conference of advanced robotics (ICAR 95).-IEEE Press, 1995.

27. Muratet L., Doncieux S., Meyer J-A. A contribution to Vision-Based Autonomous Helicopter flight in urban environments. In Proceedings of the International Session on Robotics, September 2004.

28. Cheng V.H. Concept development of automatic guidance for rotorcraft obstacle avoidance. IEEE transactions on robotics and automation, 1990, Vol.6, №2. P.252-257.

29. Carroll C.P, Stephen R.N., McClaren R.T. AUV path planning: An A* approach. Proc Symp. On AUV Technology.-Washington D.C., 1992.-P. 79-84.

30. WarrenW.C. A technique for autonomous underwater vehicle route planning IEEE Journal of Oceanic Engineering, 1990, Vol 15, №3.-P. 199-204.

31. Никольская K.A. Правила моделирования пространства млекопитающими. Материалы 13-ой международной конференции по нейрокибернетике "Проблемы нейрокибернетики". Сборник трудов. Т.2. Ростов- на- Дону: Изд-во ООО "ЦВР", 2005. - С. 192-195.

32. Trullier О., Meyer J.A. Place sequence learning for navigation, in: Artificial Neural Networks. ICCAN'97,1997. P. 757-762.

33. Jensen O., Idiart M., Lisman J. Physiologically realistic formation of auto associative memory in networks with theta/gamma oscillations: Role of fast NDMA channels. Learning and Memory, 1996, №3. P. 243-256.

34. Muller R., Stead M., Pach. J. The hippocampus as a cognitive graph. Journal of General Physiology, 1996, №2. P. 663-694.

35. Shmajuk N., Thieme A. Purposive behavior and cognitive mapping: A neural network model. Biological Cybernatics, 1992, №6. P. 165-174.

36. Анохин K.A. Естественный путь к искусственному интеллекту. Компьютерра, 2002, №41.

37. Adomi G., Cagnoni S., Enderle S. Vision-based localization for mobile robots. Robotics and Autonomous Systems, 2001, №36. P. 103-119.

38. Чернухин Ю.В., Приемко А.А. Алгоритм навигации адаптивных мобильных роботов по автоматически формируемой карте в условиях динамически изменяющейся внешней среды. Известия ТРТУ, Тематический выпуск "Интеллектуальные САПР", 2007, №1. С.46-51.

39. Чернухин Ю.В., Приемко А.А. Особенности классификации подводных объектов в условиях неопределенности //Материалы научной конференции ППС ТРТУ. Таганрог: Изд-во ТРТУ, 2003, №1. - С. 63.

40. Чернухин Ю.В., Приемко А.А Метод отождествления подводных объектов на основе нечеткой логики. Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: ТРТУ, 2006, №8. -С.5-10.

41. Чернухин Ю.В., Приемко А.А. Нейросетевая система навигационной безопасности судовождения. Известия ТРТУ. Специальный выпуск. Материалы LII Научно-технической конференции. Таганрог, 2006. -С. 83-87.

42. Чернухин Ю.В., Приемко А.А. Трехмерная нейросеть адаптивного подводного робота. Известия ТРТУ. Тематический выпуск: "Компьютерные технологии в науке инженерии и управлении". -Таганрог: ТРТУ, 2005. С. 100-103.

43. Чернухин Ю.В., Приемко А.А. Авторское свидетельство об официальной регистрации программы «Программный комплекс моделирования самообучающихся нейросетевых систем управления мобильных роботов в условиях наземной среды», №2007611017, 6 марта, 2007 г.

44. Chernukhin Yu.V., Priemko А.А. Method of an environment mapping in neural network control system of adaptive mobile robot. Optical memory and Neural Networks. NY: Allerton Press, 2006, Vol.15, №1. - P. 45-49.

45. Brooks R. Elephants Don't Play Chess. "Designing Autonomous Agents: Theory and Practice from Biology to Engineering and Back". Cambridge: MIT Press, 1990.-P. 3-15.

46. Brooks R. Intelligence without representation. Artificial Intelligence, 1991, Vol 47.-P. 139-159.

47. Clark M.R., Anderson G.T., Skinner R.D. Coupled Oscillator Control of Autonomous Mobile Robots. Autonomous Robots, 2000, Vol 9.-P. 189-198.

48. Grasso F., Consi T. R., Mountain D. C. , Atema J. Biomimetic Robot Lobster Performs Chemo-orientation in Turbulence Using a Pair of Spatially Separated Sensors: Progress and Challenges. Robotics and Autonomous Systems, 2000, Vol 30. P.l 15-131.

49. Баас P., Фервай M. Delphi 4. Полное руководство. Киев: Изд-во BHV, 1999. - 797 с.

50. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. Москва: Изд-во Бином,1998. - 558 с.

51. Ласло М. Вычислительная геометрия и компьютерная графика на С++: Пер. с англ. М.: БИНОМ, 1997. 356 с.

52. Павлидис Т. Алгоритмы машинной графики и обработки изображений. -М.: 1989.-400 с.

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

54. Сван Т. Освоение Turbo Assembler. Санкт Петербург: Изд-во Диалектика, 1996. - 544с.

55. Скэнлон Л. Персональные ЭВМ ЮМ PC и XT. Программирование на языке ассемблера. Москва: Изд-во Радио и связь, 1989. -. 336 с.

56. Мешков А, Тихомиров Ю. Visual С++ и MFC. 2 издание. Санкт Петербург: Изд-во "БХВ-Санкт-Петербург", 1999. - 1020 с.

57. Физические основы подводной акустики: Пер. с англ. М.'Советское радио, 1955.

58. Евтютов А.П., Митько В.Б. Инженерные расчеты в гидроакустике. Л.: Судостроение, 1988.

59. Takagi Т., Sugeno М. Fuzzy identification of systems and its application to modeling and control. IEEE Transactions on SMC, 1985. P. 116-132.70.0ссовский С. Нейронные сети для обработки информации. М. "Финансы и статистика", 2002. - 343 с.

60. Takagi Т., Sugeno M. Fuzzy identification of systems and its application to modeling and control. IEEE Transactions on SMC, 1985. P. 116-132.