Программные продукты и системы

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

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

Разработка таких систем и особенно систем визуализации динамических сцен является новой и перспективной задачей.

В настоящее время можно выделить несколько направлений, в рамках которых разрабатываются системы типа "Текст-рисунок", получившие название ТЕКРИС [4].

Деловая графика.

В этом направлении создаются пакеты деловой графики для составления различных до-

кументов с текстово-графическим представлением информации [5].

Компьютерная анимация.

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

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

Когнитивная графика.

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

В [17] разработана система визуализации простейших динамических сцен по их текстовому описанию, а в [2] рассматривается задача визуализации пространственных сцен. В работах [13, 18] описываются системы типа "рисунок-текст", генерирующие описания сцены по рисунку.

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

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

ных отношений и действий. Динамическая версия системы ТЕКРИС получила название ТЕКРИС-Д.

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

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

Основные допущения в модели следующие.

1)       Принятие свойства детерминированности мира. Считается, что изменения в мире не про исходят самопроизвольно, а являются резуль татом выполнения действий, производимых субъектом.

2)       Среди множества действий, производи мых субъектом, рассматривается подмножест во действий, характеризующих изменения про странственно-временных отношений в сцене.

3)       Предполагается, что в динамической си туации действует один субъект.

4)       Графический образ объектов в сцене мо делируется с помощью параллелепипедов, ха рактеризующихся длиной, шириной, высотой и координатами так называемой точки опоры.

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

Архитектура системы ТЕКРИС-Д представлена схемой на рисунке 1.

Описание динамической ситуации на естественном языке поступает на вход лингвистического процессора. В качестве примера рассмотрим следующий текст (текст 1):

"В комнате находится стол. На столе стоит лампа. Позади стола, далеко слева находится'диван. Справа от дивана стоит шкаф, Иван находится на диване.

Иван подошел к столу. Взял лампу. Поставил ее на шкаф."

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

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

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

Рис. 2. Графическое представление динамической сцены

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

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

Основу языка внутреннего представления ЕЯ-описаний составляет набор базовых действий, изменяющих пространственные отношения в сцене. На данном этапе используется 7 базовых действий:

-    переместиться,

-    переместить объект,

-    взять объект,

-    поставить объект на,

-    приложить силу к,

-    разъединить,

-    соединить.

Фреймовая часть БЗ состоит из описаний прототипов объектов, действий, базовых действий, отношений, субъектов, сцен к сценариев. Опишем их.

Представление прототипов действий (в русском языке выражаемых глаголами):

(действие: isa prototype,

имя = ,

{слоты, отражающие семантические падежи действия},

завершенность действия = {Т, если действие

завершенное}, время = , ее = {концептуальная структура})

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

Представление прототипов базовых действий:

(переместиться: isa prototype,

кто = С (субъект действия),

откуда = А,

куда = В,

как = (по умолчанию считается, что с помощью ног), предусловие = (существует путь из А в В в исходной

сцене ?), результат = (С находится около В))

