Похожие публикации

На мероприятии присутствовали: Чрезвычайный и Полномочный Посол Республики Таджикистан в Республике Беларусь Козидавлат Коимдодов, директор департамента гуманит
Документ
На мероприятии присутствовали: Чрезвычайный и Полномочный Посол Республики Таджикистан в Республике Беларусь Козидавлат Коимдодов, директор департамен...полностью>>

О внесении изменений в Решение Екатеринбургской городской Думы от 28. 06. 2011 №48/44 Об утверждении Положения о департаменте архитектуры, градостроительст
Решение
Рассмотрев Постановление Администрации города Екатеринбурга от № «О внесении изменений в Решение Екатеринбургской городской Думы от 28.06.2011 № 48/44...полностью>>

Положение о коалиционной добровольческой акции
Документ
Весенняя неделя добра (ВНД) – коалиционная добровольческая акция, целью которой является продвижение идеи добровольчества как важного ресурса для реше...полностью>>

О проведении акции «Чистый лес» на территории города Губкинского
Документ
Во исполнение Указа Президента Российской Федерации от 11.08.2012 №1157 « О проведении в Российской Федерации Года охраны окружающей среды», в соответ...полностью>>



Навигация интеллектуальных агентов в сложных синтетических пространствах


САНКТ-ПЕТЕРБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

ЖУКОВ Сергей Юрьевич

НАВИГАЦИЯ ИНТЕЛЛЕКТУАЛЬНЫХ АГЕНТОВ В СЛОЖНЫХ СИНТЕТИЧЕСКИХ ПРОСТРАНСТВАХ

Специальность 05.13.16 – Применение вычислительной техники,
математического моделирования и математических методов
в научных исследованиях

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель д. ф.-м. наук Л. В. Петухов

Санкт-Петербург

2000

Оглавление

Оглавление 2

Введение 5

Моделирование поведения и анимации интеллектуальных агентов 7

Обзор методов решения задачи построения траектории движения 10

Постановка задачи 10

Методы, ориентированные на агента 13

Методы, ориентированные на пространство 16

Навигация интеллектуальных агентов 21

Постановка задачи 23

Представление синтетического пространства 26

Движение в синтетическом пространстве 27

Использование систем синтетического/технического зрения 28

Построение навигационных карт 29

Краткое содержание диссертационной работы 30

Глава 1. Задача навигации в синтетическом пространстве 33

1.1. Различные варианты постановки задачи навигации 33

1.1.1. Задача навигации в неизвестном пространстве 33

1.1.2. Навигация в неизвестном пространстве с использованием синтетического зрения 35

1.1.3. Навигация в известном пространстве (с предобработкой) 36

1.1.4. Выделение основных задач навигации 37

1.2. Способ решения основных задач навигации 38

1.2.1. Описание свойств агента по прохождению 38

1.2.2. Выделение свойств достижимости 41

1.2.3. Представление свойств достижимости 42

1.3. Задача построения навигационной карты пространства 44

1.3.1. Построение дескриптивной и метрической навигационной карты 46

1.3.2. Оптимизационная постановка задачи прохождения по карте 47

1.4. Основные результаты работы 48

Глава 2. Представление знаний о достижимости 50

2.1. Определения и предположения 50

2.2. Ассоциация 52

2.3. Представление дескриптивных навигационных свойств пространства 56

2.3.1. Звездность и полнота зон 56

2.3.2. Связность зон 56

2.3.3. Дескриптивная навигационная карта пространства 59

2.3.4. Вычислительная сложность задачи построения дескриптивной навигационной карты 60

2.4. Представление метрических навигационных свойств пространства 64

2.5. Условные свойства полноты и связности 67

Глава 3. Навигационная Система 70

3.1. Достройка графа достижимости 71

3.1.1. Построение дополнительных ребер 71

3.1.2. Оценка стоимости дополнительных ребер 73

3.2. Планирование пути по карте (модуль PP) 76

3.3. Система Прохождения (WS) 77

3.3.1. Оптимизация пути при прохождении 78

3.3.2. Алгоритм Прохождения (W) 80

Глава 4. Построение навигационной карты пространства 85

4.1. Дискретизация множества F 85

4.2. Построение звездных и полных зон в Fd 88

4.3. Построение дескриптивной навигационной карты. Алгоритм IDMC 90

4.4. Построение метрической карты пространства. Алгоритм IMMC 96

4.4.1. Построение метрической навигационной карты с полными и сильно связными зонами 101

4.4.2. Оптимизация алгоритма IMMC 103

Глава 5. Сходимость алгоритмов построения навигационной карты 105

5.1. Сходимость в 2D 106

5.1.1. Построение графа кратчайших путей 106

5.1.2. Сходимость алгоритма IMMC в непрерывном варианте 108

5.1.3. Сходимость алгоритма IMMC в дискретном варианте 109

5.2. Проблема сходимости в 3D 111

Глава 6. Навигация в синтетических пространствах 113

6.1. Навигация к движущейся цели 113

