Материал: Элементы искусственного интеллекта в робототехнике. Ефремов Д.А

2.1. Структура экспертных систем

ЭС в общем случае представляются как продукционные системы /1/. В продукционной системе данные представляются в символьном виде, набор символов составляет алфавит систе­мы. С помощью символов составляются описания. В зависи­мо­сти от принятого способа представления данных символь­ное описание состоит или из последовательных символов, или сим­волов объединенных связками (связка – некоторое ло­ги­ческое понятие, объединяющее символы). Обработка сим­воль­ных данных состоит в преобразовании символьного опи­сания. Это действие называется продукцией. Продукция пред­ставляется как X_iWWY_i. Это означает, что если в некотором описании Y присутствует последовательность символов X_i, то продукция состоит в исключении X_i из Y и в присоединении к оставшейся части Y_i . Например, если Y:abc, то продукция abWWd представляет Y:cd.(приводит к модификации Y:cd).

Продукции поддерживаются правилами преобразования описания, которые называются продукционными. Таким обра­зом, продукционная система включает в себя набор описаний (данных), набор продукционных правил и интерпретатор. Интерпретатор определяет последовательность применения правил к данным. С учетом изложенного продукционная система имеет вид:

PS=(B, R, I),

где B – база данных;

R – продукционные правила или база знаний;

I – интерпретатор.

Интерпретатор представляется в виде:

I=(V, S, K, W)

10

Последовательность действий интерпре­татора:

На шаге V осуществляется выборка данных и знаний. Эта выборка может выполняться тривиально, т.е. последовательным выбором всех данных и всех правил, или по определенным формальным признакам.

На шаге S осуществляется сопоставление выбранных данных и правил, т.е. выявляется, к каким данным какие правила можно применить. Создаются активные пары "данные-пра­ви­ла", которые используются на следующих шагах.

На шаге K выполняется разрешение конфликтов, при котором определяется последовательность работы с активны­ми парами. Эта последовательность задается механизмом вывода (стратегией поиска).

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

ОК

ИР

И

РП

Рис.2. Структура статической экспертной системы

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

11

Ядро системы – интеллектуальный решатель ИР, представляющий собой многопроцессорную систему, обес­печивающую работу с базой данных, решение задач поиска и информационное взаимодействие с внешним миром.

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

1. Компонент приобретения знаний КПЗ. Этот компо­нент обеспечивает наполнение системы данными и знаниями. Его основа - символьные языки и програм­мные средства их поддержки;

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

3. Объяснительный компонент ОК. Этот компонент - средство предст­ав­ления пользователю сведений о том, почему экс­перт­ная система принимает то или иное решение.

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

Системы, которые могут самостоятельно пополнять базы данных и знаний, называются динамическими. Ядро динами­чес­кой системы – статическая система, дополнительные элементы: сред­ства получения информации из предметной области, средства преобразования этой информации, модель предмет­ной области. Динамическая система в рабочем режиме посто­ян­но получает информацию из предметной области. Ее

12

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

Статические и динамические системы работают в режиме обучения (накопления знаний) и консультаций. Первый ре­жим реализуется при разработке системы; второй – пользователь­ский, когда с системой работает конечный пользователь. В первом режиме максимально задействован КПЗ, во втором – ОК и ДК.

2.2. Технология разработки экспертных систем

Информация для экспертной системы поступает из пред­метной области ПО. Разработка экспертной системы для кон­кретной ПО состоит из нескольких унифицированных этапов (Рис.3). Первый из них - идентификация И. На этом этапе рассматри­вается предметная область и определяется целесообразность и возможность создания экспертной системы. Принцип целесо­образности состоит в выявлении степени неопределенности предметной области. Если предметная область может быть четко формализована в виде алгоритмической или матема­ти­ческой модели, то экспертную систему создавать нецелесообразно.

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

После этого осуществляется формализация Ф. При Ф

13

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

ПО ЭС

И

ПФ ПК

К

Рис.3. Последовательность разработки экспертной системы

По завершении этапа В система готова для использования; до передачи ее конечному пользо­вателю выполняется тестирование Т и опытная эксплуатация ОЭ. При тестировании разработчиками проекта предлагаются системе различные наборы данных с известными решениями. Контролируются правильность принятия решений и последо­вательность их поиска. При опытной эксплуатации системе предлагаются реальные задачи ПО, и оценивается объектив­ность решения с контролем последовательности его принятия. По результатам тестирования и опытной эксплуатации прини­ма­ется решение о степени готовности системы. При отрица­тельном решении может выполняться переформулирование ПФ поставленной задачи на этапах И и К и (или) п ереконстру­ирование на этапе формали-

14

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

Обычно разработка систем выполняется как разработка прототипов, т.е. не ставится задача разработки сразу системы с полным объемом знаний. Для начала на этапах И и К выбира­ются наиболее существенные признаки ПО, и система разраба­тывается и тестируется только в объеме этих признаков. В даль­нейшем в систему добавляется новый объем признаков, создается второй прототип и так далее до исчерпания всех известных признаков.

2.3. Механизм вывода в экспертных системах

При принятии решения сначала выполняется выборка Выб (Рис. 4). При выборке из рабочей памяти РП извлекаются данные, а из базы знаний БЗ правила.

В

РК

ОМ

Рис. 4. Последовательность вывода в экспертных системах

Выбранный означенный модуль ОМ выполняется на этапе выполнения Все извлекаемые данные и знания анализируются на возможность применения при решении. В ре­зуль­тате чего создается набор активных модулей АМ. Далее модули из набора сопоставляются (Соп). При сопоставлении создаются пары или тройки из данных и правил, т.е. выбира­ют­ся данные и правила, которые к этим данным можно приме­нить. Резуль

15

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

2.4. Методы поиска решений в экспертных системах

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

2.5. Поиск в одном пространстве состояний

Поиск в одном пространстве состояния рассматривается в графовой интерпретации. Граф представляет из себя сово­куп­ность признаков, объединенных связями: G=G(X,Y),

где G – представление графа;

X – множество признаков;

Y – множество пар X_i,X_j;

X_i,X_j – признаки из множества X, объединенных связями f,

f – оператор переводящий состояние X_i в состояние X_j .

Каждому Х соответствует вершина графа, а каждому f – линия соединяющая вершины (дуга). Таким образом,

16

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

X₀ – вершина начального состояния;

X_ц – целевые вершины (вершины, соответствующие решениям);

X_т – терминальные вершины (вершины, означающие отсут­ствие решения, или тупиковые). К терминальным вершинам не применяется ни один оператор.

Граф обычно представляется в виде слоев (Рис. 5). В каждом графе нулевой слой – слой начальных состояний (исходные данные из предметной области). Поиск решения состоит в применении операторов к признакам нулевого слоя. Эта опе­рация называется раскрытием вершин. Состояние, получившее­ся в результате применения оператора, соответствует дочерней вершине, множество которых образует слой номер 1. Дальней­шее раскрытие вершин слоя 1 порождает слой 2 и т.д. пока не будут достигнуты вершины Х_у (целевые) или Х_т (терминаль­ные).

Процесс поиска может заканчиваться различными исхо­дами:

• раскрытием всех целевых и терминальных вершин;

• раскрытием определенного количества целевых вершин;

• достижением определенной глубины поиска.

Глубина поиска определяется номером слоя, до которого проводится раскрытие вершин. Если в этом граничном слое

имеются целевые вершины, то они принимаются как решения,

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

системы. Затем раскрываются порожденные вершины до завершения поиска по одному из критериев, указанных выше.

17

X₀₁ X₀₂ X₀₃