(переместить объект: isa prototype,

жто = С (субъект действия),

что = О (объект действия),

куда = В,

как = (по умолчанию считается, что с помощью рук),

предусловие =

(1 (С находится около В? и если нет,

то реализовать дополнительно действие "переместиться к В"), (2 (если О тяжелый, то С - сильный, в противном

случае действие нереализуемо)) результат = (О находится ожоло В)

(взять: isa prototype, ■ кто = С (субъект действия), что = О (объект действия),

гак = (по умолчанию считаете», что с помощью рук), предусловие =

(1 (С находится около О? и если нет,

то реализовать дополнительно действие "переместиться к Он), (2 (если О тяжелый, то С - сильный, в противном

случае действие нереализуемо)) результат = (С держит О, О находится на ружах С)

(поставить: isa prototype,

кто = С (субъект действия),

что - О (объект действия),

куда = А,

как = (по умолчанию считается, что с помощью рук),

предусловие =

(1 (С держит О? и если нет, то выполнить

действие "взять О") (2 (С находится около А? и если нет,

то выполнить действие "переместиться к А"), (3 (высота А меньше высоты С?

иначе действие нереализуемо)) результат = (О находится на А)

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

Представление прототипов объектов:

(объект: isa prototype,

имя = ,

тип = {простой или сложный}, длина = , ширина = ,

высота = , цвет = ,

вес = {легкий, средний или тяжелый}, скорость = {медленный, быстрый или средний), мобильность = {число степеней свободы), размер = {маленький, средний нлн большой}) (субъект: isa prototype,

имя = , длина = , ширина = ,

высота = , цвет = ,

вес = {легкий, средний или тяжелый}, скорость = {медленный, быстрый или средний}, мобильность = {число степеней свободы}, размер = {маленький, средний или большой) сила = {сильный, слабый или средний})

Представление прототипов состояний сцены:

(сцена: isa prototype,

имя = ,

объекты = {список объектов в текущей сцене,

включая субъект}, отношения = {список отношений между

объектами в сцене}, время = { })

Значение слота "время", равное 0, соответствует исходной сцене.

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

(сценарий: isa prototype,

имя = ,

исходная сцена ■ ,

последовательность действий = )

Сценарий в нашей задаче задается текстом.

Внутреннее представление текстового описания содержит фреймы-экземпляры рассмотренных выше прототипов. Для нашего примера имеем следующее представление:

(для простоты в описаниях экземпляров опущены наследуемые из прототипов слоты)

Список описаний экземпляров отношений в исходной пространственной сцене:

(oTiil: отношение, акт! = об1, акт2 = мир,

имя = находиться в), где мир - пространственная константа, задающая мир сцены с системой координат

(отн2: отношение,

акт1 = об2,

акт2 = об1,

имя = находиться на)

(отнЗ: отношение,

акт1 = обЗ,

акт2 = об1,

имя = позади .далеко .слева)

(отн4: отношение, акт1 = об4, акт2 = обЗ, имя = справа)

(отн5: отношение,

акт1 = об5,

акт2 = обЗ,

ИМЯ = находиться на)

Данное внутреннее представление исходного ЕЯ-текста является результатом работы лингвистического процессора системы.

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

Предлагается рассмотреть способ описания логики протекания физических действий во времени и пространстве - в виде так называемой псевдофизической логики действий (ПФЛД). Основным допущением в ПФЛД является принятие свойства детерминистичности мира. Будем считать, что изменения в нем не происходят произвольно.

Рассмотрим следующие конечные множества:

•       базовых действий Д = {д1, д2, .... 67};

•       объектов 0 = {г>1, о2, оЗ, ...};

•       субъектов действий S={si, s2, s3, ...};

•       инструментов действий И={и1, и2, иЗ, ....};

•       локализаций действий Л={л1, л2, лЗ, ...};

•       времен T={ml, m2, m3, ...};

•       отношений над действиями R — {R1, R2, ...}; (заметим, что все объекты множеств задаются своими именами).

Определим на этих множествах следующие отношения.

1.       Отношения, характеризующие направле ние движения при совершении действия: дейст вие направлено с поверхности объекта, на по верхность, в сторону объекта, от объекта.

2.       Отношения, характеризующие место дей ствия: действие происходит внутри объекта, по поверхности его, вокруг объекта и т.п.

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

4.       Отношения-модификаторы, характери зующие специфику протекания действий: дей ствие имеет модификатор скорости (быстро, медленно и т.п.), модификатор силы (резко, слабо и т.п.).

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

6.       Отношения, характеризующие контекст действий: действие имеет цель, результат, тре бует наличия условий, имеет побочное дейст вие.

7.       Отношения, характеризующие каузаль ную взаимосвязь действий.

Рассмотрим следующие типы каузальных отношений между действиями.

П1 - необходимая и достаточная причина.

Действия д1 и д2 связаны отношением П1, если реализация д1 всегда вызывает реализацию действия 62, и, наоборот, появление 62 всегда вызывается 61. Чаще всего, П! отражает различные физические законы реального мира (например "сверкнула молния - грянул гром")

П2 - достаточная причина.

Она означает, что реализация действия 61 всегда вызывает действие 62, однако из появления действия 62 не всегда следует появление

dl (например "нырнул в реку — оказался в воде")

ПЗ - обусловливающая причина.

Действия 61 и 62 связаны отношением ПЗ, если реализация действия 61 обеспечивает необходимые условия для реализации 62, которое, однако, может и не произойти (например "вошел в комнату - включил свет").

8.        Отношения, характеризующие действия по признаку изменения свойства или состоя ния: действие деформирует объект, разрушает его, меняет состояние объекта.

9.        Отношения, характеризующие действия, связанные с измерением: действие выявляет меру веса, длины, площади, объема.

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

Использование ПФЛД в интеллектуальных системах позволяет пополнять базу знаний, а также проводить контроль корректности описания ситуаций внешнего мира.

Зададим правильно построенные формулы (ППФ) следующим образом:

0)        выражение вида д(о s Л и т), где о, s, л, и, т - семантические падежи данного действия -ППФ, оеО, seS, леЛ, иеИ, теТ.

1)        любой элемент из Д, О, S, Л, И, Т, R - ППФ

2)        любое выражение вида (di R dj) - ППФ

3)        если А и В - ППФ, то А ~В - ППФ, где " - операция конъюнкции.

4)        других ППФ нет.

Множество правил вывода составляют следующие:

Ф/, Ф1 =*> Ф2 Ф1 " Ф2 Ф1 ' Ф2

Ф2 где Ф1, Ф2 - ППФ.

Приведем несколько схем аксиом, описывающих действия.

1)  61 R д2 => 61 г д2, где г отношение быть раньше.

