ГЛАВА 15. Решение проблем конструирования (II)

Стратегии конструирования

15.2. Архитектура систем планирования и метапланирования

Извлечение, представление и применение знаний о проектировании

Реализация обратного прослеживания в системе VT

Приобретение знаний с помощью системы SALT

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

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

Упражнения

ГЛАВА 15. Решение проблем конструирования (II)

Стратегии конструирования

15.2. Архитектура систем планирования и метапланирования

Извлечение, представление и применение знаний о проектировании

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

Упражнения

В предыдущей главе мы рассматривали экспертные системы для решения проблем конструирования, в которых по ходу процесса никогда не возникала необходимость отмены уже принятых решений. Однако такая стратегия подходит далеко не для всех задач конструирования, поскольку мы не всегда располагаем всеми необходимыми для этого знаниями о предметной области. В этой главе мы проанализируем применение двух стратегий — наименьшего принуждения (least commitment) и предложение и пересмотр (propose and revise). Завершит главу обзор некоторых инструментальных средств приобретения знаний, которые используются в системах решения проблем конструирования.

Стратегии конструирования

Предположим, у вас возникла необходимость расставить мебель в комнате. Цель решения этой задачи можно сформулировать следующим образом: найти такой вариант расстановки, который, во-первых, удовлетворял бы заданным геометрическим ограничениям (комната имеет конечные размеры, в ней, возможно, имеются какие-то специфические особенности, например альков, предметы обстановки также имеют свои размеры и т.п.), а во-вторых, учитывал бы определенные предпочтения, касающиеся взаимного расположения предметов обстановки (рабочий стол возле окна, диван против телевизора и т.д.). Скорее всего вы начнете с того, что выберете место для одного-двух главных предметов, которые зададут "точки привязки" для остальных. Далее выполняется расстановка остальных предметов и проверяется, насколько полученный вариант удовлетворяет сформулированным требованиям.

Если вам очень повезет, то первый же вариант может оказаться удачным, но рассчитывать на это вряд ли стоит. Скорее всего окажется, что на каком-то этапе расстановки нарушаются сформулированные ограничения. Когда такое случится, совсем не обязательно отменять все ранее сделанное и возвращаться в самое начало процесса. Как правило, вы найдете способ, как, сдвинув пару-другую предметов, "втиснуться" в ограничения. Лучшим из способов такой "подстройки" является тот, который сохранит самую большую часть ранее проделанной работы.

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

(1) Если это возможно, начать с частичного варианта расстановки, который удовлетворяет заданным ограничениям. В противном случае начать с размещения первого компонента.

(2) Если расставлены все компоненты, прекратить процесс. В противном случае выполнить "наиболее многообещающее" расширение текущего варианта — поместить в планировку новый компонент.

(3) Если новый вариант размещения "не вписывается" в ограничения, предложить такой способ корректировки этого варианта, который требует как можно меньших переделок выполненных этапов.

(4) Перейти на шаг 2.

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

При решении задачи расстановки множества предметов может оказаться, что пространство поиска будет очень большим и таким образом проблема может перейти в разряд нерешаемых. Но, как правило, такие задачи можно упростить, рассматривая их на разном уровне представления деталей. Рассмотрим, например, задачу планировки дома на заданном участке земли. Пусть сейчас нас интересует компоновка помещений. Эту задачу можно сформулировать на разных уровнях абстракции (см. [Rosenman et al, 1987]):

в терминах взаимного положения, например "комната А рядом с комнатой Б";

в терминах ориентации, например "комната А на север от комнаты Б";

в терминах координат, которые точно указывают положение комнаты А по отношению к комнате Б.

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

Такой иерархический подход хорошо знаком тем, кто часто имеет дело с проектированием планировок. Что касается экспертных систем, предназначенных для такого рода задач, то в таких системах, как NOAH [Sacerdoti, 1974] и NONLIN [Tate, 1977], которые явились развитием программы STRIPS, упрощение пространства поиска было достигнуто за счет следующего:

действия на более высоких уровнях абстракции рассматриваются как группы, объединяющие целую последовательность действий более низких уровней;

проблема планирования решается в терминах частичного упорядочения таких групп;

уточнение деталей выполняется на все более низких уровнях абстракции до тех пор, пока план не будет полностью завершен.

