Реферат


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


Содержание


1. Введение

2. Обзор технологий интерактивных комплексов

3. Искусственный интеллект

4. Проблема проектирования искусственного интеллекта

5. Выводы

6. Литература

Введение


Основной концепцией развития современной всемирной паутины является интерактивность и быстрая реакция на события. С появлением Web 2.0 интернет приобрел принципиально новое обличие, так как появились возможности простому пользователю без специальных знаний и умений создать свою страницу, не зная даже базовых принципов функционирования интернет.

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

  • онлайн приложения:
    • системы с использованием прогрессивных графических технологий (Flash, Silverlight и т д)
    • многопользовательские игры (в общем случае с использованием искусственного интеллекта)
  • оффлайн приложения:
    • тренажеры и симуляторы
    • игры для настольных компьютеров и игровых консолей (в том числе с использованием современных устройств, учитывающих перемещение игрока в реальном мире)


Актуальность

Актуальность выбранной темы необходимо рассматривать отдельно с позиций онлайн и оффлайн приложений.
Перспективы построения интерактивных миров в браузере стали вполне реальными с анонсированием технологии Adobe Flash Molehill. Использование графического ядра системы и 98% установок копий Adobe Flash по всему миру открывает возможности построения сложных систем, которые смогут отображать одновременно более 3 миллионов полигонов без замедлений. Очевидно, что такими системами сможет воспользоваться каждый, не зависимо от операционной системы и браузера.
Что касается оффлайн приложений, с появлением технологий Microsoft Kinect и PlayStation Move появились новые возможности как взаимодействия с персонажем, так и ориентации в пространстве и учета поведения самого пользователя. Технология Microsoft Kinect также находится в процессе портирования на платформу Flash.
С точки зрения разработки сценария поведения, с появлением различных новых технологий концепции построения сценариев взаимодействия с пользователем и принципы искусственного интеллекта, разработанные раннее, требуют существенного пересмотра вследствие появления расширенных возможностей.


Цели и задачи

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


Предполагаемая научная новизна

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


Планируемые практические результаты

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

Обзор технологий интерактивных комплексов


Microsoft Kinect и XNA (WPF)

Kinect — "контроллер без контроллера" для Xbox 360. Технология включает следующие принципы:

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

Изначально Microsoft разработала данное устройство в противовес PlayStation Move только для игровых консолей. На сегодняшний день устройство портированно под PC, энтузиастами созданны наборы драйверов. Официальных драйверов для PC от Microsoft пока нет.
Kinect открывает широкие возможности для эмуляции различного рода поведения. С появлением официальной поддержки для PC, это устройство ляжет в основу большинства симуляторов и тренажеров. При поддержке технологии XNA Games игры можно разрабатывать с пользователем-контроллером, а с помощью WPF появляется возможность создавать приложения с интерфейсом, взаимодействие с которым происходит частями тела в воздухе.
Kinect — это горизонтально расположенная коробка на небольшом круглом основании, которую помещают выше или ниже дисплея. Размеры — примерно 23 см в длину и 4 см в высоту. Состоит из двух сенсоров глубины, цветной видеокамеры и микрофонной решетки. Проприетарное программное обеспечение осуществляет полное 3-х мерное распознавание движений тела, мимики лица и голоса. Микрофонная решетка позволяет Xbox 360 производить локализацию источника звука и подавление шумов, что дает возможность говорить без наушников и микрофона Xbox Live. Датчик глубины состоит из инфракрасного проектора объединенного с монохромной КМОП-матрицей, что позволяет датчику Kinect получать трёхмерное изображение при любом естественном освещении.
Диапазон глубины и программа проекта позволяет автоматически калибровать датчик с учётом условий игры и окружающих условий, например мебели, находящейся в комнате.
Судя по недавнему патенту Microsoft, Kinect будет способен распознавать язык жестов. Пока патент касается только ASL, но, возможно, другие языки будут добавлены позже. Ожидается, что это расширит аудиторию пользователей и поможет обучать немых языку жестов. Однако, согласно официальному комментарию, эта особенность не будет включена в первую версию Kinect из-за сниженного в угоду цене разрешения камер. С другой стороны, Microsoft не отказывается от использования патента.


Adobe Flash и Molehill