R= {П1 П2ПЗ}

2)       61 ПЗ 62, 62 П1 63 => д/ ПЗ дЗ

3)       6(s о и л m) =*■ (s г л) (о г л)

где г - отношение "находиться около"

4)       61 R 62 => 61 г 62, где г -_ "быть раньше", R - отношение "результат действия"

5)       dl R1 62, 63 R2 62 => 63 R3 61 ' 62 R3 61, где

R1 - отношение "действие требует наличия условий,"

R2 - "имеет результат", R3 - каузальное отношение

6)       61 RI 62, 62 R1 дЗ^-62 R3 61 ' дЗ R3 61

7)       61 R1 62 => 61 "раньше" 62

8)       61 R3 62 => 61 "раньше" 62

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

Эта модель включает в себя несколько компонент: модель качественных физических рассуждений о динамике, статике и кинематике действий. Простейшие правила — продукции, отражающие качественные рассуждения о статике, использовались в системе ТЕКРИС для анализа статических сцен. Например следующие:

-     если ol R о2, где R - пространственное отно шение "находиться на", то о2 имеет точку опоры оЗ\

-     если ol R о2 и размер ol - большой и размер о2 - маленький, то ситуация некорректна, где R отношение "находиться в".

Модели качественных физических рассуждений используются для предсказания к интерпретации поведения динамической системы [6, 19].

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

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

Рассмотрим простейшую задачу планирования движения робота по горизонтальной поверхности в помещении с препятствиями. Будем считать, что робот стоит на полу в некоторой точке помещения и держит некоторый предмет. Пусть нам заданы размеры всех предметов в помещении, в том числе и робота, а также расстояния между всеми объектами. Говоря о размерах объектов, мы предполагаем, что они представляют собой либо параллелепипеды (прямые бруски), либо являются объединением конечного числа параллелепипедов, поэтому размеры задаются как упорядоченные тройки <длина, ширина, высота>. Мы будем рассматривать только случай, когда робот может совершать поступательные движения по полу помещения, т.е. повороты запрещены, и при этом предмет, который он держит, остается неподвижным относительно робота. Это предположение существенно, так как теперь для описания движения робота с предметом достаточно двух степеней свободы. Задача состоит в том, чтобы найти кратчайший путь из исходной точки в заданную, при перемещении вдоль которого не произойдет столкновении между роботом и другими объектами.

