Навигация интеллектуальных агентов в сложных синтетических пространствах тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Жуков, Сергей Юрьевич

• Жуков, Сергей Юрьевич
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Жуков, Сергей Юрьевич

Оглавление.

Введение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3. Система Прохождения (Ж!?).

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

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

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

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

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

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

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

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

4.4.2. Оптимизация алгоритма 1ММС.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Навигация интеллектуальных агентов в сложных синтетических пространствах»

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

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

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

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

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

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

Задача реалистичного изображения синтетического пространства для систем BP успешно решается в течение вот уже нескольких десятков лет [24] [26]. Основными направлениями исследований являются: представление виртуального пространства, алгоритмы визуализации (rendering pipeline) [23] [24] [61], предобработка и оптимизация геометрического представления пространства [24][33][34][53], освещение [24][26][64][67], и т.п.

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

Под обеспечением реалистичного взаимодействия пользователя с виртуальным пространством подразумеваются как программно-аппаратные средства, обеспечивающие передачу команд и воссоздающие "ощущения" от взаимодействия с виртуальной средой (например, force feedback devices), так и программные модули, имитирующие столкновение виртуального образа пользователя с пространством [32][38], "выполнение" физических законов в виртуальном мире и кинематических ограничений при движении агентов (kinematic constraints) [29] и т.п.

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

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

Общие принципы построения системы моделирования поведения интеллектуальных агентов, а также способы реализация отдельных модулей системы были изложены автором диссертационной работы в [3][4][5] и [65] [68] [71] [72] [73] [74]. В дальнейшем, будем придерживаться введенной в этих работах терминологии и способам разбиения задачи моделирования поведения интеллектуальных агентов на подзадачи (уровни моделирования).

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

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

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

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

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

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

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

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

Множество состояний агента на каждом уровне моделирования поведения обычно описывается в виде конечного автомата с функциями переходов [12][13][45][31]. Для определения функции переходов между состояниями (что соответствует принятию решения агентом), вместо стандартного if-else подхода [12] [13] [45] [31] более целесообразно применять метод, основанный на построении целевого функционала с последующим принятием решения в соответствии со значением функционала [69] [70] [71]. Это позволяет заменить трудоемкое выписывание if-else конструкций, описывающих все возможные ситуации, на настройку системы посредством определения весовых параметров в минимизируемом выражении. Такой подход позволяет также эффективно стыковать решения, полученные на разных уровнях моделирования поведения, например, модифицировать путь, определенный уровнем Глобальной Навигации для выполнения локальных подзадач. Другой подход к принятию решений интеллектуальным агентом, основанный на "конкуренции поведений" рассмотрен в [16][17].

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

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

Процесс самообучения часто организуется следующим образом. Во время работы каждый уровень управления набирает статистику результатов выполнения своих команд нижними уровнями. На основе этой информации происходит уточнение локальных структур данных и передача обобщенных данных верхним уровням. Каждый уровень "стремится" к тому, чтобы ему дали правильную команду, поскольку он сам передает верхним уровням информацию, на основе которой те смогут избежать далее выдачи неверных или неэффективных команд. Практически, процесс обучения может представлять собой уточнение локальных структур данных, например, карты пространства на соответствующем уровне детализации, перевес оценочных штрафов нахождения в различных областях пространства, коррекцию приоритетов "желаний" (см. также [16]), перевес коэффициентов в целевых функционалах, и т.п. [69][71].

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

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

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

Рассмотрим сначала упрощенную постановку задачи построения пути (траектории движения). В упрощенной постановке задачи построения пути игнорируются динамические свойства робота и другие кинематические ограничения, а также рассматриваются только неконтактные движениями (таким образом, игнорируя механическое взаимодействие между физическими объектами). Эти предположения существенно трансформируют "физическую" проблему планирования движения в чисто геометрическую задачу планирования пути. Задача построения пути в упрощенной постановке ставится следующим образом [29] [36]:

Твердым телом будем называть замкнутое ограниченное подмножество множества Ям, где N-2 или 3. Граница твердого тела предполагается кусочно-гладкой.

Дано твердое тело А (робот), которое может перемещаться в Евклидовом пространстве Ж (рабочее пространство), представленном как Ям, где N—2 или 3. Заданы также Вь ., Вй - твердые тела, расположенные в IV (2?, называются препятствиями).

Предполагается, что геометрическое описание А, В\, ., Вд и расположение В, точно известно. Предполагается также, что нет никаких кинематических ограничений на движение робота (то есть робот может свободно перемещаться).

Требуется: по заданным начальной позиции и ориентации, и конечной позиции и ориентации А в IV, построить путь т, являющийся непрерывной последовательностью позиций и ориентаций А без касания (пересечения) А с Путь т должен начинаться в начальной позиции и ориентации и заканчиваться в конечной позиции и ориентации. Если такого пути не существует, то возвратить FALSE.

Для постановки обобщенной задачи построения пути вводится сначала более общее понятие робота и конфигурационного пространства (см. также [ 15] [29] [36] [43] [55]).

Дан робот А, состоящий из конечного множества твердых тел (возможно, соединенных связями (соединениями) различного типа).

Конфигурация робота - набор конфигураций всех твердых тел, из которых состоит робот. Конфигурация q твердого тела задается его позицией и ориентацией локальной системы координат относительно системы координат рабочего пространства W.

Конфигурационное пространство робота А это множество С всех конфигураций робота Л. Количество степеней свободы - размерность множества С.

Подмножество W, занимаемое роботом А находящимся в конфигурации q, обозначим как A(q). Аналогично, точку а робота А в конфигурации q обозначим a{q).

Введем на С функцию расстояния d: CxC—>R. В качестве функции d можно взять, например: d(q,q ) = Махяел II a{q) - a(q % где || х-х'\\ означает Евклидово расстояние между точкамихих'вRN.

Путем робота А из конфигурации qinit в конфигурацию qgoai будем называть непрерывную функцию т: [ОД]—>С такую, что z[0]=qinit и z[l]=ggoa/. Непрерывность тозначает, что Vä0g[0,1], lim s^s0 { d{j{s), zt^o))} = 0.

Каждое препятствие в рабочем пространстве W отображается в С в область:

СВ,-= { qeC | A(q)nBi*0}. Свободное конфигурационное пространство (Cfree) определяется следующим образом:

