DemonScript: Пространственные отношения

Введение

Рассмотрим четыре отношения, которые составляют основу описания относительного расположения объектов в пространстве:

Ещё одно отношение X below Y - все части объекта Х находятся ниже всех частей объекта Y, не является независимым так как для него справедлива связь X below Y <-> Y above Х.

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

Примеры

Ниже приведен пример для отношений in и ins (a внутри b, b внутри c и d вне всех остальных). Справа от рисунка записаны пары объектов для которых отношения истинны (первая колонка) и для которых они ложны (вторая колонка). Ложное отношение, как обычно, помечается восклицательным знаком "!":

Например, (a in c) истинно (транзитивность). В тоже время (a ins c) ложно (a находится не непосредственно внутри c, а через вложение в b). Аналогичны примеры для отношений above, on:

Объекты выше изображены прямоугольниками, символизирующими некоторые ящики. Это может быть реальный ящик (коробка, сундук) или воображаемый параллелепипед, полностью окружающий объект. Подчеркнём, что эти отношения применяются к закрытым ящикам. В частности, для истинного отношения X ins Y, объект X не может выглядывать за Y. Если один ящик ставится на другой (X on Y), то он не "проваливается вниз" (есть крышка у Y). Наконец, отношение X above Y будет ложным, если хотя-бы часть объекта Х не выше объекта Y.

Для закрытых ящиков возможны вполне корректные (и многочисленные) модели в которых данное отношение ложно (ниже первые три примера). Однако, можно нарисовать картинки, которые запрещены в принципе (последние два примера):

Для двух ящиков Х и Y существует 9 вариантов из расположения (X непосредственно внутри Y, X вложен в Y и т.д.):

На второй картинке ящик Х окружён пунктиром. Это подчеркивает, что в общем случае между ним и ящиком Y могут быть другие ящики, вложенные друг в друга. Аналогично для Y на четвёртой картинке. Мы не ограничиваем относительных размеров ящиков (за исключением возможности их вложения ins, in). Поэтому в последнем примере, при ложности отношения выше X above Y и Y above Х, не принципиально кто из ящиков больше или "чуть выше" (они нарисованы одинаковыми и на одном уровне).

True, False и Undef

Задание отношений не всегда однозначно фиксирует модель. Это означает, что данному множеству отношений может удовлетворять несколько различных "картинок" (= моделей). Например, пусть известно, что Y непосредственно находится внутри Z, а X - выше Y. Этой информации удовлетворяет пять моделей:

Ящик Х, находящийся выше Y, может быть как внутри Z, так и не вне его (но выше Y). Отношения, приведенные справа от рисунков, в одних моделях истинные, а в других ложные. Поэтому в вероятностной логике для них используется значение "возможно"= Undef. Истинность такого отношения не доказуема, но не доказуема и его ложность.

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

Аксиоматика отношения in

Отношение in образует строгий древесный порядок. Ниже на рисунке приведена система вложенных друг в друга ящиков. Если нарисовать отношение непосредственного вложения ins, то получится древесный граф. С учётом транзитивности, в графе отношения in добавляются ещё рёбра A-E и B-E (последний рисунок):

Графы выше приведены в традиционном для математики виде (указаны только истинные рёбра). Первый граф фактически является диаграммой порядка для отношения in (не рисуются рёбра транзитивности), а второй - графом отношения in на котором указаны все True рёбра отношения.

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

Строгий древесный порядок in обладает следующими четырьмя свойствами:

Древесность означает, что Z не может находится одновременно и в X, и в Y, если они, в свою очередь, не являются вложенными (см. выше разрешённый пример с ящиками B,C,E на последнем графе).

В DemonScript аксиомы отношения in запишем следующим образом: 

edges in, ins, on, above, below;                  // декларируем отношения

