Выразительность и расширения языка
Всевозможные ограничения, налагаемые в представлении Strips, были выбраны в надежде на то, что алгоритмы планирования станут более простыми и эффективными и вместе с тем при описании реальных задач не будут возникать слишком значительные трудности. Одно из самых важных ограничений состоит в том, что литералы должны быть свободными от функций. Благодаря наличию такого ограничения можно быть уверенным в том, что каждую схему действий для каждой конкретной задачи удастся пропозиционализировать, т.е. преобразовать в конечную коллекцию чисто пропозициональных представлений действий без переменных (дополнительную информацию по этой теме см. в главе 9). Например, в проблемной области грузовых авиационных перевозок для задачи с десятью самолетами и пятью аэропортами можно преобразовать схему Flyip, from, to) в 10x5x5=250 чисто пропозициональных действий. Планировщики, описанные в разделах 11.4 и 11.5, работают непосредственно с пропозиционализированными описаниями. Если же будут разрешены функциональные символы, то количество состояний и действий, которые могут быть сконструированы, станет бесконечно большим.
В последние годы стало очевидно, что язык Strips является недостаточно выразительным для некоторых реальных проблемных областей. В результате этого было разработано много вариантов данного языка. В табл. 11.1 кратко описан наиболее важный из них, язык ADL (Action Description Language — язык описания действий), на основе его сравнения с базовым языком Strips. В языке ADL действие Fly можно записать следующим образом:
Action{Fly{p:Plane, from:Airport, to:Airport), Precond: At{p, from) A {from Ф to), Effect: -i At(p, from) A At{p, to))
Результат р л —iQ означает добавление Р и -iQ и удаление —iP и Q
Квалифицированные переменные в целях: цель Эх A t (Pi, х) A A t (Р2, х) состоит в том, чтобы Pi и Р2 находились в одном и том же месте
В целях допускается использование конъюнкций и дизъюнкций: —I Poor A [Famous v Smart)
Разрешены условные результаты: when Р: Е означает, что Е является результатом, только если выполнено условие Р
Предикат равенства (х=у) является встроенным
Переменные могут иметь типы, как, например, в выражении (р:Plane)
Обозначение р: Plane в списке параметров представляет собой сокращение для Plane (р) в предусловии; применение такого обозначения не приводит к повышению выразительной мощи, но позволяет повысить удобство для чтения. (Применение этого обозначения приводит также к сокращению количества возможных пропозициональных действий, которые могут быть сконструированы.) Предусловие (fron&to) выражает тот факт, что полет не может быть совершен из некоторого аэропорта в сам этот аэропорт. Такое условие не может быть выражено кратко в языке Strips.
Различные формальные средства планирования, применяемые в искусственном интеллекте, были систематизированы в рамках стандартного синтаксиса, получившего название PDDL (Planning Domain Definition Language — язык определения проблемной области планирования). Этот язык позволяет исследователям обмениваться эталонными тестовыми задачами и сравнивать полученные результаты. Язык PDDL включает подязыки для Strips, ADL и иерархических сетей задач (Hierarchical Task Network — HTN), которые будут рассматриваться в главе 12.
Системы обозначений Strips и ADL являются вполне приемлемыми для многих реальных проблемных областей. В приведенных ниже подразделах описаны некоторые простые примеры. Тем не менее эти языки все еще характеризуются некоторыми существенными ограничениями. Наиболее очевидным из них является то, что эти языки не позволяют представить естественным образом последствия действий. Например, если в самолете есть люди, пакеты или частички пыли, то все они в процессе полета самолета также меняют свое местонахождение. Можно было бы представить эти изменения как прямой результат полета, но кажется более естественным представить изменение местонахождения содержимого самолета как логическое следствие изменения местонахождения самого самолета. Дополнительные примеры подобных ограничений состояния приводятся в разделе 11.5. Кроме того, в классических системах планирования не предпринимается даже попытка решить проблему спецификации: проблему не представленных в определении задачи обстоятельств, которые могут вызвать неудачное завершение действия. Способы решения проблемы спецификации описаны в главе 12.
Пример: воздушный грузовой транспорт
В листинге 11.1 показана одна из задач организации перевозок с помощью воздушного грузового транспорта, в которой предусматривается загрузка и разгрузка грузов в самолеты и из самолетов, а также перелет из одного места в другое. Эта задача может быть определена с помощью трех действий: Load, Unload и Fly. Действия влияют на значения двух предикатов: предикат In (с, р) означает, что груз с находится в самолете р, а предикат At{x, а) означает, что объект х (либо самолет, либо груз) находится в аэропорту а. Следует отметить, что предикат At больше вообще не обусловливает местонахождение груза, если предикат In определяет, что груз находится в самолете, поэтому At фактически означает "доступен для использования в указанном местонахождении". Для того чтобы научиться прорабатывать все эти детали должным образом, необходимо приобрести определенный опыт составления определений действий. Ниже приведен план, который является решением данной задачи.
[Load(Clf Plf SFO) , Fly{Plf SFO, JFK), Unload { Clf Plf JFK) , Load {C2, P2, JFK) , Fly{P2 , JFK, SFO) , Unload (C2, P2, SFO) ]
Листинг 11.1. Задача Strips, в которой предусматривается транспортировка груза между аэропортами
Init{At(Clt SFO) A At{C2, JFK) A At{Plf SFO) A At{P2, JFK) A Cargo (Ci) л Cargo (C2) л Plane (Pi) л Plane (P2) л Airport{JFK) A Airport{SFO) ) Goal{At{C1, JFK) A At{C2, SFO))
Action{Load{с, p, a),
Precond: At {с, а) л At{p, а) л Cargo (с) л Plane (p) л Airport {a)
Effect: -i At{c, а) л In(c, p) ) Action{Unload(c, p, a),
Precond: Хл(с, p) л At{p, а) л Cargo (с) л Plane{p) л Airport {a)
Effect: At(c, а) А -л In{c, p) ) Action{Fiy(p, from, to) ,
Precond: At(p, from) л Plane (p) л Airport {from) л Airport {to)
Effect: -i At(p, from) л At(p, to))
В применяемом здесь представлении используется чистый (т.е. не дополненный) язык Strips. В частности, это представление не исключает того, что самолет может вылететь и прилететь в один и тот же аэропорт. Возникновение такой ситуации могут предотвратить литералы неравенства, предусмотренные в языке ADL.
Пример: задача с запасным колесом
Рассмотрим задачу смены колеса со стертой покрышкой. Точнее, цель состоит в том, чтобы на оси автомобиля было правильно смонтировано исправное запасное колесо, тогда как в начальном состоянии на оси имеется колесо со стертой покрышкой, а в багажнике находится исправное запасное колесо. Для того чтобы упростить эту задачу, рассмотрим чрезвычайно абстрактную ее версию, в которой не учитываются крепко прихваченные крепежные гайки или другие усложнения. Существуют только четыре действия: выемка запасного колеса из багажника, снятие колеса со стертой покрышкой с оси, установка запасного колеса на ось и оставление автомобиля без присмотра на ночь. Предполагается, что автомобиль находится в районе с исключительно неблагоприятной криминогенной обстановкой, поэтому результатом его пребывания ночью на улице становится исчезновение колес.
Описание ADL этой задачи приведено в листинге 11.2. Обратите внимание на то, что оно является исключительно пропозициональным. Это описание превосходит по своим возможностям описание на языке Strips в том, что в его предусловии для действия Put On {Spare, Axle) (поместить запасное колесо на ось) используется отрицаемый предикат -iAt (Flat, Axle) (отрицание предиката At {Flat, Axle) — на оси находится колесо со стертой покрышкой). Необходимости в этом можно избежать, применяя вместо него предикат Clear {Axle) (отсутствие колеса на оси), как будет показано в следующем примере.
Листинг 11.2. Простая задача с запасным колесом
Init(At{Flat,Axle) A At(Spare, Trunk)) Goal(At(Spare,Axle))
Action(Remove(Spare,Trunk),
Precond: At(Spare,Trunk)
Effect: -nAt (Spare, Trunk) A At (Spare, Ground) ) Action(Remove(Flat, Axle) ,
Precond: At(Flat,Axle)
Effect: -At(Flat,Axle) л At(Flat,Ground)) Action(PutOn(Spare, Axle),
Precond: At (Spare, Ground) л -iAt (Flat, Axle)
Effect: —At (Spare, Ground) л At (Spare, Axle) ) Action {LeaveOvernight, Precond:
Effect: -iAt (Spare, Ground) л -nAt (Spare, Axle) л —At (Spare, Trunk) A —iAt {Flat, Ground) л —At {Flat, Axle) )
Пример: мир блоков
Одна из наиболее широко известных проблемных областей планирования известна под названием мира блоков. Эта проблемная область состоит из множества блоков кубической формы, находящихся на столе3. Блоки можно укладывать в столбик, но на верхней поверхности одного блока может быть непосредственно размещен только еще один блок. Робот может брать манипулятором блок и перемещать его в другую позицию — либо на стол, либо на верхнюю поверхность другого блока. С помощью манипулятора может быть взят одновременно только один блок, поэтому невозможно взять блок, на котором стоит еще один блок. Цель всегда заключается в том, что должны быть построены один или несколько столбиков из блоков, а сами задачи формулируются в терминах того, какие блоки находятся над указанными другими блоками. Например, задача может состоять в том, чтобы поставить блок А на В и блок С на D.
Для указания на то, что блок Ь находится на блоке х, где х— либо другой блок, либо стол, используется предикат On (b, х). Для перемещения блока Ь с верхней поверхности блока х на верхнюю поверхность блока у применяется действие Move(b,х,у). Итак, одним из предусловий перемещения Ьявляется то, что на нем не стоит какой-то другой блок. В логике первого порядка оно может быть представлено с помощью выражения -Зх Оп{х,Ь) или альтернативного выражения Vx —Юп{х,Ь). Эти выражения могут быть сформулированы как предусловия на языке ADL. Но мы могли бы оставаться в рамках языка Strips, введя новый предикат, Clear (х), который является истинным, если на блоке х ничего нет (верхняя поверхность блока х свободна).
Действие Move позволяет переместить блок Ь с блока х на блок у, если свободны верхние поверхности и блока Ь, и блока у. После выполнения этого действия верхняя поверхность блока х свободна, а блока у — нет. Формальное описание действия Move в языке Strips состоит в следующем:
Action {Move {b, х, у) , Precond: On{b,x) A Clear{b) A Clear{y) , Effect: On{b,y) A Clear{x) А -лОп(Ь,х) А -nClear(y) )
К сожалению, в этом действии предикат Clear не сопровождается должным образом, если блок х или блок у находится на столе. Если х= Table, то результатом этого действия будет Clear {Table), но поверхность стола не должна становиться свободной (поскольку она и так всегда свободна), а если у= Table, то действие имеет предусловие Clear (Table), но вся поверхность стола не обязана быть свободной для того, чтобы на нее можно было поместить блок (поскольку на столе всегда и без того достаточно места). Для исправления такого положения необходимо предусмотреть два изменения. Во-первых, введем еще одно действие для перемещения блока Ь с блока х на стол:
Action {MoveToTable (b, х) , Precond: Оп(Ь,х) л Clear(b)), Effect: On(b, Table) л Clear{x) л -лОп(Ь,х))
Во-вторых, примем интерпретацию предиката Clear (b) как означающую, что "на Ь есть достаточно свободного места, чтобы поместился один блок". При этой интерпретации предикат Clear {Table) всегда будет истинным. Единственная проблема состоит в том, что ничто не будет препятствовать планировщику использовать действие Move(b, х, Table) вместо действия MoveToTable (b, х). Можно смириться с этой проблемой (она приводит к созданию пространства поиска с размерами больше необходимого, но не становится причиной получения неправильных ответов) или ввести в предусловие Move предикат Block и добавить в предусловие действия Move выражение Block(b) л Block{y).
Наконец, существует проблема фиктивных действий, таких как Move (В, С, С), которые должны представлять собой пустую операцию, но имеют противоречивые результаты. Обычно принято игнорировать подобные проблемы, поскольку они редко вызывают выработку неверных планов. Правильный подход состоит в добавлении предусловий в неравенство, как показано в листинге 11.3.
Листинг 11.3. Задача планирования в мире блоков: построение столбика из трех блоков. Одним из решений является последовательность действий [Move {В, Table, С), Move (A, Table, в) ]
Init{On{A, Table) л Оп{В, Table) л Оп{С, Table)
л В1оск{А) л Block(B) А В1оск{С)
A Clear(A) A Clear(B) А С1еаг{С)) Goal(On{А,В) А Оп{В, С)) Action{Move{b, х, у) ,
Precond: On(b,x) A Clear(b) A Clear{у) A Block(b) А (b Ф х) А (Ь Ф у) А (х Ф у) ,
Effect: On{b,y) A Clear(x) A -iOn(b,x) л -iClear(y) ) Action (MoveToTable (b, x) ,
Precond: On(b,x) л Clear(b) A Block(b) л (b Ф x) ,
Effect: On(b,Table) л Clear(x) л -iOn(b,x))