8134

Планирование с помощью пропозициональной логики. Планирование с частичным упорядочением. Графы планирования

Лекция

Информатика, кибернетика и программирование

Планирование с помощью пропозициональной логики. Планирование с частичным упорядочением. Графы планирования Данный подход основан на проверке выполнимости логического высказывания, модель которого выглядит примерно так: Начальное состояние...

Русский

2013-02-04

62.5 KB

3 чел.

Планирование с помощью пропозициональной логики.

Планирование с частичным упорядочением. Графы планирования

Данный подход основан на проверке выполнимости логического высказывания, модель которого выглядит примерно так:

Начальное состояние & Все возможные описания действий & Цель

Такое высказывание должно содержать пропозициональные символы, соответствующие каждому возможному проявлению действия. Модель, в которой выполняется это высказывание, должна присваивать значение 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 выражений.


 

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

40260. Права, обязанности и ответственность аудиторов 31.5 KB
  самостоятельно определять формы и методы аудиторской проверки исходя из требований нормативных актов РФ а также конкретных условий договора с экономическим субъектом и содержание поручения органов дознания прокурора следователя суда и арбитражного суда; 2. проверять у экономических субъектов в полном объеме документацию по финансовохозяйственной деятельности наличие денежных сумм и ценных бумаг материальных ценностей получать разъяснения по возникшим вопросам и дополнительные сведения необходимые для аудиторской проверки;...
40261. Права, обязанности и ответственность аудируемых экономических субъектов 29 KB
  К числу прав относятся следующие: 1 получать от аудиторской организации или индивидуального аудитора информацию о законодательных и нормативных актах Российской Федерации на которых основываются выводы аудиторской организации или индивидуального аудитора; 2 получать от аудиторской организации или индивидуального аудитора аудиторское заключение в срок определенный договором оказания аудиторских услуг; 3 осуществлять иные права вытекающие из существа правоотношений определенных договором оказания аудиторских услуг и не противоречащие...
40262. Правовое основа аудиторской деятельности в РФ 38.5 KB
  В Российской Федерации для регулирования аудиторской деятельности согласно закону об аудиторской деятельности создается уполномоченный федеральный орган государственного регулирования аудиторской деятельности. Функции федерального органа государственного регулирования аудиторской деятельности осуществляет уполномоченный федеральный орган исполнительной власти определяемый Правительством Российской Федерации. Во исполнение Федерального закона Об аудиторской деятельности Правительство Российской Федерации приняло постановление О вопросах...
40263. Приветствия и ответы на них 21.5 KB
  Очень часто после следует вопрос о состоянии здоровья дел: How re you = Как поживаешь Как здоровье How re you doing = Как дела How re you getting on = Как поживаешь How is it getting on = Как дела How is it going = Как дела How is everything = Как здоровье дела Ответ на подобный вопрос обычно звучит так: I'm well thnk you. I'm fine thnk you. Fine thnks при близком знакомстве = Сразу после ответа поинтересоваться состоянием здоровья дел собеседника: nd wht bout you = А у тебя nd you более разговорный...
40264. Привлечение третьих лиц 38.5 KB
  В качестве эксперта аудиторские фирмы могут использовать работу специализированной организации являющейся юридическим лицом а также могут привлекаться физические лица. При проведении аудита аудиторские фирмы могут использовать работу оценщика инженера геолога страховщика или другого эксперта. Решение об использовании работы эксперта при проведении аудита принимает аудиторская фирма исходя из характера и сложности работы обстоятельств подлежащих исследованию уровню их существенности а также их целесообразности надежности и...
40265. Принципы и требования к организации системы внутреннего контроля 40 KB
  Принцип подконтрольности каждого субъекта внутреннего контроля работающего в организации. Принцип компетентности добросовестности и честности субъектов внутреннего контроля. Принцип компетентности состоит в проявлении контролером высокого уровня знаний при контроле финансовохозяйственной деятельности а также предполагает обязательное пополнение багажа знаний через курсы повышения квалификации семинары тренинги необходимо постоянно быть в курсе всех последних изменений в законодательстве изучать опыт и новые методы контроля стремиться...
40266. Принципы формирования учетной политики 29.5 KB
  Допущение непрерывности деятельности означает что организация будет продолжать свою деятельность в обозримом будущем у нее отсутствуют намерения и необходимость ликвидации или существенного сокращения деятельности и следовательно обязательства будут погашаться в установленном порядке. Допущение временной определенности факторов хозяйственной деятельности означает что эти факты относятся к тому отчетному периоду в котором они имели место независимо от фактического времени поступления или выплаты денежных средств связанных с этими...
40267. Продовольственная безопасность страны 37.5 KB
  Вторым важнейшим показателей состояния продовольственной безопасности страны является динамика среднедушевого производства зерна. При этом практика многих стран мира свидетельствует что солидная государственная поддержка АПК способствует росту отечественного производства и обеспечению страны собственным продовольствием. Достижение продовольственной безопасности в России обусловлено достаточностью размеров земельных ресурсов сельского хозяйства и биоклиматического потенциала для производства в необходимых размерах основных продуктов питания....
40268. Планирование аудита 42.5 KB
  Цель задачи и содержание планирования Аудиторская проверка достаточно сложный процесс. Исходя из изложенного выше целью планирования является обеспечение проведения проверки наилучшим оптимальным образом с точки зрения выбранного критерия. Для эмпирического приближения к оптимальному варианту проведения проверки в ходе планирования решают следующие задачи: сбор информации о потенциальном клиенте в частности о его бизнесе организации бухгалтерского учета и внутреннего контроля на его предприятии; оценка уровня существенности...