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


 

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

75416. Оптичні давачі. Давачі дифузного типу 2.47 MB
  Давачі дифузного типу Давач дифузного типу створений за принципом давача з відбиттям від рефлектора. Давачі дифузного типу Давач дифузного типу з придушенням заднього фону Давачі дифузного типу з придушенням заднього фону були розроблені для того щоб досягти визначеного діапазону сканування для будьяких обєктів незалежно від їх яскравості кольору та інших властивостей а також від яскравості заднього фону. Такі давачі ігнорують всі обєкти які знаходяться до давача ближче ніж попередньо налаштований діапазон виявлення.
75417. Безконтактний магніточутливий давач 262 KB
  Давач що виявляє зміну напруженості постійного магнітного поля має напівпровідниковий комутуючий елемент і що не містить рухомих частин в чутливому елементі рис. Спрацювання давача відбувається при зміні напруженості магнітного поля викликаного наприклад переміщенням постійного магніту розташованого на рухомої частини механізму. Крім того магніточутливих давачи можуть відрізнятися по реакції на зміну магнітного поля: При збільшенні напруженості зовнішнього магнітного поля наприклад при наближенні постійного магніту...
75418. Блоки живлення, лічильники імпульсів, реле часу, сигналізатори рівня, розєми і зєднувачі, вибухобезпечне устаткування 753.5 KB
  Блок живлення — це вторинне джерело живлення, призначене для забезпечення живлення електроприладу електричною енергією, при відповідності вимогам її параметрів: напруги, струму, і т. д. шляхом перетворення енергії інших джерел живлення.
75419. Сенсори. Аналогові сенсори. Сенсори положення, кута, віддалі та товщини 575 KB
  Сенсори положення кута віддалі та товщини. Аналогові сенсори За допомогою аналогових сенсорів перетворюють механічні величини наприклад зміну положення або електричні величини наприклад зміну потужності на електричні сигнали напруги або струму. Сигнали з вимірювального перетворювача можуть бути представлені у фізичних величинах наприклад у випадку перетворювача положення в мм. Сенсори положення кута віддалі та товщини Потенціометричні контактні сенсори При пересуванні ковзного контакту в поступальному потенціометрі або повороту...
75420. Індуктивні безконтактні кінцеві сигналізатори 568 KB
  Котушка з відкритим, чашковим феромагнітним осердям створює високочастотне електромагнітне поле. Котушка є індуктивною частиною коливного контуру, який збуджується за допомогою частотного генератора з частотою близько
75421. Сенсори розтягу, сили, обертового моменту i тиску 585 KB
  Види виконання вимірювальних сіток фольгових тензометрів Для одночасного вимірювання в кількох напрямках служать спеціальні тензометри в яких вимірювальні сітки розміщені одна відносно іншої під кутом 120 або під кутом 45 до напрямку видовження рис.
75422. Сенсори прискорення. Сенсори температури 164 KB
  Сенсори температури. Сенсори температури Найважливішим різновидом давачів є давачі температури оскільки багато процесів у тому числі і в повсякденному житті регулюються температурою наприклад: регулювання опалення на підставі вимірювання температури теплоносія на вході і виході а також температури в приміщенні і зовнішньої температури; регулювання температури води в пральній машині; регулювання температури електропраски електроплитки духовки...
75423. Бінарні сенсори. Цифрові сенсори 480 KB
  Бінарні сенсори влаштовані як реле (перемикачі) або як аналогові сенсори з перемикачем порогового значення. Коли вхідна величина сенсора досягає порогу перемикання, бінарний вихідний сигнал змінює значення. Під час зміни вхідної величини у зворотному напрямі, по досягненню порогового значення...
75424. Інкрементальні сенсори положення. Кодові лінійки і диски абсолютних сенсорів 631 KB
  Інкременгальні сенсори переміщення оснащені лінійкою з рисковими поділками. Читання положення рисок здійснюється оптичними або магнітними методами. В сенсорах через які проходить світло використовуються скляні лінійки з рисками які поглинають світло і проміжками які пропускають світло шириною 4 мкм рис. Пристрої які зчитують це складаються з потужного джерела світла зчитувальної пластинки і електронної системи аналізу.