В феврале 2011 года корпорация Adobe выпустила сборку инкубатор Flash 11 с новым API Molehill. Molehill - кодовое название нового метода отображения 2D и 3D графики. Это набор низкоуровневых команд графического процессора, которые включают расширенные возможности между разничными экранами и устройствами с использованием технологии Adobe Flash. Этот новый низкоуровневый интерфейс обеспечивает расширенные возможности разработки 2D и 3D приложений, обеспечивая гибкость и перемещение нагрузки на графическое ядро системы, что существенно повышает производительность. На сегодняшний день, Adobe Flash Player отображает тысячи неотсортированных полигонов примерно за 30 Гц. С новым программно-аппаратным интерфейсом, разработчик может использовать сотни тысяч отсортированных полигонов, которые отображаются в высоком разрешении на весь экран за 60 Гц. С помощью Molehill с Flash Player или Adobe Air можно создать сложный 3D мир, который будет доступен практически на каждом компьютере или устройстве, подключенном к Интернет.

Большинство передовых компаний, которые занимались раннее разработкой программных 3D-движков на Flash (AlternativaPlatform, Away3D, Papervision), активно поддержали Molehill разработку. Наиболее удачной разработкой на сегодняшний день является AlternativaPlatform.

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

Дизайнер комнат
Рисунок 1 - Интерактивный дизайнер помещений в браузере

Искусственный интеллект


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

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


Проблема выбора

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


Проблема безошибочности

Для большинства игр и симуляторов достаточно просто сделать пользователя проигравшим. Поэтому на сегодняшний день разработчики задаются вопросом: как повысить реалистичность искусственного интеллекта, который действует безошибочно?
Самый простой способ оглупить ИИ — граничить его вычислительные ресурсы. Конечно, программа сразу станет играть хуже. Для того же бильярда есть следующий вариант: добавлять к удару по правильной траектории случайную погрешность. Но проблема в том, что это снижает реализм игры. В этом случае компьютер начинает делать слишком глупые ошибки. Такие глупые, каких человек никогда бы не сделал.
Другими словами, обычное ухудшение качества игры ИИ не является достаточно реалистичным. Оно не доставляет удовольствия игроку.
Из этого положения есть один выход. Нужно сделать так, чтобы компьютер играл в полную силу, но при этом сдавал игру. Как в спорте — ряд мелких, на первый взгляд, случайных просчётов, которые ведут к проигрышу или значительно увеличивают шансы противника. То есть ИИ должен делать умные, продуманные ошибки.
"Ошибки" такого рода требуют значительно больше вычислительных ресурсов, чем честная игра в полную силу, но зато у человека появится реальный шанс победить сильного соперника. От разработчиков игр требуется проявить недюжинный интеллект, чтобы создать искусственную глупость такого рода.
Чтобы сделать ИИ глупее, необходимо не уменьшить точность расчёта, а наоборот — увеличить её. Необходимо рассчитывать ходы в игре настолько далеко, чтобы человек даже не заподозрил подвоха. ИИ должен быть не просто умнее человека, а на две головы его умнее, чтобы реалистично ему поддаваться. Нужно предсказывать человека на несколько ходов вперёд, чтобы подстроить идеальную случайность, которой тот воспользуется. Или не воспользуется, но тогда проиграет. Но всё равно нужно дать ему шанс.


Проблема потери объекта

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


Рисунок 2 - Демонстрация потери объекта

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

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


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

Система принятия решений - СПР - любая система, которая принимает "ситуацию" на входе и генерирует "ответ" на выходе. Примером СПР может быть простая нейронная сеть, набор жестко заданных правил, набор нечетких логических правил. Наиболее важной особенностью системы должна являться ПРОСТОТА и ЛЕГКОСТЬ МОДИФИКАЦИИ - в частности она должна принимать на входе данные от малого, конечного возможного набора входных данных и генерировать на выходе подобный малый, конечный возможный набор выходных данных.

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

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

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

Эта система может представлять хорошую концептуальную модель для написания искусственного интеллекта в сложной стратегической игре. Дерево СПР может использоваться, для эмуляции цепочки командования в военной иерархии. Определенно, можно использовать относительно более простую СПР для каждого уровня. Входными данными для СПР уровня "k" будут выходные данные уровня "k+1", а выходные, в свою очередь, входными для "k-1" уровня. Выходные данные 0 уровня используются для обновления данных о территории (поле битвы).

Стратегия
Рисунок 3 - Схема построения стратегического искусственного интеллекта