Cfree=C \ Ü СВ, = {qsC I A(q)n ( О СВг) =0}. i=l г-1

Свободным путем между двумя конфигурациями qinit и qgoai называется непрерывная функция г: [0,1]->С^.ее такая, что T\ü\=qimt и т[1 ]=qg0ab

11

Полусвободным путем между двумя конфигурациями qinil и qgoai называется непрерывная функция т: [0,1 ]-»с/ (Cfree), где cl (Cfree) означает замыкание Cfree. При некоторых разумных предположениях, любой полусвободный путь может быть сделан свободным, причем его стоимость увеличится на произвольно малую величину.

Требуется: по заданным qinit и qgoai построить полусвободный путь т, между заданными конфигурациями, или же возвратить FALSE если такого пути не существует.

Далее в работе, если не оговорено противное, под путем или траекторией движения будем подразумевать полусвободный путь.

Задачи построения путей (кратчайших путей) рассматривались многими исследователями в различных постановках. Конкретная постановка задачи определяется рассмотрением дополнительных факторов [43] [55], основными из которых являются:

• Стоимостная функция: как измеряется длина (стоимость) траектории?

• Статическое или динамическое пространство: могут ли объекты вставляться, удаляться или двигаться по заранее определенным траекториям?

• Входная геометрия: какого типа препятствия и как они задаются?

• Размерность проблемы: 2D, 3D, 33D. Будем различать следующие типы передвижения интеллектуальных агентов: движение в 2D пространстве; движение в 3D пространстве и движение по поверхности 3D пространства (53D).

• Тип движущегося объекта: как определен интеллектуальный агент или аппарат -либо это точечный объект, либо более сложная геометрия? Надо ли учитывать кинематические ограничения движения агента?

• Точный или приближенный алгоритм построения оптимального пути: Можно ли ограничиться результатом, который отличается от оптимального не более чем в некоторое, наперед заданное, число раз?

• Единичная или массовая задача: надо ли строить эффективные структуры данных для ускорения ответов на массовые запросы?

• Постановка цели: надо ли просто пройти к целевой точке, либо дополнительно необходимо посетить или осмотреть другие области?

• Известна ли заранее геометрическая карта пространства, либо ее надо создавать в процессе прохождения?

• Количество агентов в пространстве и необходимость распределять информацию между ними.

Стоимость (длина) траектории обычно вычисляется как Евклидова длина, или lF метрика. Широкий обзор остальных вариантов (например, link-distance) можно найти в [15] [29][43] [55]. Там же приведены результаты исследований движения аппаратов различной формы (диск, отрезок, полигон), а также аппаратов с наличием соединений различного типа (holonomic constraints). Кинематические ограничения неголономного типа (nonholonomic constraints) определяют зависимость траектории движения от скорости аппарата. Учет кинематических неголономных ограничений может производиться посредством увеличения размерности пространства состояний [15] [29], что увеличивает вычислительную сложность задачи. Широко исследовалась также задача навигация (планирование движения) группы взаимодействующих аппаратов [20]. В [44] приведен обзор основных результатов, полученных при различных вариантах постановки задачи планирования путей.

В общем случае, для задачи планирования пути в конфигурационном пространстве размерности т существуют алгоритмы, вычислительная сложность которых экспоненциальна от т. Более того, есть предположение, что эта экспоненциальная зависимость не может быть понижена [14]. Про некоторые варианты постановки задачи планирования пути доказано, что они PSPACE-трудные или NP-трудные. Задача планирования кратчайшего пути является NP-трудной уже в случае точечного агента, свободно движущегося в 3D пространстве с препятствиями в виде тетраэдров.

Далее, если не оговорено противное, будем предполагать, что пространство статично (то есть не изменяется во времени), и целевая точка неподвижна. Будем считать также, что состояние интеллектуального агента полностью описывается координатами его центра в пространстве (3 степени свободы в 3D), то есть движение агента не зависит от его ориентации, пройденного пути, скоростей, внутренних степеней свободы, и других кинематических ограничений. Для определения пересечения с пространством, формой агента может быть точка, диск (в 2D) или сфера.

Основные методы решения задачи построения пути (кратчайшего пути) в статичном пространстве можно классифицировать как "ориентированные на пространство", и "ориентированные на агента".

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

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

Обходы в 2D

В случае навигации (планирования пути) в 2D пространстве, существует универсальная стратегия, позволяющая агенту пройти к целевой точке (если это возможно), или определить, что такого пути не существует. Приведем стратегию BUG1 [40][41], которая использует только тактильную информацию о пространстве: Двигаемся вдоль прямой линии (<геометрической, или в пространстве состояний), соединяющей начальную точку и точку цели. Как только достигнуто i-e препятствие (в точке касания H¡), обходим его кругом {например, по правшу правой руки), вычисляя в результате координаты точки Ьг - ближайшей точки к цели на текущей компоненте связности границы i-го препятствия. Далее, идем из H¡ в Lh выбрав оптимальное направление обхода препятствия. Если из L¿ невозможно движение на цель, то СТОП — цель недостижима.

Рис. 2. а) Стратегия BUG1: Пунктирной линией показан полный обход /-го препятствия, при котором определяется ближайшая к у точка - L,. Затем производится обход препятствия до L, по оптимальному направлению и свободное движение к цели; Ь)

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

Очевидно, что эта стратегия доказуемо достигает цели, если это возможно, причем длина получаемого пути не превышает 1.5 P'(C/ree)+dE(x,y), где P'(Cfree) -сумма периметров всех препятствий, пересекающих круг с центром в точке у и радиусом [ху], a dE(x,y) - Евклидово расстояние между х и у. Невозможность достижимости целевой точки определяется с аналогичной верхней оценкой.

Другая стратегия BUG2 [40] [41] позволяет строить путь в пространстве с выпуклыми препятствиями с длиной получаемого пути не превышающей P'(Cfree)+dE(x,y) - в худшем случае, и 0.5 -P^Cf^+dsix,у) - в среднем. В пространстве произвольного вида стратегия BUG2 имеет значительно худшую оценку.