var X,Y,Z                                         // переменные для аксиом
Mind.add
(                                    
   X !in X,                                       // (1) антирефлексивность    
   X in Y -> Y !in X,                             // (2) асимметричность
   X in Z & Z in Y -> X in Y,                     // (3) транзитивность
   Z in X & Z in Y -> X in Y | Y in X | X==Y      // (4) деревесность
)
В объект Mind, при помощи метода add, добавляются аксиомы. Символ -> обозначает логическое следствие, | - логическое ИЛИ (дизъюнкция), & - логическое И (конъюнкция) и ! - отрицание. Аксиомы предполагаются всегда истинными. Поэтому, в частности, антирефлексивность !X in X означает, что X in X ложно.

Заметим, что из антирефлексивности и транзитивности следует асимметричность. Действительно, положив X=Y в аксиоме транзитивности (3) и записав её в КНФ, имеем: 

   X !in Z | Z !in X | X in X    =>    X !in Z | Z !in X   =>   X in Z -> Z !in X,
где сначала опущен член X in X как всегда ложный (по первой аксиоме), а затем КНФ снова превращена в импликацию. Аналогично, из асимметричности следует антирефлекивность: 
   X in Y -> Y !in X   <=>   X !in Y | Y !in X   =>    X !in X | X !in X   <=>  X !in X.
Вообще говоря, теоремы, следующие из аксиом, можно не указывать явным образом в Mind. Поэтому, можно опустить (2) или (1). Однако мы этого делать не будем. Дело в том, что Mind может работать в режиме в котором значения различных переменных считаются различными. В этом режиме опускание одной из аксиом приведёт к неполноте аксиоматики отношения.

Аксиоматика отношения ins

Добавим отношение непосредственного вложения ins, которое в языковых конструкциях будем обозначать предлогом "внутри", в отличии от предлога "в" для отношения in. Отношение ins антирефлексивно и асимметрично однако не обладает транзитивностью (далее опускаем Mind.add(...)): 

   X !ins X,                                      // антирефлексивно
   Y ins X -> X !ins Y                            // асимметрично
Так как транзитивность отсутствует, свойство асимметричности необходимо указать явным образом, однако можно опустить антирефлексивность (что мы, как указывалось выше, делать не будем).

Справедлива ещё одна "аксиома единственности": если истинно, что Х находится внутри Z, то он не может находится внутри другого Y, который не есть Z: 

    X ins Z & Z!=Y -> X !ins Y                    // (6) единственность
Примеры для этой аксиомы приведены ниже на первом рисунке:

Свяжем теперь отношение ins с отношением in. Очевидно, что, если Х непосредственно (ins) внутри Y, то оно находится и где-то в (in) Y (но не наоборот!): 

    X ins Y -> X in Y,                            // (7) если "внутри", то "в"
Эта аксиома эквивалентна X !in Y -> X !ins Y (если не где-то в, то тем более и не непосредственно внутри).

Должны также выполняться две аксиомы, примеры для которых приведены на рисунках выше: 

    X in Z & Z in Y -> X !ins Y,                  // (8)
    X in Z & Y !in Z & Y != Z -> X ins Y          // (9)

На этом с отношениями in и ins всё.

Тестируем in и ins

Решим следующую задачу. Пусть известно, что ящик "a" находится где-то в ящике "c", ящик "b" не находится в "c". Какие выводы из этой информации можно сделать? Понятно, что возможны две модели. В одной ящик "b" находится вне ящика "c", а в другой ящик "c" находится в "b" (и "b", соответственно, в "c" также не находится). Эти модели приведены на рисунках справа.

Получим решение при помощи DemonScript: 

var G = GRAPH("G")                                // создаём пустой граф
GRAPH = G                                         // делаем его текущим
nodes a,b,c                                       // добавляем в него три узла

a  in c;                                          // а находится в c
b !in c;                                          // b не находится в c

out G                                             // выводим исходный граф
Mind.set_graph(G)                                 // запускаем логический вывод             
out G                                             // выводим финальный граф
Исходный граф и граф после проведения логических выводов (метод set_graph) выглядят следующим образом: 
   G { 
      a {  in: [c]  },
      b {  in: [!c] },
      c {}          }

   G {
      a{ in: [c,!a],      ins: [!a,!b],    },
      b{ in: [!c,!b,!a],  ins: [!b,!c,!a], },
      c{ in: [!c,!a],     ins: [!c,!a],    } }
