59. Формальні моделі представлення знань. Формальные модели представления знаний.

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

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

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

Формальная теория должна, таким образом, удовлетворять следующему определению:

Всякая формальная теория F = (A, V, W, R), определяющая некоторую аксиоматическую систему, характеризуется:

Наличием алфавита (словаря), A,

Множеством синтаксических правил, V,

Множеством аксиом, лежащих в основе теории, W,

Множеством правил вывода, R.

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

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

60. Комплексна схема нечіткого планування задач.

Комплексная схема нечеткого планирования

Недостатком большинства известных в настоящее время систем планирования является их жесткая привязка к схеме планирования. Любая из них всегда ищет решение либо SS-проблемы, либо PR-проблемы. Связано это с фиксацией формы представления информации для планирования. Для классических моделей SS- и PR-проблем эти формы различны. Ясно, однако, что человек в своей деятельности успешно комбинирует шаги планирования из решения SS- и PR-проблем. Вторым недостатком является детерминированность систем планирования. В реальных ИС детерминированность планирования, как правило, не имеет места. Обобщение нечетких SS- и PR-проблем заключается в допущении нечетких состояний и нечетких операторов перехода из состояния в состояние. Разбиение задачи на подзадачи имеет весовые коэффициенты на дугах со значениями из [0, 1], которые интерпретируются как достоверности решения соответствующих подпроблем. Достоверность решения PR-проблемы определяется как минимум достоверностей решения ее подпроблем.

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

Схемой SS-проблемы называется пара M=(S,G), где S-множество состояний, G-множество отображений g: S->S, называемых операторами. Путем из состояния s₀эs в состояние s_rэs называется конечная последовательность p=(( s₀, , g₀), (s₁, g₁),...,(s_k-1, g_k-1) s_k ) , такая, что g_io s_i= s_i+1 для i=0,..., k-1. SS-проблема-это четверка Р=(S, G, i ,f), где (S, G)-схема SS-проблемы, i, fэs-соответственно начальное и заключительное состояние. Путь х, ведущий из i в f, есть решение Р, а множество всех подобных путей составляет множество решений.

Схемой PR-проблемы называется пара .N=( , Г), где  -множество проблем, Г-множество отображений  :  -> ⁺, называемых операторами. Если Рэ ,  э ⁺, то  _р( )-отображение, представляющее проблему Р в виде цепочки подпроблем  =P1...Pn. Для схемы N= ( , Г) накрывающий путь q из проблемы  ₀ в конечное множество проблем  _k= { ₁,...,  _n}э _ ^| является конечной последовательностью, где q= ((x₀ , y₀), (x₁, y₁),..., (x_k-1, y_k-1), x_k), x_i э  ⁺ для i=0,...,k, yэг⁺ для i=0,..., k-1, так что x₀= ₀, x_kэ ⁺_k. PR-проблема представляет собой четверку Z=( , Г, Ро, Ф), где ( , Г)-схема PR-проблемы, Р_оэ -начальная проблема, Ф  -множество конечных проблем. Решение Z представляет собой накрывающий путь ( , Г) из Р_о в Ф^/_x Ф, множество решений x_z, есть множество всех решений Z.

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