6.1.1. Сходимость Динамической Навигационной Системы 113

6.1.2. Перепланирование пути в DNS 115

6.2. Особенности практического применения 117

6.2.1. Проблема недетерминированности 117

6.2.2. Проблема дискретности 118

6.2.3. Генерация множества Fd 120

Заключение 121

Литература 123

Приложение 128


Введение

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

Основной задачей систем ВР является предоставление пользователю возможности “присутствовать” в виртуальном пространстве, перемещаться в нем, наблюдать его, а также взаимодействовать с пространством, объектами и персонажами - интеллектуальными агентами (intelligent agents), находящимися (“живущими”) в созданном синтетическом мире. Обязательным требованием к системам ВР является минимальное время отклика на действия пользователя, в частности на перемещение точки наблюдения, что определяет необходимость отображения пространства со скоростью не менее 5 кадров в секунду (обычно 15-30 кадров в секунду).

Основными задачами при создании систем виртуальной реальности являются:

  • реалистичное отображение синтетического пространства;

  • отображение движущихся объектов и интеллектуальных агентов, в том числе движение (анимация) объектов и поведенческая анимация (behavioral animation) интеллектуальных агентов;

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

Задача реалистичного изображения синтетического пространства для систем ВР успешно решается в течение вот уже нескольких десятков лет 6.2.36.2.3. Основными направлениями исследований являются: представление виртуального пространства, алгоритмы визуализации (rendering pipeline) 6.2.36.2.36.2.3, предобработка и оптимизация геометрического представления пространства 6.2.36.2.36.2.36.2.3, освещение 6.2.36.2.36.2.36.2.3, и т.п..

В настоящее время предложено большое количество методов решения задачи анимации объектов и агентов в системах виртуальной реальности. Так, в 6.2.3 описано задание движений с помощью прямой или инверсной кинематики (forward/inverse kinematics). В 6.2.36.2.3 описаны современные направления по вычислению переходов между движениями (motion transitions). В 6.2.36.2.3 описан процедурный подход к созданию более качественных (натуралистичных) движений интеллектуальных агентов при прохождении по сложной поверхности.

Под обеспечением реалистичного взаимодействия пользователя с виртуальным пространством подразумеваются как программно-аппаратные средства, обеспечивающие передачу команд и воссоздающие “ощущения” от взаимодействия с виртуальной средой (например, force feedback devices), так и программные модули, имитирующие столкновение виртуального образа пользователя с пространством 6.2.36.2.3, “выполнение” физических законов в виртуальном мире и кинематических ограничений при движении агентов (kinematic constraints) 6.2.3 и т.п.

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

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

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

Моделирование поведения и анимации интеллектуальных агентов

Задачу реалистичного отображения движения, поведения и анимации интеллектуальных агентов в системах виртуальной реальности будем называть моделированием движения, поведения и анимации соответственно. Будем выделять три основных уровня моделирования поведения и анимации агентов: Верхний Уровень Управления, уровень Локальной Навигации, и Анимационную Систему.

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

На уровне Локальной Навигации происходит уточнение траектории движения на основе информации о пересечении со сценой и данных синтетического зрения (synthetic vision) или анализа поступающей видеоинформации. Происходит сопоставление дискретной карты пространства с тем, что реально “видит" интеллектуальный агент, а также отработка движущихся объектов и изменений в пространстве.

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

Части уровней моделирования поведения агентов, отвечающие за планирование пути и передвижение интеллектуального агента, образуют Навигационную Систему (NS, Navigation System) (Рис. 1).

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

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

Множество состояний агента на каждом уровне моделирования поведения обычно описывается в виде конечного автомата с функциями переходов 6.2.36.2.36.2.36.2.3. Для определения функции переходов между состояниями (что соответствует принятию решения агентом), вместо стандартного if-else подхода 6.2.36.2.36.2.36.2.3 более целесообразно применять метод, основанный на построении целевого функционала с последующим принятием решения в соответствии со значением функционала 6.2.36.2.36.2.3. Это позволяет заменить трудоемкое выписывание if-else конструкций, описывающих все возможные ситуации, на настройку системы посредством определения весовых параметров в минимизируемом выражении. Такой подход позволяет также эффективно стыковать решения, полученные на разных уровнях моделирования поведения, например, модифицировать путь, определенный уровнем Глобальной Навигации для выполнения локальных подзадач. Другой подход к принятию решений интеллектуальным агентом, основанный на “конкуренции поведений” рассмотрен в 6.2.36.2.3.

“Самообучение” интеллектуальных агентов

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

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

Одной из наиболее важных задач самообучения интеллектуальных агентов является получение знаний о навигационной структуре пространства (то есть о свойствах достижимости между различными точками пространства). Эти знания, представленные, например, в виде графов достижимости (accessibility graphs) 6.2.3, могут использоваться при планировании пути, при реализации различных стратегий поведения (например, смелая/трусливая) 6.2.36.2.3, в системах навигации с использованием синтетического зрения и т.п.

Обзор методов решения задачи построения траектории движения