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

2.10. Поиск в альтернативных пространствах

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

23

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

Рис. 10. Поиск решения в альтернативных пространствах

А1, А2, А3 – исходные признаки;

АП1, АП2 – альтернативные пространства.

В представленных альтернативных пространствах общими являются исходные данные А1, А2, А3. Поиск в пространствах АП1 - АП2 выполняется до тех пор, пока не будет определено решение в одном их них. Если поиск в первом пространстве не дал результата, то вы­пол­няется возврат на исходные данные и начинается поиск во втором пространстве. Каждый раз при отрицательном резуль­тате поиска выполняется переход к исходным данным.

2.11. Поиск с использованием нескольких моделей

Пространство признаков представляется некоторым словесным описанием, которое в большинстве случаев учи­ты­вает

24

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

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

3. Представление знаний в системах

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

25

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

Основные логические связки:

 - конъюнкция (и); Эта связка применяется для объединения признаков.

- дизъюнкция (или). Применяется для выбора одного или нескольких признаков из группы.

 - отрицание (не).

 - импликация. Эта связка устанавливает причинно-следственную связь между признаками и означает (если..., то).

 - эквивалентность или равенство. Означает полное совпадение признаков.

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

3.1. Продукционные системы

Продукционные системы организуются по принципу “условие-дей­ствие”. Условия задаются данными, хранящимися в базе данных сис­темы. Действия определяются правилами, которые хранят­ся в базе знаний. Интерпретатор системы определяет порядок ис­поль­зования правил, который обычно задается в виде прио­ри­тетов, т.е. правила с более высоким приори-

тетом исполня­ют­ся ранее остальных. В продукционных системах ис­пользуются логические связки конъюнкции и дизъюнкции и используется единственное правило: “следует ”. Суть

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

Пример. АВСD

Это выражение означает, что при истинности признаков А, В, С следует истинность D. В соответствии с этим правилом

26

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

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

Пример. Предположим, что база данных системы содержит некоторые сведения A, F, которые считаются истинными. База знаний содержит набор правил:

1. АВСD

2. AFB

3. FC

4. DG

5. GH

Предположим, что нам надо выявить истинность Н. На первом шаге поиска решения выявляется, присутствует ли Н в базе данных. Поскольку в базе данных его нет, определяются правила, в которых Н находится в правой части (правило 5). Н истинно, если истинно G. Проверяется наличие G в базе дан­ных. Оно отсутствует. Поэтому выбирается правило, в кото­ром этот признак в правой части (правило 4). Связка 4 истин­на, если истинна D, которая также отсутствует в базе. Для оп­ределе-

деления истинности D необходима проверка на истин­ность правила 1. В условиях этого правила А истинно по опре­де­ле-

нию, В истинно как следствие 2, а С истинно как след­ствие 3. Следовательно, D истинна и далее по 4 и 5 истинна Н. Все по­лу­ченные в результате применения правил результаты могут заноситься в базу данных.

3.2. Системы поиска на основе классической логики

Объект предметной области представленный в виде символов образует простейшие формулы, называемые атомарны-

27

ми /2/. Отрицание атомарных формул и сами атомарные фор­му­лы называются литерами. Из литеров с помощью логичес­ких связок строятся сложные описания, которые называются правильно построенными формулами (ППФ).

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

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

Функционально-истинностные состояния для основных логических связок приведены в таблице 1.

Таблица 1

Более сложные формулы раскрываются по аналогичной

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

Пример. Z(XY).

Первой выполняется операция конъюнкции Х и Y, затем дизъюнкция полученного результата с Z.

Помимо составления функци­ональ­но-истинностных таблиц используется приведение ППФ к некоторым каноническим формам. Основными формами являются конъюн­ктив­ная и дизъюнктивная нормальные формы (КНФ и ДНФ). КНФ

28

представляет собой конъюнкцию дизъюн­кций признаков, т.е.

КНФ: D1D2...DN