Приведем более простые стратегии обходов, которые не являются универсальными, но дают реалистичное движение в простейших случаях. Обход по левой/правой руке (LHT/RHT, left/right hand traversé) Этот вариант обхода является наиболее простым (Рис. 3): Двигаемся вдоль прямой линии (геометрической, или в пространстве состояний), соединяющей начальную точку и точку цели. Как только достигнуто препятствие начинаем обход по правшу левой/правой руки, пока не станет возможно движение к цели. Условный обход {СТ, conditional traverse)

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

ЛНТ

Ь) х Ф

КНТ, ст шг $ о ц о

Рис. 3. а) Обход препятствия по стратегиям ИНТ, ШТ и СТ, Ь) Все три стратегии не могут обойти препятствие; с) Стратегии ИНТ и СТ не могут обойти три выпуклых препятствия.

Заметим, что существуют и другие типы обходов, не являющиеся универсальными, но позволяющие более качественно обходить препятствия (см., например, [10]). Если при движении аппарата/интеллектуального агента используются системы технического/синтетического зрения, то траектория обхода может быть значительно улучшена [ 10] [ 17] [ 18] [40] [51].

Если стратегия обхода не является универсальной, то для достижения целевой точки используется метод "постановки и раскрытия дополнительных подцелей". При этом, если подцель оказывается тупиковой, то происходит рекурсивный возврат к предыдущей подцели [Ю][36][49].

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

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

- нахождение кратчайших путей в графе [ 1 ] [7];

- построение "карты дорог" [ 15] [55];

- построение графа видимостей [11][43][46][55];

- метод декомпозиции [36];

- метод минимизации потенциальной энергии [ 12] [3 6] [5 5],

- вероятностные алгоритмы [14].

Нахождение кратчайших путей в графе

Пусть задан граф (г=( ¥,Е) с неотрицательными весами ребер. Для построения множества кратчайших путей из одного источника, применяется алгоритм Дейкстры [1][7], с временной сложностью Т(п)=0(п2), где п= \У\, и алгоритм А* [9] [36]. Для построения транзитивного замыкания отношения достижимости в графе С? используется алгоритм Уоршола-Флойда [1][7], с временной сложностью Т(п)=0(пг).

Если все ребра в графе С имеют одинаковую стоимость, то можно использовать "поиск в ширину" [1][7] для построения оптимального пути за время 0(п+т).

В некоторых случаях планирования путей в динамически изменяемом пространстве, когда могут появляться или детектироваться дополнительные препятствия, существуют методы эффективного пересчета кратчайшего пути к цели, например, алгоритм £> [19][56][57].

Карты высот

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

Для решения задачи планирования пути по картам высот большого размера применяются приближенные алгоритмы, которые сначала строят путь на карте с меньшим разрешением (уровнем детализации), а затем уточняют его на более точной карте. Будем говорить, что такой подход к решению задачи использует ЬСЮ-технологию (сокращение от 1еуе1-о/-йе1аИ - уровень детализации) (см., например, [57]).

Карты дорог (гоайтаря)

При планировании путей для аппаратов/роботов часто используются так называемые "карты дорог" (гоасЬтрэ) [15][29][36][43][55]. Карта дорог 91 представляет собой сеть одномерных кривых, принадлежащих Cfree, удовлетворяющих следующим двум свойствам:

1. Щ сохраняет свойство связности Cfree, то есть Ш внутри каждой связной компоненты С^ее- не пусто и связно.

2. Существует простая процедура движения из любой точки хеС/гее к некоторой точке 9f, определяемой функцией притяжения фя (х), которая является тождественной на Ш. производится разбиение на трапеции, по которым затем стоится карта.

К методам данного класса обычно относят метод силуэтов (silhouette method), метод свободных путей (freeway method), построение функции притяжения {retraction approach)[36], а также графы видимостей (см. далее). Недостатком использования карт дорог для навигации интеллектуальных агентов является то, что данный метод плохо обобщается на произвольные способы передвижения интеллектуальных агентов (так, не понятно как в сложном 3D пространстве определять функцию притяжения фя(х)). Другим недостатком является невозможность строить пути, длина которых близка к оптимальной (например, не превосходит ее более чем в некоторое, наперед заданное, число раз).

Графы видимостей (visibility graphs)

Рассмотрим задачу построения кратчайшего пути в полигональном 2D пространстве (polygonal domain) Р, где Р определяет множество препятствий, заданных в виде непересекающихся полигонов. Множество допустимых точек Cfree определяется как множество всех точек, не являющихся внутренними точками ни одного полигона.

Для решения задачи построения кратчайшего пути в Р используется граф видимостей {visibility graph) VG={ Vvg,Evg) [11] [15] [29] [43] [46] [48]. Множество вершин графа видимостей VVG совпадает с множеством вершин Р, а множество ребер Evg образуется всеми парами вершин такими, что отрезок их соединяющий не пересекает внутренности Р. После задания исходной точки х и целевой точки у, происходит достройка графа VG{P) до графа VGxy{P), для чего добавляются вершины, соответствующие точкам х и у, а также ребра, соединяющие х и у со всеми видимыми вершинами Р. Затем на полученном графе VGxy{P) производится поиск оптимального пути из х в у. Известно [11][15][36][46], что оптимальный путь в Р из х в у проходит по ребрам графа VGxy{P). Далее будем считать, что отрезок [х,у] не принадлежит VG^P), что позволяет исключить рассмотрение тривиальных случаев.

Заметим, что в VG{P) есть ребра, которые не образуют оптимального пути ни при каких х и у. Для построения оптимального пути в Р, в графе видимостей достаточно рассматривать только такие отрезки [v„vy], которые являются локальными касательными к препятствиям в точках v, и vy- [36]. Такой граф называется сокращенным графом видимостей {reduced visibility graph, RVG) (Рис.

5).

Рис. 5. Сокращенный граф видимостей 13\/0(Р) и достройка до Увху (обозначено пунктиром).

Построение графа видимости для Р и его последующая достройка могут быть произведены с временной сложностью T{n)=0{m+n■logn) и емкостной сложностью 8{п)=0{п), где т=\Еуо\ - количество ребер в УО{Р), а п - количество вершин в Р. По полученному графу УСху с аналогичной сложностью строится дерево кратчайших путей из исходной точки х к целевой точке и ко всем вершинам полигона.

