8134

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

Лекция

Информатика, кибернетика и программирование

Планирование с помощью пропозициональной логики. Планирование с частичным упорядочением. Графы планирования Данный подход основан на проверке выполнимости логического высказывания, модель которого выглядит примерно так: Начальное состояние...

Русский

2013-02-04

62.5 KB

2 чел.

Планирование с помощью пропозициональной логики.

Планирование с частичным упорядочением. Графы планирования

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

Начальное состояние & Все возможные описания действий & Цель

Такое высказывание должно содержать пропозициональные символы, соответствующие каждому возможному проявлению действия. Модель, в которой выполняется это высказывание, должна присваивать значение true действиям, являющимся частью правильного плана, и false – другим действиям. Если задача планирования неразрешима, то данное высказывание будет невыполнимым.

Рассмотрим задачу воздушной транспортировки. В начальном состоянии (время 0) самолет P1 находится в аэропорту SFO, а самолет P2 – в аэропорту JFK:

at(P1,SFO)0 & at(P2,JFK)0 & ¬at(P1,JFK)0 & ¬at(P2,SFO)0

Задача состоит в выработке плана действий для достижения состояния, когда самолет P1 находится в аэропорту JFK, а самолет P2 – в аэропорту SFO.

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

at(P1,JFK)1  (at(P1,JFK)0 & ¬Fly(P1,JFK,SFO)0) or (at(P1,SFO)0 & Fly(P1,SFO,JFK)0)

at(P2,SFO)1  (at(P2,SFO)0 & ¬Fly(P2,SFO,JFK)0) or (at(P2,JFK)0 & Fly(P2,JFK,SFO)0)

Здесь, например, символ Fly(P1, SFO, JFK)0 является истинным, если самолет P1 вылетает из аэропорта SFO в аэропорт JFK во время 0.

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

Fly(P1,JFK,SFO)0 => at(P1,JFK)0

Fly(P2,SFO,JFK)0 => at(P2,SFO)0

Предположим, что цель истинна в начальном состоянии, во время T=0. То есть проверяем целевое утверждение:

at(P1,JFK)0 & at(P2,SFO)0

Если попытка окажется неудачной, то повторим ее снова во время T=1, то есть проверим выполнимость высказывания

Начальное состояние & Аксиомы состояния-преемника & Цель1

и т.д. до тех пор, пока не достигнем осуществимого плана с минимальной длиной. Можно наложить верхний предел Тmax для безусловного завершения этого алгоритма. В нашем случае Тmax= 1. После нахождения модели выполнимого высказывания план извлекается путем поиска тех пропозициональных символов, которые относятся к действиям, и которым в модели присвоено значение true. Решением данной задачи является следующий план:

Fly(P1,SFO,JFK)0, Fly(P2,JFK,SFO)0

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

¬Fly(P1,SFO,JFK)0 & Fly(P1,SFO,LAX)0

¬Fly(P2,JFK,SFO)0 & Fly(P2,JFK,LAX)0

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

для любых p, x,y,t  x≠y => (at(p,x)t & at(p,y)t)

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

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

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

 T*|act|*|O|P,

где |act| - количество схем действий, |O|- количество объектов в проблемной области, P – максимальная арность (количество параметров) любой схемы действий. Количество выражений еще больше. Например, при 10 временных этапах, 12 самолетах и 30 аэропортах полная аксиома исключения действий состоит из 583 миллионов выражений.

Одним из способов преодоления указанного недостатка является процесс расщепления символов. Например, символ действия fly(P1,SFO,JFK)0, арность которого равна 3, можно заменить тремя новыми символами:

Fly1(P1)0 – самолет P1 прилетел во время 0,

Fly2(SFO)0 – аэропортом отправления в этом полете был SFO,

Fly3(JFK)0 – аэропортом назначения в этом полете был JFK.

Теперь требуется только T*|act|*P*|O| символов.

Аналогичные сокращения допускаются в аксиомах предусловия и аксиомах исключения действий. Для описанного выше случая полная аксиома исключения действий сокращается с 583 миллионов выражений до 9360 выражений.


 