На рисунке 3:
  • Генерал – малое количество параметров позволяют предвидение и рассуждения вида "что-если"
  • Солдаты – много параметров, но принимаемые решения простейшие, без попыток предвидения и рассуждений вида "что-если"
Основное преимущество этой схемы состоит в том, что она позволяет "более высоким уровням" иерархии формулировать стратегию, без того, чтобы сокрушиться огромным и труднообрабатываемым количеством возможностей, которые компьютерный AI должен был бы рассмотреть, обладай он только информацией об индивидуальных солдатах. Действительно, на самом верхнем уровне, решения будут довольно абстрактные:
  • "направлять все военные действия на захват территории X", или
  • "вести войну на истощение на территориях X, Y, и Z", или
  • "выиграть время - придерживаться дипломатии до некоторого времени", или
  • "избегать, прямых столкновений - концентрироваться на прерывании вражеской добычи ресурсов", и т.д.

При этих обстоятельствах, для компьютера будет возможно рассчитать ситуацию на следующий момент времени (предвидеть). В то время как при обычной системе AI в которой параметры, представлены действиями индивидуальных солдат, это невозможно.
Пример того, как это может быть:
Уровень 3 дает прика
  • расширение влияния на карте
Уровень 2 более конкретизирует этот приказ:
  • добыча ресурсов
  • атака противника
Уровень 1:
  • строительство юнитов для добычи ресурсов и строительства базы
  • строительство юнитов для атаки
  • отдача приказов юнитам
Уровень 0:
  • передвижение
  • атака
  • сбор
Предположим:
  • у0 передвигаясь заметил вражеских юнитов в позиции X,Y передал у1
  • у1 обработал полученные данные, дополнив их данными о количестве и силе врага и передал параметры у2
  • у2 просчитал шансы исходя из существующих на данный момент сил и вероятности их увеличения, как со своей, так и с вражеской стороны, и передал данные у3
Тогда:
  • у3 считает шансы на увеличение влияния на карте высокими и дает приказ на подавление противника у2
  • у2 выделяет необходимые силы, разрабатывает стратегический план и дает приказ на атаку этой группы противника у1
  • у1 делит силы на группы, строит группы и дает приказ на атаку каждого отдельного вражеского юнита у0

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

Выводы


Существует множество ниш для создания уникальных сценариев поведения. Эти ниши были созданы новыми технологиями. Также существует широкий выбор технологий, где можно использовать полученные в ходе исследований результаты, проверяя и редактируя разработанную модель алгоритма. При рассмотрении средств для исследования сценариев поведения в интерактивных комплексах в онлайн следует склониться в сторону технологии AlternativaPlatform с использованием Adobe Molehill, так как данные технологии являются перспективными и имеют хорошую поддержку. В настольных решениях для исследования предпочтительно использовать Microsoft Kinect и XNA Games.

Литература


1. Stage3D APIs for Adobe Flash Player and Adobe AIR - Adobe Labs
Интернет-ресурс. Режим доступа - URL: http://labs.adobe.com

2. Джоб Макар. Секреты разработки игр в Macromedia Flash MX.

3. Анатолий Ализар. Как научить ИИ делать продуманные ошибки
Интернет-ресурс. Режим доступа - URL: http://habrahabr.ru

4. Lennart Steinke. Искусственный интеллект в играх: передвижения монстров.
Интернет-ресурс. Режим доступа - URL: http://www.iskint.ru

5. AlternativaPlatform
Интернет-ресурс. Режим доступа - URL: http://alternativaplatform.com

6. David Bliss. Using Kinect within Flash Applications.
Интернет-ресурс. Режим доступа - URL: http://odopod.com

7. Елена Сагалаева. Искусственный интеллект в играх.
Интернет-ресурс. Режим доступа - URL: http://www.addconf.ru

8. Алекс Дж. Шампандар. Искусственный интеллект в компьютерных играх: как обучить виртуальные персонажи реагировать на внешние воздействия.

9. Kinect
Интернет-ресурс. Режим доступа - URL: http://ru.wikipedia.org

10. Ричард Псмит (Андрей Ленский). Что такое хороший сценарий?
Интернет-ресурс. Режим доступа - URL: http://lki.ru

11. Andrew Luppnow. Проблема проектирования искусственного интелекта
Интернет-ресурс. Режим доступа - URL: http://www.realcoding.net




* При написании данного автореферата магистерская работа еще не завершена. Окончательное завершение — 1 декабря 2011 г. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.