Стратегии конструирования
Предположим, у вас возникла необходимость расставить мебель в комнате. Цель решения этой задачи можно сформулировать следующим образом: найти такой вариант расстановки, который, во-первых, удовлетворял бы заданным геометрическим ограничениям (комната имеет конечные размеры, в ней, возможно, имеются какие-то специфические особенности, например альков, предметы обстановки также имеют свои размеры и т.п.), а во-вторых, учитывал бы определенные предпочтения, касающиеся взаимного расположения предметов обстановки (рабочий стол возле окна, диван против телевизора и т.д.). Скорее всего вы начнете с того, что выберете место для одного-двух главных предметов, которые зададут "точки привязки" для остальных. Далее выполняется расстановка остальных предметов и проверяется, насколько полученный вариант удовлетворяет сформулированным требованиям.
Если вам очень повезет, то первый же вариант может оказаться удачным, но рассчитывать на это вряд ли стоит. Скорее всего окажется, что на каком-то этапе расстановки нарушаются сформулированные ограничения. Когда такое случится, совсем не обязательно отменять все ранее сделанное и возвращаться в самое начало процесса. Как правило, вы найдете способ, как, сдвинув пару-другую предметов, "втиснуться" в ограничения. Лучшим из способов такой "подстройки" является тот, который сохранит самую большую часть ранее проделанной работы.
Как уже не раз подчеркивалось, основная сложность решения задач конструирования состоит именно в том, что чаще всего нельзя заранее сказать, подойдет ли данная частично выполненная конструкция для окончательного варианта, т.е. можно ли будет, развивая дальше это частичное решение, получить окончательный вариант, удовлетворяющий всем ограничениям. В применении к задачам конструирования восходящая стратегия (стратегия снизу вверх), которую мы использовали для решения задач малой размерности, выглядит примерно так.
(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].
