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

Методы конструктивного решения проблем применяются в экспертных системах, которые используются для планирования, проектирования и некоторых видов диагностирования.

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

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

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

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

Относительно простые случаи каждой из перечисленных задач вполне могут решаться методами классификации. Например, в главе 10 мы рассматривали систему ONCOCIN, которая формировала план лечения онкобольных, выбирая из библиотеки заготовки возможных вариантов. Выбранный вариант нуждался в дальнейшем только в конкретизации дозировок и расписания приема препаратов. Более сложные проблемы таким способом решить не удается, поскольку объем библиотеки заготовок пришлось бы сделать слишком большим. Для таких случаев единственно возможным становится конструктивный подход, который позволяет более гибко строить и модифицировать набор примитивных операций в формируемом плане действий.

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

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

Система R1/XCON

Система R1 была одной из первых успешных попыток применения экспертных систем в промышленности в начале 1980-х годов [McDermott, 1980], [McDermott, 1981], [McDermott, 1982,а]. Эта система предназначена для помощи разработчикам при определении конфигурации вычислительной системы на базе вычислительных устройств и блоков семейства VAX. Сначала программа проверяет полноту спецификации требований к проектируемой системе, которая представлена заказчиком. На втором этапе программа определяет конфигурацию системы, соответствующую этим требованиям. Коммерческая версия системы, разработанная совместно университетом Карнеги—Меллон и корпорацией Digital Equipment, получила наименование XCON. При описании истории разработки мы иногда будем обращать ваше внимание на отличия между начальным проектом и его коммерческой версией.

Первым практическим применением системы XCON была разработка конфигурации вычислительного комплекса VAX-11/780 на заводе фирмы DEC в Салеме, шт. Нью-Гемршир. Затем последовала разработка конфигураций других типов вычислительных комплексов, таких как VAX-11/750 и последующих модификаций продукции DEC. Наш интерес к этой экспертной системе объясняется тем, что она продемонстрировала, чего можно достичь при использовании даже относительно слабого метода решения проблем, если имеется достаточно знаний о предметной области. История развития этой системы также показывает, как расширяется сфера применения коммерческой экспертной системы при правильном менеджменте и как системы такого типа "врастают" в производственную среду.

Задачу системы R1 нельзя отнести к типу тривиальных. Типовой вычислительный комплекс включает 50-100 компонентов, главными из которых являются центральный процессор, устройство управления оперативной памятью, блоки управления интерфейсом по шинам UNIBUS и MASSBUS, причем все эти компоненты подключены к единой плате синхронизации. Шинные интерфейсы поддерживают обмен с широкой номенклатурой периферийных устройств — устройствами внешней памяти на магнитных лентах и дисках, принтерами и т.п. В результате имеется возможность строить системы самой различной конфигурации.

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

Компоненты и ограничения

Хотя и R1, и MYCIN являются программами, использующими в своей работе порождающие правила, между ними имеется ряд серьезных отличий. Одно из них состоит в том, что в MYCIN процесс решения проблемы направляется гипотезами (hypothesis-driven), т.е. процесс начинается с формулировки определенной цели, а затем она преобразуется в набор подцелей, совместное достижение которых позволяет достичь главной цели (см. об этом в главе 3). В системе R1 главным является подход, предполагающий, что процесс решения направляется данными (data-driven). Сначала программа определяет множество компонентов и далее пытается сконструировать такую конфигурацию этих компонентов, которая удовлетворяла бы ограничениям, вытекающим как из характеристик отдельных компонентов, так и из отношений и связей между ними. Для реализации программы был использован язык OPS5, один из первых языков представления правил, прямой предшественник языка CLIPS.

Для успешной работы программа R1 нуждается в знаниях двух видов:

о характеристиках компонентов — электрических (напряжение питания, потребляемая мощность, параметры выходных сигналов и т.п.), механических (габариты, тип и количество разъемов), структурных (количество портов) и т.п.;

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

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

RK611

CLASS: UNIBUS MODULE

TYPE: DISK DRIVE

SUPPORTED: YES