Для дальнейшего рассмотрения понадобится понятие конфигурационного пространства, введенное в [9] и получившее развитие в [8]. Пусть система координат связана с одной из вершин робота, например левой, нижней, дальней, в начальный момент времени. Обозначим робота с предметом, который он держит, как многогранник А, вершину, связанную с системой координат - rv. Остальные объекты в помещении обозначим через В с индексом. Конфигурацией многогранника называется множество независимых параметров, характеризующих его положение. Таким образом, конфигурация А может рассматриваться как точка х в tf-мерном пространстве конфигураций, где d -число степеней свободы А. Это 4-мерное конфигурационное пространство обозначим Cspace(A), многогранник А в конфигурации х -(А)х, A в начальной конфигурации - (А)о.

Не все конфигурации в Cspace(A) являются допустимыми, в частности те, в которых пересечение А и некоторого Bj непусто, незаконны, т.к. они приводят к столкновениям.

Конфигурационным              препятствием

CO(AjB), порожденным объектом В, назовем множество:

CO(AjB) ~ {xvnCspace(A)l пересечение (А)х и В непусто}

В случае, когда А и В - выпуклые многогранники, если rv находится вне конфигурационного препятствия, то А и В не сталкиваются, другими словами каждое из препятствий "растягивается" на величину движущегося объекта в направлении, зависящем от выбора вершины координат. Это простое понятие позволяет свести задачу планирования движения А среди препятствий Bj к задаче планирования движения точки rv среди препятствий CO(AjB). Если А и Bj - невыпуклые многогранники, то конфигурационное препятствие можно вычислить как объединение соответствующих кусков для каждого из параллелепипедов, образующих А и Bj.

Для вычисления CO(AjBj) нам понадобится следующее простое утверждение, подобное доказанному в [8]:

CO(AIBj) = Pr [Bj - (A)oJ,              (1)

где В — А = {b-а / "а" принадлежит А, "Ь" принадлежит В),

А + В = {а + Ъ I "а" принадлежит А, "Ь" принадлежит В},

Pr{D) - проекция многогранника D на прямоугольник, по которому перемещается робот.

Обозначим conv(D) - выпуклую оболочку многогранника D, a vert(D) - множество вершин этого многогранника. В [8] доказывается:

conv(A + В) — conv(A) + conv(B) = conv(vert(A) + vert(B))

Поскольку мы считаем, что нам задано разбиение А на параллелепипеды АР и разбиение каждого из В на параллелепипеды В Р , то в силу выпуклости АР и В.Р , получаем:

 (2)

следовательно,

СО(А/В) = Рг[Объединение по i,j, к

(ВР-(АР)о)] =

/"/{Объединение по i,j, к

conv(vert(B.Pyvert(AP' )o)] (3)

J К                                   i

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

Итак, мы свели задачу к поиску траектории точки внутри прямоугольника (пол помещения), не пересекающей ни один из многоугольников COiAjB ). Для решения этой задачи кажется естественным воспользоваться свойствами диаграммы Вороного [12], планарный граф, носящий это название, неоднократно использовался в работах, посвященных планированию движения [15, 16, 20]. Наиболее привлекательное свойство диаграммы Вороного то, что она является деформационным ретрактом свободного пространства, т.е. любая траектория, не пересекающая препятствия, может быть непрерывно отображена в диаграмму Вороного, и, кроме того, зазор между движущейся точкой и препятствиями максимален в случае, если движение осуществляется вдоль ребер диаграммы Вороного.

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

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

Планировщик и визуализатор системы Текрис-Д служат для построения графических образов траектории. Эти блоки являются моди-

фикацией соответствующих блоков системы ТЕКРИС для статического случая [4].

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

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

Список литературы

1.      Албу Б,А„ Хорошевский В.ФГ КОГР - система когнитивной графики. Разработка, реализация и применение // Иэв. АН СССР. Техн. киберне тика,- 1990,-N5.

2.      Ильин Г.М., Игнатова В.Н. Модель системы перевода от текста опи сания трехмерной сцены на естественной языке к ее графическому изображению. // Труды 2 Всесовн. конф. по искусственному интеллекту, - Минск, 1990. - Т2.

3.      Кандрашина Е.Ю., Лнтвинцсва ЛЛ, Поспелов ПА. Представление

знаний о времени и пространстве в интеллектуальных системах. - М. Наука, 1939.

4.   Литвинцева Л,В„ Поспелов Д.А. Визуализация пространственных сцен по текстовым описаниям для интеллектуальна систем. И Изв. АН СССР Техн. кибернетика. - 1991. - N5.

5.       Энджел Я. Практическое введение в машинную графику. // - М.: Радио н связь, 1984.

6.   Forbus К. "Qualitative process theory". // "Artificial Intelligence", 1984, V.24, N.l-3, "Special volume on qualitative reasoning", p. &5-1G8;

7.   Kirkpalric D.G. "Efficient computation of continuous skeletons" // 20th Symposium on Foundations of Computer Science, FOCS-79, IEEE, 1979 (October), Proceed Lnes, p,!S-77.

S. Lozano-Perez T. "Spatial planning: a configuration space approach". //

IEEE Transactions on Computers, 1983 (Febr.), v.32, N 3, p. 108-120.

9. Lozano-Perez T_ Wesley М.Л. "An algorithm for planning ccltlslon-free

paths among polyhedral obstacles". // Communications of Ihe ACM, ]У79

(Oct.), V. 22, N 10, p, 560-570.

ID. Magnehat-Thalmann N. New trends In the direction of synthetic actors

II Computer graphics around the world. Tokyo: Springer Verlag.1990.

11.        Nadin M. Intelligence for animation // GI-90 Jahrestagung III A.Reuler (Hrsg). Berlin: Springer Verlag, 1990.

12.        Preparata F.P., Shamos M.I. "Computational geometry: an Introduction" // N.Y, "Springer", 1985 / Русский перевод Ф .Препарата, М.Шеймос "Вы числительная 1-еометрия: введение" - М.: Мир, - 1989. - Гл.5. - 478 с.

13.        Reiter R., Nackworth A. A logical framework for depiction and image interpretation Ц Art. Int. v.4l. N2, 19S9.1 "

[4. Ridsdale G., Calvert T. Animating mlcroworlds from scripts and relational constrains // Computer animation^. Tohyo; Springer VerJag. 1990.

15.        Schwartz J.T, Sharir M. "A survey of motion planning and related geometric algorithms"// Artific. Intelllg, 19S8, v.37, N i-3, p.157-169.

16.        Sharir M. "Algorithmic motion planning in robotics" // Computer, 1989, v.22, N3, p.9-20.

17.        Shlmazu H., Takashlma Y., Tomoto M. Understanding of slories for ani mation // Proc. of the Int. Conf. on Сотр. Lingustics. v.2. Budapest, 198S. IB. Wahlster W. One word says more than a thousand pictures // Compu ters and Art. Int. V.8. N5. 19S9.

19.        Wlelinga В„ Bredeweg B. Reasoning about physical systems: unified perspective // 12th IMACS World Congr. Sel. Comput., Paris, July 18-22. 19S3. V.4, p.287-290.

20.        Yap С.-Х. "Algorithmic motion planning" // J.T^chwartz and C.-K.Yap (Eds) "Algorithmic and geometric aspects of robotics" ("Advances in robo tics", v.t \ Hlllsdale (NJ), 1987, p.95-143.