Классическое планирование и STRIPS

Классическое планирование решает задачу поиска последовательности действий для достижения цели в детерминированной, полностью наблюдаемой, статической среде, используя факторизованное STRIPS-подобное представление действий посредством предусловий и эффектов.

Definition

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

Scope

Эта тема охватывает классическую модель планирования и ее допущения (детерминированные действия, полная наблюдаемость, один агент, атомарное время), представления состояний и действий STRIPS и ADL/PDDL, основные методы решения прямого (прогрессивного) и обратного (регрессивного) поиска в пространстве состояний и планирования с частичным порядком, а также вычислительную сложность пропозиционального планирования. Эвристическое управление и графы планирования рассматриваются в соответствующей теме, а недетерминированные или вероятностные варианты выходят за рамки данной темы.

Core questions

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

Key concepts

• детерминированная, полностью наблюдаемая модель
• предусловия и эффекты STRIPS
• списки добавления и удаления
• PDDL и ADL
• прогрессивный (прямой) поиск
• регрессивный (обратный) поиск
• планирование с частичным порядком
• сложность существования плана

Key theories

Представление STRIPS

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

Прогрессивный и регрессивный поиск

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

Сложность планирования

Решение вопроса о существовании пропозиционального STRIPS-плана является PSPACE-полным в общем случае, что формально объясняет, почему планирование является сложным, и мотивирует эвристические и структурные методы для его практического применения.

Clinical relevance

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

History

STRIPS был разработан в SRI около 1971 года для управления роботом Shakey, представив модель действия предусловие/эффект, которая определяет классическое планирование. Планирование с частичным порядком развивалось в 1970-80-х годах, Байландер установил PSPACE-полноту пропозиционального планирования в 1994 году, а стандарт PDDL позже унифицировал эталоны в этой области.

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Tom Bylander
• Earl D. Sacerdoti

Seminal works

• fikes1971
• bylander1994

Frequently asked questions

Каковы допущения классического планирования?

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

Что означают списки добавления и удаления STRIPS?

При применении действия STRIPS пропозиции в его списке добавления становятся истинными, а пропозиции в его списке удаления становятся ложными; все остальные пропозиции остаются неизменными. Это простое правило обновления делает STRIPS компактным и вычислительно удобным представлением того, как действия изменяют мир.