Автоматизированное планирование
Автоматизированное планирование — это раздел искусственного интеллекта, занимающийся вычислением последовательностей действий, которые преобразуют начальное состояние мира в желаемое целевое состояние, при наличии формального описания доступных действий.
Definition
Автоматизированное планирование — это вычисление плана (упорядоченного или частично упорядоченного набора действий), который доказуемо достигает цели из начального состояния, при наличии модели того, как каждое действие изменяет состояние мира.
Scope
Эта область охватывает представление задач планирования (состояния, действия с предусловиями и эффектами, цели) и алгоритмы их решения: классическое планирование в детерминированных, полностью наблюдаемых доменах, методы графов планирования и эвристического поиска, планирование иерархических сетей задач, а также расширение на время, ресурсы и расписание. Она рассматривает стандартные формализмы, такие как STRIPS и PDDL, и сложность планирования. Планирование в условиях вероятностной неопределенности связано с рассуждениями в условиях неопределенности, а обучение моделям действий или стратегиям на основе данных относится к подобласти машинного обучения.
Sub-topics
Core questions
- Как действия, состояния и цели представляются достаточно компактно, чтобы описывать большие домены?
- Как эффективно осуществляется поиск решения задачи планирования, несмотря на экспоненциально большое пространство состояний?
- Как автоматически выводятся допустимые и информативные эвристики из описания домена?
- Как планы могут быть структурированы иерархически, и как учитываются временные и ресурсные ограничения?
Key concepts
- состояния, действия, цели
- предусловия и эффекты
- STRIPS и PDDL
- прямой и обратный поиск в пространстве состояний
- графы планирования
- доменно-независимые эвристики
- иерархические сети задач
- временное планирование и расписание
Key theories
- Представление действий STRIPS
- Формализм STRIPS описывает действия с помощью предусловий и эффектов добавления/удаления над набором пропозиций, предоставляя компактное, факторизованное представление, которое делает планирование поиском по символическим состояниям, а не перечислением явных состояний мира.
- Доменно-независимый эвристический поиск для планирования
- Современные планировщики рассматривают планирование как эвристический поиск и автоматически выводят эвристики из описания задачи, например, игнорируя эффекты удаления или используя причинно-следственную структуру, что обеспечивает высокую общую производительность.
- Планирование как иерархия классов задач
- Планирование охватывает спектр от классического детерминированного планирования до иерархических, временных и ресурсно-ограниченных вариантов, каждый из которых имеет характерные представления и сложность, организованные в стандартной теории автоматизированного планирования.
Clinical relevance
Автоматизированное планирование применяется в робототехнике и автономных системах, космических аппаратах и операциях миссий, логистике и цепочках поставок, производстве, а также в генерации игр и повествований; планировщики, разработанные на основе этих методов, управляли реальными автономными космическими аппаратами и координировали сложные рабочие процессы.
History
Автоматизированное планирование началось с STRIPS для робота Shakey в SRI примерно в 1971 году, представляя планирование как доказательство теорем на основе описаний действий. Область развивалась через планирование с частичным порядком, прорыв Graphplan (1995) и появление быстрых доменно-независимых планировщиков на основе эвристического поиска и стандарта PDDL с конца 1990-х годов, что отслеживалось через Международные соревнования по планированию.
Key figures
- Richard E. Fikes
- Nils J. Nilsson
- Malik Ghallab
- Dana Nau
- Paolo Traverso
- Malte Helmert
Related topics
Seminal works
- fikes1971
- ghallab2004
- helmert2006
Frequently asked questions
- Чем автоматизированное планирование отличается от общего поиска?
- Автоматизированное планирование является формой поиска, но оно работает с декларативным, факторизованным описанием действий (предусловия и эффекты), а не с непрозрачной функцией преемника. Эта структура позволяет планировщикам автоматически выводить эвристики и рассуждать о том, какие действия релевантны, чего не может сделать общий поиск.
- Что такое PDDL?
- PDDL, язык описания доменов планирования (Planning Domain Definition Language), является стандартным языком для описания доменов и задач планирования — объектов, предикатов, действий, начального состояния и цели. Он позволяет сравнивать доменно-независимые планировщики на общем эталоне, как это делается в Международных соревнованиях по планированию.