Часть 4.

правил в пользу таких альтернативных схем, как нейронные сети или генетические алгоритмы (часть IV)?

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

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

7.2. Экспертные системы, основанные на правилах

В экспертных системах, основанных на правилах, знания о решении задач представляют в виде правил "если..., то...". Этот подход, являясь одним из старейших методов представления знаний о предметной области в экспертной системе, применяется в системах, архитектура которых показана на рис. 7.1. Как один из наиболее естественных он широко используется в коммерческих и экспериментальных экспертных системах.

7.2.1. Продукционная система и решение задач на основе цели

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

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

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

282 Часть III. Представление и разум в ракурсе искусственного интеллекта

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

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

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

Правило 1: если

топливо поступает в двигатель и

двигатель вращается,

то

проблема в свечах зажигания. Правило 2: если

двигатель не вращается и

фары не горят,

то

проблема в аккумуляторе или проводке. Правило 3: если

двигатель не вращается и

фары горят,

то

проблема в стартере. Правило 4: если

в баке есть топливо и

топливо поступает в карбюратор,

то

топливо поступает в двигатель.

Для работы с этой базой знаний цель верхнего уровня проблема в X помещается в рабочую память, как показано на рис. 7.5. Здесь X- переменная, которая может сопоставляться с любой фразой, например, проблема в аккумуляторе или проводке. В процессе решения задачи она будет связана с некоторым значением. С выражением в рабочей памяти сопоставляются три правила: правило 1, правило 2 и правило 3. Если мы разрешаем конфликты, предпочитая правила с наименьшим номером, будет активизироваться правило 1. При этом X связывается со значением свечи зажигания, и предпосылки правила 1 помещаются в рабочую память (рис. 7.6). Таким образом, система выбирает для исследования гипотезу о неисправности свечей зажигания. Это можно рассматривать как выбор системой ветви ИЛИ на графе И/ИЛИ (глава 3).

Отметим, что для истинности заключения правила 1 должны быть удовлетворены две предпосылки. Они являются ветвями И графа поиска, представляющего декомпозицию задачи (действительно ли проблема в свечах зажигания) на две подзадачи (топливо поступает в двигатель и двигатель вращается). Затем можно активизировать правило 4, заключение которого сопоставляется с целевым утверждением топливо поступает в двигатель, и его предпосылки помещаются в рабочую память (рис. 7.7).

Глава 7. Сильные методы решения задач 283

284 Часть III. Представление и разум в ракурсе искусственного интеллекта

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

Конечно, это очень простой пример. И не только потому, что база знаний об автомобиле ограничена, а также потому, что в этом примере не учитывается ряд важных аспектов реализации. Правила описаны на русском, а не на формальном языке. При обнаружении решения реальная экспертная система сообщит пользователю свой диагноз (наша модель просто останавливается). Необходимо также поддерживать достаточно длинную историю рассуждений, чтобы в случае необходимости возвратиться назад. Если вывод о неисправности свечей зажигания окажется неудачным, нужно иметь возможность возвратиться на второй уровень и проверить правило 2. Заметим, что информация по упорядочению подцелей в рабочей памяти на рис. 7.7 и на графе, представленном на рис. 7.8, явно не выражена. Однако, несмотря на простоту, этот пример подчеркивает важность поиска на основе продукционной системы и его представления графом И/ИЛИ в экспертных системах, основанных на правилах.

Ранее мы подчеркивали, что экспертная система должна быть открытой для инспектирования, легко модифицируемой и эвристической по природе. Архитектура продукционной системы является важным фактором для каждого из этих требований. Легкость

Глава 7. Сильные методы решения задач 285

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

7.2.2. Объяснения и прозрачность при рассуждениях на основе цели

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

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

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

в баке есть топливо? да

топливо поступает в карбюратор? да

двигатель вращается? почему - Здесь пользователь задает вопрос: "Почему вы хотите знать, вращается ли двигатель?". Система отвечает с помощью символьного представления правила, к которому относится вопрос.

Было установлено, что:

топливо поступает в двигатель,

поэтому если

двигатель вращается,

то проблема в свечах зажигания.

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

