Введение к работе
Актуальность темы. Системы виртуальной реальности (системы ВР) получили в настоящее время широкое распространение в качестве трехмерных тренажеров и симуляторов, видеоигр, разнообразных систем визуализации, виртуальных www-пространств и т.п. Основной задачей систем ВР является предоставление пользователю возможности "присутствовать" в виртуальном пространстве, перемещаться в нем, наблюдать его, а также взаимодействовать с пространством, объектами и персонажами - интеллектуальными агентами, находящимися ("живущими") в созданном синтетическом мире. Обязательным требованием к системам ВР является минимальное время отклика на действия пользователя, в частности на перемещение точки наблюдения, что определяет необходимость отображения пространства со скоростью не менее 5 кадров в секунду (обычно 15-30 кадров в секунду).
Основными задачами при создании систем виртуальной реальности являются:
реалистичное отображение синтетического пространства;
отображение движущихся объектов и интеллектуальных агентов, в том числе движение (анимация) объектов и поведенческая анимация интеллектуальных агентов;
обеспечение реалистичного взаимодействия пользователя с виртуальным пространством и находящимися в нем объектами и агентами.
Наименее исследованной задачей является создание (моделирование) поведенческой анимации (или просто поведения) интеллектуальных агентов, что необходимо для обеспечения реалистичного взаимодействия пользователя с виртуальным пространством. Под поведением интеллектуального агента будем подразумевать его действия, которые обычно описываются терминами естественного языка, имеющими социальные, психологические или физиологические значения, и которые не обязательно тривиально сводятся к выполнению собственно анимации, то есть к движению эффекторов, скелета и т.п. (Thalmann, 1996).
Одной из наиболее важных задач, возникающих при моделировании поведения интеллектуальных агентов, является задача построения пути (траектории движения) в синтетическом пространстве. В системах ВР интеллектуальные агенты обычно имитируют движение аппаратов (или живых организмов) со многими степенями свободы, с кинематическими голономными и неголономными ограничениями. При этом, из-за ограниченных вычислительных ресурсов, количество степеней свободы у агентов значительно меньше. Так, агент может имитировать движение (ходьбу) человека, в трехмерном пространстве, имея только 4 степени свободы (позицию и ориентацию). Такая имитация движения агента в синтетическом пространстве обычно выполняется некоторой внешней процедурой (алгоритмом прохождения), которая может не отвечать необходимым требованиям гладкости и непрерывности. Все это приводит к тому, что
функция определения стоимости траектории может быть достаточно сложной и не являться непрерывной и аддитивной вдоль траектории движения.
Задача построения траектории движения интеллектуальных агентов имеет следующие основные особенности:
-
Задача построения траектории движения агентов не может быть сведена к "геометрической задаче" построения непрерывной траектории движения в свободном конфигурационном пространстве С/гее (как это принято при решении задачи планирования пути в робототехнике).
-
Стоимостная функция задается внешним алгоритмом и может принимать значение +оо. Стоимостная функция может не удовлетворять необходимым требованиям непрерывности и гладкости.
-
Стоимость получаемой траектории движения должна быть близка к стоимости оптимальной траектории (например, отличаться от нее не более чем в некоторое, наперед заданное число раз).
-
Задача обычно является массовой и допускает этап предобработки.
Дополнительно, задача построения траектории движения интеллектуальных агентов имеет следующие отличительные особенности:
-
Синтетическое пространство значительно более сложное, чем реальное пространство в котором обычно решаются задачи по планированию движения аппаратов или роботов (см. Рис. 2 и Рис. 3).
-
С другой стороны, размерность конфигурационного пространства С обычно невелика (2 или 3) и ограничения неголономного типа отсутствуют.
-
Нет неопределенностей и погрешностей в управлении агентом и в восприятии агентом окружающего пространства.
-
Все вычисления, необходимые для навигации и поведенческой анимации всех (!) интеллектуальных агентов, должны производиться в реальном времени, с загрузкой процессора не более 5-15%.
-
Агент обычно имеет доступ к геометрической карте пространства (хотя бы потому, что это пространство отображается в системе ВР), однако сложность пространства слишком велика для обработки в реальном времени (то есть для построения пути).
-
Способы передвижения интеллектуальных агентов могут быть произвольными и весьма сложными, что обусловлено, например, имитацией движений реальных или воображаемых персонажей. При этом, метод решения задачи навигации интеллектуальных агентов не должен зависеть от их способа передвижения, от сложности синтетического пространства и от способа его геометрического представления.
-
Необходимость обеспечения корректного взаимодействия агентов друг с другом и с виртуальным образом пользователя порождает ряд задач, которые пока еще мало исследовались в робототехнике (например, интерактивное преследование).
Задачу построения траектории движения, имеющую приведенные выше отличительные особенности, будем далее называть задачей навигации интеллектуальных агентов.
Указанные выше особенности задачи построения траектории движения агентов приводят к тому, что, к сожалению, результаты, полученные в таких областях, как вычислительная геометрия, робототехника, алгоритмическое планирование движения, не могут быть непосредственно использованы для решения задач навигации интеллектуальных агентов в сложных синтетических пространствах.
Решения некоторых частных тривиальных случаев задачи навигации интеллектуальных агентов предъявлялись многими исследователями (Badler, Thalmann, Noser). К сожалению, результаты, полученные в этой области, носят скорее эвристический и экспериментальный характер.
Данное исследование было обусловлено необходимостью создания общего метода решения задачи навигации интеллектуальных агентов с различным типом передвижения в сложных синтетических пространствах. Это привело к созданию нового подхода, основывающегося на выделении информации о достижимости в пространстве и представлении ее в виде навигационных карт (Zhukov 1998,1999, 2000).
Цель и задачи исследования. Целью диссертационной работы являлась разработка и обоснование общего метода решения задачи навигации интеллектуальных агентов в сложных синтетических трехмерных пространствах, который мог бы быть широко использован в практических приложениях (например, в системах виртуальной реальности).
Методы исследования. Для решения поставленных задач использованы методы дискретной математики и теории алгоритмов, вычислительной геометрии, робототехники, компьютерной графики, а также моделирование на компьютере.
Научную новизну составляют следующие результаты работы, являющиеся предметом защиты.
-
Выделение отличительных особенностей задачи планирования траектории движения интеллектуальных агентов (по сравнению с задачей планирования пути в робототехнике).
-
Формальное определение универсального способа выделения и представления знаний о достижимости в пространстве.
-
Математическое определение навигационной карты пространства. Определение дескриптивного, метрического и квази-метрического критериев для задачи построения навигационной карты.
-
Доказана NP-трудность задачи построения минимальной дескриптивной навигационной карты и NP-трудность ее приближенного решения (с точностью до аддитивной константы).
-
Формальное описание Навигационной Системы и анализ ее структуры. Получение критериев перепланирования пути. Анализ способов построения алгоритмов прохождения.
-
Разработка алгоритмов построения навигационной карты: алгоритм IDMC для решения дескриптивной задачи и алгоритм IMMC* для
решения метрической и квази-метрической задач. Доказательство корректности алгоритмов. Для алгоритма IDMC доказана оптимальность выполнения шагов достройки навигационной карты.
-
Определение понятия сходимости алгоритмов построения навигационной карты и получение оценок сходимости алгоритмов в различных случаях в 2D и 3D.
-
Решение задачи навигации к движущейся цели. Конструктивное доказательство существования сходящейся Динамической Навигационной Системы.
-
Анализ результатов- практического применения предложенных алгоритмов.
Практическая ценность работы состоит в создании и обосновании общих методов решения задачи навигации, пригодных для использования в практических приложениях (как в компьютерной графике, так и в робототехнике и ИИ). В работе детально определен процесс навигации по карте, выделены и исследованы такие функциональные модули, как алгоритм прохождения, перепланирование пути и т.п. Важно отметить, что все разработанные методы не зависят от способов передвижения агентов и сложности синтетического пространства.
Достоверность результатов обеспечивается использованием в диссертационной работе строгих методов дискретной математики и теории алгоритмов, вычислительной геометрии и теории сложности. Полученные в работе теоретические результаты подтверждаются данными, полученными в результате компьютерных экспериментов, а также при моделировании решения задачи навигации интеллектуальных агентов в реально работающих программных продуктах.
Апробация работы. Научные результаты и основные положения диссертационной работы докладывались и обсуждались на 7-ми международных конференциях - Computational Visual'97 (Мехико, Мексика), 7-ой и 8-ой Центрально-Европейской Конференции по Компьютерной графике и Визуализации (Пльзень, Чехия, 1997, 1998), 15-ой Конференции Еврографика-Англия (Норидж, Англия, 1997), 6-ой Конференции Скандинавских Стран по Искусственному Интеллекту (Хельсинки, Финляндия, 1997), Графикой'98 (Москва, 1998), Конференции по Компьютерной Графике и ее применению (Братислава, Словакия, 1998).
Публикации. По теме диссертации опубликовано 11 работ, список которых приведен в конце автореферата.
Структура и объем диссертации. Диссертация состоит из Введения, 6 глав, Заключения и Приложения. Диссертационная работа изложена на 135 листах и содержит 65 рисунков. Список литературы содержит 74 наименования.
