Лекция 15. Методы поиска решений в экспертных системах. 3 страница

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

Маккарти и Хэйес [1972] предложили следующий подход к решению фрейм-проблемы. Все факты разделяются на классы такие, что каждое действие относится только к одному классу, не изменяя остальных. Идея такой классификации развита в работе Хэйеса [1971] (к сожалению, такая классификация оказывается слишком грубой для практических задач). Каждому действию соответствует небольшое множество фактов, на которые это действие оказывает непосредственное влияние. Однако нельзя предполагать, что все остальные факты после совершения действия останутся неизменными, так как они могут зависеть, от изменившихся фактов по сложным причинно-следственным связям. Обозначим через АRB, что некоторый факт А изменяется при изменении причинно связанного с ним факта В. Если решатель может доказать, что ~ (АRB), то это означает, что изменения В не вызывают изменений А. Теперь при выполнений некоторого действия достаточно проверить для каждого факта А, что он не связан причинной связью ни с одним из фактов, изменяемых этим действием. Поясним сказанное на примере действий робота по перемещению ящиков. Трудность заключается в том, что если для состояния Sо известен факт:

НАХОДИТСЯ (В1,Х,S₀)

(ящик B1 находится в месте X), то неизвестно, где находится ящик В1 в состоянии S₁, вызванном движением робота из места У (в состоянии S₀) в место Z, (в состоянии S₁). Тот факт, что "положение некоторого объекта х останется неизменным после того, как робот перейдет из некоторого места и в место u, должен задаваться в явном виде.

Вопросы:

· Как классифицируются методы поиска решений в ЭС?

· Перечислите основные методы поиска.

· Опишите поиск решения в одном пространстве.

· Опишите поиск методом редукции.

· Опишите эвристический поиск.

· Опишите поиск методом "генерация - проверка".

· Опишите поиск в иерархии пространств.

· Опишите поиск в факторизованном пространстве.

· Опишите поиск в фиксированном множестве пространств.

· Какова роль ограничений при поиске?

· Опишите метапространство в иерархии пространств.

· Опишите поиск в альтернативных пространствах.