Немонотонное обоснование
Подход, предложенный Дойлом [Doyle, 1979], отличается от того, который применил Мак-Аллестер. Он основан на философии "здравого смысла", в частности на презумпции значения по умолчанию. В первом приближении, помимо хранения допущений, подтвержденных какими-либо свидетельствами, хранятся также допущения, основанные на резонном предположении, т.е. допущения, свидетельства против которых отсутствуют.
Обоснования (или, пользуясь терминологией Доила, резоны) в пользу допущения Р представляют собой упорядоченную пару списков (IN P, OUT p). Список IN p – обычные обоснования в форме, которая аналогична использованной Мак-Аллестером. Он содержит высказывания, истинность которых является необходимым условием истинности Р. Список OUTp содержит высказывания, присутствие которых во множестве допущений указывает на ложность Р. Это множество получило название множества немонотонных обоснований (nonmonotonic justification), поскольку добавление высказывания в него потребует отказаться от сделанного ранее допущения. В подходе, который рассматривался Мак-Аллестером, этот вариант не анализировался.
Пусть, например, обоснование для значения р имеет вид:
({}, {-p}).
Это означает, что можно предполагать наличие р до тех пор, пока это обоснование не станет ложным. Обоснование для q пусть имеет вид:
({p}, {r}).
Такое обоснование означает, что можно предполагать наличие q до тех пор, пока высказывание р присутствует в множестве текущих допущений (в терминологии Доила – получает статус поддержки (support status) "включено" – in), а высказывание отсутствует в множестве допущений (в терминологии Доила – получает статус поддержки "исключено" – out). Обратите внимание на то, что обоснования могут быть связанными, как в приведенном выше примере. Если -р имеет статус исключено, то, следовательно, р имеет статус включено, а тогда и q имеет статус включено до тех пор, пока имеет статус исключено.
Такая цепочка причинно-следственных связей называется SL-обоснованием (SL – сокращение от support list). Общее правило для SL-обоснований гласит, что допущение Р присутствует в текущем множестве допущений только в том случае, если каждое из допущений, перечисленных в списке IN, имеет статус включено, а каждое из допущений, перечисленных в списке OUT, имеет статус исключено.
Дуальная структура обоснований, предложенная Дойлом, может быть использована для разделения допущений на три группы.
- (1) Посылки (premises), т.е. высказывания, которые полагаются истинными без всякого обоснования (по определению). Пользуясь обозначениями из теории множеств, можно следующим образом представить определение посылки: {Р
В | IN p = OUT p = не существует }. - (2) Дедукции (deductions), т.е. высказывания, которые являются заключениями нормальной монотонной дедукции. В обозначениях теории множеств дедукции представляются выражением
- (2) Проверить консеквенсы данного узла. Если таковых не существует, то изменить статус узла с исключено на включено, сформировать связанные с ним списки IN и OUT и на этом закончить. В противном случае сформировать список L, в который включить узел и его множество последствий, зафиксировать статус включено-исключено каждого из этих узлов, временно присвоить им статус nil и перейти к шагу (3).
- (3) Для каждого узла N из списка L попытаться отыскать действительное и убедительное обоснование, которое позволяет изменить статус этого узла на включено. Если таковое найдено не будет, присвоить узлу статус исключено. В любом варианте изменения статуса узла распространить это изменение на его консеквенсы. (Примечание. Обоснование является действительным, если каждый узел, перечисленный в его списке IN, имеет статус включено, а каждый узел, перечисленный в списке OUT, – статус исключено. Обоснование является убедительным в том случае, когда в его логической цепочке отсутствует зацикливание. Например, обоснования ({-Р},{}) и ({},{Р}) являются зацикленными по отношению к Р. Из первого следует, что Р имеет статус включено только в случае, если -P также имеет статус включено, а из второго следует, что Р имеет статус включено только в случае, если Р имеет статус исключено. Таким образом, каждое обоснование, если применить его в отношении высказывания Р, приводит к противоречию.)
- (4) Если некоторый узел в списке L имеет состояние включено и отмечен как противоречивый, то запустить процедуру обратного прослеживания, ведомого зависимостями (dependency-directed backtracking). Если в процессе выполнения этой процедуры вновь возникнут условия для запуска процесса отслеживания истинности предположений (шаги (1)-(3)), повторять эти шаги до тех пор, пока не будут разрешены все противоречия.
- (5) Сравнить текущий статус поддержки каждого узла из списка L с его прежним статусом, зафиксированным ранее, и известить пользователя обо всех произведенных изменениях статуса.
Обе системы – и Мак-Аллестера, и Доила – демонстрируют более "интеллектуальный" подход к решению проблемы адекватного и непротиворечивого описания мира, чем тот, который был использован в рассмотренной ранее системе STRIPS (см. главу 7). В обоих случаях системы отслеживания истинности предположений берут на себя заботы об обновлении модели мира посредством распространения аналогов операций ADD и DELETE по сети зависимостей. Если при этом обнаруживается, что в модели возникли противоречия, пользователю предлагается отказаться от какой-либо из посылок, которые послужили причиной такого противоречия, и восстановить тем самым целостность модели.