Графы планирования и эвристики

Графы планирования и доменно-независимые эвристики — это методы, которые ускорили классическое планирование за счет компактного анализа достижимости и автоматической оценки расстояния от состояния до цели.

Definition

Граф планирования — это многоуровневая структура, которая чередует уровни пропозиций и действий с ограничениями mutex для аппроксимации достижимости; эвристики планирования — это функции, часто вычисляемые на основе таких структур или из задач с ослабленными эффектами удаления, которые оценивают стоимость достижения цели из данного состояния.

Scope

Эта тема охватывает структуру данных графа планирования, представленную Graphplan, включая уровни пропозиций и действий, а также отношения взаимоисключения (mutex), которые определяют, какие факты и действия не могут сосуществовать, и семейство доменно-независимых эвристик, полученных из ослабленных задач (в частности, игнорирующих эффекты удаления), которые управляют современными планировщиками эвристического поиска. В ней рассматривается, как информация о достижимости вычисляется и используется для направления поиска. Базовая модель классического планирования рассматривается в соответствующей теме.

Core questions

• Как граф планирования представляет достижимые пропозиции и действия уровень за уровнем?
• Что такое отношения mutex и как они отражают несовместимость между фактами и действиями?
• Как ослабление удаления используется для получения допустимых или информативных эвристик планирования?
• Как эти эвристики превращают планирование в эффективный эвристический поиск?

Key concepts

• граф планирования
• уровни пропозиций и действий
• взаимоисключение (mutex)
• Graphplan
• ослабление удаления
• эвристики h-max и h-add
• эвристика FF и ослабленные планы
• эвристический прямой поиск

Key theories

Граф планирования и Graphplan

Graphplan строит граф планирования, который компактно кодирует, какие пропозиции и действия достижимы на каждом уровне и какие пары являются взаимоисключающими, а затем извлекает план, осуществляя обратный поиск по этой структуре, что значительно ускоряет планирование.

Эвристики ослабления удаления

Игнорирование эффектов удаления действий приводит к ослабленной задаче планирования, которую гораздо легче решить; стоимость решения этого ослабления обеспечивает информативные, часто допустимые эвристики (такие как h-max и h-add и эвристика FF), которые направляют прямой поиск.

Эвристическое планирование с поиском

Современные классические планировщики сочетают автоматически выведенные эвристики с поиском по принципу «лучший первый» или жадным поиском и такими улучшениями, как предпочтительные операторы, достигая высокой общей производительности в различных областях.

Clinical relevance

Графы планирования и эвристики ослабления удаления являются основной технологией планировщиков-победителей соревнований, используемых в робототехнике, логистике и автономном управлении, где они позволяют доменно-независимым планировщикам быстро решать большие задачи без ручного создания руководства по поиску.

History

Graphplan Блюма и Фёрста (1995, журнальная версия 1997) представил граф планирования и произвел революцию в скорости планирования. Конец 1990-х и 2000-е годы ознаменовались появлением эвристик ослабления удаления, при этом планировщик FF (Хоффманн и Небель, 2001) и позднее Fast Downward (Хелмерт, 2006) утвердили эвристический прямой поиск как доминирующий подход.

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

Что такое mutex в графе планирования?

Mutex (взаимоисключение) — это отношение, которое отмечает две пропозиции или два действия, которые не могут одновременно выполняться или применяться на одном уровне, например, потому что одно действие удаляет предусловие другого. Mutex-ы делают граф планирования более точной аппроксимацией истинной достижимости.

Почему игнорирование эффектов удаления дает полезную эвристику?

Без эффектов удаления достижение одной цели никогда не отменяет другую, поэтому ослабленную задачу гораздо легче решить, и она никогда не бывает сложнее исходной. Стоимость ослабленного плана, следовательно, является нижней границей или информированной оценкой реальной стоимости, что делает ее эффективной эвристикой для направления поиска.