Мир аниматов. Первые дни творения (стр. 1 )

Мир аниматов. Первые дни творения

Работа выполнена учеником 11 класса НОУ «Лицей №36» ОаО РЖД, МБОУ ДОД ЦДТТ г. Иркутска

Глушковым Олегом Андреевичем.

Научный руководитель: , педагог дополнительного образования

МБОУ ДОД ЦДТТ

Цель: Создание примитивной виртуальной модели реального мира и население его виртуальными персонажами управляемыми искусственным интеллектом, для последующего проведения экспериментов.

Задачи:

1.  Создание Мира.

1.1.  Выбор графической библиотеки.

1.2.  Создание системы представления мира.

1.3.  Разработка оптимизированного алгоритма реагирования на столкновения.

1.4.  Разработка системы данных.

1.5.  Оптимизация рендеринга[1].

2.  Создание первого анимата.

2.1.  Создание модели анимата, как объекта в модели мира.

2.2.  Анализ существующих подходов к созданию искусственного разума.

2.3.  Формирование и реализация собственной концепции разработки примитивного обучающегося ИИ.

Введение

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

Литературный обзор

Проблема искусственного интеллекта достаточно широко освещена в литературе, наиболее близко к нашей идее её рассматривает Алекс Шампандар в своей книге «Искусственный интеллект в компьютерных играх. Как обучить виртуальные персонажи реагировать на внешние воздействия». В этом труде мы нашли такое понятие как «Воплощённый Анимат»[2] с подробным описанием методов его внедрения. Расширить наш кругозор в области науки об искусственном интеллекте помогли книги «Компьютер Обретает Разум», «Системы искусственного интеллекта. Практический курс.» (Авторы Чулков, Астахова, Потапов и другие) и … Лучше узнать действенные подходы к реализации помогли книги Александра Аркадьевича Жданова «Автономный искусственный интеллект» и и труд , и «Нечеткие модели и сети» а также «Основы Теории нечётких множеств» и книга «Понятие лингвистической переменной и его применение к принятию приближенных решений».

Для практической деятельности пригодились знания из книг «Алгоритмы» Стивена

Скиена, «С/С++ Программирование на языке высокого уровня» Татьяны Павловской и книга Бьёрна Страуструпа «Язык программирования С++».

Создание Мира

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

Примем априори[3] следующие факты:

1.  Теория Близкодействия. Согласно ей физики считают, что тела оказывают друг на друга действие лишь при контакте, так будет и у нас. Следовательно, возможно лишь одно событие между объектами мира – Соприкосновение, длящееся какое-либо время.

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

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

Далее следует ряд упрощений для первой модели (мы не уверены в их необходимости и потому возможно они изменятся впоследствии):

1.  Дискретно непрерывная структура. В своей работе Шампандар рассуждал о выборе между дискретной и непрерывной структурой в представлении мира. Каждый вариант имеет свои плюсы и минусы. Мы решили последовать примеру некоторых современных компаний и попытаться объединить эти понятия в своей модели. Прежде всего, мы делим всё пространство на две категории: Физические объекты и ландшафт. Объектам даём координаты в непрерывной системе отсчета. Ландшафт представляем дискретным.

Итак, Ландшафт представляет собой трёхмерную матрицу, наложенную на основное пространство. Каждая ячейка матрицы является прямоугольным параллелепипедом и имеет константные габаритные размеры, равные для всех ячеек. Каждая ячейка равномерно заполнена одним материалом (пустая = заполненная воздухом) и имеет ряд характеристик. Мы получаем, что каждый непрерывный объект находится в нескольких дискретных ячейках, а значит, соприкасается с ними (ячейку в определённом смысле считаем объектом). Это представление позволяет использовать положительные стороны обоих подходов. Благодаря дискретности ландшафт легко хранить, редактировать и обрабатывать (что может быть проще матрицы?), а тот факт, что мы не свели объекты к дискретным позволяет сохранить большую правдоподобность.

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

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

Выбор графической библиотеки

Одна из проблем, вставших перед нами, это выбор библиотеке для обработки графики, ибо на вывод графики уходит большинство вычислительного ресурса. Посовещавшись, мы решили не заниматься отображением 3D, ввиду того факта, что с этим связан целый ряд сложностей, да и долгая обработка не сулит ничего хорошего. Было принято решение отображать мир в изометрической проекции, такая графика может показать объём, и вместе с тем весьма экономична (С нашей точки зрения, 2D выводится быстрее).

Поэтому поиск сводился к средствам для рендеринга спрайтового[6] изображения. Имеется целый ряд вариаций библиотек. Мы избрали Microsoft XNA Framework[7], так как компания Microsoft уже долгое время работает над ней. XNA Framework обеспечивает необходимые компоненты для работы с графикой в играх, анимационных роликах и других приложениях.

Разработка оптимизированного алгоритма реагирования на столкновения

Рассмотрим самый обычный метод проверки столкновений на двухмерной плоскости (Рис. 3):

·  Мы описываем около каждого объекта мира окружность.

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

Но этот подход имеет два значительных минуса.

1.  Одна описанная окружность задаёт достаточно низкую точность определения столкновений (Рис. 4).

Как видно по рисунку окружности пересеклись, а вот объекты нет. Сразу появляется идея брать несколько окружностей, что, несомненно, поможет повысить точность (Рис. 5), но мешает вторая проблема.

2.  Сложность проверки по этому алгоритму очень велика и равна kn2. (Где n количество окружностей). Ибо каждый кружок сравнивается со всеми остальными. Посему увеличение количества кружков описывающих объект крайне нерентабельно.

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

Суть такова:

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

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

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