Отслеживание истинности предположений, основанное на анализе допущений
В системах отслеживания истинности предположений, основанных на анализе допущений {assumption-based truth-maintenance system), программа имеет дело с несколькими отличающимися контекстами, которые принято называть средами обитания (environments) [De Kleer, 1986]. Удобнее всего представить себе среду обитания как взгляд на мир через призму определенных допущений. Можно считать, что модель мира, которая использовалась в предыдущих разделах, характеризуется пустым множеством допущений. Все прочие среды, имеющие непустое множество допущений, представляют модели гипотетических миров.
В системах отслеживания истинности предположений, основанных на допущениях, различные варианты сред обитания можно организовать в виде решетки, поскольку допущения носят инкрементальный
характер. Модель, показанная на рис. 19.3, представляет на самом нижнем уровне автомобиль, в котором не горит свет и который не удается завести. На более верхнем уровне решетки находятся гипотетические миры, в которых сделаны некоторые допущения о неисправностях в автомобиле, например разряжена аккумуляторная батарея. На еще более высоком уровне можно комбинировать сделанные допущения. Обратите внимание — чем выше мы поднимаемся "по ступеням решетки", тем более специфическими становятся гипотетические миры в том смысле, что мы характеризуем их все полнее.
Не всегда можно делать произвольные допущения. Например, нельзя объединить допущения {p,q} и {—p,r}, поскольку такая комбинация будет противоречивой. Более того, хотя само множество допущений может и не быть антагонистическим, определенные комбинации допущений могут привести к противоречию, если принять во внимание и другую имеющуюся в нашем распоряжении информацию.
Предположим, что наша модель неисправного автомобиля содержит информацию о том, что одновременно не может случиться так, чтобы и карбюратор не работал из-за избытка топлива, и в баке отсутствовал бензин. Следовательно, в том варианте среды, в котором сделано допущение "в баке отсутствует бензин", не может присутствовать допущение "избыток топлива в карбюраторе". Такое логическое заключение образует контекст среды — множество высказываний, производных от сделанных допущений, и фактов, имеющихся в исходной модели мира. Например, мы можем оказаться в ситуации, представленной схематически на рис. 19.4. Здесь среда, образованная в результате объединения двух допущений, должна быть исключена из рассмотрения, поскольку ее контекст становится несовместимым (nogood).
Рис. 19.3.
Решетка сред
В системах отслеживания истинности предположений, основанных на анализе допущений, такие зависимости называются обоснованиями (justification). Конечно, такая вольная трактовка термина "обоснование" вносит некоторую неоднозначность в изложение материала (ранее мы придавали этому термину несколько другой смысл), но дело в том, что обоснование в тех системах, которые рассматриваются в данном разделе, играет роль, отличную от обоснований в простых системах отслеживания истинности, анализированных Мак-Аллестером и Дойлом. В тех системах обоснования формировались программой в результате распространения принуждений и связывались с узлами сети зависимостей, которые представляли высказывания.
Рис. 19.4.
Решетка сред, в которой выделен несовместный контекст
На рис. 19.4 отрицание высказывания "Нет бензина в баке" существует в среде, в которой сделано допущение "Избыток топлива в карбюраторе", причем в модели имеется обоснование, которое гласит примерно следующее:
"Если в карбюраторе имеется избыток топлива, то бензин не может отсутствовать в баке".
Теперь интересующее нас высказывание будет "по наследству" истинно и в несовместимом контексте, но такая среда не представляет интереса для этого высказывания и, следовательно, в список ярлыка не включается.
Предположим также, что в модели имеется обоснование
"Если свечи влажные, то бензин не может отсутствовать в баке".
В этом случае отрицание высказывания "Нет бензина в баке" имеет место в среде, в которой сделано допущение "Влажные свечи", как показано на рис. 19.5. Эту среду уже имеет смысл включить в список ярлыка. Теперь ярлык интересующего нас высказывания будет содержать список, в котором перечислены два варианты среды, причем каждый из вариантов не содержит противоречий. На рисунке эти варианты среды заштрихованы. Как и ранее, варианты, представляющие несовместимый контекст (на рисунке они выделены прямоугольниками с утолщенными линиями контура), мы будем игнорировать.
Рис. 19.5.
Решетка сред, в которой узлы, имеющие непустые списки ярлыков, заштрихованы
Таким образом, из всего сказанного выше вытекает, что основная забота системы отслеживания истинности предположений, основанной, на анализе допущений, состоит в формировании списка сред для узлов высказываний. Такой список может быть созвучным (sound), завершенным (complete), совместимым (consistent) или минимальным (minimal) ярлыком. В эти термины вкладывается следующий смысл.
- Ярлык является созвучным,
если высказывание, к которому он относится, является производным от каждой
среды, включенной в этот ярлык, т.е. оно имеет статус включено в контексте
каждой такой среды.
- Ярлык является завершенным,
если любая непротиворечивая среда, в которой имеет место соответствующее
высказывание, либо присутствует в списке, либо образована включением дополнительных
допущений в ту среду, которая присутствует в списке.
- Ярлык является совместимым,
если любая среда, включенная в список, является непротиворечивой.
- Ярлык является минимальным,
если ни одна среда, включенная в список, не образуется добавлением какого-либо
допущения к той среде, которая также присутствует в списке.