Системы искусственного интеллекта

Пусть р - элементарное высказывание, a S - приведенная ДНФ. которая м быть представлена в  виде: 

 
 

 

1.7.3. Принцип резолюций

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

Множество дизъюнктов S не выполнимо тогда и только тогда, когда логическое следствие  из него есть пустой ДИЗЪЮНКТ, т. с. дизъюнкт, всегда принимающий значение F. Таким образом, невыполнимость множества дизъюнктов S можно проверить, порождая логические следствия из нет до тех пор, пока не получится пустой дизъюнкт.

, Для порождения логических следствий используется следующая схема рассуждений. Пусть А, В. X формулы. Предположим, что - истинны. Если X принимает значение Т, то A также принимает значение Т. Если X принимает значениеF. то А принимает значение F. Следовательно, А/В принимает значение Т. То есть, или - дизъюнкты. Это правило реюлюцин.

Следствие, Нормальныеформы S и Su|r} логически эквивалентны.

Алгоритм донага тел ьсща невыполнимоегн логической формулы

1. Если в формуле  нет невыполнимых дизъюнктов, то  выбираются I. S| и S>. такие, что  \с S, и ] le S2.

2. Строится резольвента  r.

3. Заменяется 

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

Пример. Доказать невыполнимость следующего множества дизъюнктов:

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.7.4. Хорновские дизъюнкты

Часто в исчислении высказываний возникает следующая задача: нужно пи рить какую-то формулу (цель), логически выведенную из множества фактов и 1 вил. Резолюция является метолом доказательства от противного   исходя из фая] правил и отрицания цели приходим к противоречию (пустому дизъюнкту). При удобно использован, хорновские дизъюнкты. 

 

 

4. Выполнять  эту процедуру до получения  пустого дизъюнкта.

 

1.8. Применение исчисления высказываний

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

1.8.1. Пример базы знаний на основе логических высказываний Пусть необходимо формализовать знания о различных животных. Ваза знаний На основе исчисления высказываний должна состоять из фактов - единичных высказываний и формул исчисления высказываний, которые выражают логические связи Между фактами (табл. 7). 
 

 
 
 

     1.8.2. Применение- исчислении высказывании в конструировании релейно- контактных схем

Исчисление высказываний нашло широкое применение в теории и практики конструирования релейно-контактных схем благодаря основному свойству высказываний - высказывание может быть либо истинно, либо ложно. «Контакт» в электро цепи также выполняет две функции пропускать либо не пропускать электричесескй ток. Поэтому можно каждому «контакту» поставить в соответствие некое высказывание, такое что, когда «контакт» пропускает ток, высказывание истинно, а когда пропускает - ложно:

 
 

     Последовательное  соединение «контактов» соответствует  логической операции «и», а параллельное соединение - «или»:

 
 

Произвольная  комбинация соединений дает формулу  исчисления высказываний, например, a∩b∩(cVd): 

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

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

 

 

2.Сценарии  и агенты 

Двумя базовыми понятиями агенториентированого подхода, к построению систем ИИ, служат агент  и среда. Единого определения  этих понятий нет.

Неформально агент  и среда могут быть описаны  так :  

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

Агент существует в среде.

Агент взаимодействует  другими агентами и со средой.

Агент может  изменять среду.  

В агент определяется как интеллектуальное искусственное  существо (носитель ИИ).  

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

В агент это  автоматическая (полуавтоматическая) программно-аппаратная система, которая  решает комплекс задач в динамично  изменяющейся среде.  

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

Требования к  агентам по  

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

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

эффективность - агент должен решать свои задачи эффективно.

интерактивность - агент должен уметь взаимодействовать  с другими агентами.

приспособляемость - агент должен уметь адаптироваться в изменчивой среде.  

Классификация агентов по   

Реактивные агенты (behavior-based agent или situated agent).

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

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

(belief-desire-intention убеждения-желания-намерения).  

Внутреннее состояние  агента описывается с помощью  множества ментальных категорий.  

убеждения - представления  о текущем состоянии среды.

желание - состояния  среды, в которые агент стремится  среду перевести. Агент может  иметь несовместимые желания; желания  могут быть не достижимы.

цели - множество  совместимых и достижимых желаний.

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

Смешанные типы архитектур. Рассмотренные типы систем страдают рядом недостатков.

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

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

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

2 InteRRaP  

INTEgration of Reactive behavior and RAtional Plannig - объединение реактивного поведения и рационального планирования (по [5]).  

2.1 Агент и среда  

Агент InteRRaP рассматривается как некоторая функция, которая получает на вход ощущение и выдает на выход определенное действие. Для агента вводится понятие состояния (mental state) и базовых функций, которые могут изменять состояние.  

Составные части  состояния InteRRaP агента:

ощущение (perception) агента.

мн-во убеждений (beliefs) - информационное состояние.

ситуация (situation). Ситуация это состояние среды. Она определяется как некоторая структура (множество), состоящая из убеждений агента.

мн-во целей (goals). Цель можно определить как состояние среды (ситуацию).

мн-во намерений (intentions). намерение - сформировавшийся план действий, который в последствии выполняется.  

Среда в InteRRaP явным образом не определяется и присутствует как интуитивное понятие.  

Для описания агента в InteRRaP определены специальные языки.  

2.2 Архитектура  

Принципиальная  идея архитектуры InteRRaP состоит в разделении агента на три уровня (в соответствии с идеей смешанной архитектуры т.е. реактивность + способность к планированию) :

уровень поведения (behavior-based layer) - включает реактивность и методы решения стандартных (простых) задач.

уровень локального планирования (local planning layer) - предоставляет механизм для реализации целеустремленности.

уровень совместного  планирования (cooperative planning layer) - служит для взаимодействия с другими агентами.  

Решения для  архитектуры управления агента InteRRaP  

активация снизу-вверх (bottom-up activations) - уровень задействуется, только если уровень не может справиться с ситуацией.

выполнение сверху-вниз (top-down execution) - каждый уровень для достижения своих целей использует операционные примитивы определенные на ниже расположенном уровне.  

  
 
 
 
 
 
 
 
 
 
 

Рисунок: схема  InteRRaP 

Цикл управления в общем виде выглядит так :

ощущение  распознавание  решение  действие  

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

порождение и  пересмотр убеждений (belief generation and

revision) - отношение между убеждениями агента и его ощущениями.

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

активация цели (goal activation) - определяет цели агента для данной ситуаций.

планирование (planning) - отображает текущие цели агента в мн-во операционных примитивов для достижения этих целей. Определяет 'что делать'

назначение (scheduling) - процесс слияния частичных планов для различных целей в единый план выполнения. Определяет 'что и когда делать'