А также другие работы, которые могут Вас заинтересовать

21607. ЗАЩИТА АППАРАТУРЫ ОТ ВЛИЯНИЯ КЛИМАТИЧЕСКИХ ФАКТОРОВ ЭКСПЛУАТАЦИИ 439 KB
  Protection from climatic conditions of the usages Тема 5: ЗАЩИТА АППАРАТУРЫ ОТ ВЛИЯНИЯ КЛИМАТИЧЕСКИХ ФАКТОРОВ ЭКСПЛУАТАЦИИ Естествоиспытатель не принимает в расчет невероятное. Тепловой режим аппаратуры. Охлаждение аппаратуры.
21608. ЗАЩИТА АППАРАТУРЫ ОТ МЕХАНИЧЕСКИХ ВОЗДЕЙСТВИЙ И ПОМЕХ 572.5 KB
  Виды механических воздействий на РЭА. Амортизация конструкции РЭА. Применение экранов в РЭА. Защита от механических воздействий [1 2] Виды механических воздействий на РЭА.
21609. ОБЕСПЕЧЕНИЕ НАДЕЖНОСТИ РАБОТЫ АППАРАТУРЫ 518.5 KB
  Вероятность безотказной работы РЭА. Повышение надежности РЭА резервированием. Информационные методы повышения надежности РЭА. Расчет надежности РЭА.
21610. Работа с данными. Поиск и замена данных 279.5 KB
  Для поиска данных необходимо выполнить команду Правка Найти и во вкладке Найти диалогового окна Найти и заменить рис. Поиск данных во вкладке Найти диалогового окна Найти и заменить При поиске можно использовать подстановочные знаки. Результаты поиска данных во вкладке Найти диалогового окна Найти и заменить Для более детального поиска во вкладке Найти диалогового окна Найти и заменить см.
21611. Работа с форматами Excel. Копирование форматов 252.5 KB
  Ко всем выделенным фрагментам будет применен выбранный стиль. Копирование формата с использованием специальной вставки в диалоговом окне Специальная вставка Использование стилей О стилях Использование стилей обеспечивает единообразие оформления данных и ячеек во всей книге позволяет быстро устанавливать выбранный набор параметров форматирования а также мгновенно изменять оформление всех ячеек к которым применен один стиль. Для просмотра доступных стилей необходимо выполнить команду Формат Стиль. Список основных стилей приведен в...
21612. Создание и оформление диаграмм в Microsoft Excel 468 KB
  Диаграммы создаются на основе данных расположенных на рабочих листах. При необходимости в процессе или после создания диаграммы в нее можно добавить данные расположенные на других листах. Диаграмма может располагаться как графический объект на листе с данными не обязательно на том же где находятся данные взятые для построения диаграммы.
21613. СИСТЕМА МІЖНАРОДНИХ ЕКОНОМІЧНИХ ВІДНОСИН 194.5 KB
  Сучасний світ і середовище міжнародної економіки. Еволюція світового ринку та міжнародної економіки. Міжнародний поділ праці як основа розвитку міжнародних економічних відносин. Світовий ринок. Світове господарство та міжнародна мобільність факторів виробництва. Міжнародна економіка та її структура.
21614. Создание таблиц Microsoft Excel 480 KB
  Приведены требования при вводе данных в ячейки листа при этом особое внимание уделено порядку ввода дат и времени. По умолчанию все данные ячейки вводятся одной строкой. Для этого следует выделить ячейки не обязательно смежные в которые необходимо ввести данные ввести данные и нажать клавиши клавиатуры Ctrl Enter или при нажатой клавише клавиатуры Ctrl щелкнуть по кнопке Ввод в строке формул см. Одни и те же данные можно ввести одновременно в одноименные ячейки различных листов.
21615. Установка числовых форматов MS Excel 248 KB
  Особое внимание уделено возможностям использования числовых форматов при представлении чисел дат и времени. Показано использование денежного и финансового форматов. О числовых форматах Под числами в Microsoft Excel понимаются собственно числа включая числа с десятичными и или простыми дробями и числа с указанием символа процентов а также даты и время.