как топливо поступает в двигатель?

286 Часть III. Представление и разум в ракурсе искусственного интеллекта

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

Из правила 4 следует:

если

в баке есть топливо и

топливо поступает в карбюратор,

то

топливо поступает в двигатель.

в баке есть топливо - указано пользователем

топливо поступает в карбюратор - указано пользователем

Таким образом, архитектура продукционной системы обеспечивает основу для этих объяснений. В каждом цикле управления выбирается и активизируется новое правило. После каждого цикла программа может быть остановлена и проинспектирована. Поскольку каждое правило представляет "глыбу" знаний по решению проблемы, текущее правило обеспечивает контекст для объяснения. Этим продукционный подход отличается от более традиционных архитектур: если программу на С или C++ остановить во время исполнения, то вряд ли текущее выражение будет иметь много смысла.

Итак, система, основанная на знаниях, отвечает на вопросы "почему?", отображая текущее правило, которое она пытается активизировать. В ответ на вопросы "как?" она предоставляет последовательность рассуждений, которая привела к цели. Хотя эти механизмы являются концептуально простыми, они обладают хорошими возможностями объяснений, если база знаний организована логически грамотно. Главы по языкам LISP и PROLOG в части IV демонстрируют использование стеков правил и деревьев доказательств для объяснений. Если объяснения должны быть логичными, важно не только, чтобы база знаний выдавала корректный ответ, но и чтобы каждое правило соответствовало одному шагу процесса решения проблемы. Если в одном правиле базы знаний заключено несколько шагов или правила сформулированы произвольным образом, получить правильные ответы на вопросы "как?" и "почему?" будет сложнее. Это не только подрывает доверие пользователя к системе, но и делает программу более трудной для понимания и модификации разработчиками.

7.2.3. Использование продукционной системы для рассуждений на основе данных

Пример диагностики автомобиля в подразделе 7.2.1 иллюстрирует использование продукционной системы для реализации поиска на основе цели. В этом примере использовался поиск в глубину, так как перед переходом к соседним целям для каждой обнаруженной в базе правил подцели производился исчерпывающий поиск. Однако, как мы видели в разделе 5.3, продукционная система является также идеальной архитектурой и для рассуждений на основе данных. В примере 5.3.1 этот процесс был продемонстрирован для игры в "пятнашки", а в примерах 5.3.2 и 5.3.3 - для задачи о ходе конем. В каждом из этих примеров конфликт разрешался посредством извлечения и применения первого обнаруженного в базе знаний правила. При этом выполнялся поиск в глубину, хотя в этих примерах не было механизма возврата для выхода из "тупиковых состояний" в пространстве поиска.

В рассуждениях на основе данных чаще применяется поиск в ширину. Алгоритм очень прост: содержимое рабочей памяти сравнивается с предпосылками каждого пра-

Глава 7. Сильные методы решения задач 287

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

Рассмотрим, например, задачу автомобильной диагностики на основе правил из подраздела 7.2.1. Если предпосылка правила не выводится из других правил, то недостающая информация запрашивается при необходимости. Например, предпосылка правила 1 топливо поступает в двигатель не является запрашиваемой, так как этот факт является заключением другого правила, а именно - правила 4.

Поиск в ширину на основе данных начинается из состояния, показанного на рис. 7.9. Оно очень напоминает состояние, изображенное на рис. 7.5. Отличие состоит лишь в отсутствии информации в рабочей памяти. Предпосылки четырех правил проверяются на предмет "запрашиваемой" информации. Предпосылка топливо поступает в двигатель не является запрашиваемой, поэтому правило 1 применить нельзя, и управление переходит к правилу 2. Информация двигатель не вращается является запрашиваемой. Предположим, ответом на этот вопрос будет ложь, тогда в рабочую память заносится фраза двигатель вращается, как показано на рис. 7.10.

Но правило 2 применить нельзя, поскольку первая из двух конъюнктивных предпосылок является ложной. Управление переходит к правилу 3, в котором первая посылка снова принимает значение "ложь". В правиле 4 обе предпосылки являются запрашиваемыми. Предположим, ответом на оба вопроса будет "истина", тогда предложения в баке есть топливо и топливо поступает в карбюратор помещаются в рабочую память. Туда же заносится и заключение правила - топливо поступает в двигатель.

