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


 

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

52382. Розробка бінарного уроку на тему: «Вплив податкової системи на формування державного бюджету» 534 KB
  Згідно даних динаміки доходів Держбюджету України за 2003-2010 роки найбільшим джерелом доходів держбюджету є податок на додану вартість. Другим за величиною джерелом надходжень до бюджету є податок на прибуток підприємств. Вплив держбюджету на розвиток економіки Підприємство сплачує до дохідної частини держбюджету три основних види податків: акцизний збір податок на додану вартість податок на прибуток. Є ціле розмаїття податків про яких багато хто навіть і не чули 1 ведучий – Податок на...
52383. Сімейний бюджет. Доходи і витрати сім’ї 138 KB
  Доходи і витрати сім’ї. Мета: поглибити знання про доходи сім’ї як джерело збільшення її багатства; види доходів витрати обов’язкові платежі бюджет родини; вчити планувати бюджет родини раціонально розраховувати витрати і співставляти їх з доходами; усвідомити свою роль у формуванні сімейного бюджету; виховати грамотного споживача та дбайливого господаря. Основні поняття: доходи витрати бюджет сім’ї збалансований бюджет надлишковий бюджет дефіцитний бюджет....
52384. Відбитки готових природних форм (листя, трава). Композиція «Букет осіннього листя у вазі» 156.5 KB
  Актуалізація опорних знань Читання загадки вчителем Скажіть про яку пору року говориться в загадці Загадка Дрібненький дощик сумно плаче І листячко жовтогаряче З дерев повільно опадає Яка пора це наступає Осінь Чим вам подобається осінь А чи любите ви збирати листочки А що з ними можна зробити скласти букет зробити віночок ІІІ. Робота над темою уроку Вступна бесіда Ось і прийшла золота осінь. додаток 1 Вирушаючи з вами на осінню прогулянку до лісу ми уважно...
52385. Полуфабрикаты 294.5 KB
  В зависимости от источников образования и целевого назначения имущество организаций разделяют на собственное собственный капитал и заемная. Собственный капитал это вложения собственников и прибыль накопленная за время деятельности организации. Собственный капитал.Заемный капитал.
52387. Сценарий праздника “Прощанье с букварем” 65.5 KB
  Учитель. Дорогие гости! Сегодня мы проводим традиционный праздник в первом классе – Праздник Букваря. Говорят, Азбука – к мудрости ступенька. Вот вы и одолели самую трудную, самую важную первую ступеньку на пути к знаниям! Много праздников прекрасных На листках календаря, А меж ними тоже праздник Школьный – праздник Букваря.
52388. Праздник «Прощай, Букварик» 101.5 KB
  Многие из вас не умели читать и писать знали только некоторые буквы. Мы при расставании скажем на прощанье: Тебе за всё спасибо наш дорогой Букварь Буквы мы узнали слоги прочитали И сложили в слоги целые слова После в предложенье. Вдруг на удивленье сразу получилось Родина моя А потом и мама та что моет раму Дети в мяч играют Речка небо лес А ещё в программе прочитали сами Буквы на экране Поле из чудес. Напишу в тетради не оценки ради Буквы алфавита и пример решу.
52389. Прощание с Букварём 60.5 KB
  Букварь Книга для чтения. Плакат: Спасибо тебе Букварь Модель золотого ключика Диалог между мальчиком и девочкой В зале у нас суматоха и шум шёпот движения споры. Мы закончили первую школьную книгу букварь. А научил Вас читать и писать наш умный интересный и добрый друг букварь.
52390. Праздник «ПРОЩАЙ, БУКВАРЬ» 110 KB
  За год наши звездочки подросли поумнели многому научились и стали настоящими звездами а настоящие звезды ездят только в лимузинах вот посмотрите сами и вот подъехал лимузин и по красной дорожке идут наши звезды встречайте Музыкальная заставка Дети идут по звездной дорожке репортеры берут у них интервью Репортер: Скажите трудным для вас был первый год учебы Ученик: ответ – Смех и слезы радость и печаль За год довелось нам испытать Но стараний...