Ниже приведен перевод статьи "Planning" из энциклопедии "The MIT Enciclopedia of the Cognitive Science" 1999 года издания под редакцией Роберта Вилсона (Robert A. Wilson) и Фрэнка Кайла (Frank C. Keil). Статья для энциклопедии написана Остином Тэйтом (Austin Tate).
Планирование - это процесс генерации (возможно частичных) представлений о будущем поведении до того, как полученные таким образом планы будут использованы для реализации этого поведения. Результатом планирования обычно является некоторое множество действий, а также наложенные на них временные и другие ограничения, и предполагается, что эти действия будут исполняться каким-либо агентом или агентами. Будучи ключевым аспектом человеческого интеллекта, исследования в области планирования начались еще в момент становления искусственного интеллекта и наук о мышлении (cognitive science). Исследования в области планирования способствовали созданию множества полезных инструментов для прикладных программ, а также помогли глубже понять организацию поведения и природу рассуждений о действиях.
Ранние работы в области наук о мышлении были направлены на создание универсальных, независимых от предметной области решателей задач, которые демонстрировали наличие некоторых характерных черт, наблюдаемых у людей при решении задач. Наибольшую известность среди систем такого рода получил Универсальный решатель задач (GPS), представленный в 1959 году (Newell and Simon, 1963). В нем были предложены технологии, используемые и по сей день: анализ средств и целей (means-ends analysis) или целеориентированное решение задач (goal directed problem solving), а также нахождение различий между целью и текущим состоянием.
Эта работа сочетала в себе поисковые методы (например, метод ветвей и границ), изучаемыми такой научной дисциплиной как исследование операций (operational research), и различные методы доказательства теорем, предлагаемые исследованиями в области представления знаний и выполнения рассуждений посредством логики предикатов (например, Green, 1969). Таким образом, в конце 60-х появилось несколько методов, которые долгое время использовались в дальнейшем.
В 1969 был создан Решатель задач Стэнфордского исследовательского института (STRIPS) (Fikes, Hart, and Nilsson, 1971). В этой системе было предложено представлять состояния модели предметной области при помощи логики предикатов первого порядка; предложен способ представления действий в терминах изменений, вносимых в состояние мира; был использован анализ средств и целей для определения целей и подцелей, которые должны быть достигнуты, как промежуточные шаги решения; был применен поиск в пространстве возможных решений; и было использовано простое, но эффективное представление действий, допустимых в данной предметной области - в форме STRIPS-операторов. Многие из этих технологий сформировали основу для дальнейших работ в области планирования.
Многие методы планирования рассматривают проблему планирования как задачу поиска. Ранние методы планирования, включая STRIPS, использовали поисковый метод, в котором вершины пространства поиска (графа поиска) представляли непосредственно состояния модели мира, а дуги в пространстве поиска представляли действия, которые могли преобразовывать (transform) эти состояния. Это поисковое пространство обозначается термином "пространство состояний" или "пространство ситуаций". Например, вершина-состояние может описывать расположение робота-официанта и предметов на столах:
At( Robot, Counter ) and On( Cup-a, Table-1 ) and On( Plate-a, Table-1),
а дуга-действие может описывать перемещение робота-официанта или действие "взять предмет":
Operator Pickup(x)
Preconditions: On(x,y) and At(Robot, y)
Delete list: On(x,y)
Add list: Held(x)
STRIPS-операторы предполагают, что всякое действие имеет предусловие, которое должно удовлетворяться в состоянии, в котором действие выполняется, список удалений и список добавлений, которые описывают эффект, представляющий изменение состояния, являющееся следствием применения действия.
Более поздние методы сосредотачиваются на поиске в другом пространстве - пространстве частично определенных планов. Вершиной такого поискового пространства является частичный план, а дугой - оператор модификации частичного плана (partial plan modification operator - PMO). Например, PMO может гарантировать достижение некоторого условия определенным действием в частичном плане. Каждая вершина в пространстве поиска определяет целое множество возможных уточнений плана, которые соответствуют ограничениям в частичном плане. Следовательно, этот метод может опираться на "наложение ограничений" или "слабое связывание при планировании", когда вместо случайного (но немедленного) выбора пути поиска принятие решения (о выборе пути поиска) откладывается (насколько это возможно).
В рамках этого подхода возможна интеграция мощных методов управления ограничениями и методов планирования (например, так, как это сделано в MOLGEN (Stefik, 1981) для ограничения на объекты, или в Deviser (Vere, 1981) и FORBIN (Dean, Firby, and Miller, 1990) для временных ограничений, или в SIPE (Wilkins, 1988) для ограничений на ресурсы). Это значит, что методы планирования и составления расписаний можно смешивать (см. TEMPORAL REASONING).
Поисковые пространства частичных планов используются в подходе, называемом "уточняющее планирование" (Kambhampati, Knoblock, and Yang, 1996), где приблизительный план уточняется путем устранения еще не разрешенных недостатков (flaw) или проблем. Однако они также подходят для уточнения существующих частичных описаний решения проблемы, для конкретизации ранее полученных обобщенных планов или адаптации планов, взятых из библиотеки прецедентов (см. CASE-BASED REASONING AND ANALOGY).
В середине 80-ых появились NOAH (Net of Action Hierarchies) (Sacerdoti, 1977), а затем "Nonlin" (nonlinear planner) (Tate, 1977) - системы, которые допускали представление планов в виде набора частично упорядоченных действий в противовес требованию полного (total) упорядочения действий. (К сожалению, терминология того времени привела к тому, что частично упорядоченные планы стали называть "нелинейными", что стало причиной неразберихи с "линейными" и "нелинейными" подходами к планированию, различаемых на самом деле по критерию значимости или незначимости порядка достижения целей и подцелей.) Некоторые задачи, которые вызывали затруднение у ранних планировщиков, таких как STRIPS, легко решались при использовании частично упорядоченного представления планов, но стало сложнее гарантировать, что условия действий удовлетворяются эффектами действий, расположенных ранее в плане. В корректном плане должно разрешаться потенциальное взаимовлияние параллельных действий. В планировщик должны быть добавлены средства "защиты" достигнутого условия (такие, как представленные в системе HACKER; Sussman, 1975). Процедура ответов на вопросы планировщика "Nonlin" (Tate, 1977) включала средства для определения, было ли определенное условие уже достигнуто в данной точке частично упорядоченной сети действий, и, если необходимо, могла предложить упорядочивающие ограничения (на действия), которые будучи добавленными в план, удовлетворяли бы эти условия. Она являлась источником информации, которая могла использоваться для защиты (сохранения) причинно-следственной структуры плана (называемой также "структурой целей" или "телеологией"). В дальнейшем эта работа легла в основу формализации "критерия модальной истинности" (Chapman, 1991), ставшего ядром ряда появившихся позднее планировщиков и использовавшегося для достижения и защиты условий.
Алгоритмы частично упорядоченного планирования (partially ordered planning - POP) являются основой ряда современных планировщиков, таких как SIPE (Wilkins, 1988), O-Plan (Currie and Tate, 1991) и UCPOP (Penberthy and Weld, 1992).
Важной методологией, способной в ряде предметных областей уменьшить сложность задачи планирования и значительно увеличить длину планов, которые можно породить, является иерархическая организация описаний действий. Большинство практических планировщиков используют методы "иерархического планирования". Библиотека описаний действий поддерживается в такой форме, что ряд действий могут быть подвергнуты декомпозиции на несколько более детализированных поддействий, а ряд действий считаются "примитивными". Например, в предметной области с роботом-официантом высокоуровневое действие "Cleartable" (очистить стол) может быть разложено на примитивные поддействия "подойти к столу", "взять предмет", "подойти к служебному столу" и "положить предмет, который робот держит в своей руке". Всякое высокоуровневое действие в плане может быть заменено некоторой подходящей декомпозицией на более детализированные действия. На такой подход иногда ссылаются как на HTN-планирование (Hierarchical Task Network).
HTN-планирование укладывается в модель уточняющего планирования. Начальный план может включать постановку (спецификацию) задачи, описание ситуации, в которой план будет исполняться и, возможно, частичное решение. Этот план в дальнейшем может уточняться приобретая большую детализацию (по мере движения по уровням детализации иерархии), а кроме этого, уточняться путем устранения недостатков (flaw) и проблем.
С течением времени ученые и инженеры в области планирования дополнили STRIPS-представление действий многими дополнительными особенностями. Они включают:
Выразительность способа представления действий планировщиком играет важную роль в обеспечении эффективности систем планирования, но может также привести к очень большим пространствам поиска, если не обратить на это внимание (см. COMPUTATIONAL COMPLEXY).
В настоящее время технологии инженерии знаний и приобретения знаний стали использоваться для улучшения качества модели (мира) и приобретения знаний о предметной области. Подобно опыту в системах основанных на знаниях (KNOWLEDGE-BASED SYSTEMS), использование богатых моделей предметной области оказалось выгодным, например, для сокращения пространства поиска или направления (guidance) алгоритма поиска.
В планировании, как области исследований, в последнее время появилось много новых направлений, чтобы включить широкий спектр вопросов связанных с рассуждениями о действиях. Одной из важных областей исследования является планирование действий в среде, где результат действий точно не известен (uncertain). Например, действие Pickup (взять предмет) робота-официанта может не привести к описываемому эффекту, если объект слишком тяжелый. Некоторые методы, используемые в "классическом" интеллектуальном планировании, полагают, что информация об результате выполнения действия абсолютна "точна". Однако очень важным является также умение справляться с неопределенностью в процессе планирования или исполнения плана.
В план могут включаться альтернативные пути действий, используемые при определенных условиях, или когда возникает непредвиденная ситуация, для описания всех наиболее вероятных сценариев. Методы "реактивного планирования" могут использоваться для выбора действий в процессе исполнения плана, основываясь на ситуации, в которую система попала. Неопределенность может также разрешаться обычными алгоритмами для решения задачи планирования, основанными на использовании марковского процесса (Dean et al., 1995, см. также MULTIAGENT SYSTEMS).
Книга Readings in Planning (Allen, Hendler, and Tate, 1990) объединяет ряд основополагающих статей, которые описывают основные достижения в области планирования. Она представляет собой историческую ретроспективу работ, проделанных в этой области. Отдельные обзоры в этой книге служат в качестве введения для начала исследований в области планирования.
См. также KNOWLEDGE REPRESENTATION; ROBOTICS; PROBLEM SOLVING; INTELLIGENT AGENT ARCHITECTURE.
— Austin Tate
На русский язык статью перевел Трофимов И.В.
август 2005 г