Для решения единичной задачи построения оптимального пути в Р, может быть применен метод "continuous Dijkstra", строящий оптимальный путь в полигональном пространстве, с временной сложностью T(n)=0(n-log п) и емкостной сложностью S(n)-0(n-log п) [48].

Если форма интеллектуального агента (аппарата) Ра представляет собой диск или выпуклый полигон, то вышеизложенные алгоритмы могут быть применены к сумме Минковского для С/гееиРА [15] [46] [5 5].

В случае, когда препятствиями являются обобщенные полигоны (generalized polygons), граница которых может быть составлена из множества отрезков или дуг окружностей, то для построения кратчайшего пути используются обобщенные графы видимостей (generalized visibility graphs) [36].

Оптимальные пути в 3D и SSD

Задача построения кратчайшего пути в 3D пространстве оказывается значительно сложнее, чем в 2D, поскольку вершины кратчайшего пути могут не принадлежать вершинам многогранника, а лежать где-нибудь на ребрах. Доказано, что эта задача является NP-трудной, даже если препятствия представляют собой множество параллельно расположенных треугольников [44].

В <93D пространстве, для построения кратчайшего пути между двумя точками на произвольной многогранной поверхности (дискретная геодезическая задача) существует эффективный полиномиальный алгоритм с временной сложностью Т(п)=0(п), и емкостной S(n)=0(n) [44].

Метод декомпозиции (cell decomposition)

Метод разбивает множество Срее на простые, не пересекающиеся области, называемые ячейками {cells), для которых затем строится неориентированный граф смежности (iconnectivity graph) [36]. Метод декомпозиции (Рис. 16.а,Ь) может быть как точным (объединение всех ячеек совпадает с С^ее), так и приближенным (объединение всех ячеек строго принадлежит С/гее).

Метод потенциалов

При построении пути из точки х к целевой точке у методом потенциалов [10] [12] [36] [5 5] сначала вводится потенциальное поле на множестве допустимых точек - Рху(г). Выбор функции Рху(г) во многом определяет эффективность метода. Обычно РХу{г) состоит из двух слагаемых: Рху(г)=0хо>(г)+0(г), где "притягивающая" функция 0Ху(г) убывает с приближением текущей точки 2 к цели у, а функция 0(г) определяет потенциал, "отталкивающий" агента от препятствий. В качестве "притягивающей" функции обычно используется:

СХу(£)=а-<3Е(г,у)+/3-<ЗЕ{г,[ху]), гДе 0, и с1Е(2,[ху\) - Евклидово расстояние между точкой г и отрезком [ху].

Если агент находится в точке хь то следующий шаг производится в такую точку в которой сумма (Рху(х^ 1 )+<фс„хг+\)) минимальна, где ¿/(хгуС;+|)- стоимость выполнения шага из хг в х,+\.

Рис. 6. Пример прохождения агента по "методу потенциалов". Стоимость перешагивания через препятствия О и Е =+оо. Препятствие О определяет отталкивающий потенциал, позволяющий агенту обойти его, что не помогает при обходе препятствия Е.

Основная проблема метода потенциалов заключается в том, что агент может попасть в локальный минимум, из которого движение далее невозможно (путь хг на Рис. 6). Различные подходы к решению этой проблемы рассмотрены в [36]. В [63] описан способ построения потенциального поля без локальных минимумов и плато, который требует очень больших вычислительных мощностей и поэтому имеет чисто теоретическое значение.

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

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

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

Рис. 7. а) Траектория движения агента, Ь) Соответствующая траектория в С^ее

На примере Рис. 7 изображена траектория движения агента, который может подняться на ступеньку к\, но не может подняться на ступеньку высоты /г2. Определим С^ее как множество точек на поверхности СВ, (Рис. 7.Ь). При этом, стоимость перехода из х в у меньше +оо, тогда как стоимость перехода из г в £ равна +оо. Следовательно, стоимость идентичных участков траектории может быть различной и стоимость траектории не является аддитивной функцией вдоль самой траектории.

С другой стороны, сведение задачи построения траектории движения агента к задаче построения траектории движения точки в С^ее не является точным, поскольку при таком сведении могут существенно измениться свойства достижимости. Действительно, раз стоимость траектории определяется внешним алгоритмом, работающим на {В,}, то при переходе в С/гее происходит частичная потеря информации о структуре препятствий. а)

С В,

Если же теперь предположить, что агент должен имитировать движение прыгающего аппарата (что достаточно часто требуется в системах виртуальной реальности), то в выбранном множестве С/гее (Рис. 7) это приведет к разрывной траектории движения агента.

Таким образом, задача построения траектории движения агентов не может быть сведена к "геометрической задаче" построения С^ее с последующим нахождением непрерывной траектории движения точки в С^ее. Это объясняется тем, что агент, находясь в конфигурационном пространстве малой размерности должен имитировать движение аппарата, обладающего большим количеством степеней свободы и сложными кинематическими ограничениями.

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

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

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

От интеллектуального агента часто ожидается, что траектория, полученная при движении к цели, будет удовлетворять неформальному критерию реалистичности. Этот критерий может быть частично формализован следующим образом: стоимость получаемой траектории движения должна быть близка к стоимости оптимальной траектории (например, отличаться от нее не более чем в некоторое, наперед заданное число раз).

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

1. Задача построения траектории движения агентов не может быть сведена к "геометрической задаче" построения непрерывной траектории движения в Сугее (как это принято при решении задачи планирования пути в робототехнике).

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

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

4. Задача обычно является массовой и допускает этап предобработки.

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

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

6. С другой стороны, размерность конфигурационного пространства С обычно невелика (2 или 3) и ограничения неголономного типа отсутствуют.

7. Нет неопределенностей и погрешностей в управлении агентом и в восприятии агентом окружающего пространства.

8. Все вычисления, необходимые для навигации и поведенческой анимации всех (!) интеллектуальных агентов, должны производиться в реальном времени, с загрузкой процессора не более 5-15%.

9. Агент обычно имеет доступ к геометрической карте пространства (хотя бы потому, что это пространство отображается в системе ВР), однако сложность пространства слишком велика для обработки в реальном времени (то есть для построения пути).

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

11. Необходимость обеспечения корректного взаимодействия агентов друг с другом и с виртуальным образом пользователя порождает ряд задач, которые пока еще мало исследовались в робототехнике (например, интерактивное преследование).

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

