Сложности, связанные с использованием пропозициональных кодировок
Основным недостатком описанного пропозиционального подхода являются колоссальные размеры пропозициональной базы знаний, которая формируется на основе первоначальной задачи планирования. Например, схема действий Fly(p, alfa2) преобразуется в т х | Planes | х | Airports \2 различных пропозициональных символов. Вообще говоря, общее количество символов действий ограничено значением Т х | Act | х | О| р, где | Act | — количество схем действий; | О | — количество объектов в проблемной области; Р — максимальная арность (количество параметров) любой схемы действий. Количество выражений еще больше. Например, при 10 временных этапах, 12 самолетах и 30 аэропортах полная аксиома исключения действий состоит из 583 миллионов выражений.
Поскольку количество символов действий экспоненциально зависит от арности схемы действий, одним из способов преодоления указанного недостатка может оказаться попытка уменьшить арность. Это можно сделать, заимствовав одну идею из области семантических сетей (см. главу 10). В семантических сетях используются только бинарные предикаты; предикаты с большим количеством параметров сводятся к множеству бинарных предикатов, которые описывают каждый параметр отдельно. Применяя эту идею к символу действий, такому как Fly{PlfSFO,JFK)°, получим следующие три новых символа:
Flyi{Pi)°: самолет Pi прилетел во время О
Fly2{SFO)°: аэропортом отправления в этом полете был SFO Flyi{JFK)°: аэропортом назначения в этом полете был JFK
Этот процесс, называемый расщеплением символов (symbol splitting), позволяет устранить необходимость в использовании экспоненциального количества символов. Теперь требуется только Т х |Act| х Р х |о| символов.
Расщепление символов само по себе позволяет сократить количество символов, но не приводит к автоматическому уменьшению количества аксиом в базе знаний. Это означает, что если бы каждый символ действия в каждом выражении был просто заменен конъюнкцией трех символов, то общий размер базы знаний остался бы примерно тем же самым. Расщепление символов фактически приводит к уменьшению базы знаний потому, что некоторые из расщепленных символов станут нерелевантными для определенных аксиом и могут быть удалены. Например, рассмотрим аксиому состояния-преемника, приведенную в уравнении 11.1, модифицированную так, чтобы в нее был включен символ аэропорта LAX и исключены предусловия действия (которые будут учитываться с помощью отдельных аксиом предусловия):
AtiPx.JFK)1 <=* {At{P\, JFK) 0 Л -,Fly(PlfJFK, SFO)0 Л -.Fly (Pi, JFK, LAX) 0 ) v Fly (Pi, SFO, JFK)0 v Fly(PllLAX,JFK)°
В первом условии сказано, что самолет Р1 должен быть в аэропорту JFK, если он находился в нем во время 0 и не улетел из JFKb какой-то другой город, неважно, какой именно; во втором условии сказано, что он должен находиться в аэропорту JFK, если он прилетел туда из другого города, неважно, из какого именно. При использовании этих расщепленных символов мы можем удалить параметр, значение которого нас не интересует:
At(PllJFK)1 (At(PlfJFK)° л -.(Flyi(Pi)0 Л Fly2(JFK)°) ) v (Flyi(Pi)0 Л Fly2(JFK)°)
Обратите внимание на то, что в этой аксиоме аэропорты SFO и LAX больше не упоминаются. Вообще говоря, теперь расщепленные символы действий позволяют добиться того, чтобы размер каждой аксиомы состояния-преемника был независимым от количества аэропортов. Аналогичные сокращения допускаются в аксиомах предусловия и аксиомах исключения действий (см. упр. 11.16). Для описанного выше случая с 10 времен-нб/ми этапами, 12 самолетами и 30 аэропортами полная аксиома исключения действий сокращается с 583 миллионов выражений до 9360 выражений.
Но остается непреодоленным еще один недостаток: представление с помощью расщепленных символов не допускает описания параллельных действий. Рассмотрим два параллельных действия, Fly[P1, SFO, JFK)0 и Fly(P2, JFK, SFO) °. Преобразовав их в расщепленные представления, получим следующее:
Flyi(Pi)0 л Fly2{SFO)° Л Fly2{JFK)° л Fly!(P2)° л Fly2(JFK)° л Fly2(SFO)°
Теперь больше нет возможности определить с помощью этого выражения, что произошло! Мы знаем, что самолеты Рх и р2 вылетели, но не можем выяснить места их отправления и назначения. Это означает, что должна использоваться полная аксиома исключения действий со всеми указанными выше недостатками.
Планировщики, основанные на проверке выполнимости, способны обрабатывать крупные задачи планирования, например находить оптимальные тридцати-этапные решения для задач планирования в мире блоков с десятками блоков. Размер пропозиционального представления и стоимость решения в высшей степени зависят от задачи, но в большинстве случаев узким местом становится нехватка памяти, требуемой для хранения пропозициональных аксиом. Одним из интересных результатов этих исследований оказалось то, что алгоритмы поиска с возвратами, такие как DPLL, часто лучше решают задачи планирования по сравнению с алгоритмами локального поиска, подобными WalkSAT. Это связано с тем, что основная часть пропозициональных аксиом представляет собой хорновские выражения, которые эффективно обрабатываются с помощью метода распространения единичных выражений. Это наблюдение привело к разработке гибридных алгоритмов, в которых комбинируется некоторый метод случайного поиска с возвратами и метод распространения единичных выражений.