288 Часть III. Представление и разум в ракурсе искусственного интеллекта

Итак, по первому разу все правила рассмотрены, и начинается повторное рассмотрение правил с учетом нового содержания рабочей памяти. Как показано на рис. 7.11, при сопоставлении правила 1 с данными в рабочей памяти его заключение - проблема в свечах зажигания - помещается в рабочую память. Больше никаких правил применить нельзя, и сеанс решения задачи завершается. На рис. 7.12 показан граф поиска, узлы которого содержат информацию, находящуюся в рабочей памяти (РП).

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

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

Глава 7. Сильные методы решения задач 289

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

Во-вторых, и это является прямым результатом только что сказанного, пояснения, выдаваемые пользователю в процессе поиска, весьма ограничены. В системах на основе правил в ответ на вопрос "почему?" пользователю представляется рассматриваемое правило (см. подраздел 7.2.2). Однако, если последовательность правил точно не отслеживается (например, с помощью оппортунистического поиска), это объяснение нельзя развить. "Расплывчатость" поиска на основе данных затрудняет подобные объяснения. И, наконец, при достижении цели системе трудно дать исчерпывающее объяснение в ответ на вопрос "как?". В качестве частичного или полного объяснения можно лишь использовать содержимое рабочей памяти или список активизированных правил. Но опять-таки эти пояснения не дают полного согласованного обоснования, которое мы наблюдали в рассуждениях на основе цели.

7.2.4. Эвристики и управление в экспертных системах

Вследствие разделения базы знаний и механизма вывода, а также особенностей работы механизма вывода важным методом программного управления поиском является структурирование и упорядочение правил в базе знаний. Такое микроуправление на множестве правил открывает новые возможности, особенно с учетом зависимости стратегий управления от специфики предметной области и объема знаний. Хотя правило вида if p, q, and r then s (если р, q и г, то s) напоминает логическое выражение, оно может быть интерпретировано как последовательность процедур или шагов решения задачи: "чтобы получить s, сначала нужно выполнить р, затем q, затем r". Важность упорядочения правил и их предпосылок была неявно продемонстрирована в только что рассмотренных примерах из раздела 7.2.

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

Есть еще одна причина для такого упорядочения. Если двигатель не вращается, то не имеет значения, поступает ли в него топливо. В правиле 4 пользователя сначала просят

290 Часть III. Представление и разум в ракурсе искусственного интеллекта

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

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

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

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

До сих пор в своем обсуждении мы описывали поведение продукционной системы в терминах исчерпывающего рассмотрения базы правил. Хотя такое поведение является достаточно дорогостоящим, оно включает внутреннюю семантику продукционной системы. Однако существует ряд алгоритмов, таких как RETE [Forgy, 1982], которые могут быть использованы для оптимизации поиска потенциально полезных правил. По существу, алгоритм RETE интегрирует правила в сетевую структуру, позволяющую системе сопоставлять правила с данными, прямо указывающими на правило. Этот алгоритм значительно ускоряет выполнение, особенно для больших множеств правил, в то же время сохраняя семантику поведения, описанную в данном разделе.

И в заключение, правила были и остаются важным средством построения решателей

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

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

правил управления нерегулярными случаями и другими исключениями. Во многих

Глава 7. Сильные методы решения задач 291

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

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

7.3. Рассуждения на основе моделей, на базе опыта и гибридные системы

7.3.1. Введение в рассуждения на основе модели

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

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

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

292 Часть III. Представление и разум в ракурсе искусственного интеллекта

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

