Продукционные системы

Развитие мыслительных способностей машин уже долгие годы является темой исследований. Выяснилось, что большой класс проблем мышления обладает сходными характеристиками. Эти характеристики объединены в систему, известную как продукционная система (production system), которая состоит из трех основных компонентов:

1. Набор состояний. Каждое состояние (state) — это ситуация, которая может возникнуть в программной среде. Начальное состояние называется стартовым (start state); желаемое состояние (или состояния) называется целевым состоянием (goal state). (В нашем случае состояние — это конфигурация головоломки; начальное состояние — конфигурация головоломки, когда она передается машине; целевое состояние — конфигурация собранной головоломки, как показано на рис. 10.2.)

2. Набор порождений (правил перемещения). Порождение (production) — это операция, которая может быть выполнена в программной среде для перехода из одного состояния в другое. Каждое порождение может быть связано с входными условиями, то есть в среде могут существовать условия, необходимые для применения порождения. (В нашем случае порождения — это перемещения фишек. Для каждого перемещения фишки существует входное условие, которое заключается в том, что рядом с ней должно быть свободное место.)

3. Система управления. Система управления (control system) состоит из логики, решающей проблему перехода из начального в целевое состояние. На каждом шаге процесса система должна выбирать, какое из порождений, для которых в данный момент выполнены входные условия, необходимо применить. (Рассмотрев определенное состояние головоломки, мы обнаружим, что рядом со свободным местом есть несколько фишек, то есть применить можно несколько порождений. Система управления должна решить, какую фишку необходимо передвинуть.)

Обратите внимание, что задачу для нашей машины для решения головоломки можно сформулировать в контексте продукционной системы. В этом случае система управления принимает форму программы, которая изучает текущее состояние головоломки, определяет последовательность порождений, которые приведут к целевому состоянию, и выполняет эту последовательность. Наша задача — разработать систему управления для решения головоломки.

Важная составляющая разработки системы управления — граф состояний (state graph). Это удобный способ представления всех состояний, порождений и входных условий продукционной системы. Термин «граф» обозначает структуру, которую математики называют направленным графом (directed graph), что означает, что набор положений, называемых узлами (nodes), соединен стрелками. Граф состояний состоит из узлов, представляющих состояния системы, соединенных стрелками, обозначающими порождения, которые переводят систему из одного состояния в другое. Два узла соединены стрелкой в графе состояний тогда и только тогда, когда в продукционной системе существует порождение, преобразующее систему из состояния в начале стрелки в состояние в конце стрелки. Входные условия неявно представляются отсутствием стрелок между определенными узлами.