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


 

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

22755. Участь делегації УРСР в роботі Дунайської конференції 73 KB
  право України було відновлено. У 19941996 роках ЄС ухвалив Спільну позицію щодо України 28 листопада 1994 р. Указом Президента України було затверджено Стратегію інтеграції України до ЄС розраховану на період до 2007 року. на Гельсінському самміті Євросоюзу була ухвалена Спільна стратегія ЄС щодо України яка спрямована на зміцнення стратегічного партнерства з Україною.
22756. Участь УРСР в роботі конференції в Сан-Франциско 55.5 KB
  Політика ЄС стосовно України. Основні проблеми безпеки України зовнішній аспект та механізми їх гарантування. Політика ЄС стосовно України. У 19941996 роках ЄС ухвалив Спільну позицію щодо України 28 листопада 1994 р.
22757. VI сесія (1944р.) Верховної Ради УРСР щодо формування союзного Наркомату закордонних справ 37 KB
  Наслідки розширення ЄС для зовнішньої політики України. питання про утворення НКЗС Українибуло розглянуто на Політбюро ЦК КПб України. Поперше було вирішено встановити дипломатичні відносини України з Великою Британією і США подруге з іншими країнами антигітлерівської коаліції. Наслідки розширення ЄС для зовнішньої політики України Розширення Європейського Союзу яке відбулося 1 травня 2004 року призвело до історичних змін політичних географічних та економічних умов для України та Євросоюзу.
22758. Діяльність УРСР в ООН 1945 - 1990 рр 38 KB
  Економічне співробітництво України та Росії: стан проблеми та механізми їх вирішення. Європейська політика України: концептуальні засади та практика. Виступивши проти зосередженості ЮНЕСКО тільки на фінансуванні та інших формах розв'язання проблеми встановлення причин ракових захворювань делегат від України Тульчинська порушила питання про негайне впровадження у життя вже одержаних результатів її пропозиція була схвалена більшістю делегацій 21 проти 18 при 7 що утрималися. Економічне співробітництво України та Росії: стан проблеми та...
22759. Участь УРСР в обговоренні ООН грецького та індонезійського питань 35.5 KB
  Питання делімітації та демаркації кордонів кордону України: досягнення і проблеми. Інтереси України в Балканському регіоні та механізми їх реалізації. Півстоліття назад саме міністр закордонних справ України Мануїльский із трибуни ООН проголосив Руки геть від Індонезії . Погана спадщина радянськоіндонезійських відносин що повністю дісталося Росії абсолютно не стосується України той самий випадок коли не варто шкодувати про усіх без винятку боргах й активах колишнього СРСР.
22760. Участь делегації УРСР в конференції в Сан-Франциско 43 KB
  На території РФ функціонують Посольство України м. На території України здійснюють діяльність Посольство Російської Федерації м. розстрілу Білого дому та зміцнення позицій реформаторів у Кремлі курс щодо України став жорсткішим що виявилось у намаганнях на дострокових виборах 1994 р. У першу чергу це стосується умов тимчасового перебування та функціонування Чорноморського Флоту РФ на території України договірноправового оформлення українськоросійського державного кордону тощо.
22761. Участь УРСР в роботі міжнародних організацій 1950-ті- 1980-тірр 41 KB
  Політика ЄС стосовно України. Питання зовнішньої політики в роботі Верховної Ради України. 202 пропозиції поправки резолюції що вносилися представниками України у міжнародних організаціях та конференціях. Політика ЄС стосовно України.
22762. Зміст і значення конституційних змін в УРСР 1944 р 50 KB
  Міжнародне правова база співробітництва України та ЄС. Відносини України з державами Близького та Середнього Сходу. Міжнародно правова база співробітництва України та ЄС. Відносини між Україною та Європейським Союзом були започатковані в грудні 1991 року коли Міністр закордонних справ Нідерландів як головуючої в ЄС у своєму листі від імені Євросоюзу офіційно визнав незалежність України.
22763. Питання звичайних озброєнь в зовнішній політиці України 58.5 KB
  Основні напрямки і принципи зовнішньої політики України. Питання звичайних озброєнь в зовнішній політиці України. Напередодні краху СРСР Останніми роками перед розпадом СРСР змінився характер західних наукових підходів до проблем України. Як показав подальший перебіг подій більшість дипломатів Української РСР виявилася готовою до плідної роботи в ім'я незалежної України.