Файл: Методыискусственногоинтеллекта.pdf

1.2. Системы, основанные на правилах, или продукционные системы
35
для формул же из множества D, которые также в результате этого процесса превратились в факты, значения, находящиеся на местах свободных переменных, удаляются из таблиц, соответствующих этим фактам в смысле отображения I.
В дальнейшем тройку: множество правил + рабочая память +
+ стратегия управления будем называть системой, основанной на
правилах.
Состоянием системы, основанной на правилах, будем называть со- стояние рабочей памяти вместе с множеством применимых правил.
Системы, основанные на правилах, являются важным классом си-
стем, основанных на знаниях.
1.2.4. Разрешение конфликтного множества правил.
Определение 1.2.4. Конфликтным множеством называется мно- жество правил, применимых к некоторому состоянию.
Разрешение конфликтного множества, т. е. выбор одного правила из множества применимых, достигается использованием тех или иных стратегий управления.
Можно выделить два основных типа стратегий управления [8, 10]:
безвозвратный и пробный. В стратегиях безвозвратного типа выбран- ное правило исполняется необратимо, без возможности пересмотра в дальнейшем. В пробном режиме резервируется возможность возврата к исходному состоянию для испытания другого правила.
Среди пробных режимов управления различаются режим с возвра-
щением, где запоминается точка возможного возврата, и управление с поиском на графе, где происходит запоминание результатов приме- нения нескольких цепочек правил с дальнейшим поиском на графовых структурах.
Безвозвратные стратегии управления используются, главным обра- зом, в коммутативных системах правил, поскольку, как мы покажем ниже, в коммутативных системах применение неудачного правила ото- двигает, но не блокирует завершение вычислений.
Определение 1.2.5. Последовательность правил называется при-
менимой, если условие каждого правила последовательности выполня- ется в состоянии, полученном в результате применения предыдущего правила.
Определение 1.2.6. Множество П правил коммутативно, если а) каждое из правил множества правил П, применимое к состоя- нию S рабочей памяти D, применимо к состоянию S
1
рабочей памяти D, полученному при выполнении любого применимого правила из П к S;
2*

36
Гл. 1. Методы представления знаний
б) целевое состояние, удовлетворяющееся некоторым состоянием S
рабочей памяти D, удовлетворяется состоянием, полученным из
S выполнением любого применимого правила из П;
в) в любой применимой последовательности перемена мест правил не приводит к изменению результирующего состояния.
Теорема 1.2.1. Если существует последовательность π правил
из множества П, переводящая начальное состояние
S
0
рабочей
памяти в целевое состояние
S
1
, и множество П коммутативно, то
любая иная применимая последовательность
π
∼
правил из П может
быть продолжена таким образом, что будет переводить состояние
S
0
в состояние, удовлетворяющее целевому состоянию
S
1
Д о к а з а т е л ь с т в о. Построим последовательность hπ, π
∼
i. В си- лу п. а) определения 1.2.6 эта последовательность будет применимой,
а в силу п. б) того же определения целевое состояние будет удовлетво- ряться результирующим состоянием этой последовательности.
Переместим правило П
∼
1
из последовательности π
∼
на место перво- го правила П
1
последовательнсти π так, чтобы правило П
1
оказалось вторым в этой последовательности.
Правило П
∼
1
окажется применимым к S
0
в силу условия теоремы,
а правило П
1
— применимым к S
1
в силу п. а) определения 1.2.6.
В силу п. в) того же определения такая перестановка не изменит результирующего состояния последовательности.
Продолжая выполнение перестановок до исчерпания правил по- следовательности π
∼
, получим последовательность hπ
∼
, πi, которая окажется применимой и удовлетворяющей целевое состояние S
1
. Тем самым, теорема доказана.
П
РИМЕЧАНИЕ
. Фраза «состояние X удовлетворяет состояние Y »
означает, вообще говоря, что формулы состояния Y выполняются в со- стоянии X; в нашем же случае, когда для простоты под состоянием понимается множество фактов, приведенная выше фраза означает, что
Y ⊆ X.
Из доказанной теоремы вытекает важное следствие о полноте
безвозвратных стратегий в коммутативных системах правил. Это означает, что в коммутативных системах правил можно использовать безвозвратные стратегии без риска потерпеть неудачу.
Таким образом, коммутативные системы правил представляют со- бой важный класс правил, обладающий полезными свойствами.
Стратегии с возвращениями. Стратегия с возвращениями основа- на на том, что запоминается всякое состояние, в котором сформировано конфликтное множество правил. Из этого конфликтного множества

