Комнатный мир: 1. Графы мест и событий
Введение
В этом документе мы ограничимся двумя действиями: goto и give, обсудим организацию памяти и использование обыденных знаний для восстановления информации, которая подразумевается, но явно не задаётся. Считается, что есть горизонтальная поверхность (пол, земля) по которой передвигаются люди. Они могут подходить друг к другу (goto) и передавать (give) предметы или других людей (которых переносят держа на руках).
История
Пусть есть следующая история:
Сэм отдал ключ Лизе. Лиза подошла к Мии.
Пока предполагается, что информация о действиях в истории полна и непротиворечива.
Полнота означает, что все действия указаны явным образом.
Первое событие ("Мия подошла к Лизе") означает, что в начальном состоянии S0 Мия и Лиза были не рядом и не на руках друг у друга. После совершения действия, в состоянии S1 они оказались рядом (и по-прежнему стоят на полу).
Второе действие ("Мия дала ключ Сэму") вводит ещё два объекта.
По определению, дать может тот, кто имеет, тому, кто рядом.
Поэтому Мия имела ключ. Сэм находится рядом с Мией (и Лизой). Однако, где конкретно - не определено.
Он может быть:
1) на полу рядом с Лизой; 2) на руках у Лизы; 3) на руках у Мии;
Вариант "Лиза на руках у Сэма" не рассматриваем, считая, что подойти (Мия) можно только к тому, кто стоит на полу (Лиза).
Вариант мира в котором Сэм находится на руках Мии отпадёт после следующих двух действий (Мия отошла от Лизы, а Сэм дал ключ Лизе).
Поэтому остаются две версии мира, изображённые схематически справа на рисунках.
В обоих вариантах возможны также вариации начального состояния S0 в которых Боб стоит или рядом с Мией, или не рядом с ней. На основе построенной модели (в 4-х её вариантах) можно получить ответы на следующие контрольные вопросы к истории:
- Где был ключ в начале истории? [у Мии]
- Была ли Лиза рядом с Сэмом в начале истории? [да]
- Был ли Боб рядом с Сэмом в начале истории? [нет]
- Были ли рядом Мия и Боб в начале истории? [неизвестно]
- Где сейчас ключ? [у Лизы]
- Рядом ли сейчас Боб и Сэм? [неизвестно]
- Рядом ли сейчас ключ и Мия? [да]
Действия не только меняют состояния, но и предоставляют дополнительную информацию, которая явно не указана, но подразумевается (источник информации считает, что её приёмник недостающие факты восстановит при помощи общепринятых обыденных знаний). Кроме этого, действие изменяет не только два соседних состояния (до и после), но и, вообще говоря, все предыдущие состояния. Например, когда Мия дала ключ Сэму выяснилось, что у неё был ключ, а Сэм стоял рядом с Лизой. Если все действия в истории указаны, следует считать, что эти два факта были также истинны и в начале истории. При этом факт "Мия рядом с Сэмом" в начале истории не является истинным, также как и то, что у Лизы был ключ.
Отношения и действия
Кроме предопределённых в DemonScript отношений: X isa Y (X является подмножеством или элементом класса абстрактных сущностей Y) и A sub S (S является субъектом действия A), нам потребуются ещё пять отношений:
edges pos, // X pos Y : объект X находится в локации (месте) Y on, // X on Y : X находится на поверхности Y (стоит, лежит) hold, // X hold Y : X держит Y (в руках, зубах, в кармане) near, // X near Y : X находится рядом с Y prev; // X prev Y : событие X предшествует событию Y (previous)
Допустимые действия перечислим как узлы графа абстрактных классов Sen. Добавим также абстрактную сущность "пол":
var Sen = GRAPH("Sen");
Sen.nodes
$goto, // субъект Sub подходит к месту или объекту Des
$give, // субъект Sub даёт объект Obj другой персоне Des
$floor; // пол, горизонтальная поверхность по которой ходят
Отношение hold возникает в результате действия give. Если X дал объект Obj некому Y-ку, то перед действием X hold Obj истинно, а Y hold Obj - ложно. После действия - наоборот. Подобную переустановку рёбер графов будет проводить демон действия give. Кроме этого, система должна обладать рядом обыденных знаний. Например, "если X держит Obj, то его больше никто не держит" (hold имеет дело с небольшими предметами и совместная переноска брёвен описыватся другим отношением).
Чтобы было возможным действие give(Sub, Obj, Des), необходимо, чтобы Sub и Des находились рядом. Они оказываются рядом, если Sub, например, подходит (goto) к Des. При этом, в первом приближении (модель!) не будем учитывать размеры объектов, считая их небольшими. В частности, если X подходит к Y, который стоит рядом с Z, то X оказывается рядом и с Z. Впрочем, Sub может дать объект и тому Des, который находится у него на руках или наоборот.
Граф мест
Различные положения объектов в пространстве удобно выделить в отдельный граф Loc. Его узлы являются областями пространства (точечными или протяжёнными) в которых находились объекты, описываемые в истории. Эти области будем называть локациями (location) или местами.
var Loc = GRAPH("Loc") // граф мест
Например, событие "Мия подошла к Лизе" порождает три места:
- Loc=>1 - где Мия была перед началом движения;
- Loc=>2 - где Мия оказалась после перехода;
- Loc=>3 - место, где находится Лиза.
Loc=>1 !near Loc=>2; Loc=>2 near Loc=>3; Mia pos Loc=>1; Liz pos Loc=>3; // до перехода Mia pos Loc=>2; Liz pos Loc=>3; // после перехода
Удобно считать, что объект Y, находящийся на руках у некого X (X hold Y), не обладает отношением pos. Тогда, при перемещении X достаточно отслеживать только его положение, считая при "ответах на вопросы", что Y находится там же, где и его владелец.
Отношение near будет использоваться не только для указания близости мест в графе Loc, но и непосредственной близости объектов. Когда Мия подошла к Лизе они находятся рядом, потому, что рядом их положения. Это будет продублировано отношением Mia near Liz. В следующем действии "Мия дала ключ Сэму" указывается, что Сэм рядом с Мией (Mia near Sam), а, следовательно, и рядом Лизой. При этом, находится ли Сэм на земле или у кого-то на руках - неизвестно. Поэтому у него нет отношения pos (положения на земле). Вообще, отслеживание факта близости объектов в условиях неопределённости (вариантов мира) достаточно непростая задача. Поэтому наличие двух механизмов оказывается полезным, хотя, возможно, один из них и избыточен.
Граф состояний и событий
Все состояния (память о происходящем) будут храниться в графе Evs (события). Структура этого графа имеет вид:
Узлы состояний S0, S1,... чередуются с узлами событий (действий) E1, E2,..., меняющих состояния. Напомним, что узлы графа могут хранить данные (value). Для узлов S0, S1,..., в качестве этих данных, будут выступать графы G0, G1,... состояний. Событие (узел Ei), при помощи ребра isa в граф Sen, указывает тип действия. Он также связывается различными рёбрами с графом предыдущего состояния, для конкретизации совершённого действия (кто: sub, что: obj и т.д.):
В графе G0 помечено, что Мия находится в месте Loc=>1 и не рядом с Лизой (перед тем как к ней подойти), а в графе G1 (Мия подошла к Лизе) отношение "Mia pos Loc=>1" меняется на "Mia pos Loc=>2", а (Mia near Liz) == True. Изменением этих отношений занимаются демоны действий.
Начальное состояние
Зададим граф G0 начального состояния S0 с шестью конкретными сущностями, находящимися в сознании системы:
var G0 = GRAPH("G0") // создаём граф начального состояния
G0.verbose(0); // блокируем информацию о смене рёбер
GRAPH = G0; // делаем G0 текущим
nodes Mia, Liz, Sam, Bob, key, floor; // Мия, Лиза, Сэм, Боб, ключ, пол
floor isa Sen=>$floor
Необходимость введения поверхности floor по которой перемещаются люди будет объяснена ниже.
Создадим пустой граф событий, добавим один узел и поместим в него граф G0 начального состояния:
var Evs = GRAPH("Evs") // граф событий
var S0 = Evs=>(Evs.add_node("S0")); // узел начального состояния
S0.value(G0); // помещаем в него граф G0
Так как граф состояний Evs единственный, все его узлы (состояний и событий)
будут связываться с графом, что уменьшит число переключений типа GRAPH = Evs.
Добавление узлов событий
Напишем демона, который принимает узел текущего состояния S1, создаёт узел события Act, соединяя их рёбрами prev:
def create_event(S1, Act, Sub)
{
static ID = 1; // номер события (для имени)
var E = Evs=>(Evs.add_node("E"+(ID++))); // добавляем узел события
S1 prev E; // он следует за S1
E isa Act; // и является действием Act
var G1 = S1.value() // граф состояния перед действием
E sub G1=>Sub; // действие совершил субъект Sub
return E // возвращаем узел события
}
Аналогичен демон, создающий узел нового состояния S2.
Граф этого состояния является копией графа предыдущего состояния:
def create_state(S1,E)
{
static ID = 1; // номер текущего состояния (для имени)
var S2 = Evs=>(Evs.add_node("S"+ID)); // добавляем узел нового состояния
E prev S2; // он следует за узлом события
S2.value(S1.value().copy("G"+(ID++))) // помещаем копию графа из состояния S2
return S2 // возвращаем узел нового состояния
}
Эти демоны напрямую вызываться не будут (только внутри демонов конкретных действий). Получение и создание положений
Демон, возвращающий положение объекта X (узел в графе Loc) имеет вид:
def pos(X)
{
var P = X.nodes(pos)
if P.size() > 0 : return P[0] // положение есть, возвращаем его
P = Loc.add_node() // иначе создаём новое положение
X pos P; // связываем его с объектом
return P // и возвращаем
}
Пока будем считать, что в данном состоянии объект может находиться только в одном месте. Поэтому отношение "X pos P" получается методом X.nodes(pos), возвращающим массив узлов, связанных с X отношением pos. Если массив не пустой, то местом считается его первый (и единственный) элемент. Когда массив пуст, создаётся новое место и связывается с объектом X.
Положения объектов будут создаваться только тогда, когда они упоминаются в действии. Как обсуждалось выше, если положение объекта неизвестно, он существует без отношения pos. В частности ключ, который в начале истории держала Мия, не имеет места, а состоит с Мией в отношении "Mia hold key" (это выяснится во втором событии "Мия дала ключ Сэму"). Так как у ключа нет места, он перемещается вместе Мией. Т.е. места пока считаются положениями объектов на полу (земле).
Создадим также демона, возвращающего положение объекта X в текущем состоянии:
def where(X)
{
var P = X.nodes(pos) // массив положений X
if P.size() > 0 : return P[0] // если не пуст, берём первый элемент
GRAPH = X.graph()
if exists(Y, Y hold X) : // возможно X носит некий Y,
return where(Y) // тогда его положение
}
Так как X может держать Y, который держит Z (например, Боб взял Лизу на руки, а у Лизы есть ключ),
демон where в if вызывает сам себя для владельца X (если таковой есть).
В общем случае, демон where может вернуть неопределённое (Undef) значение.
С помощью where определяется демон, выясняющий близость в пространстве двух объектов:
def near(X, Y)
{
return ifdef X near Y // есть явное отношение между объектами
var PX = where(X), PY = where(Y) // получаем положения X и Y
if PX != Undef & PY != Undef: // если они определены
return Loc=>PX near Loc=>PY // near из графа Loc
}
Он возвращает True, False или Undef.
Действие give
Описание демонов действий начнём, с более простого действия give. В этом действии субъект Sub даёт объект Obj другой сущности Des. Демон give(S1, Sub, Obj, Des) получает текущее состояние S1 и возвращает новое состояние S2, которое затем можно передать следующим действиям:
def give(S1, Sub, Obj, Des)
{
var E = create_event(S1, Sen=>$give, Sub); // узел события
GRAPH = S1.value() // граф состояния до действия
Sub hold Obj; // В S1 субъект Sub имел,
Des !hold Obj; // а Des не имел объект Obj
Sub near Des; Sub near Obj; // Sub, Des, Obj были рядом
Mind.set_graph(GRAPH)
var S2 = create_state(S1,E); // узел нового состояния
GRAPH = S2.value(); // граф состояния после действия
Sub !hold Obj; // в S2 субъект Sub не имеет,
Des hold Obj; // а Des имеет объект Obj
Mind.set_graph(GRAPH)
return S2; // новое текущее состояние
}
В демоне, вначале создаётся узел события (create_event) и фиксируются отношения hold в состоянии перед совершением действия. Помечается также, что участники действия находятся рядом. Затем вызываются обыденные знания в виде аксиом объекта Mind (их описание приведено ниже).
Это начальное состояние порождает новое состояния (create_state), в граф которого попадают все текущие отношения. В нём меняется отношение hold между участниками действия и снова запускаются обыденные знания.
Обратим внимание, что история, состоящая из одного действия "Мия дала Сэму ключ", допускает несколько возможных моделей. В наиболее правдоподобной модели, Мия и Сэм стоят рядом друг с другом на полу. Однако возможно также, что Мия находится на руках у Сэма или Сэм находится на руках у Мии. Кроме этого, могут быть неизвестные субъекты на руках которых находятся Мия и Сэм. Поэтому задавать (создавая!) их положение на полу нельзя. Выше мы ограничились лишь констатацией того, что Sub, Des, Obj находятся рядом (иначе действие невозможно).
Действие goto
Если некто Sub подходит к Des,
то в предыдущем состоянии его рядом с Des не было, а в новом состоянии он там оказался.
Кроме этого, Sub и Des не могли друг друга держать ("на руках").
Будем считать, что перемещение происходит по некоторой поверхности Surf (пол floor).
def goto(S1, Sub, Des, Surf)
{
var E = create_event(S1, Sen=>$goto, Sub); // узел события
GRAPH = S1.value(); // граф состояния до действия
var SP1 = pos(Sub) // место Sub до перехода (было или новое)
var SP2 = Loc.add_node() // место Sub после перехода (новое!)
var DP = pos(Des) // место назначения Des (было или новое)
SP1 !near DP; // Sub и Des были не рядом
SP2 near DP; // затем оказались рядом
SP1 !near SP2; // начало движения и его конец не рядом
Mind.set_graph(Loc, 1) // только группа аксиом для near с номером 1
Sub !near Des; // находятся не рядом друг с другом
Sub on Surf; // стоят на поверхности (полу, земле)
Des on Surf;
Mind.set_graph(GRAPH)
var S2 = create_state(S1,E); // узел состояния после действия
GRAPH = S2.value(); // граф этого состояния
// ... Анализ соседей ... // код находится в следующем разделе
Sub pos SP1 = Undef; // В S2 Sub покидает старое место
Sub pos SP2; // и переходит в новое место
Sub near Des; // находятся рядом с Des
Mind.set_graph(GRAPH)
return S2; // новое текущее состояние
}
В состоянии до действия goto субъект перемещения Sub и его цель Des не держали (hold) друг друга. Кроме этого, раз Sub перемещается по поверхности и подходит к Des, который на ней стоит, их не могла держать "в руках" никакая другая сущность. Эту информацию можно указать в цикле по всем объектам X типа: X !hold Sub. Однако, если к текущему моменту действия не все объекты известны, то для них это отношение выставлено не будет. Одно из решения этой проблемы - пересчитывать всю историю заново при появлении новых сущностей. Выше принято другое решение. При помощи отношения "on" запоминается, что Sub и Des стоят на полу. В дальнейшем будет введена аксиома: (X on Y) -> !(Z hold X): если X стоит на Y, то X никто не держит в руках. Она позволяет, зная, что Sub и Des находятся на полу, сделать вывод, что новые сущности их не держат.
Анализ соседей
В демоне give изменяются только отношения между участниками действия. Всеми остальными отношениями занимаются обыденные знания. Например, если известно, что Obj кто-то держит, то больше его ни кто держать не может. В перемещении goto ситуация сложнее и необходимо отслеживать изменения отношения near между большим числом объектов.
Субъект действия Sub связан отношеним near
с тремя категориями объектов: 1) те, которые стоят на полу; 2) те, которых держат; 3) те, статус которых
неизвестен (они могут стоять на полу, их может держать Sub или кто-то другой).
К третьей категории относится, например, Сэм (на рисунке справа, такой объект S изображён в "подвешенном состоянии").
Анализом всех этих категорий занимается кусок кода демона goto под названием "Анализ соседей":
var Nodes = Sub.nodes(near) // все, связанные с Sub ребром near
for N in Nodes : if N != Sub {
if N on Surf { // если они стоят на полу
if Sub near N : // от близких
Sub near N = N near Sub = False; // уходим
else : // далёкие
Sub near N = N near Sub = Undef; // становятся неопределёнными
}
else { // остальные (их держат или неизвестно)
var Nds = N.nodes(near) // делаем неопределённым отношение near
for Y in Nds : if Y != N :
Y near N = N near Y = Undef
}
}
Те, кто был рядом с Sub в состоянии S1 и при этом стоял на полу, в состоянии S2 будут не рядом с Sub (отношение near меняется на False). Для тех N, кто не был рядом (известно, что для них (Sub near N) == False), отношение делается неопределённым. После того как Sub окажется рядом с Des (на рисунке это объект A), обыденные знания установят правильные значения near, как для Sub, так и для тех, кого он несёт. Неопределённым делается также отношение near для всех, кто на полу не стоит. Теми, кого несут, займутся обыденные знания. "Подвешенные" останутся неопределёнными (их Sub несёт, или не несёт).
Первая итерация
Протестируем введенных демонов действий, записав с их помощью историю из начала документа:
var S1 = goto(S0, Mia, Liz, floor) // Миа подошла к Лизе var S2 = give(S1, Mia, key, Sam) // Мия дала ключ Сэму var S3 = goto(S2, Mia, Bob, floor) // Миа подошла к Бобу var S4 = give(S3, Sam, key, Liz) // Сэм дал ключ Лизе var S5 = goto(S4, Liz, Mia, floor) // Лиза подошла к МииЭволюцию отношений по состояниям представим в виде двух таблиц (для hold и near). Они формируются при помощи демона out_table(Edges, Col_W) из файла room_common_out.ds. По строкам таблиц находятся состояния, а в колонках - объекты из которых выходит ребро отношения. Например, в S1 имеем Mia{ hold:[key] }, т.е. Мия имеет ключ:
hold
Mia Liz Sam Bob key
S0 [] [] [] [] []
S1 [ key] [] [!key] [] []
S2 [!key] [] [ key] [] []
S3 [!key] [!key] [ key] [] []
S4 [!key] [ key] [!key] [] []
S5 [!key] [ key] [!key] [] []
near
Mia Liz Sam Bob key
S0 [!Liz] [!Mia] [] [] []
S1 [ Liz, Sam, key] [ Mia] [] [] []
S2 [ Liz, Sam,!Bob, key] [ Mia] [] [!Mia] []
S3 [!Liz, Sam, Bob, key] [!Mia] [ Liz, key] [ Mia] []
S4 [!Liz, Sam, Bob, key] [!Mia] [ Liz, key] [ Mia] []
S5 [ Liz, Sam, Bob, key] [ Mia] [ Liz, key] [ Mia] []
Результат получился не вполне удовлетворительный.
Существуют проблемы с пониманием перемещения ключа между людьми (очевидно, что у Боба его не должно быть как и у Лизы в состояних S1,S2).
Для восстановления этой (подразумеваемой неявно) информации потребуются обыденные знания.
Кроме этого, отсутствует понимание наиболее вероятных отношений между объектами до их появления в действиях. Например, при полноте информации о событиях, следует считать, что ключ (который Мия дала Сэму) был у Мии и в начальном состоянии S0. Аналогично, положение Боба должно быть неизменным и в состояниях S0,S1, а Сэма в S0.
Обыденные знания
Демоны действий задают базовые отношения, которые сопровождают данное событие. Эти отношения порождают истинность или ложность некоторых других отношений. Подобный процесс удобно реализовать при помощи объекта логических выводов Mind, в который добавим следующие аксиомы:
Mind.add(
!(X hold X), // антирефлексивность
(X hold Y) -> !(Y hold X), // асимметричность
(X hold Y) & Z != X -> !(Z hold Y), // единственность
near(X, Y) -> (X near Y), // near из графа Loc
!near(X, Y) -> !(X near Y),
(X on Y) -> !(Y on X),
(X on Y) -> !(Z hold X), // ни кто не держит стоящего на полу
!(X near Y) -> !(X hold Y), // кто не рядом, тот не держит
);
Mind.group(1)
Mind.add(
(X near X), // рефлексивность
(X near Y) -> (Y near X), // симметричность
(X near Z) & (Z near Y) & X != Y -> (X near Y),// транзитивность
);
Последним трём аксиомам присваивается номер группы 1. Эта группа
будет использоваться для фиксирования отношения near в графе Loc
(для него остальные аксиомы не нужны).
Третья аксиома для hold сообщает, что если некий X держит Z, то больше никто другой держать Z не может. Отсутствие проверки Y!=X было бы ошибочным. Когда обыденные знания записываются в виде аксиом, часто предполагается, что входящие в них переменные относятся к различным сущностям. Однако, для Mind это надо указывать явным образом. Поэтому, записав аксиому, следует сделать в ней попарно все переменные одинаковыми, проверяя, не получилось ли "странного" утверждения. Например, в аксиоме (X hold Z) -> !(Y hold Z), положив Y=X, получим (X hold Z) -> !(X hold Z), что, очевидно, неверно. Поэтому необходимо добавить Y!=X. Варианты X=Z и Y=Z ни к чему плохому не приводят.
Для отношения near первая аксиома рефлексивности является тривиальным утверждением о том, что объект всегда находится рядом с самим собой. Аксиома симметричности означает, что, если X рядом с Y, то и Y должен быть рядом с X. Третей идёт аксиома транзитивности, означающая, что если X находится рядом с Z и Z находится рядом с Y, то и X находится рядом с Y. Так как пока мы не учитываем размеров объектов, система будет считать их "точечными". Если два человека стоят рядом и к ним подходит третий человек, то все они оказываются рядом друг с другом. Понятно, что для больших объектов подобное свойство может нарушаться и в более реалистичной модели эту аксиому придётся подправить.
Аксиома near(X, Y) -> (X near Y) и такая же с отрицаниями, уточняет положение near между объектами исходя из занимаемого ими положения в графе Loc. В этих аксиомах вызывается определённый выше демон near(X,Y).
В результате получается следующая эволюция отношений по состояниям отношения hold и near (везде опускаем "тривиальные" результаты антирефлексивности !(X hold X) и рефлексивности X near X):
hold
Mia Liz Sam Bob key
S0 [!Liz] [!Mia] [!Mia,!Liz] [!Mia,!Liz] [!Mia,!Liz]
S1 [!Liz, key] [!Mia,!key] [!Mia,!Liz,!key] [!Mia,!Liz,!key] [!Mia,!Liz]
S2 [!Liz,!Bob,!key] [!Mia,!Bob,!key] [!Mia,!Liz,!Bob, key] [!Mia,!Liz,!Sam,!key] [!Mia,!Liz,!Sam,!Bob]
S3 [!Liz,!Sam,!Bob,!key] [!Mia,!Bob,!key] [!Mia,!Liz,!Bob, key] [!Mia,!Liz,!Sam,!key] [!Mia,!Liz,!Sam,!Bob]
S4 [!Liz,!Sam,!Bob,!key] [!Mia,!Bob, key] [!Mia,!Liz,!Bob,!key] [!Mia,!Liz,!Sam,!key] [!Mia,!Liz,!Sam,!Bob]
S5 [!Liz,!Sam,!Bob,!key] [!Mia,!Bob, key] [!Mia,!Liz,!Bob,!key] [!Mia,!Liz,!Sam,!key] [!Mia,!Liz,!Sam,!Bob]
near
Mia Liz Sam Bob key
S0 [!Liz] [!Mia,] [] [] []
S1 [ Liz, Sam, key] [ Mia, Sam, key] [ Mia, Liz, key] [] [ Mia, Liz, Sam]
S2 [ Liz, Sam,!Bob, key] [ Mia, Sam,!Bob, key] [ Mia, Liz,!Bob, key] [!Mia,!Liz,!Sam,!key] [ Mia, Liz, Sam,!Bob]
S3 [!Liz,!Sam, Bob,!key] [!Mia, Sam,!Bob, key] [!Mia, Liz,!Bob, key] [ Mia,!Liz,!Sam,!key] [!Mia, Liz, Sam,!Bob]
S4 [!Liz,!Sam, Bob,!key] [!Mia, Sam,!Bob, key] [!Mia, Liz,!Bob, key] [ Mia,!Liz,!Sam,!key] [!Mia, Liz, Sam,!Bob]
S5 [ Liz, Bob, key] [ Mia, Bob, key] [] [ Mia, Liz, key] [ Mia, Liz, Bob]
Экстраполяция в прошлое
Перейдём теперь к восстановлению предыстории. Появившиеся в результате вывода отношения между объектами будем "экстраполировать" в прошлое, если они в предыдущих состояниях имели неопределенное значение. Для этого сравниваются графы G1 и G2 двух последовательных состояний S1 и S2. Если в G2 между узлами X и Y есть отличное от Undef ребро E, а в G1 такое же отношение (X E Y) неопределено, то мы присваиваем ему значение из G2:
def set_undef(G1, G2)
{
GRAPH = G1;
for E in [hold, on]: // по отношениям
for N1 : // по узлам
for N2 :
if (G2=>N1 E G2=>N2) != Undef & (G1=>N1 E G1=>N2) == Undef:
(G1=>N1 E G1=>N2) = (G2=>N1 E G2=>N2);
}
Например, если Мия даёт Сэму ключ, это означает, что у неё этот ключ был перед началом действия (Mia hold key). Если ранее ключ не упоминался, то в предыдущих состояния он не связан с Мией ни каким отношением. Экстраполяция (копирование определённых отношений в неопределённые), "протащит" это отношение во все состояния в прошлом. В результате, в начальном состоянии станет известно, что у Мии есть ключ.
Ещё пример: "Мия заходит в комнату и подходит к столу". В конце истории становится ясным, что стол находится в комнате. Экстраполяция в прошлое приводит к выводу, что стол находился в комнате и когда Мия была вне комнаты.
Естественно, экстраполяция приводит к "разумным результатам" когда поступающая информация полна. Если же это не так, потребуется организация ветвления вариантов предыдущих состояний. Для этого необходимо вводить возможные не упомянутые события ("Перед тем как перейти к Лизе, Мия взяла ключ со стола" и т.п.).
Реализация экстраполяции
Копирование отношения (pos) выделим в отдельный демон:
def set_undef_pos(G1, G2)
{
GRAPH = G1;
for N {
var P = G2=>N.nodes(pos); // положение N в графе G2
if exists(X, X hold N) : continue // его не должны держать
if P.size() > 0 & G1=>N.nodes(pos).size() == 0 :
(G1=>N pos P[0]) = (G2=>N pos P[0]);
}
}
Проверка существования X, который держит N необходимо,
чтобы не копировать старые положения объекта N, если некий X
"взял его в руки". Если это произошло, то у N не должно быть положения (он находится там же, где и X).
Демоны set_undef и set_undef_pos вызовем в демоне recalc, который пересчитывает все состояния в прошлое, от текущего состояния Cur:
def recalc(Cur)
{
GRAPH = Evs;
Mind.set_graph(Cur.value()); // пересчёт текущего состояния
if !exists(Ev, Ev prev Cur): return True // нет предыдущего события
if exists(Prv, Prv prev Ev) { // предшествующее состояние
Mind.set_graph(Prv.value());
set_undef(Prv.value(), Cur.value()) // копируем отношения
Mind.set_graph(Prv.value());
set_undef_pos(Prv.value(), Cur.value()) // копируем положения
recalc(Prv, Set); // рекурсивно идём в прошлое
}
}
Вызов Mind перед копированием рёбер, а затем ещё раз перед копированием
положений может показаться избыточным. Однако в ряде случаев это необходимо.
Например, при помощи аксиом можно выразить следующее знание: "если X держит Y, то они имеют одно положение".
Чтобы это правило корректно отработало, в копируемое состояние должны сначала попасть отношения X hold Y,
а только потом скопироваться положения. В противном случае скопированное старое положение Y может
прийти в противоречие с положением X (если X переходил с места на место).
Демон recalc вызывается для финального состояния.
Результаты
Отношение pos соответствует положению объектов на полу. Им не обладает ключ, который носят люди и Сэм, которого, возможно, носит Лиза:
pos Mia Liz Sam Bob key S0 [ Loc=>1] [ Loc=>3] [ ] [ Loc=>5] [] S1 [ Loc=>2] [ Loc=>3] [ ] [ Loc=>5] [] S2 [ Loc=>2] [ Loc=>3] [ ] [ Loc=>5] [] S3 [ Loc=>4] [ Loc=>3] [ ] [ Loc=>5] [] S4 [ Loc=>4] [ Loc=>3] [ ] [ Loc=>5] [] S5 [ Loc=>4] [ Loc=>6] [ ] [ Loc=>5] []
Отношения near для графа положений Loc в "читаемом" виде
выводит демон clasters из файла room_common_out.ds.
Он группирует места, связанные отношением near в кластеры:
C1: [1] near: [!C2] C2: [2,3] near: [!C1,!C3] C3: [4,5,6] near: [!C2]Кластер C1, состоящий из одного места (начального положения Мии), находится не рядом с кластером C2 (места 2,3). Но рядом ли он с кластером C3 не известно (Undef - может быть рядом, а может нет). Соответствующая информация помечена на рисунке рёбрами между кластерами. Буквы рядом с местами - это люди, которые в данных местах побывали.
Отношение hold вполне соответствует пониманию естественным интеллектом рассматриваемой истории:
hold Mia Liz Sam Bob key S0 [!Liz,!Sam,!Bob, key] [!Mia,!Bob,!key] [!Mia,!Liz,!Bob,!key] [!Mia,!Liz,!Sam,!key] [!Mia,!Liz,!Sam,!Bob] S1 [!Liz,!Sam,!Bob, key] [!Mia,!Bob,!key] [!Mia,!Liz,!Bob,!key] [!Mia,!Liz,!Sam,!key] [!Mia,!Liz,!Sam,!Bob] S2 [!Liz,!Sam,!Bob,!key] [!Mia,!Bob,!key] [!Mia,!Liz,!Bob, key] [!Mia,!Liz,!Sam,!key] [!Mia,!Liz,!Sam,!Bob] S3 [!Liz,!Sam,!Bob,!key] [!Mia,!Bob,!key] [!Mia,!Liz,!Bob, key] [!Mia,!Liz,!Sam,!key] [!Mia,!Liz,!Sam,!Bob] S4 [!Liz,!Sam,!Bob,!key] [!Mia,!Bob, key] [!Mia,!Liz,!Bob,!key] [!Mia,!Liz,!Sam,!key] [!Mia,!Liz,!Sam,!Bob] S5 [!Liz,!Sam,!Bob,!key] [!Mia,!Bob, key] [!Mia,!Liz,!Bob,!key] [!Mia,!Liz,!Sam,!key] [!Mia,!Liz,!Sam,!Bob]
Отношение near, в соответствии с аксиомами, учитывает как непосредственное ребро near между объектами, так и между их положениями на полу:
near Mia Liz Sam Bob key S0 [!Liz, key] [!Mia, !Bob,!key] [] [ !Liz ] [ Mia,!Liz] S1 [ Liz, Sam,!Bob, key] [ Mia, Sam,!Bob, key] [ Mia, Liz,!Bob, key] [!Mia,!Liz,!Sam,!key] [ Mia, Liz, Sam,!Bob] S2 [ Liz, Sam,!Bob, key] [ Mia, Sam,!Bob, key] [ Mia, Liz,!Bob, key] [!Mia,!Liz,!Sam,!key] [ Mia, Liz, Sam,!Bob] S3 [!Liz,!Sam, Bob,!key] [!Mia, Sam,!Bob, key] [!Mia, Liz,!Bob, key] [ Mia,!Liz,!Sam,!key] [!Mia, Liz, Sam,!Bob] S4 [!Liz,!Sam, Bob,!key] [!Mia, Sam,!Bob, key] [!Mia, Liz,!Bob, key] [ Mia,!Liz,!Sam,!key] [!Mia, Liz, Sam,!Bob] S5 [ Liz, Bob, key] [ Mia, Bob, key] [] [ Mia, Liz, key] [ Mia, Liz, Bob]
Для near проблемным оказалось положение Сэма. Например, в начальном состоянии S0 (он должен быть рядом с Лизой). Связано это с отсутствием экстраполяции отношения near в прошлое (см. демоно set_undef). Если её добавить, возникнет другая проблема: в начальном состоянии Мия окажется не рядом с Бобом, что не так (для них в S0 отношение near равно Undef).
Полный текст скрипта, описанного в документе, находится в файле room01.zip. Главным скриптом является history01.ds. В нём, при помощи директив #include, подключаются ещё 4 скрипта: room_common.ds (демоны создния узлов графа Evs и их экстраполяция в прошлое) room_common_act.ds (демоны действий),room_common_mind.ds (обыденные знания), room_common_out.ds (демоны вывода).