Итоги анализа систем решения проблем конструирования

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

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

Если задачи конструирования в определенной области могут иметь несколько вариантов решения, самая простая стратегия для экспертной системы — выбрать первое подходящее, ограничиваясь проверкой только жестких ограничений. Перебор нескольких вариантов и их последующее сравнение требует слишком больших вычислительных затрат. Это связано, в первую очередь, с тем, что проблемы конструирования или выбора компоновки многокомпонентной системы определены на довольно большом, а иногда и на бесконечно большом пространстве поиска вариантов, и этим они разительно отличаются от проблем классификации, рассмотренных в главах 11 и 12.

Совершенно очевидно, что размер пространства решений влияет на проблемы конструирования значительно сильнее, чем на проблемы классификации. Даже если обратиться к простейшим игровым задачам, вроде задачи о ферзях, которая рассматривалась в одном из упражнений главы 1, то и на их примере нетрудно убедиться, что метод, который позволит решить задачу о четырех или восьми ферзях, нельзя применить, когда речь пойдет о сотне или тысяче ферзей. Проблемы классификации относятся к числу тех, с которыми следует поступать по принципу "разделяй и властвуй", особенно если пространство категорий может быть организовано иерархически.

К слову сказать, существует множество реальных задач, типа планирования поведения роботов или составления расписания мероприятий, которые включают комбинаторику, не позволяющую использовать принцип "разделяй и властвуй". Частично это объясняется отсутствием подходящей метрики, которая позволила бы оценить, насколько близко конкретный фрагмент решения подходит к общему решению задачи. План можно оценить только целиком; нельзя сказать, насколько он будет хорош по характеристикам его отдельных этапов. Подход, основанный на "библиотеке заготовок" (он использовался в системе ONCOCIN; см. главу 10), также не годится для решения большинства проблем конструирования.

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

В главе 18 будет рассмотрена система, предназначенная для идентификации трехмерных структур протеинов в растворах. Комбинаторика, связанная с просмотром всех возможных вариантов компоновки молекул, совершенно очевидно не позволяет использовать исчерпывающий поиск или обратное прослеживание на сколько-нибудь значительную глубину. Поэтому программа организована таким образом, что в ней имеется несколько баз знаний, поддерживающих разные эвристики управления поиском в пространстве решений. Такая архитектура, получившая, название системы с доской объявлений (blackboard system), обеспечивает мощный механизм реализации таких стратегий, как последовательное уточнение частичных решений и восстановление после принятия неудачных решений.

В главе 19 мы рассмотрим системы обработки правдоподобия (truth maintenance) — усовершенствованный механизм фиксации решений, который существенно облегчает выполнение обратного прослеживания. В тех случаях, когда обратного прослеживания избежать невозможно, желательно, по крайней мере, быстро определить, в какую именно точку вычислений нужно вернуться, а не отменять по очереди все предыдущие операции, анализируя каждый раз последствия такой отмены.

Рекомендуемая литература

Применение экспертных систем для выполнения планирования рассматривается во множестве статей, включенных в популярные сборники, среди которых рекомендуем обратить внимание на следующие: [Nilsson, 1980], [Genesereth and Nilsson, 1987] и [Charniak and McDermott, 1985]. Читателей, интересующихся ранними исследованиями в области использования стратегии наименьшего принуждения для планирования, мы отсылаем к работе [Sacerdoti, 1974], Описание других исследований, касающихся решения проблем конструирования, можно найти в работах [Brown and Chandrasekaran, 1989] и [Coyne, 1988].

Результаты более поздних исследований представлены в книге [Dean and Wellman, 1991] и публикуемых IEEE трудах ежегодных конференций AI Simulation and Planning in High Autonomy Systems (выпуски за 1991 и 1992 гг.).

С системой EXPECT, которая является одной из автоматизированных систем приобретения знаний, аналогичной по возможностям рассмотренной _в этой главе системе VT, можно ознакомиться в работе [Gil and Paris, 1984].

Упражнения

1. Поясните смысл стратегии наименьшего принуждения. В чем отличие этой стратегии и стратегии предложение и пересмотр!

2. Постарайтесь перечислить как можно больше задач, к которым, по вашему мнению, можно применить стратегию наименьшего принуждения; нельзя применить стратегию наименьшего принуждения, не подкрепив ее какой-нибудь другой.

Подумайте о тех задачах, с которыми вы достаточно часто сталкиваетесь в повседневной жизни, например планирование похода по магазинам. Чем отличаются эти два класса задач?

3. Объясните смысл терминов метауровневая архитектура и метапланирование.

4. Проанализируйте программу, представленную во врезке 15.1. Подумайте над тем, каким образом нужно модифицировать данные, приведенные в операторе deffacts, -чтобы программа прервала работу, поскольку не смогла сформировать расписание, хотя, в принципе, его можно составить. (Указание: попробуйте манипулировать только приоритетами задач.)

5. Программа планирования мероприятий, представленная во врезке 15,1, не сможет составить расписание для следующего набора исходных данных, несмотря на то, что такое расписание существует.

(deffacts the-facts

(goal (subgoal start))

(errand (name hospital)

(earliest 1030)

(latest 1030) (duration 200) (priority 1))

(errand (name doctor)

(earliest 1430) (latest 1530)

(duration 200) (priority 1))

(errand (name lunch)

(earliest 1130) (latest 1430)

(duration 100) (priority 2))

(errand (name guitar-shop)

(earliest 1000) (latest 1700)

(duration 100) (priority 2))

(errand (name haircut)

(earliest 900) (latest 1700)

(duration 30) (priority 2))

(errand (name groceries)

(earliest 900) (latest 1800)

(duration 130) (priority 2))

(errand (name bank)

(earliest 930) (latest 1530)

(duration 30) (priority 2))

(errand (name dentist)

(earliest 900) (latest 1600)

(duration 100) (priority 1)))

Почему?

Ниже представлено дополнительное правило для программы составления расписания, которое позволит разрешить проблему, на которой программа споткнулась в предыдущем упражнении. Это правило разрешает конфликт между задачами, одна из которых должна начаться в точно зафиксированное время, а другая уже вставлена в расписание. Для этого вторая задача сдвигается в расписании. Если же в конфликте участвует задача, для которой не оговорено точное время начала, сдвигается та задача, которая имеет более низкий приоритет.

(defrule clash

(declare (salience 100))

(goal (subgoal fix))

?S <- (schedule (task?M) (start?M1))

(errand (name?N)

(earliest?E1) (latest?L1)

(duration?C)) (schedule

(task?N&"?M)

(start?Nl&:(and (<=?M1?Nl)

(<?N1 (+?M1?C)))))

(errand (name?N) (duration?D)

(earliest?E2) (latest?L2i:

(< (-?L2?E2) (-?L1?E1)))) =>

(printout t crlf?M " clashes with "?N t crlf)

;; (?M " конфликтует с "?N

(modify 7S (start (+t?N1?D))))

Это правило гласит: "В случае конфликта передвинуть в расписании ту задачу, которая имеет меньшее ограничение". Оно активизируется только в том случае, если текущей является подцель fix. Правила start и finish, которые контролируются подцелями start и finish, остаются без изменений.