D_i: (X1X2...XM)

При проведении ППФ к нормальным формам использу­ют­ся основные законы преобразования логических выражений:

1. XY(XY)(YX),

где  - логическая эквивален­тность. Это преобразование позволяет исключить из выражения связки эквивалентности.

2. XYXY

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

3. XYZZXY (закон коммутативности)

В связках дизъюнкции можно менять местами слагаемые.

4. X (YZ)(XY)(XZ)

X(YZ)(XY)(XZ)

Дистрибутивные законы позволяют приводить выражения к конъюнкции дизъюнктов.

5.  XX

Д войное отрицание X, есть X (X=X)

6.  (XY)XY

(XY)XY

Законы двойственности (Моргана) устанавливают эквивалентность дизъюнктов и конъюнктов через отрицание.

П ри преобразовании формул вводятся понятия общезначимой и невыполнимой формул. Общезначимая формула истинна при любых значениях входящих литеров, а невыполнимая – ложна при тех же условиях. Общезначимая формула о бозначается И ( ), а невыполнимая - Л( ).

П ример. XX - общезначимая формула.

XX - невыполнимая формула.

При объединении логическими связками выражений с общезначимыми и невыполнимыми формулами справедливы следующие выражения:

X  X; X  ; X  ; X X

29

Последовательность приведения ППФ к нормальным формам:

1. Исключение связок эквивалентности.

2. Исключение связок импликации.

3. Минимизация зоны действия знаков отрицания.

4. Многократное применение дистрибутивных законов (раскрытие скобок).

5. Применение законов двойственности.

6. Замена конъюнкций на дизъюнкции и наоборот с целью формирования дизъюнктов (конъюнктов), связанных конъюнктами (дизъюнктами).

3.3. Использование логики предикатов первого порядка при представлении знаний

При представлении знаний в логике предикатов используются следующие понятия:

1. Индивидные символы или константы a, b, c,... Константы соответствуют отдельным признакам объектов предметной области.

2. Переменные x, y, z,... означают признаки, которые могут принимать разные значения.

3. Функциональные символы f, φ,... используются для объединения признаков, которыми могут быть константы или переменные.

Предикатные символы P, Q, T,... используются для обозначения логических функций и объединяют кон­станты, переменные и функциональные символы логи­чес­кими связками.

4. Логические функции, обозна­ча­емые предикатными символами, принимают значе­ние 0, 1 (И, Л). Таким образом, расширение класси­че­с­кой логики до логики предикатов заключается в том, что символы, которые в классической логике рассмат­ри­ваются как единое неделимое понятие, в логике пре­ди­катов заменяются логическими функциями мно­гих аргументов. Если в классической логике ин­тер­пре­тация формулы состоит в получении фикси­ро­ван­ных значений И, Л, то в логике предикатов интерпре­та­ция формулы есть некоторые множества, состоящие из предикатных символов, которые объединяют приз­наки предметной области в виде констант и пере­мен­ных могут иметь множественные значения.

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

31

Эти связки называются кванторами. В основном используются два вида кванторов:

1. xP(x) – квантор всеобщности, означает, что для всех X функция P истинна.

2. xP(x) – квантор существования, означает, что существуют такие X, для которых P истинна.

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

1. Исключение связок эквивалентности и импликации;

2. Подстановка переменных для того, чтобы область действия кванторов распространялась только на одну переменную;

3. Исключение кванторов существования;

4. Применение преобразования логических связок до получения КНФ;

5. Исключение из КНФ кванторов всеобщности.

3.4. Использование фреймов при представлении данных

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

Фрейм – информационный модуль, содержащий набор данных, адекватных ситуациям.

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

Слот – единица информации фрейма, которая содержит данные, относящиеся к отдельному признаку.

Имя слота – указатель на эту группу данных.

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

32

Последовательность работы фреймовых структур следующая:

1. Создаются фреймы – шаблоны, которые содержат описание ситуации;

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

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