1.2. Системы, основанные на правилах, или продукционные системы
37
выбирается некоторое правило П и применяется. К полученному со- стоянию применяется следующее применимое правило и т. д. Если этот путь не ведет к решению, то все сделанные шаги «забываются»
и вместо правила П выбирается другое правило.
Стратегии с возвращениями можно использовать независимо от того, насколько полной информацией для выбора подходящего правила мы располагаем. Если такая информация вообще отсутствует, можно выбирать правила в соответствии с произвольной схемой. В конечном счете, механизм возвращений позволит выбрать подходящее правило.
Однако если имеется информация о том, как выбрать подходящее правило, возвращения будут реже и вычисления окажутся более эф- фективными.
Если, например, на множестве состояний системы определить неко- торую функцию, значения которой будут говорить о «качестве» при- мененного правила, то выбор правила будет осуществляться на основе вычисления значений этой функции.
Второй путь состоит во введении на множестве состояний метрики таким образом, чтобы в этой метрике можно было бы оценивать сте- пень близости полученного состояния к целевому. Во многих случаях этот подход позволяет уменьшить число возвращений, а на монотонных участках траектории системы полностью их исключает.
Третий путь состоит в использовании знаний о возможных состо- яниях и переходах между ними: о тех, в которые следует переходить,
и о тех, которые являются «запрещенными». Например, в шахматных программах к первому типу относятся знания о гамбитах, эндшпилях,
миттельшпилях и т. д., ко второму типу — знания об угрозах коро- лю, другим фигурам и т. д. В системах, например, автоматического планирования сборочного процесса автомобильного двигателя к числу запрещенных состояний относится, в частности, состояние, в котором на двигатель установлена крышка газораспределительного механизма,
однако не установлен распределительный вал. Существует и ряд иных процедур «оптимизации» процесса поиска.
Стратегии поиска на графе. В стратегиях с возвращением управ- ляющая система забывает все пробные пути, не приведшие к успеху.
Однако если бы стратегия запоминала пробные пути для того, чтобы любой из них мог быть кандидатом на дальнейшее продолжение, такая стратегия была бы более гибкой.
Стратегию управления с поиском на графе можно рассматривать как средство нахождения пути на графе от вершины, являющейся исходным состоянием рабочей памяти, к вершине, являющейся целе- вым состоянием рабочей памяти. Часто оказывается полезным каждой дуге графа (i, j) приписать некоторое положительное число c(i, j) —

38
Гл. 1. Методы представления знаний
ее стоимость. Стоимость пути между двумя вершинами равна сумме стоимостей всех дуг на этом пути.
Задачи простейшего типа сводятся к поиску пути (возможно, с ми- нимальной стоимостью) между вершиной s, соответствующей началь- ному состоянию рабочей памяти, и известной вершиной t, соответству- ющей состоянию рабочей памяти, удовлетворяющему целевое условие.
Нередко встречается ситуация, в которой требуется найти путь между вершиной s и любой вершиной из множества {t}, представляющего состояния рабочей памяти, удовлетворяющие целевое условие.
В большинстве практически интересных случаев стратегия управле- ния используется для порождения фрагментов имплицитно заданных графов. Для имплицитного задания графа необходимо задать началь- ную вершину, представляющую исходное состояние рабочей памяти и правила изменения состояния. Таким образом, стратегию управления с поиском на графе можно рассматривать как процесс выявления под- графа имплицитного графа, содержащего целевую вершину.
Опишем в качестве примера порождения такого графа процедуру
SEARCH
Procedure SEARCH.
1. Создать списки INITIAL и FINISH; FINISH:=∅;
2. Создать граф поиска, состоящий из начальной вершины g1.
INITIAL := INITIAL
∪ g1;
3. M1: если INITIAL = ∅, то неудача, останов.
4. Упорядочить вершины в INITIAL в соответствии с некото- рым отношением;
5. Выбрать первую (в смысле порядка) вершину в INITIAL,
обозначить ее через f , INITIAL := INITIAL \{f };
FINISH := FINISH
∪ {f };
6. Если f - целевая вершина, то успешное завершение работы;
7. Породить из вершины f множество M = {m
1
, m
2
, ..., m k
} дочер- них вершин;
H := {(f , m
1
), (f , m
2
), ..., (f , m k
)};
8. INITIAL := INITIAL
∪H;
9. Перейти к п. 3.
Эта процедура порождает граф H, называемый графом поиска. На шаге 4 она должна упорядочивать вершины графа, так чтобы «лучшая»
из них была выбрана первой для порождения дочерних вершин. Это упорядочивание может основываться на различных эвристических иде- ях или иных критериях.
Рассмотрим некоторые из возможных эвристик. Один из подходов основан на введении оценочной функции v. При этом под v(n) ча- сто понимается оценка стоимости пути (минимальной стоимости) от исходной вершины к целевой, при условии, что этот путь проходит через вершину n. Упорядочение вершин графа в списке INITIAL будем производить таким образом, чтобы вершины располагались в порядке