В данной работе будем дополнительно предполагать, что в задаче навигации интеллектуальных агентов рабочее пространство (N=2 или 3) и конфигурационное пространство С совпадает с рабочим пространством № (при этом, С/гееаИ\{В^).

Далее, если не оговорено противное, будем предполагать, что пространство статично (то есть не изменяется во времени), и целевая точка неподвижна. Будем считать также, что состояние интеллектуального агента полностью описывается координатами его центра, то есть движение агента не зависит от его ориентации, пройденного пути, скоростей, внутренних степеней свободы, и других кинематических ограничений. Для определения пересечения с пространством, формой агента может быть точка, диск (в 2Т>) или сфера.

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

-решения некоторых частных тривиальных случаев задачи навигации интеллектуальных агентов предъявлялись многими исследователями. Так, в [12] [13] описано применение метода минимизации потенциала, а в [16] [18] [59] приведены результаты использования системы синтетического зрения при решении задачи навигации и поведенческой анимации интеллектуальных агентов. К сожалению, результаты, полученные в области навигации интеллектуальных агентов, носят скорее эвристический и экспериментальный характер. Тем не менее, данные результаты формируют основу для разработки общих методов, пригодных для

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

Выделим два основных способа достижения критерия "реалистичности" траектории движения агента:

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

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

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

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

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

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

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

В настоящее время существует большое количество различных методов задания трехмерных пространств, различающихся по способу представления поверхностей: сплайны (например, NURBS) [24] [61], мета-сферы (meta-balls, meta-clays) [24] и т.п. В системах BP, препятствия обычно задаются с помощью множества плоских многоугольников (полигонов) (см. Рис. 60 и Рис. 61), поскольку такие геометрические объекты (polygon mesh) являются наиболее простыми и удобными для обработки. Процесс создания трехмерной сцены называется моделированием и выполняется в программных продуктах, позволяющих эффективно конструировать трехмерные сцены и объекты (например, Softimage Creative Environment, Alias/Wavefront, Maya, 3D Studio Max, LightWave, CAD/CAM приложения), или происходит процедурно, посредством программы, генерирующей пространство. Объекты в синтетическом пространстве обычно объединены в иерархию, то есть для них определено отношение "отец-сын", задающее корневое дерево.

Далее будем считать, что препятствия в 3D (2D) пространстве задаются конечным набором непересекающихся 3D (2D) полиэдров (полигонов). На практике, при моделировании синтетического пространства, препятствия задаются множеством пересекающихся полиэдров (см. Рис. 60), а их объединение выделяется неявно алгоритмом определения пересечения с препятствиями - алгоритмом CDT (collision detection).

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

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

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

- GoStraight - выполняется движение к цели по прямой линии до касания с препятствием;

GoCDT - выполняется движение к цели, если же при этом происходит касание препятствия, то алгоритм CDT подправляет движение так, что в 2D случае оно в каждый момент времени выполняется вдоль границы препятствия в направлении, составляющем наименьший угол с направлением на цель (Рис. 8). Если направление на цель противоположно нормали к поверхности, то движение не происходит (тупиковая ситуация, см. Рис. 8.Ь);

Рис. 8. воСОТ: направление выполняемого шага совпадает с направлением на цель, результирующее движение выполняется вдоль поверхности; а) Несимметричное отношение достижимости по ЭоСОГ для точек х и у; Ь) Тупиковая ситуация при движении от х' к у. с) Выполнение шага по воСОГ. а)

- стратегии обходов LHT, RHT, СТ,

- обход по левой/правой руке в некоторой плоскости в 3D/33D;

- выполнение прыжка.

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

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

В стратегиях прохождения с использованием синтетического зрения (SVB-стратегии, synthetic vision-based) агент при построении траектории движения анализирует двумерную картинку / того, что он реально "видит". При этом, обычно используется дополнительная информация о дальности до видимых объектов, об индексах самих объектов (идентификация препятствия) и т.п. Это позволяет избежать решения многих задач, связанных с распознаванием объектов в пространстве и определением дальностей, что составляет важную часть при реализации систем технического зрения в робототехнике, и сосредоточиться на решении непосредственно задачи навигации.

Использование SKB-стратегий требует значительных вычислительных затрат, особенно при моделировании движения нескольких интеллектуальных агентов в реальном времени в сложном 3D пространстве. В настоящее время системы синтетического зрения в приложениях BP обычно используются в сильно упрощенном виде, например, в 2D случае, или визуализируя изображение небольшого размера, или определяя координаты пересечения с пространством для некоторого количества лучей. Существующие примеры реализаций £РВ-стратегий носят скорее эвристический и экспериментальный характер и могут быть использованы лишь в очень простых случаях [12] [13] [18] [51] [60]. Системы навигации, использующие техническое зрение [10] [25][42][54], пока могут быть использованы в пространствах значительно меньшей сложности чем, например, синтетические пространства изображенные на Рис. 60-Рис. 65.

Как было отмечено ранее, для построения "реалистичной" траектории движения интеллектуального агента в сложном пространстве совсем не обязательно использовать синтетическое зрение (в том случае, если возможна предобработка пространства). Метод решения задачи навигации, приведенный в данной работе, основывается на построении навигационных карт и может быть использован для произвольных стратегий и способов передвижения агентов - как с использованием синтетического зрения, так и без использования.

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

Будем рассматривать задачу навигации без кинематических ограничений для агента, представляемого точкой или сферой (диском в 2D). При построении навигационной карты будем рассматривать только множество таких точек из Cfree, в которых агент может находиться в статичной позиции. Это множество будем называть множеством допустимых точек (permissible points), и обозначать как F (FdCfree).

В случае движения в 2D/3D выполняется F=Cfree, тогда как в случае движения в 53D, если агент может двигаться вдоль поверхности препятствий (например, ползать по стенам и потолку), то допустимыми точками являются только точки на границе препятствий. Если же агент может передвигаться только по горизонтальной поверхности, то точки на стенах и потолке не включаются в F. В любом случае будем предполагать, что существует простая процедура, позволяющая определить принадлежит ли точка х еС/гее множеству F или нет.