Поскольку экспертные системы первого поколения основывались на эвристических правилах, полученных из описаний методов решения задач человеком-экспертом, они обладали рядом ограничений [Clancy, 1985]. Если ситуация не соответствовала заложенным в систему эвристикам, она просто терпела неудачу, хотя более строгий теоретический анализ мог бы привести к успешному решению. Часто экспертные системы применяли эвристики в несоответствующих ситуациях, в которых более глубокое понимание проблемы могло бы указать другой курс. Эти ограничения позволяют преодолеть подходы, основанные на моделях. Механизм рассуждения, который базируется на спецификации и функциональности физической системы, называется системой на основе модели. Система рассуждений на основе модели осуществляет программное моделирование тех функций, которые необходимо понять или зафиксировать. (Существуют, конечно, и другие типы систем, основанных на моделях, в частности, логические и стохастические. Они будут рассмотрены в главе 8.)

Первые системы рассуждений на основе моделей появились в середине 1970-х и продолжали развиваться в 1980-х годах [Davis и Hamscher, 1992]. Интересно отметить, что некоторые из наиболее ранних работ были направлены на создание программных моделей различных физических приборов, таких как электронные цепи, с целью их изучения [deKleer, 1976], [Brown и др., 1982]. В этих работах прибор или цепи описывались в виде набора правил, например, законов Кирхгофа и Ома. Обучающая система могла проверить знания студента в данной области, а также передать ему недостающие данные. Правила, с одной стороны, обеспечивали представление функциональности, а с другой - представляли собой среду для передачи знания студенту. Развитием этих ранних обучающих систем, задача которых сводилась к моделированию и обучению функциональности системы, стали системы рассуждения на основе моделей, предназначенные для устранения неисправностей. При выявлении неисправности в физической системе модель предлагает множество прогнозируемых вариантов поведения. Неисправность отражается в различии между ожидаемым и наблюдаемым поведением. Система, основанная на модели, сообщает пользователю, чего ожидать, а различия между наблюдаемым и ожидаемым поведением приводят к идентификации неисправностей.

Качественные рассуждения на основе моделей включают следующие аспекты.

Описание каждого компонента прибора, позволяющее моделировать их поведение.

Описание внутренней структуры прибора. Оно обычно содержит представление

компонентов и их взаимосвязей наряду с возможностью моделировать их взаимодействие. Требуемая степень знаний внутренней структуры зависит от применяемого уровня абстракции и ожидаемого диагноза.

Диагностика частной проблемы. Это требует наблюдений реального поведения

прибора, обычно - измерения его входов и выходов. Входные и выходные измерения получить легче всего.

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

Для представления причинно-следственной и структурной информации в моделях можно использовать различные структуры данных. Для отражения причинности и

Глава 7. Сильные методы решения задач 293

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

Чтобы конкретизировать процесс разработки и описания модели, рассмотрим несколько примеров анализа устройств и цепей, взятых из работы [Davis и Hamscher, 1992]. Поведение устройства описывается множеством выражений, определяющих отношения между значениями на клеммах прибора. Для сумматора, показанного на рис. 7.13, эти выражения имеют такой вид.

Если известны значения в точках А и В, то значение в точке С

вычисляется как А+В (сплошная линия).

Если известны С и А, значение в точке В вычисляется как С-А

(крупный пунктир).

Если известны значения С и В, значение в точке А вычисляется

как С-В (пунктир).

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

В качестве второго примера рассмотрим схему из трех мультиплексоров и двух сумматоров (рис. 7.14). В этом примере входные значения задаются в точках А-Е, а выходные вычисляются в точках F и G. Ожидаемые выходные значения задаются в круглых скобках, а действительные выходы - в квадратных. Задача заключается в определении неисправности, объясняющей различие между этими значениями. В точке F наблюдается конфликт: ожидаемым выходным значением является 12, а реально полученным - 10. Проверяя зависимости в этой точке, определяем, что значение в точке F вычисляется как функция от ADD-1. Это значение, в свою очередь, зависит от выходов MULT-1 и MULT-2. Одно из этих устройств содержит неисправность, следовательно, необходимо рассмотреть три гипотезы: либо поведение сумматора неадекватно, либо некорректным является один из двух его входов. Тогда проблему надо искать дальше в цепи.

Если исходя из результата F (значения 10) предположить, что поведение ADD-1 и значение б его первого входа X корректны, то значение на втором входе ADD-1 (обозначим его Y) должно быть равно 4. Но это противоречит ожидаемому значению 6, являющемуся результатом правильного поведения MULT-2 и входов В и D. Мы наблюдали за этими входами и знаем, что на них поступали правильные значения.

