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 выражений.


 

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

48457. ЗАМЕТКИ ПО РУССКОМУ СЛОВООБРАЗОВАНИЮ 21.91 KB
  Морфемы двух типов: 1 основы непроизводные первичные 2 аффиксы присоединение которых к первичным основам превращает их в основы производные. значение слов с производной основой всегда определимо посредством ссылки на значение соответствующей первичной основы если по выделении из состава какойнибудь основы известного звукового комплекса в остатке получится звуковой комплекс не обладающий какимнибудь значением представляющий собой пустое звукосочетание то выделение произведено неправильно то есть не отразило реального факта языка....
48458. Установление консулата. Расцвет консульства во Франции 31.01 KB
  Consult период в истории Франции во время которого власть в стране фактически принадлежала Наполеону Бонапарту но юридически его власть была различным образом ограничена. Вторым и третьим консулами с правом совещательного голоса становятся Камбасерес 1753 1824 и Лебрен Шарль Франсуа 1739 1824 Избрание членов Сената и Государственного совета Репрессивные меры против печати Учреждение префектур и административная реформа Разгром Австрии и упрочение власти Бонапарта Покушение на Бонапарта 3 нивоза IX года и изгнание...
48459. ЭЛЕКТРОТЕХНИЧЕСКОЕ И КОНСТРУКЦИОННОЕ МАТЕРИАЛОВЕДЕНИЕ 642.05 KB
  При изучении хаотического теплового и направленного под действием силы электрического поля движения электронов был выведен закон Ома. Связь плотности тока J в амперах на квадратный метр и напряженности электрического поля в вольтах на метр в проводнике дается известной формулой: дифференциальная форма закона...
48460. Радиосвязь и электронные приборы 5.04 MB
  Варисторы Варистор полупроводниковый резистор сопротивление которого зависит от приложенного напряжения. где U I Напряжения и ток варистора. Для повышения обратного напряжения диоды включаются последовательно. Стабилитроны Полупроводниковый диод напряжение на котором в области пробоя слабо зависит от тока и который используется для стабилизации напряжения.
48461. Перспективи розвитку українського біржового аграрного ринку 83 KB
  Теоретичні аспекти та Інфраструктура світового аграрного ринку Економічна сутність ринку виражається насамперед як категорія обміну, який організований за законами товарного виробництва і обігу, сукупність відносин товарного і грошового обміну
48462. Проверка функциональности программ 124.5 KB
  тестирование Аналитическая стахостическое детерминированное система Флойда система Дейстра система Хоара Метод не подвижности точки программы 3Понятие о системе Хоара Логика Хоара формальная система с набором логических правил предназначенных для доказательства корректности компьютерных программ Основной характеристикой логики Хоара является тройка Хоара.Оценки сложности программы LOC наработанный...
48463. Магнитное поле 2.39 MB
  Импульсно-индукционный метод измерения. Приборы применяющиеся при измерении индукции импульсно-индукционным методом измерения. Магнитными измерениями называется область измерительной техники которая занимается измерением величин характеризующих магнитное поле магнитные цепи магнитные свойства веществ и материалов. Магнитные измерения неразрывно связанны с электрическими измерениями.
48464. Разработка и внедрение комплексного учебно-методического обеспечения подготовки специалистов по специальностям «Коммерческая деятельность», «Экономика и управление на предприятии» по курсу Коммерческое страхование 2.06 MB
  Экономическая сущность и роль страхования в экономике. Социально-экономическая сущность страхования. Классификация страхования. Страховые термины связанные с существенными условиями страхования.
48465. Дистанционное обучение 1.31 MB
  Это отражается как на технической оснащенности образовательных учреждений их доступе к мировым информационным ресурсам так и на использовании новых видов методов и форм обучения ориентированных на активную познавательную деятельность учащихся обучение в сотрудничестве и т. Благодаря средствам новых информационных и коммуникационных технологий появилась еще одна форма обучения в дополнение к традиционным очному и заочному обучению дистанционное обучение. В процессе такого обучения студент определенную часть времени самостоятельно...