Геометрическую сложность синтетического пространства будем вычислять как количество вершин в полигонах (в 2D случае) или количество вершин в полиэдрах (в 3D), задающих F, и обозначать \F\.

Навигационная карта пространства (будем обозначать ее М) описывает разбиение множества допустимых точек F на области (зоны), соединенные отношениями связности (см. также [71][72][73][74]). Допустимые точки объединяются в области по некоторому критерию взаимной достижимости, зависящему от способа передвижения интеллектуального агента. Проверка принадлежности точки некоторой области производится с помощью функции ассоциации, что имеет ряд преимуществ по сравнению, например, с методами декомпозиции (см. параграф 2.2). В графе достижимости Gm=(V,A), отвечающему навигационной карте М, множество вершин V соответствует множеству областей, а множество ребер А определяет отношения достижимости между областями.

Навигационная карта является удобным способом представления знаний о достижимости в пространстве, причем стоимость пути, полученного при прохождении по навигационной карте, имеет разумную верхнюю оценку. Метод построения навигационных карт не зависит от способа передвижения интеллектуального агента. Формальные определения зон, отношений достижимости и навигационной карты пространства будут приведены далее в Главе 2. Частным случаем навигационной карты является граф видимостей и дискретный вариант карты дорог Ш, причем функция притяжения ф$кх) соответствует функции ассоциации.

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

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

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

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

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

В четвертой главе разрабатываются методы построения навигационной карты пространства, не зависящие от типа передвижения интеллектуального агента. В начале главы определяются требования к дискретизации пространства F. Затем приводится алгоритм построения звездных и полных зон в F4. Далее приводится схема алгоритма построения дескриптивной навигационной карты пространства (алгоритм 1DMC) и показывается ее корректность. Для алгоритма IDMC доказывается оптимальность выполнения шагов достройки навигационной карты. Затем в работе приводится схема алгоритма построения метрической карты пространства (алгоритм IMMC) и доказывается ее корректность. Далее в Главе 4 приводятся способы оптимизации алгоритма IMMC, что позволяет строить метрические навигационные карты с временной сложностью 0(\1^\2). В конце главы описывается алгоритм IMMC*.

В пятой главе исследуется сходимость алгоритмов построения навигационной карты в различных случаях в 2D и 3D.

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

Описанные в диссертации алгоритмы практически реализованы в программном продукте (видеоигре) и нескольких тестовых приложениях, что дало возможность подтвердить практическую значимость и эффективность полученных результатов. Анализ практического применения приводится в Приложении в конце диссертационной работы. Результаты диссертационной работы опубликованы в работах [3][4][5] и [68] [69] [70] [71] [72] [73] [74] и представлены на многих международных конференциях по компьютерной графике и искусственному интеллекту.

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Жуков, Сергей Юрьевич

Заключение

В диссертационной работе представлен новый универсальный метод решения задачи навигации интеллектуальных агентов. Метод основывается на выделении свойств достижимости между различными областями пространства Р и сохранении этой информации в виде навигационных карт. Навигационная карта задается как пара ({£,•},Сщ), где - покрытие Р конечным множеством зон, а См - граф достижимости, вершины которого соответствуют зонам, а ребра обозначают отношения связности между зонами.

В теоретической части работы дается формальная постановка задач навигации интеллектуальных агентов в синтетическом пространстве. Выделяются основные задачи навигации: построение навигационной карты пространства и прохождение по карте. Вводятся дескриптивный, метрический и квази-метрический критерии построения навигационной карты; определяются требования к дискретизации пространства, и предлагается новый эффективный способ решения задачи декомпозиции Р, использующий принцип неоднозначной ассоциации. Далее, определяется понятие зоны, свойства зон и отношения их связности; описывается строение Навигационной Системы, подробно рассматривается Система Прохождения по карте и принципы построения Алгоритмов Прохождения. Затем, на основе введенных определений и понятий, разрабатываются методы построения навигационных карт, не зависящие от типа передвижения интеллектуального агента. Приводятся схемы алгоритмов построения дескриптивной и метрической карты пространства (алгоритмы ЮМС, 1ММС и 1ММС*), доказывается их корректность и производится анализ сходимости в различных случаях в Ю и ЗБ.

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

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

Обсудим возможные расширения и/или ограничения предложенного в работе способа представления знаний о достижимости и методов построения навигационных карт. В параграфе 1.1 было зафиксировано предположение о том, что агент должен быть представлен точкой или сферой (диском в 20). Для того, чтобы расширить предложенные методы на агентов с дополнительными степенями свободы можно использовать общепринятый подход, использующий увеличение размерности пространства состояний [36] (что приводит к увеличению вычислительной сложности задачи). Аналогично можно учитывать и неголономные кинематические ограничения. В этих случаях алгоритм прохождения должен также иметь возможность управлять и учитывать такие параметры, как скорость, ориентация и т.п. Другое предположение заключалось в том, что агент двигается в статичном пространстве. В случае динамически изменяющегося пространства может производиться соответствующая модификация графа достижимости (например, добавление или удаление ребер при открывании или закрытии дверей), или использование в алгоритме прохождения подходящих стратегий обхода.

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

Список литературы диссертационного исследования кандидат физико-математических наук Жуков, Сергей Юрьевич, 2000 год

1. А. Ахо, Дж. Хопкрофт, Дж. Ульман "Построение и Анализ Вычислительных Алгоритмов", М., Мир, 1979

2. М. Гэри, Д. Джонсон, "Вычислительные Машины и Труднорешаемые Задачи", М., Мир, 1982

3. С. Жуков, А. Ионес, "Моделирование реалистичного движения интеллектуальных персонажей по сложной поверхности в реальном времени", Труды каф. «Прикладная математика», СПбГТУ, 1996, стр. 159-167

4. С. Жуков, А. Ионес, "Моделирование поведения интеллектуальных персонажей в трехмерных пространствах в реальном времени", Труды каф. «Прикладная математика», СПбГТУ, 1996, стр. 167-174

5. С. Жуков, А. Ионес, М. Глазырин, "Моделирование поведения компьютерных персонажей в сложном синтетическом 3D пространстве в реальном времени", Фундаментальные исследования технических Университетов, Материалы Научно-Технической Конференции, 1997

6. О. П. Кузнецов, Г.М. Адельсон-Вельский, "Дискретная математика для инженера", М., Энергоатомиздат, 1988

