Типовые алгоритмы построения экспертных систем

28. Планировщик STRIPS – основные алгоритмы и эвристики

STRIPS (St anford R esearch I nstitute P roblem S olver) — это автоматический планировщик, разработанный Ричардом Файксом и Нильсом Нилсоном в 1971. В последующем слово STRIPS стало также использоваться для обозначения формального языка, описывающего входные данные этого планировщика. Этот язык является основой большинства современных языков описания задач автоматического планирования. Данная статья описывает только язык (так называемый STRIPS-формализм), а не сам планировщик.

Первой системой, которая создавалась именно для решения задачи планирования, была система STRIPS (STanford Research Institute Problem Solver). Разработана система была в 1971 году двумя исследователями - Ричардом Файксом и Нильсом Нильсоном. Описание системы опубликовано в трудах 2-ой международной конференции по искусственному интеллекту (IJCAI'71) [Fikes, Nilsson, 1971].

Файкс и Нильсон сформулировали задачу планирования такой, какова она и по сей день. Задача планировщика найти такую последовательность действий, которая преобразует начальное состояние в такое состояние, в котором достигается заранее заданное целевое условие (В оригинальной статье используются понятия " модель мира" для обозначения состояния и " оператор" для обозначения действия. Мы будем придерживаться современной терминологии.). Состояние представляется множеством формул логики первого порядка (в оригинальной статье, well-formed formulas (wffs)). Цель также описывается формулой. Действия описываются в виде специальных конструкций, которые мы рассмотрим ниже.

STRIPS пользуется методологией доказательства теорем только в рамках одного заданного состояния для получения ответа на вопросы " какие действия применимы" и " достигнуты ли целевые условия" (в отличие от QA3, где методы доказательства теорем использовались и для перехода из состояния в состояние). В STRIPS поиск в пространстве состояний осуществляется по аналогии с системой GPS, а именно, используется стратегия " анализ средств и целей".

Формально, постановка задачи в STRIPS включает три составляющие: начальное состояние, множество действий и целевую формулу. Как уже было сказано, состояния описываются множеством формул. Например, то, что объект obj₁ находится в комнате room₂, можно выразить следующей формулой: At(obj₁, room₂). Кроме таких " описательных" аксиом, можно включать аксиомы-правила, наподобие тех, что использовал Грин. Например, можно написать, что если объект находится в комнате room₂, то он не находится ни в какой другой комнате. Формально это можно представить так: (" x, y, z) [ At(x, y) & (y = z) —> At(x, z) ]. Если формула является литералом, то это должен быть позитивный литерал (без знака отрицания). Все атомарные формулы во множестве формул, описывающих состояние, должны быть означены (ground), т.е. не иметь свободных переменных. Утверждения, не входящие в число формул, описывающих состояние, и не являющиеся их логическим следствием, считаются ложными. Это последнее допущение в литературе называют допущение о замкнутости мира (closed-world assumption).

Действия группируются в классы действий, называемые схемами действий (в оригинальной статье, соответственно, схемы операторов). Такой подход позволил существенно сократить описание задачи. Рассмотрим, например, действие goto, перемещающее робота из одной комнаты в другую (напомним, что STRIPS создавался для управления роботом). Существует множество таких действий для каждой пары сообщающихся комнат. Было бы удобно сгруппировать все такие действия в рамках одной параметризованной схемы goto(x, y), где параметр x - обозначает начальное месторасположение робота, а y - конечное. Конкретные действия получаются из описания схемы путем подстановки конкретных сущностей (констант) вместо параметров. Применять можно только конкретизированные схемы действий, т.е. сами действия.

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

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

Условия применимости действия, называемые также предусловием (precondition), задаются при помощи одной формулы. Для того, чтоб узнать применимо ли действие в некотором заданном состоянии, мы должны проверить истинность предусловия, т.е. доказать, что предусловие является логическим следствием множества аксиом данного состояния. Если предусловие истинно, то действие применимо.

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

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

Приведем пример того, как схема действия может быть описана в STRIPS. Рассмотрим схему действия Fly - перелет самолета из одного аэропорта в другой.

fly (p, from, to)
precondition = At(p, from) & Plane(p) & Airport(from) & Airport(to)
delete list = { At(p, from) }
add list = { At(p, to) }.

Здесь fly - имя схемы действия, за которым следует список параметров схемы (p, from, to). Следующая строка описывает предусловие. Для того, чтобы действие перелета совершилось, нужно чтобы самолет находился в аэропорту отправления. В предусловии мы указываем, что p - это самолет (Plane(p)), а from и to - аэропорты (Airport(from) & Airport(to)), и что самолет находится в пункте отправления (At(p, from)). В следующей строке описан список удаления. Он состоит всего из одного элемента - At(p, from). Удаляя эту формулу из состояния, мы получим эффект того, что самолет больше не находится в пункте отправления. И наконец, последняя строка описывает список добавления, который также состоит из одной формулы - At(p, to) - постулирующей то, что самолет окажется в пункте назначения после того, как действие будет выполнено.

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

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

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

Авторы также отмечают, что в списке удалений иногда удобно записывать не сами формулы, а некоторые их прототипы. Например, одним из эффектов действия goto для робота должно быть удаление информации о том, куда робот был направлен лицом, даже если эта информация не указывается в качестве параметра схемы действия. В этом случае в список удаления можно поместить запись вида facing($), смысл которого следующий: " всякая формула соответствующая этому прототипу (независимо от значения $) должна быть удалена".

Коль скоро мы имеем дело со сложными формулами, мы должны учитывать следующий момент, связанный с удалением формул. Если мы удаляем некоторую формулу, мы должны будем также удалить и все формулы, которые были выведены на основании данной.

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

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

В последствии STRIPS подвергался обширной критике и за подход к описанию мира и действий, и за алгоритм поиска.

29. ЭС MYSIN – основные алгоритмы и эвристики

MYCIN была ранней экспертной системой, разработанной за 5 или 6 лет в начале 1970х годов в Стэнфордском университете. Она была написана на Лиспе как докторская диссертация Edward Shortliffe под руководством Bruce Buchanan, Stanley N. Cohen и других. В этой же лаборатории была ранее создана экспертная система Dendral, но на этот раз внимание было акцентировано на использовании решающих правил с элементами неопределенности. MYCIN был спроектирован для диагностирования бактерий, вызывающих тяжелые инфекции, такие как бактериемия и менингит, а также для рекомендации необходимого количества антибиотиков в зависимости от массы тела пациента. Название системы происходит от суффикса «-мицин», часто встречающегося в названиях антибиотиков. Также Mycin использовалась для диагностики заболеваний свертываемости крови.

MYCIN оперировала с помощью довольно простой машины вывода, и базы знаний из ~600 правил. После запуска, программа задавала пользователю (врачу) длинный ряд простых «да/нет» или текстовых вопросов. В результате, система предоставляла список подозреваемых бактерий, отсортированный по вероятности, указывала доверительный интервал для вероятностей диагнозов и их обоснование (то есть MYCIN предоставляла список вопросов и правил, которые привели её к именно такому ранжированию диагнозов), а также рекомендовала курс лечения.

Несмотря на успех MYCIN, она вызвала дебаты по поводу правомерности её машины вывода. Исследования, проведенные разработчиками, показали, что эффективность системы минимально зависит от конкретных числовых особенностей реализаций правил вывода. Они допустили, что эффективность в значительно большей степени зависит от способа представления знаний и способа вывода. Этот вопрос был рассмотрен в (Shortliffe EH and Buchanan BG. A model of inexact reasoning in medicine. Mathematical Biosciences 23: 351-379, 1975) и потом в их подробной книге о MYCIN и связанных с ней экспериментах (Rule Based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project, EH Shortliffe, eds. Reading, MA: Addison-Wesley, 1984).

Результаты

Исследования, проведенные в Stanford Medical School, обнаружили, что MYCIN предлагает приемлемую терапию примерно в 69 % случаев, что лучше, чем у экспертов по инфекционным болезням, которых оценивали по тем же критериям. Это исследование часто цитируют, чтобы продемонстрировать возможную степень несогласия между решениями врачей, даже если они эксперты, когда нет «золотого стандарта» для правильного лечения (Yu VL, et al. Antimicrobial selection by a computer — a blinded evaluation by infectious disease experts. Journal of the American Medical Association 242: 1279-1282, 1979).

Практическое использование

Фактически, MYCIN никогда не использовалась на практике. И не в силу низкой её эффективности. Как уже упоминалось, в тестах она превосходила профессоров Stanford medical school. Некоторые исследователи поднимали этические и правовые вопросы, связанные с использованием компьютеров в медицине — если программа дает неправильный прогноз или предлагает неправильное лечение, кто должен отвечать за это? Тем не менее, наибольшей проблемой и настоящей причиной, почему MYCIN не используется в повседневной практике, было состояние технологий системной интеграции, особенно во времена её создания. MYCIN была автономной системой, требующей от пользователя набора всей необходимой информации. Программа запускалась на сервере с разделением времени, доступному по раннему Интернету (ARPANet), когда еще не было персональных компьютеров. В наше время, подобная система была бы интегрирована с системой медицинских записей, извлекала бы ответы на свои вопросы из базы данных о пациентах, и была бы значительно менее зависима от ввода информации врачом. В 1970-х, сеанс работы с MYCIN мог легко занять 30 минут и более — что составляет недопустимые потери времени для занятого врача клиники.

Наибольшим достижением MYCIN была демонстрация мощи её подхода к представлению знаний и построению выводов. Позже было разработано множество экспертных систем, основанные на правилах. В 1980-х появились «оболочки» для экспертных систем (в том числе основанных на MYCIN, известная как E-MYCIN (разрабатываемая KEE)), что способствовало разработке экспертных систем в разнообразных прикладных областях.

Главной трудностью, с которой столкнулись во время разработки MYCIN и последующих экспертных систем, было «извлечение» знаний из опыта людей-экспертов для формирования базы правил. Сейчас данными вопросами занимается инженерия знаний.