Импликата проблемы Р есть пара ( ,  ), где  =p_ip₂... P_k - цепочка проблем,  -отображение из Х_р1  Х_р2 ...  Х_рk в Х_р( Х_рi обозначает

Множество решений Р_i<). Импликативная схема есть тройка  =(Р,  ,  ), такая, что Р - проблема, ( ,  ) - импликата Р. Множество Т импликативных схем называется импликативной сетью. Множество проблем импликативной сети

 _t={x|(  )(( =(Р,  ,  )) ((х=Р)\/(х- символ  ))}.

Объединим синтаксис и семантику подхода, основанного на разбиении проблемы на подпроблемы. PR-проблема Z=( , Г, Ро, Ф) представляет импликативную сеть Т тогда и только тогда, когда  = _t и для каждого  =(Р,  ,  )эt существует в точности одно  эг, такое, что Р = , и для каждого  эг, и для каждого Р из области определения  существует в точности одно  =(Р,  , ) T, такое,что  =P Проблема Р решена тогда и только тогда, когда Х_p- непустое множество.

Если PR-проблема представляет импликативную сеть, то проблема Р₀ разрешима. Для существования решения достаточно, чтобы импликативные схемы в импликативной сети Т существовали только для всех пар (xi, у,),i=0,..., k-1, входящих в накрывающий путь схемы PR-проблемы. В этом случае синтаксис и семантика PR-проблемы не совпадают. В данном случае PR-проблема частично представляет импликативную сеть Т.

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

Рассмотрим понятие, объединяющее подходы разбиения проблемы на под-проблемы и поиска в пространстве состояний. 1-проблемой (объединенной проблемой) называется четверка R=(B, Г, Р₀, Т), где В-множество SS-проблем;

(В, Г)-схема PR-проблем; р₀эb -основная проблема;T-импликативная сеть, такая, что  _T B  . Кроме того, R есть решение SS-проблемы Р₀. Учитывая связь между существованием импликативной сети и разрешимостью проблемы, легко показать, что если для заданной I-проблемы найден накрывающий путь х из Р₀ на множество Ф' В, проблемы Ф' разрешимы как SS-проблемы, если х частично представляет импликативную сеть Т, то и проблема R разрешима как SS-проблема.

Рассмотрим головоломку "Ханойская башня" . Имеются три стержня 1, 2 и 3 и три диска различных размеров А, В, С с отверстием в центре, которые могут одеваться на стержни. В исходной позиции диски находятся на стержне 1; самый большой диск С-внизу, самый маленький диск А- наверху. Требуется перенести все диски на стержень 3, перемещая за один раз только один диск. Брать можно только самый верхний диск на стержне, причем его нельзя класть на диск, меньший по размерам. Используем для записи состояний и операторов классическую формализацию. Выражение ijk обозначает конфигурацию, при которой диск С находится на стержне i, диск В - на стержне j и диск А-на стержне k. Выражение xij обозначает действие, при котором диск х перемещается со стержня i на стержень j. С помощью этого формализма можно просто записать все состояния и переходы головоломки в виде треугольного графа, где вершины соответствуют расположению дисков на стержнях, а дуги-возможным перекладываниям дисков (рис.1). На этой головоломке легко проиллюстрировать все основные понятия обобщенной стратегии проблем.

Представим головоломку в виде модели I-проблемы. Рассмотрим I-проблему R=(B, Г, P₀T), где B={Р₀, P₁,...,P₉}; Г={ }; T=={ ₁, ₂, ₃}. SS-проблемы Р₀,P_1...,P₉ определяются следующим образом. На рис. 1 показана схема SS-проблемы M==(S, G), где

P₀=(S, G, 111, 333), P₁=(S, G, 111, 122), P₂=(S, G, 122, 322),

Рз=(S, G, 322, 333), P₄=(S, G, 111, 113), P₅,=(S, G, 113, 123),

P₆==(S, G, 123, 122), P₇=(S, G, 322, 321), P₈=(S, G, 321, 331),

P₉=(S G, 331,333).

Схема PR-проблемы N= (В, Г) приведена на рис. 2; импликативная сеть Т- на рис.3, причем  ₁=(P₀, P₁Р₂Р₃,  ),  ₂= (P₁, P₄P₅P₆,  ),  з== (Р₃, P₇P₈P₉, ), где  (x₁,x₂,x₃)=x₁x₂x₃.

Проблемы Р₂ и P₄-P₉ решаются перекладыванием одного диска и являются элементарными. Проблемы P₁ и Р₃ решаются с помощью манипуляций только с дисками В и А и являются более простыми, чем Р₀. Проблемы P₁ и Р₃ решаются, а проблема Р₀ сводится к P₁, P₂ и Р₃ аналогичной манипуляцией с дисками, синтаксис которой выражен оператором  , а семантика - отображением  .

Представление этой головоломки в виде PR-проблемы (рис.2) является более компактным и наглядным, чем представление в виде SS-проблемы (рис.1), а представление в виде I-проблемы (рис..3) сочетает достоинство обоих и показывает взаимосвязь подпроблем и тех действий, которые нужно выполнить, чтобы решить головоломку.

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

Неоднозначны.

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

Нечеткой SS-проблемой назовем SS-проблему, у которой i , f-нечеткие множества, операторы g эg-нечеткие матрицы,  -решением нечеткой SS-проблемы называется путь g=g₁...g_n,g_iэg,i=1,...,n, такой, что iog₁o... ... Og_nof  , где О - максимальное произведение нечетких матриц.

Нечеткой PR-проблемой называется PR-проблема, у которой элементам  эг приписывается степень принадлежности   ( )э[0,1],  -решением нечеткой PR-проблемы называется решение PR-проблемы, для которой min _{ij } , _ij эy_i.

Накрывающий путь в этом случае называется накрывающим  -путем. Степень принадлежности   (  ) интерпретируется как степень возможности разбиения проблемы на подпроблемы.

Нечеткой импликативной схемой называется импликативная схема, все отображения  которой имеют степень принадлежности   ₍( )э[0,1]. Степень принадлежности интерпретируется как возможность получения решения проблемы из решений соответствующих подпроблем. Нечеткой импликативной сетью называется импликативная сеть с нечеткими импликативными схемами.Нечеткая PR-проблема представляет нечеткую импликативную сеть, если кроме обычных условий для импликативной сети выполняется неравенство   ( )   ( )   ,

Т. Е. Возможность разбиения на подпроблемы не меньше возможности получения решения для каждой пары соответствующих  и  .

Аналогично определяется нечеткая I-проблема. Но построить  -решение нечеткой PR-проблемы по  -решениям ее нечетких подпроблем можно лишь в частных случаях и при наложении дополнительных условий. Пусть задана нечеткая PR-проблема, где  -нечеткие SS-проблемы, и существует простейшее  -решение Z,

Т.е.такое  э  ⁺,что   _{p  } ,и если  =P₁..P_n,то все проблемы P_{i } -разрешимы,

Где P_i=(S_i,G_i,J_i,F_i ). -решение проблемы P₀ существует при   ( )   ( )  для импликативной сети.Запишем более конструктивное условие для этого.Пусть для всех i оператор g_i есть  -путь решения проблемы P_iи F_i=J_i+1.Тогда,если выполняется

Max  [F_n (F_n-1 (...F_1 (J o g₁)o g₂)...)O g_n)] 

И g=g₁...g_n,то g-  -решение SS-проблемы P₀.