7. В. Липский, "Комбинаторика для программистов", М., Мир, 1988

8. Дж. Митчел, Д. Маунт, К. Пападимитриу, "Дискретная Геодезическая Задача", Кибернетический сборник №27, 1990

9. Н. Нильсон, "Принципы искусственного интеллекта", М., Радио и связь, 1985

10. Д. Е. Охоцимский, Ю. Ф. Голубев, "Механика и управление движением автоматического шагающего аппарата", М., Наука, 1984

11. Ф. Препарата, М. Шеймос. "Введение в Вычислительную Геометрию", М., Мир, 1988

12. N. Badler, "Dynamic Behaviors for Real-Time Synthetic Humans", SIGGRAPH'95 Course Notes (11)

13. N. Badler, B. Webber, W. Becket, C. Geib, M. Moore, C. Pelachaud, B. Reich, M. Stone, "Planning for Animation", in "Interactive Computer Animation", Ed. by N.M. Thalmann, D. Thalmann, Prentice Hall, 1996

14. J. Barraquand, L. Kavraki, J.-C. Latombe, T. Li, R. Motwani, P. Raghavan, "A Random Sampling Scheme for Path Planning", 1996

15. M. de Berg, M. van Kreveld, M. Overmars, O. Shwarzkopf, "Computational Geometry. Algorithms and Applications", Springer-Verlag, 1997

16. B. M. Blumberg, T. A. Galyean, "Multi-Level Direction of Autonomous Creatures for Real-Time Virtual Environments", SIGGRAPH'95 Conference Proceedings, pp.47- 54

17. B. M. Blumberg, "Old Tricks, New Dogs: Ethology and Interactive Creatures", Ph.D. Thesis, M.I.T., Media Laboratory, Learning and Common Sense Section, 1996

18. R. Boulic, H. Noser, D. Thalmann, "Automatic Derivation of Curved Human Walking Trajectories from Synthetic Vision", SIGGRAPH'95 Course Notes (7), pp. 5.325.40

19. B. Brumitt, C. Coulter, A. Stentz, "Dynamic trajectory planning for a cross-country navigator", Robotics Institute, Carnegie Mellon University, Pittsburgh, http://www.frc.ri.cmu.edu/~belboz/research/spie92/spie92.doc.html

20. B. Brumitt, A. Stentz, "Dynamic mission planning for multiple mobile robots", Robotics Institute, Carnegie Mellon University, Pittsburgh, http://www.frc.ri.cmu.edU/~belboz/research/icra96/icra96.4.doc.html

21. J. Canny, "The Complexity of Robot Motion Planning", MIT Press, Cambridge, MA, 1988

22. J. Canny, M. Lin, "An opportunistic global path planner", Tech. Research No. IRI-8958577, University of California, Berkeley

23. D. Dobkin, S. Teller, "Computer Graphics", in "Handbook of Discrete and Computational Geometry", Ed. by J.E. Goodman, J. O'Rourke, CRC Press, 1997

24. J. Foley, A. van Dam, S. Feiner, J. Hughes, "Computer Graphics. Principles and Practice", Addison-Wesley, 1990

25. M. Franz, B. Scholkopf, H. Mallot, H. Bulthoff, "Learning view graphs for robot navigation", Autonomous Robots, Kluwer Academic Publishers, 1997

26. A. Glassner, "Principles of Digital Image Synthesis ",Morgan Kaufmann Publishers, 1995

27. Gottschalk et al. "OBBTree: A Hierarchical Structure for Rapid Interference Detection", Proc. of SIGGRAPH'96 Conference, pp. 171-180, 1996

28. J. P. Granieri, W. Becket, B. D. Reich, J. Crabtree, N. I. Badler, "Behavioral Control for Real-Time Simulated Human Agents", SIGGRAPH'95 Course Notes (11)

29. D. Halpern, L. Kavraki, J.-C. Latombe, "Robotics", in "Handbook of Discrete and Computational Geometry", Ed. by J.E. Goodman, J. O'Rourke, CRC Press, 1997

30. M. Held, J. T. Klosowski, J. Mitchell "Evaluation of collision detection methods for virtual reality fly-throughs". In Canadian Conference on Computational Geometry, 1995

31. J. K. Hodgins, "Dynamic Behaviors for Real-Time Synthetic Humans", SIGGRAPH'95 Course Notes (11/B), 1995

32. P. M. Hubbard, "Interactive collision detection", Proc. of IEEE Symposium on Research Frontiers in Virtual Reality, October 1993

33. A. Iones, S. Zhukov, A. Krupkin "Building optimal bounding volumes for real-time 3D visualization", GKPO'98 (Borki, Poland) / Machine Graphics & Vision, vol. 1/2, 1998, pp. 84-92

34. A. Iones, S. Zhukov, A. Krupkin, "On optimality of OBBs for visibility tests for frustum culling, ray shooting and collision detection", in Proc. of CGI'98 (Hanover, Germany), pp. 256-263

35. D. Johnson, L. McGeoch, "The Traveling Salesman Problem: A Case Study in Local Optimization", pp. 215-310 in "Local Search in Combinatorial Optimization", ed. by E.H.L. Aarts, and J.K. Lenstra, John Wiley and Sons, London, 1997

36. J.-C. Latombe, "Robot Motion Planning", Kluwer Academic Publishers, 1991

37. J. Laszlo, M. van de Panne, E. Fuime, "Limit Cycle Control and its Application to the Animation of Balancing and Walking", SIGGRAPH'96 Conference Proceedings, pp. 155162

38. M. C. Lin "Efficient Collision Detection for Animation and Robotics" Ph.D. Thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley, 1993

39. T. Lozano-Perez, M. Wesley, "An Algorithm for Planning Collision-Free Paths Among Polyhedral Obstacles", Comm. ACM, 22(10), pp. 560-570, 1979

40. V. Lumelsky, A. Stepanov, "Path-Planning Strategies for a Point Mobile Automaton Moving Amidst Unknown Obstacles of Arbitrary Shape", Algorithmica 2:403-430, 1987

41. V. Lumelsky, "Algorithmic and Complexity Issues of Robot Motion in an Uncertain Environment", Journal of Complexity 3:146-182, 1987