1.2. Системы, основанные на правилах, или продукционные системы
39
возрастания соответствующих им функций v. При совпадении значений упорядочение осуществляется произвольным образом.
Если рассмотреть, например, игру в «8», то для нее можно взять простую оценочную функцию v(n) = d(n) + W (n), где d(n) — глуби- на вершины n на дереве поиска и W (n) — число находящихся на нужном месте фишек в состоянии рабочей памяти, соответствующем вершине n. Легко продемонстрировать, что применение процедуры
SEARCH
приводит к решению с испытанием меньшего числа вершин,
чем, например, при использовании оценочной функции v(n) = d(n).
Достаточно распространены эвристики с монотонными ограничени- ями: говорят, что эвристическая функция удовлетворяет монотонному ограничению, если для всех вершин n и m, таких что m — дочерняя вершина n, имеет место c(n, m) > v(n) — v(m), причем v(t) = 0, где t —
целевая вершина, а v(n) и v(m) — оценки стоимостей оптимального пути к целевой вершине t от вершин n и m, соответственно.
Можно показать, что если алгоритм SEARCH использует такую оценочную функцию, что ее значение v(n) для любой вершины n оце- нивает сумму стоимости пути (минимальной стоимости) от исходной вершины s к вершине n и стоимости аналогичного пути от вершины n к целевой и эта функция удовлетворяет монотонному ограничению, то алгоритм SEARCH обнаруживает оптимальный путь к любой вершине.

40
Гл. 1. Методы представления знаний
Итак, отображение I ставит в соответствие предикатному символу
On бинарное отношение на M , предикатным символам Em и Er —
одноместные отношения на M . Обозначим эти отношения так же, как соответствующие предикатные символы, только иным шрифтом. Иначе говоря, I(On) = On,
I(Em) = Em,
I(Er) = Er.
Поскольку все отношения конечны, то их можно представить в виде таблиц (рис. 1.2, а) и б)). Элементы множества M обозначим через m
1
, m
2
, ..., m n
Рис. 1.2. а) начальное состояние; б) целевое состояние
В начальном состоянии первая из таблиц не заполнена, а две другие заполнены полностью. Таким образом, на рис. 1.2, а) изображе- но начальное состояние «Мира кубиков». Целевое состояние должно иметь вид, приведенный на рис. 1.2, б; заметим здесь, что мы считаем все кубики идентичными и, поэтому, нумерации элементов из M не будем придавать значения.
Если мы принимаем решение использовать описания состояний,
приведенные на рисунках 1.2, а) и б) в качестве рабочей памяти си- стемы, основанной на правилах, то сами правила должны применяться к описаниям этих состояний для порождения новых состояний и такая система называется прямой системой правил. Однако в рабочей памяти можно хранить описания целей, подцелей и т. д. Такая система правил будет называться обратной. Впрочем, различие между этими двумя системами правил можно провести лишь на интуитивном уровне.