Автоматизированное планирование и планирование , иногда называемое просто планированием ИИ , [1] — это отрасль искусственного интеллекта , которая касается реализации стратегий или последовательностей действий, обычно для выполнения интеллектуальными агентами , автономными роботами и беспилотными транспортными средствами . В отличие от классических задач управления и классификации , решения сложны и должны быть найдены и оптимизированы в многомерном пространстве. Планирование также связано с теорией принятия решений .
В известных средах с доступными моделями планирование можно выполнять в автономном режиме. Решения можно найти и оценить до их реализации. В динамически неизвестных средах стратегию часто необходимо пересматривать в режиме онлайн. Модели и политику необходимо адаптировать. Решения обычно прибегают к итеративным процессам проб и ошибок, обычно наблюдаемым в искусственном интеллекте . К ним относятся динамическое программирование , обучение с подкреплением и комбинаторная оптимизация . Языки, используемые для описания планирования и составления графиков, часто называют языками действий .
Учитывая описание возможных начальных состояний мира, описание желаемых целей и описание набора возможных действий, задача планирования состоит в синтезе плана, который гарантированно (при применении к любому из начальных состояний) генерировать состояние, содержащее желаемые цели (такое состояние называется целевым состоянием).
Сложность планирования зависит от используемых упрощающих допущений. Можно выделить несколько классов задач планирования в зависимости от свойств, которыми проблемы обладают в нескольких измерениях.
Простейшая возможная задача планирования, известная как классическая задача планирования, определяется:
Поскольку исходное состояние известно однозначно, а все действия детерминированы, состояние мира после любой последовательности действий можно точно предсказать, и вопрос наблюдаемости неактуален для классического планирования.
Кроме того, планы можно определить как последовательность действий, поскольку заранее всегда известно, какие действия потребуются.
В случае недетерминированных действий или других событий, находящихся вне контроля агента, возможные выполнения образуют дерево, и планы должны определять соответствующие действия для каждого узла дерева.
Марковские процессы принятия решений в дискретном времени (MDP) решают проблемы планирования с:
Когда полная наблюдаемость заменяется частичной наблюдаемостью, планирование соответствует частично наблюдаемому марковскому процессу принятия решений (POMDP).
Если агентов более одного, мы имеем мультиагентное планирование , которое тесно связано с теорией игр .
При планировании ИИ планировщики обычно вводят модель предметной области (описание набора возможных действий, моделирующих предметную область), а также конкретную проблему, которую необходимо решить, заданную начальным состоянием и целью, в отличие от тех, в которых нет указан входной домен. Такие планировщики называются «независимыми от предметной области», чтобы подчеркнуть тот факт, что они могут решать проблемы планирования из широкого спектра областей. Типичными примерами областей являются укладка блоков, логистика, управление рабочими процессами и планирование задач роботов. Следовательно, для решения проблем планирования во всех этих различных областях можно использовать единый независимый от предметной области планировщик. С другой стороны, планировщик маршрутов типичен для планировщика, специфичного для конкретной области.
Наиболее часто используемые языки для представления областей планирования и конкретных задач планирования, такие как STRIPS и PDDL для классического планирования, основаны на переменных состояния. Каждое возможное состояние мира представляет собой присвоение значений переменным состояния, а действия определяют, как изменяются значения переменных состояния при выполнении этого действия. Поскольку набор переменных состояния создает пространство состояний, размер которого является экспоненциальным в наборе, планирование, как и многие другие вычислительные задачи, страдает от проклятия размерности и комбинаторного взрыва .
Альтернативным языком описания задач планирования являются иерархические сети задач , в которых задан набор задач, и каждая задача может быть либо реализована с помощью примитивного действия, либо разложена на набор других задач. Это не обязательно связано с переменными состояния, хотя в более реалистичных приложениях переменные состояния упрощают описание сетей задач.
Временное планирование можно решить методами, аналогичными классическому планированию. Основное отличие состоит в том, что из-за возможности одновременного выполнения нескольких перекрывающихся во времени действий с продолжительностью определение состояния должно включать информацию о текущем абсолютном времени и о том, как далеко продолжалось выполнение каждого активного действия. Кроме того, при планировании с рациональным или реальным временем пространство состояний может быть бесконечным, в отличие от классического планирования или планирования с целочисленным временем. Временное планирование тесно связано с проблемами планирования , когда присутствует неопределенность, и его также можно понимать с точки зрения синхронизированных автоматов . Простая временная сеть с неопределенностью (STNU) — это задача планирования, которая включает в себя контролируемые действия, неопределенные события и временные ограничения. Динамическая управляемость для таких задач — это тип планирования, который требует стратегии временного планирования для реактивной активации управляемых действий по мере наблюдения неопределенных событий, чтобы гарантировать выполнение всех ограничений. [2]
Вероятностное планирование может быть решено с помощью итеративных методов, таких как итерация значений и итерация политики , когда пространство состояний достаточно мало. При частичной наблюдаемости вероятностное планирование решается аналогичным образом итерационными методами, но с использованием представления функций ценности, определенных для пространства убеждений, а не состояний.
При планировании на основе предпочтений цель состоит не только в составлении плана, но и в удовлетворении предпочтений, указанных пользователем . В отличие от более распространенного планирования, основанного на вознаграждении, например, соответствующего MDP, предпочтения не обязательно имеют точное числовое значение.
Детерминистическое планирование было введено в систему планирования STRIPS , которая представляет собой иерархический планировщик. Названия действий упорядочены в последовательности и это план робота. Иерархическое планирование можно сравнить с автоматически создаваемым деревом поведения . [3] Недостаток заключается в том, что обычное дерево поведения не так выразительно, как компьютерная программа. Это означает, что нотация графа поведения содержит команды действий, но не содержит циклов или операторов if-then. Условное планирование устраняет узкое место и вводит сложную систему обозначений, аналогичную потоку управления , известную из других языков программирования, таких как Паскаль . Это очень похоже на синтез программ , что означает, что планировщик генерирует исходный код, который может быть выполнен интерпретатором. [4]
Ранним примером условного планировщика является Warplan-C, представленный в середине 1970-х годов. [5] В чем разница между обычной последовательностью и сложным планом, содержащим операторы «если-то»? Это связано с неопределенностью во время выполнения плана. Идея состоит в том, что план может реагировать на сигналы датчиков , неизвестные планировщику. Планировщик заранее генерирует два варианта выбора. Например, если объект был обнаружен, то выполняется действие А, если объект отсутствует, то выполняется действие Б. [6] Основным преимуществом условного планирования является возможность обработки частичных планов . [7] Агент не обязан планировать все от начала до конца, он может разделить проблему на части . Это помогает уменьшить пространство состояний и решает гораздо более сложные проблемы.
Мы говорим о «планировании на случай обстоятельств», когда окружающую среду можно наблюдать с помощью датчиков, которые могут быть неисправными. Таким образом, это ситуация, когда агент планирования действует на основе неполной информации. Для задачи условного планирования план больше не является последовательностью действий, а деревом решений , поскольку каждый шаг плана представлен набором состояний, а не одним совершенно наблюдаемым состоянием, как в случае классического планирования. [8] Выбранные действия зависят от состояния системы. Например, если идет дождь, агент решает взять зонтик, а если нет, то он может не брать его.
Майкл Л. Литтман показал в 1998 году, что при ветвлении действий задача планирования становится EXPTIME -завершенной. [9] [10] Частный случай непрерывного планирования представлен задачами FOND - для «полностью наблюдаемых и недетерминированных». Если цель указана в LTLf (логика линейного времени на конечной трассе), то проблема всегда является EXPTIME-завершенной [11] и 2EXPTIME-завершенной, если цель указана с помощью LDLf.
Согласованное планирование — это когда агент не уверен в состоянии системы и не может делать никаких наблюдений. Тогда у агента есть убеждения о реальном мире, но он не может проверить их, например, с помощью ощущений. Эти проблемы решаются методами, аналогичными методам классического планирования, [12] [13] , но где пространство состояний является экспоненциальным по размеру проблемы из-за неопределенности относительно текущего состояния. Решение задачи согласованного планирования — это последовательность действий. Хаслум и Йонссон продемонстрировали, что проблема согласованного планирования является EXPSPACE -полной, [14] и 2EXPTIME-полной, когда исходная ситуация неопределенна и имеется недетерминизм в результатах действий. [10]
{{cite journal}}: CS1 maint: multiple names: authors list (link){{cite conference}}: CS1 maint: multiple names: authors list (link){{cite conference}}: CS1 maint: multiple names: authors list (link)конференция: Последние достижения в планировании искусственного интеллекта