42. H. Mallot, M. Franz, B. Scholkopf, H. Bulthoff, "The View-graph approach to visualthnavigation and spatial memory", Proceedings of 7 Intl. Conference of Artificial Neural Networks, ICANN-97, Lausanne, 1997

43. J. S. B. Mitchell, "Shortest Paths and Networks", in "Handbook of Discrete and Computational Geometry", Ed. by J.E. Goodman, J. O'Rourke, CRC Press, 1997

44. J. S. B. Mitchell, "Geometric Shortest Paths and Network Optimization", 1998

45. H. Noser, O. Renault, D. Thalmann, "Navigation for Digital Actors based on Synthetic Vision, Memory and Learning", SIGGRAPH'95 Course Notes (7), pp. 5.23-5.32

46. J. O'Rourke, "Computational Geometry in C", Cambridge University Press, 1995

47. J. O'Rourke, "Art Gallery Theorems and Algorithms", Oxford University Press, 1987

48. J. O'Rourke, "Visibility", in "Handbook of Discrete and Computational Geometry", Ed. by J.E. Goodman, J. O'Rourke, CRC Press, 1997

49. M. Overmars, P. Svestka, "A Probablistic Learning Approach to Motion Planning". Algorithmic Foundation of Robotics, K. Goldberg et al. (eds.), A. K. Peters, Wellesley, MA, 19-37, 1995

50. A. Pirzadeh, W. Snyder, "A Unified Solution to Coverage and Search in Explored and Unexplored Terrains Using Indirect Control ", Proc. of the IEEE Intl. Conference on Robotics and Automation, May, 1990

51. O. Renault, N. M. Thalmann, D. Thalmann, "A Vision-Based Approach To Behavioral Animation", SIGGRAPH'95 Course Notes (7), pp. 5.14-5.22

52. C. Rose, B. Guenter, B. Bodenheimer, M. Cohen, "Efficient Generation of Motion Transitions using Spacetime Constraints", SIGGRAPH'96 Conference Proceedings, pp. 147-154

53. H. Samet "Spatial Data Structures: Quadtree, Octrees and Other Hierarchical Methods", Addison-Wesley, 1989

54. B. Scholkopf, H. Mallot, "View-based cognitive mapping and path planning", Tech. Report No. 7, Max Planck Institute, November, 1994

55. M. Sharir, "Algorithmic motion planning", in "Handbook of Discrete and Computational Geometry", Ed. by J.E. Goodman, J. O'Rourke, CRC Press, 1997

56. A. Stentz, "The focussed D* algorithm for real-time replanning", Proc. of the Intl. Joint Conference on Artificial Intelligence, Aug, 1995

57. A. Stentz, "Optimal and Efficient Path Planning for Partially-Known Environments", in Proc. of IEEE International Conference on Robotics and Automation, May 1994

58. S. Suri, "Polygons", in "Handbook of Discrete and Computational Geometry", Ed. by J.E. Goodman, J. O'Rourke, CRC Press, 1997

59. D. Thalmann, H. Noser, Zh. Huang, "How to Create Virtual Life?", in "Interactive Computer Animation", Ed. by N.M. Thalmann, D. Thalmann, Prentice Hall, 1996

60. Tu, Terzopoulos, "Artificial Fishes: Physics, Locomotion, Perception, Behavior", SIGGRAPH'94 Conference Proceedings

61. A. Watt, M. Watt, "Advanced Animation and Rendering Techniques", Addison-Wesley, 1994

62. A. Witkin, Z. Popovic, "Motion Warping", SIGGRAPH'95 Conference Proceedings, pp.105-108

63. J. S. Zelek, "Dynamic motion Planning", Center for Intelligent Machines & Dept. of Electrical Engineering, McGill University, Montreal, Quebec, Canada, H3A 2A7

64. S. Zhukov, A. Iones, G. Kronin "On a Practical Use of Light Maps in Real-Time Applications.", in Proc. of SCCG'97 (Slovakia, Bratislava), vol. 2, 7-14

65. S. Zhukov, A. Iones, "Open 3D animation system based on procedural motion generation", in Proc. of WSCG'97 Central European conference on Computer Graphics and Visualization'97, (Plzen, Czech Rep.)

66. S. Zhukov, A. Iones, G. Kronin: "Using Light Maps to create realistic lighting in real-time applications", in Proc. of WSCG'98 Central European conference on Computer Graphics and Visualization'98, pp. 464-471 (Plzen, Czech Rep.)

67. S. Zhukov, A. Iones, G. Kronin: "Ambient Light Illumination Model", in Proc. of Eurographics Rendering Workshop'98 (Vienna, Austria)

68. S. Zhukov, A. Iones, "Procedural Intellectual Animation of 3D Characters over Complex Terrain in Real-Time", Proceedings of Computational Visual'97 (Mexico)

69. S. Zhukov, A. Iones, "Real-Time Behavior Control of Intelligent 3D Agents", in Proc. of 15th Eurographics-UK Conference (UK, Norwich, 1997)

70. S. Zhukov, A. Iones, "Real-Time Behavioral Control of Intelligent 3D Agents in Complex Synthetic Environment", in Proc. of SCAI'97 (FIN, Helsinki, 1997)

71. S. Zhukov, A. Iones, G. Kronin: "Navigation of intelligent characters in complex 3D synthetic environment in real-time applications", in Proc. of WSCG'98 Central

72. European conference on Computer Graphics and Visualization'98, pp. 456-463 (Czech Rep., Plzen)

73. S. Zhukov, A. Iones, G. Kronin, "Environment preprocessing for real-time navigation of intelligent agents", in Proc. of SCCG'98 (Slovakia, Bratislava), 1998, pp. 225-234

74. S. Zhukov, "Accessibility Knowledge Representation", Programming and Computer Software, vol. 3, Moskow, RAS, 1999 (имеется перевод: "Представление Знаний о Достижимости", Программирование, том. 3, стр. 4-15, 1999, Москва, РАН)

75. S. Zhukov, A. Iones, "Building the Navigational Maps for Intelligent Agents", Computers and Graphics, Elsevier Science, vol.1,20001риложение

76. Рис. 61. Изображение того же пространства с текстурами

77. Рис. 63. Часть пространства, в которое помещен летающий персонаж (W=GoStraight в 3D)