Напомним, что a {...} - это узел a графа, где в фигурных скобках перечислены все рёбра, которые исходят из узла. Пока у нас есть только два типа рёбер in и ins. После их имён, в квадратных скобках идёт перечисление узлов в которые эти рёбра направлены. Если перед именем узла стоит восклицательный знак, это означает, что данное отношение ложно.

Например, !a in a или a in a == False (это сработала аксиома антирефлексивности). Более нетривиальный вывод !a ins b, т.е. ящик "a" не может находиться непосредственно внутри "b" (т.к. b не находится в "c", где находится "a"). Ещё один важный вывод: !b in a ("b" не может находиться в "a").

При этом a ins c, в отличии от a in c, имеет неопределённое значение ("c" отсутствует в массиве a { ins: [...] }). Это связано с тем, что информация a in c; означает, что "a" находится где-то в "c", т.е. не обязательно непосредственно внутри "c"). Если мир не замкнут (могут существовать другие ящики), то между "a" и "c" может оказаться ящик (а может и не оказаться). Именно поэтому отношение a ins c имеет неопределённое значение.

Аналогично стоит проанализировать остальные результаты вывода.

Для аналогичной задачи с отношениями ins результат другой. В этом случае условиям соответствует уже три модели. 

G.clear_edges()                                   // очищаем рёбра
a  ins c;                                         // а находится непосредственно внутри c
b !ins c;                                         // b не находится непосредственно внутри c


G { 
   a{  in: [!a,c],  ins: [c,!a,!b], },
   b{  in: [!b],    ins: [!c,!b],   },
   c{  in: [!c,!a], ins: [!c,!a],   } }

Аксиоматика отношения above

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

   X !above X,                                    // (10) антирефлексивно
   X above Z & Z above Y -> X above Y             // (11) транзитивно
Отношение above связано с отношением in двумя очевидными правилами: 
    X in Y -> X !above Y,                         // (12)
    Y in X -> X !above Y,                         // (13)
Кроме этого, для трёх объектов справедливы две разрешающие аксиомы (приводящие к истинности отношения above): 
    X in Z    & Z above Y -> X above Y,           // (14)
    X above Z & Y in Z    -> X above Y            // (15)
Соответствующие этим аксиомам примеры приведены на следующих рисунках:

Аксиоматика отношения on

Отношение on антирефлексивно и асимметрично, но, как и ins, транзитивностью не обладает: 

  X !on X,                                        // (16) антирефлексивно
  Y on X -> X !on Y,                              // (17) асимметрично
Если Х находится на Y, то он его выше, а если не выше, то не может быть on: 
   X on Y -> X above Y,                           // (18)

Если между Х и Y "вклинивается" третий объект Z, то отношение X on Y запрещено: 

   X above Z & Z above Y -> X !on Y,              // (19)
    
   X in Z & Y !in Z & Y!=Z -> X !on Y,            // (20)
   X !in Z & Y !in Z & X!=Z -> X !on Y            // (21)

Ещё два правила выглядят понятнее, если их записать не как запрещающие для on, а как разрешающие для ins: 

   X on Z & Z ins Y  ->  X ins Y,                 // (22)
   Z on X & Z ins Y  ->  X ins Y                  // (23)
Эти аксиомы проиллюстрированы на следующих рисунках:

На этом аксиоматика отношений in, ins, above и on окончена.

Аксиоматика отношения below

Для полноты картины добавим также аксиомы для отношения below: 

    Y above X -> X below Y,                       // (24)
    Y below X -> X above Y                        // (25)
Двустороннее следование означает формулу эквивалентности X below Y <-> Y above X.

Тест для всех отношений

G.clear_edges()                                   // очищаем рёбра
nodes d                                           // добавляем ещё один узел

a ins c;
b on  c;
d below c;

