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


 

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

28213. Психологичсское значение дистантных ощущений. Отражение пространства при парной работе дистантных анализаторов 42 KB
  1 базальные ощущения тактилънокинестетическое осязание 2 ведущие зрение слух от них идет максимальная информация 3 сквозные ощущения кинестетические движение. Дистанционные ощущения в процессе эволюции развились позже контактных: вибро и хеморецепция обоняние слух зрение как повышение адаптивных возможностей организма ОТРАЖЕНИЕ ПРОСТРАНСТВА функция парных анализаторов напр. Бинокулярное зрение. При раздражении несоответствующих диспарантных точек бинокулярное зрение или диссоциируется раздваевается или...
28214. Операциональная природа мышления как процесса отражения связей и отношений. Виды мыслительных операций 45.5 KB
  Операциональная природа мышления как процесса отражения связей и отношений. Виды мышления =стадии развития: 1Нагляднодейственное элементарная форма практического мышления направленного на разрешение элементарных практических задач. Виды мышления: А. Типологические классификации мышления: При построении типологий виды мышления обычно различаются попарно как противостоящие друг другу по тем или иным конкретным характеристикам.
28215. Развитие мышления в онтогенезе: сравнительный анализ эмпирических характеристик допонятийного и понятийного мышления 43.5 KB
  Мышление высший психический процесс обобщенного и опосредованного отражения действительности в ходе ее анализа и синтеза при обязательном участии языка речи. В онтогенезе мышление развивается по пути все большей генерализации признаков и объединения их в более крупные классы.Допонятийное мышление нагляднодейственное через практическое действие с объектом нагляднообразное с помощью образных представлений 2.Понятийное мышление словеснологическое с помощью логических понятий и знаков Допонятийное мышление мышление при...
28216. Понятия «эгоцентризм» и «децентрация» в стадиальной концепции интеллекта Жана Пиаже 36.5 KB
  Пиаже показал что ребенок на определенной ступени развития в большинстве случаев рассматривает предметы такими какими их дает непосредственное восприятие то есть он не видит вещи в их внутренних отношениях. Ребенок думает например что луна следует за ним во время его прогулок останавливается когда он останавливается бежит за ним когда он убегает. Свое мгновенное восприятие ребенок считает абсолютно истинным. Вербальный эгоцентризм ребенка определяется тем что ребенок говорит не пытаясь воздействовать на собеседника и не осознает...
28217. Стадии формирования понятия (по Выготскому). Методы исследования и диагностики понятийного мышления 42 KB
  Методы исследования и диагностики понятийного мышления. Понятийное мышление ведущий вид мышления характеризуется использованием понятий логических конструкций которые существуют на базе языка и языковых средств. Понятийное мышление осознанное вербальное мышление. С ее помощью было установлено что формирование понятий у детей проходит через 3 основные ступени: Образование неоформленного неупорядоченного множества отдельных предметов их синкретического сцепления обозначаемого одним словом.
28218. Отношение мышления и речи. Роль внутренней речи в процессе мышления (по А.Н.Соколову). Методы исследования внутренней речи 37 KB
  Отношение мышления и речи. Роль внутренней речи в процессе мышления по А. Методы исследования внутренней речи. Внутренняя речь производная форма внешней звуковой речи специально приспособленная к выполнению мыслительных операций в уме.
28219. Язык и речь: виды речи и ее функции 38.5 KB
  Язык и речь: виды речи и ее функции. Речь конкретный продукт использования носителем языка системы вербальных знаков проявляющийся в различных процессах речи. Речь форма общения опосредствованная языком. Речь процесс использования языка.
28220. Память как сквозной психический процесс: ее функции, виды и процессы 48.5 KB
  При выделении процессов памяти в качестве основания рассматривают различные функции выполняемые памятью в жизни и деятельности. Основные процессы памяти: запоминание сохранение воспроизведение Есть еще один процесс памяти забывание. Деятельность памяти начинается с запоминания т. Таким образом запоминание можно определить как процесс памяти в результате которого происходит закрепление нового путем связывания его с приобретенным ранее.
28221. Основные характеристики памяти и методы их исследования 37 KB
  У нормального человека в процессе запоминания впечатления внешнего мира подвергаются классификации отбору переработке. Опосредствованный осмысленный характер запоминания. Отбирая нужное существенное подлежащее сохранению человек пользуется для лучшего удержания этого материала какимлибо обозначением чаще всего словом Опосредствованное запоминание осмысленного материала это высший уровень запоминания. Если в раннем детстве ребенок многое запоминает механически то впоследствии он все более широко пользуется опосредствованными...