Описанный подход к решению проблемы можно отнести к типу нисходящих. В чем-то он напоминает организацию задача-подзадача, принятую в системе R1. Но существенное отличие от системы R1 состоит в том, что в данном случае иногда приходится пересматривать уже принятые решения в пределах одного и того же уровня абстракции, чего в программе R1 никогда не делается. Это и есть реализация той части стратегии, которая обозначена словом пересмотр в общем названии предложение и пересмотр (propose and revise). При решении очень сложных задач планирования иногда приходится выполнять пересмотр решений, принятых и на более верхних уровнях абстракции, а затем возвращаться на текущий уровень. Конечно, желательно по возможности избегать такого переноса, а потому серьезное внимание должно быть уделено выработке наиболее перспективных предложений и реализации стратегии наименьшего принуждения.

В следующем разделе мы рассмотрим систему MOLGEN [Stefik, 1981, a], [Stefik, 1981, b], которая предназначена для планирования экспериментов в исследованиях по молекулярной генетике. По ходу описания системы мы еще раз обратим ваше внимание на те моменты, о которых шла речь в этом разделе. Эта система является хорошим примером применения многоуровневого подхода на основе стратегии наименьшего принуждения для решения проблем конструирования. В разделе 15.3 будет рассмотрен метод восходящего решения проблем в системе VT [Marcus et al, 1988]. Эта система предказначена для проектирования лифтовых систем и использует стратегию предложение и пересмотр. В этом же разделе вы познакомитесь с методикой приобретения знаний, основанной на использовании инструментальной системы SALT [Marcus, 1988, b].

15.2. Архитектура систем планирования и метапланирования

Экспертная система MOLGEN, предназначенная для планирования экспериментов в исследованиях по молекулярной генетике, имеет многоуровневую организацию, в которой каждый более верхний уровень управляет расположенными ниже. Такой вид организации экспертной системы получил в литературе название метауровневой архитектуры (meta-level architecture). Идея состоит в том, что в дополнение к представлению "первого уровня" проблемы в предметной области добавить еще более высокие уровни, представляющие такие понятия, как возможные действия с объектами предметной области, критерии выбора и комбинирования таких действий.

В терминологии системы MOLGEN уровни управления называются пространствами планирования (planning space). Программа использует три таких пространства, каждое из которых имеет собственные объекты и операторы, которые взаимодействуют друг с другом с помощью протоколов передачи сообщений (см. главу 7). Схематически организация уровней управления в системе MOLGEN представлена на рис. 15.1. На этой схеме в левой части прямоугольников, представляющих каждое пространство планирования, приведен список некоторых операторов этого пространства. Интерпретатор организует внешний цикл управления системой. Фактически он формирует и следит за соблюдением определенной стратегии поведения системы. Как будет показано ниже, в этих стратегиях реализуется логический вывод суждений на метауровне, которые управляют способом решения проблемы планирования эксперимента.

Мы начнем анализ архитектуры системы MOLGEN с самого нижнего уровня — пространства лабораторных экспериментов (laboratory space). В этом пространстве содержатся знания об объектах и операциях, выполняемых в лаборатории в процессе проведения экспериментов. Объектами этого пространства являются те сущности, которыми манипулируют лаборанты, а операторы — это те действия, которые с этими сущностями могут выполняться, например сортировка, слияние и т.д. Мы не будем подробно останавливаться на этом уровне. Читатели, которых интересуют подробности его организации, могут обратиться к статьям Стефика [Stefik, 1981, а] и [Stefik, I981, b].

Пространство разработки (design space) содержит знания о планах проведения экспериментов в форме классов операторов для выполнения следующих действий:

проверки прогнозируемых характеристик и выявления необычных характеристик объектов — операторы сравнения (comparison-operators),

формирования предложений относительно целей, операций и прогнозируемых результатов — операторы временного расширения (temporal-extension operators);

уточнения этапов плана в соответствии с имеющимися ограничениями — операторы специализации (specialization operators).

Например, оператор Propose-Goal (предложение цели) относится к группе операторов временного расширения и устанавливает для лабораторного пространства цели проведения экспериментов. Оператор Check-Prediction (проверка прогнозируемых результатов) относится к группе операторов сравнения и выполняет сравнение прогнозируемых результатов экспериментов с текущей целью. Оператор Refine-Operator (уточнение) входит в группу операторов специализации. Он заменяет в форме уточняемого плана абстрактные этапы в операциях пространства лабораторных экспериментов на более конкретные.

Рис. 15.1. Организация пространств планирования в системе MOLGEN ([Stefik, 1981,b])

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