Mind.set_graph(G)
out G
Результат: 
   a{ in: [!a,c,!d],  ins: [c,!a,!b,!d],   on: [!a,!c,!b,!d],  above: [!a,!c,d],    below: [!a,!c,!d]},
   b{ in: [!b,!a,!d], ins: [!b,!a,!c,!d],  on: [c,!b,!a],      above: [!b],         below: [!b],   },
   c{ in: [!c,!a,!d], ins: [!c,!a,!b,!d],  on: [!c,!b,!a],     above: [!c,!a,d],    below: [!c,!a,!d]},
   d{ in: [!d,!c,!a], ins: [!d,!c,!a],     on: [!d,!a],        above: [!d,!a,!c],   below: [c,!d,a] }

Открытый и закрытый мир

Построенная выше аксиоматика пространственных отношений основывается на модели открытого мира. В такой модели могут существовать объекты, которые не упомянуты в исходной информации. В ряде случаев это может оказаться не удобным. Например, если утверждается, что существуют только ящики a,b,c и других нет, то эту информацию также необходимо уметь использовать. Подобная ситуация называется закрытым миром. В модели закрытого мира с двумя ящиками "a" и "b" противоречивыми являются факты a in b; a !ins b. В открытой модели они непротиворечивы и означают существование такого "c", что: a in c; c in b.

Чуть более сложный пример. Пусть известно, что 

[a, b] ins c; 
d !ins c; d in c;
В закрытом мире это означает, что "d" должно находится или в "a" или в "b" (но не в обоих). В открытом мире, кроме этих возможностей следует допустить существование внутри "c" пятого объекта в котором находится "d".

Закрытый мир реализуется при помощи построения всех возможных, полностью определённых моделей. Для этого в Mind существует метод .get_models. Впрочем, часть сгенерённых им моделей, при наличии нескольких отношений, по-прежнему будут "открытыми". Более прямой путь, это "руками" получать все возможные модели, перебрав известные объекты. В примере с четырьмя ящиками a,b,c,d это выглядит так: 

out Mind.set_graph(G)                             // применяем аксиомы для in, ins

out "============== Models in close world:"
for X in (d ins X) == Undef {                     // для всех X в которых d может быть
   var Tmp = G.copy();
   Tmp.d ins Tmp.X;                               // его туда помещаем
   Mind.set_graph(Tmp)                            // и ещё раз применяем аксиомы
   out Tmp                                        // выводим модель
}

out "============== Models in open world:"
var Models = Mind.get_models(G, ins, 0);          // генерация моделей для отношения ins
for M in Models:                                  
   out M                                          // выводим эти модели
Первый способ даст две модели (d ins a и d ins b). Во втором способе дополнительно будет модель d !ins a; d in a, потому, что возможен не упомянутый пятый ящик вокруг ящика d.

Заключительные замечания

  • Приведенная аксиоматика не учитывает размерности пространства. В большинстве случаев это не критично. Однако иногда может оказаться важным. Например, если ввести отношения слева, справа, спереди, сзади в 2-мерном пространстве (прямоугольники), при помощи 4-х объектов можно "зажать" между ними пятый. В 3-мерном пространстве для этого необходимо ещё два объекта и отношения above, below.

  • Отношение above более общее, чем on (включает его), а in - более общее, чем ins. В посылках правил надо стремиться к наиболее общим отношениям (тогда они будут справедливы и для частных). Большая общность означает, что данное отношение выполняется на большем числе моделей. Например X above Y может быть истинно, и когда X on Y ложно, но не наоборот.

  • При генеративном порождении значений отношений (применяем аксиомы, пока граф не перестаёт изменяться), необходимо учесть, что если есть аксиома F -> G, то также справедливо и !G -> !F. В объекте Mind это автоматически учитывается, так как все формулы представляются в КНФ. В частности аксиома F -> G имеет вид !F | G. Аналогично, если в посылке два атома, то аксиомы утраиваются. Например: 
          A & B -> C    <=>     !С & B -> ! A       <=>     A & !C -> В.
    Однако все они имеют одинаковую КНФ: !A | !B | С, поэтому достаточно в Mind добавить только одну запись этой аксиомы.

  • Рассмотренные в этом документе примеры можно найти в скрипте: in_above.ds