Исследования в области искусственного интеллекта активно и являются актуальными во многих отраслях науки и техники. В начале 80-х годов в исследованиях появляется новое направление, называемое «Искусственная Жизнь», в задачи которого входят создание и изучение «более общих форм жизни» [1−3]. Исследователи ставили своей целью понимание общих принципов организации биологической жизни. Результаты, полученные в данной области, планировалось применить в таких областях как разработка мобильных роботов, медицина, социология, биология и других [4−8]. Направление базировалось на моделях, разработанных в 60-х годах M.JI. Цетлиным и М. М. Бонгардом, которые разработали ряд моделей, способных приспосабливаться к окружающей среде [9−11]. Модели не были реализованы технологически из-за своей громоздкости и вычислительной сложности.
В 90-х годах складывается еще одно направление, тесно связанное с «Искусственной Жизнью», называемое «Адаптивное Поведение», в задачи которого входит исследование принципов совместного функционирования животных в условиях изменяющейся среды [12, 13]. Исследователи, работающие в данном направлении стремятся проанализировать эволюционное развитие познавательных способностей животных и человека и получить модель зарождения и развития человеческого интеллекта [14, 15].
Основной метод работы в данном направлении — проведение компьютерного моделирования развития сообществ искусственных существ, способных приспосабливаться к окружающей среде. Эти созданияавтономные роботы, наделенные некоторыми чертами поведения животных, их назвали «аниматами», от слов «animal» и «robot» [16−18]. Для исследований в области «Адаптивное Поведение» характерен специализированный метод конструирования архитектуры, обеспечивающей «интеллектуальное» поведение аниматов — исследователь сам разрабатывает данные архитектуры, по аналогии с теми структурами, которые обеспечивают адаптивное поведение у реальных животных, например, моделируя потребности живого организма и механизм их удовлетворения [4, 19].
Исследователь также конструирует внешний мир для эволюционной системы, задавая физические законы и параметры, исходя из конкретных задач. Существа способны поддерживать свою жизнь, размножаться, гибнуть, взаимодействовать друг с другом. Механизм размножения искусственных существ позаимствован у биологических «аналогов»: родители передают ребенку свою генную информацию, которая определяет схему поведения животного, его параметры и т. д. При передаче информации возможны случайные мутации [20−22].
Сообщества аниматов относят к классу многоагентных компьютерных систем. Ключевое отличие моделей аниматов от других многоагентных систем является наличие эволюционных изменений в популяции, ее развитие за счет появление новых аниматов (аниматов-потомков), несущих измененную генную информацию, подверженную также случайным мутациям. В общем случае, метод компьютерного моделирования искусственной жизни является стохастическим и его можно рассматривать как подмножество методов Монте-Карло [23].
Область применения моделей искусственной жизни разнообразна: -случаи сложного и разнообразного поведения отдельных индивидуумов, например, в зависимости от локального окружения, приводящие к трудностям в получении системы уравнений, описывающих динамику популяции;
— решение трудно формализуемых задач- -исследование когнитивной эволюции животных- -задачи «управления роем» [12, [24−26].
Этот круг задач и определяет основное отличие «Адаптивного Поведения» и «Искусственной Жизни» от остальных исследований в области искусственного интеллекта: «создание аниматов ориентировано в конечном итоге на решение ими нечетко сформулированных задач в плохо предсказуемой среде — т. е. таких, с которыми приходится иметь дело живым организмам. Аниматы создаются не для игры в шахматы, а для таких задач, как исследование поверхности планет в условиях, когда время и ресурсы робота ограничены, а местность не изучена» [27].
Сегодня можно также наблюдать бурное развитие именно тех технологий, для которых теория аниматов может быть использована в полной мере: нанотехнологий в роботостроении и рост вычислительных мощностей компьютерной техники [28].
Развитие индустрии компьютерных технологий привело сегодня к росту развития виртуальных пространств, заселенных виртуальными существами: программные агенты помогают модераторам отслеживать контент, отвечают на вопросы пользователей, являются партнерами человека в стратегических играх, следят за обновлениями новостей, отвечают за безопасность систем, осущетвляют тематический поиск в сети. Примеры таких виртуальных агентов можно увидеть на сайтах Ananova, Microsoft, Codeprogect, CodeGuru и других. Эти системы широко используются сегодня и имеют огромные перспективы развития. Рекламируя свою новую разработку в среде IT, компания Microsoft также обратилась к аниматам — в 2003;2004 году был проведен конкурс на лучшее искусственное животное в нити проектов MicrosoftResearch.
Теория аниматов нашла свое применение и в кино — для создания массовых батальных сцен создатели одного из самых кассовых фильмов «Властелин Колец» использовали компьютерную графику в сумме с моделированием поведения аниматов. Было написано специальное программное обеспечение для моделирования сражений существ двух видов, на основе которого были отрисованы сцены массовых сражений [24, 29].
Развитие технологий роботостроения в сторону уменьшения размеров привело к созданию многих проектов, которые также используют теорию аниматов для управления. Например, в 2002 году в Intelligent Autonomous.
Systems Laboratory Британского Университета был создан робот-садовник, небольшой мобильный робот для «ручной» очистки сада от слизняков. Робот получил название SlugBot, был опробован на реальных задачах и одобрен пользователями. С точки зрения «Адаптивного Поведения» SlugBot — не анимат в чистом виде, т.к. в сообществе роботов пока не реализованы механизмы самовоспроизведения, но, тем не менее, сообщество таких роботов может быть наделено «стадностью», они адаптивны, и это одна из первых весьма удачных разработок в данной области науки [30]. Беспилотные автобусы, построенные к проведению выставки EXPO 2005 компанией Toyota, также можно отнести к категории таких удачных моделей: автобусы имеют цель движения, собираются в стаи и разъединяются для выполнения собственных локальных задач [31].
Современные проекты с использованием нанороботов также пока не включают этап самовоспроизводства, но в будущем вполне могут это сделать согласно проекту «Roboblood», предлагающему заменить кровяные тельца человека сообществом нанороботов в ближайшем будущем [32].
Согласно описаниям этих настоящих и будущих проектов можно прогнозировать стремительное развитие теории аниматов, как одного из возможных путей управления роем нанороботов, а также интеллектуализации компьютерных игр и виртуальных сред, что указывает на актуальность работ в области построение моделей в областях «Искусственная Жизнь» и «Адаптивное Поведение».
Целью данной диссертационной работы является повышение эффективности существующих моделей сообществ аниматов, за счет разработки новой модели анимата, вычислительная сложность которой не превышает оценок nlog2(n), и затраты на модернизацию и адаптацию к конкретной задаче не превышают полиномиальных оценок. Рабочей гипотезой является предположение о том, что достичь поставленной цели можно, используя математический аппарат вероятностных автоматов.
Для достижения поставленной цели в работе решались следующие основные задачи:
• анализ разработанных на данный момент моделей аниматов, а также моделей организации сообществ аниматов, анализ затруднений, возникающих при реализации тех или иных моделей, анализ трудозатрат на реализацию и модернизацию существующих моделей;
• построение общей рабочей модели анимата, а также модели сообщества аниматов, оценка качества полученной модели, сравнение с аналогами;
• абстрактный синтез автомата, принимающего решение о конкретном действии в данной ситуации, разработка универсального входного алфавита, классификация ситуаций состояния внешней и внутренней среды анимата с использованием фильтров восприятия;
• построение алгоритма обучения анимата в условиях активной внешней среды.
Научная новизна данной работы заключается в следующем:
— разработана модель анимата на основе математического аппарата вероятностных автоматов;
— количество состояний внешней и внутренней среды сокращено за счет включения механизма фильтров восприятия в процесс сбора информации о состоянии среды;
— разработан универсальный входной алфавит для анимата, описывающий группы состояний внешнего и внутреннего мира, на основе аппарата регулярных выражений;
— разработан метод обучения аниматов на основе успешности выполняемых действий. Практическую ценность представляют:
— предложенная модель анимата на основе разработанного вероятностного автомата;
— разработанный алгоритм фильтрации информации о ситуациях внутреннего и внешнего мира анимата;
— принцип построения входного алфавита на основе группировки схожих ситуаций;
— полученные экспериментально оптимальные схемы поведения «животных» в результате эволюционных изменений в сообществе аниматов.
Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные САПР» (пос. Дивноморское 2004 г.), на Всероссийскх научных конференциях студентов и аспирантов «Радиоэлектроника, микроэлектроника, системы связи и управления» (г. Таганрог 2002 — 2004 гг.), внутривузовских конференциях ТРТУ (2004 г.). Результаты диссертации отражены в 8 печатных работах. Основные результаты данной работы были использованы в г/б НИР № 12 353 «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений». Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ. Использование результатов диссертационной работы подтверждено соответствующими актами.
Диссертационная работа состоит из введения, четырех глав, заключения, приложений, списка использованной литературы из 114 источников и содержит 143 страницы основного текста, 46 рисунков и 17 таблиц. Общий объем работы 150 страниц.
4.6. Выводы.
В результате практической работы была реализована программа на языке С#, объемом 71 Kb исходного кода и 32 Kb исполняемого кода. Программа работает под Microsoft .Net FrameWork 1.0, требует не менее 128 Kb ОЗУ. В процессе работы программа сохраняет информацию о модели в базу данных формата mdb.
Анализ результатов экспериментов № 1 — 4 позволяет сделать ряд выводов.
1. Разработанная в данной работе модель обладает более высоким быстродействием, чем модели, основанные на нейросетевых алгоритмах, преобладающие на данный момент в научно-исследовательском направлении «Искусственная Жизнь». Полученная программа позволила получить 40%-ное понижение временных затрат на моделирование.
2. Модель реализована качественно, экспериментальное быстродействие отличается от расчетного в рамках допустимых отклонений.
3. Полученная модель искусственной жизни функционирует успешно, животные развиваются, размеры популяции растут до некоторых пределов, определяемых размерами поля и количеством пищи. Полученные в результате моделирования эволюции стратегии поведения соответствуют ожидаемым — стратегии поведения обеспечивают как выживаемость отдельного существа, так и популяции в целом. Результаты моделирования в целом, соответствуют результатам других исследователей направления «Искусственная Жизнь».
4. В результате экспериментов выявлено позитивное влияние социальных мотиваций на процесс эволюции популяции.
Обобщая все вышесказанное, можно заключить, что реализованная в рамках данной работы модель полностью соответствует поставленной задаче: модель анимата имеет линейную сложность (большинство существующих моделей имеет квадратичную), модель позволяет получить стратегии поведения в условиях изменяющейся среды, выработанные аниматами стратегии поведения близки к оптимальным стратегиям, полученным другими исследователями направления.
Результаты экспериментов говорят также о том, что гипотеза о упрощении вычислительной сложности модели при применении математического аппарата вероятностных автоматов в построении блока принимающего решения подтверждается не только теоретически, но и экспериментально.
Заключение
.
В рамках данной диссертационной работы были получены следующие результаты:
1. Проведен анализ существующих на данный момент разработок в направлениях «Адаптивное Поведение» и «Искусственная Жизнь». Рассмотрены достоинства и недостатки существующих систем, выявлены основные проблемы реализации таких систем. Основной причиной затруднений в реализации является их вычислительная сложность, на этом основании были сделаны выводы о необходимости разработки новой модели, обладающей более высоким быстродействием.
2. Проанализированы возможные методы организации модели управления аниматом, выявлены наиболее перспективные методы, в частности, метод организации модели на базе конечного автомата. Предварительная оценка затрат на поддержку и модернизацию такой модели показали ее оптимальность.
3. Произведен абстрактный синтез автомата для реализации модели управления аниматом. Разработан механизм фильтров восприятия аниматом ситуаций внешней и внутренней среды, что позволило отсеять лишнюю информацию, и как следствие, оптимизировать входной алфавит автомата. Использование фильтров также позволило сделать входной алфавит автомата универсальным для всех видов искусственных существ. Разработан алгоритм разбора ситуаций внешнего мира, позволяющий значительно сократить временные затраты по принятию решения о рекомендуемом действии анимата.
4. В целях проведения компьютерного моделирования были разработаны программные модули, реализующие вышеуказанные алгоритмы. Разработан план эксперимента, проведено моделирование согласно ранее разработанному плану. Полученные экспериментальные данные (динамика изменения популяции, выработанные стратегии поведения) были сравнены с результатами аналогичных исследований в данной области. Результаты сравнения говорят о 40%-ном повышении эффективности модели оп сравнению с моделью «Кузнечик».
5. На базе материалов данной диссертационной работы были опубликованы статьи и тезисы докладов в журналах и сборниках конференций.
В результате проведенных теоретических и экспериментальных исследований была разработана модель анимата, обладающая более высоким быстродействием, чем существующие в данный момент аналоги. Временные затраты на моделирование поведения особи понижены на порядок по сравнению с моделью «Кузнечик» и ее модификациями. Экспериментальные оценки позволяют говорить о 40%-ном понижении временных затрат на работу модели.
Результаты серии проведенных экспериментов позволяют также утверждать, что результаты моделирования (выработанные аниматами эффективные стратегии поведения, качественные показатели модели) соответствуют результатам полученным в области «Искусственная Жизнь» и «Адаптивное Поведение» за последние 10 лет.