294 Часть III. Представление и разум в ракурсе искусственного интеллекта

Следовательно, неисправен модуль MULT-2. Вариантом второй гипотезы может быть предположение, что модуль ADD-1 исправен, а неисправен компонент MULT-1.

Продолжая рассуждения, приходим к выводу, что если на первый вход X модуля ADD-1 поступает корректное значение и сам ADD-1 работает корректно, то значение второго входа Y должно быть равно 4. Если это так, то G должно принимать значение 10, а не 12, так что выход MULT-2 должен равняться б и быть корректным. Здесь мы отбрасываем гипотезу, что неисправность содержится в MULT-1 или в ADD-1. Эти модули можно рассмотреть при дальнейшем тестировании.

В рассуждениях о ситуации, показанной на рис. 7.14, рассматривались три задачи.

Создание гипотезы о том, какие компоненты устройства могли вызвать расхождение ожидаемого и реального значений.

Проверка гипотезы, в процессе которой при заданной совокупности потенциально

неисправных компонентов определяется, какой из них может объяснить наблюдаемое поведение.

Выделение гипотез, когда в результате тестирования остается несколько версий

(как на рис. 7.14) и необходимо определить, какая дополнительная информация

может помочь выявить неисправность.

И, наконец, мы должны отметить, что в примере на рис. 7.14 предполагается, что неисправен единственный модуль. Мир не всегда так прост, хотя предположение о единственной неисправности является полезной и часто корректной эвристикой.

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

Глава 7. Сильные методы решения задач 295

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

Однако с подходом на основе модели связаны более глубокие проблемы. Как и рассуждения на основе правил, модель системы - это всего лишь модель. Она является необходимой абстракцией системы и на некотором уровне детализации становится некорректной. Например, рассмотрим входные клеммы на рис. 7.14. Мы считали эти значения заданными и корректными, не проверяя состояние самих шин и контактов с мультиплексорами. А если повреждены провода или неисправны контакты? Если пользователь не учел эту информацию, модель не будет соответствовать действительному устройству.

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

Но, несмотря на эти недостатки, рассуждения на основе моделей являются важным дополнением к инструментальным средствам инженера по знаниям. Исследователи продолжают углублять наше понимание диагностики за счет исследования принципов эффективного решения этой задачи человеком-экспертом, а также улучшения машинной реализации алгоритмов [Stern и Luger, 1997].

7.3.2. Рассуждения на основе моделей: пример NASA

В настоящее время NASA разрабатывает флотилию интеллектуальных космических зондов, предназначенных для автономного исследования солнечной системы [Williams и Nayak, 1996], [Bernard и др., 1998]. Этот проект начался с разработки программного обеспечения для первого зонда в 1997 и запуска аппарата Deep Space 1 в 1998 году. Для успешной работы в суровых условиях космического путешествия космический корабль в ответ на неудачи должен уметь радикально перестраивать свой режим управления и учитывать эти неудачи при планировании оставшейся части полета. Для обеспечения приемлемой стоимости и скорости реконфигурации необходимо быстро подключать стандартные модули, которые составляют программное обеспечение полета. Кроме того, NASA считает, что множество неудачных сценариев и возможных ответов будет слишком большим, чтобы использовать простой перечень всех возможных случаев. Космический корабль должен реактивно размышлять при реконфигурации своей системы управления.

В системе Livingstone [Williams и Nayak, 1996] реализованы ключевые функции реактивных самоорганизующихся автономных систем, основанных на моделях. Языком представления рассуждений на основе моделей в Livingstone является пропозициональное исчисление. Обратите внимание на отход от исчисления предикатов первого порядка (глава 2) - традиционного языка представления в задачах диагностики на основе моделей. Основываясь на своих предыдущих исследованиях по разработке быстрой пропозициональной логики для конфликтных алгоритмов диагностики, Вильяме (Williams) и Наяк

296 Часть III. Представление и разум в ракурсе искусственного интеллекта

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

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

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

Глава 7. Сильные методы решения задач 297