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


 

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

78910. Зависимость СГН от социокультурного контекста 28 KB
  в науке преобладала классическая рациональность которая реализовывалась по схеме: Субъект познания Способы познания Объект познания. ни способы которыми он пользуется не оказывают влияния на искомый результат познания и мы получаем образ объекта в чистом виде на схеме это обозначено скобками. Второй этап характеризующийся формированием неклассической рациональности начинается тогда когда науки переходят к исследованию объектов воздействие на которые способов познания является неустранимым и сказывается на результате...
78911. Сходства и отличия наук о природе и об обществе 28.5 KB
  Проблема разграничения наук о природе и социальногуманитарных наук и определение предмета гуманитарного знания которым посвящен первый вопрос является важнейшей методологической проблемой современного наукознания. Сложность ее решения связана с тем что относительно предмета социальногуманитарных наук не существует единства мнений. Чаще всего различные исследователи пытаются выделить среди этих наук какуюто ключевую дисциплину вокруг которой можно было бы объединить все другие науки о духе.
78912. Специфика объекта СГП 21.5 KB
  Вовторых в структуру и содержание объекта социальногуманитарного познания с необходимостью входит субъект познания. Объективация предмета познания оказывается в этом случае неполной и сопряжена с большими методологическим трудностями. Втретьих исследование объекта осуществляется в социальногуманитарном знании с ценностных позиций поскольку субъект познания будучи сам частью социальной системы оказывается нагруженным идеологическими предпосылками предрассудками некритически воспринятыми установками и т.
78913. Социокультурная обусловленность дисциплинарной структуры социально-гуманитарного знания 25 KB
  Прежде всего речь идет о различении социальных наук как наук об обществе и гуманитарных наук как наук в фокусе которых находится человек индивидуальная и социальная психология этика и т. Разделение наук по предмету о чем речь уже шла выше. Разделение наук по методу: в социальных науках используется метод объяснения тогда как в гуманитарных базовой методологической процедурой выступает понимание сразу же заметим что такое разделение грешит противопоставлением понимания объяснению. Разделение наук одновременно по предмету и методу...
78914. Конвергенция естественно-научного и СГН в современой науке 24 KB
  Логику развития методологии гуманитарного познания можно представить следующим образом: сначала проблематика методологии гуманитарных наук развивалась в направлении выявления и обоснования их специфики по сравнению с науками о природе. Главной на этом этапе является проблема идентификации социальногуманитарных наук и их демаркации от наук естественных. Обоснованию специфики социальногуманитарного познания посвящены работы Дильтея Описательная психология Гадамера Истина и метод Фуко Слова и вещи Рикера Герменевтика и...
78915. Специфика научной картины мира в СГН 31.5 KB
  Специфика научной картины мира в СГН Научная картина мира исторична она опирается на достижения науки конкретной эпохи в пределах тех знаний которыми располагает человечество. Научная картина мира представляет собой синтез научных знаний соответствующих конкретноисторическому периоду развития человечества. Поэтому она более строгое понятие чем образ мира или видение мира. В научную картину мира входят знания отвечающие критериям научности.
78916. Специфика субъекта СГП 34 KB
  В сфере познания субъект определяет предмет исследования выделяя его как некий срез противостоящего ему объекта а также выстраивает концептуальную и эмпирическую модели познаваемого предмета. В современном познании субъект проектирует ряд условий познания данного предмета проходит основные этапы процесса познания опираясь на те методы которые в наибольшей степени соответствуют характеристикам и самой природе познаваемого объекта. Субъектами социального и гуманитарного познания могут быть как индивиды отдельные исследователи...
78917. Кантовские представления о диалектике теоретического и практического разума 27 KB
  Правда на сами эти предпосылки Кант не покушается: более того он увековечивает их как прирожденные свойства разума. Резкий метафизический разрыв теоретического и практического разума опытных и априорных суждений анализа и синтеза общего и единичного целого и части – весь комплекс противоречий к которым неизбежно приходит метафизическое мышление Кант выставил перед философией как решающую проблему. Их можно только мыслить как условия возможности и науки и нравственности как гарантии теоретического и...
78918. Принципы логики социальных наук Поппера 47.5 KB
  Именно поразительный прогресс естественных наук о котором идет речь в моем первом тезисе постоянно напоминает нам о нашем незнании даже в области естественных наук...