Автоматизированное планирование и составление расписаний , иногда обозначаемое просто как планирование ИИ , [1] является разделом искусственного интеллекта , который касается реализации стратегий или последовательностей действий, обычно для выполнения интеллектуальными агентами , автономными роботами и беспилотными транспортными средствами . В отличие от классических задач управления и классификации , решения являются сложными и должны быть обнаружены и оптимизированы в многомерном пространстве. Планирование также связано с теорией принятия решений .
В известных средах с доступными моделями планирование может осуществляться в автономном режиме. Решения могут быть найдены и оценены до выполнения. В динамически неизвестных средах стратегия часто должна быть пересмотрена в режиме онлайн. Модели и политики должны быть адаптированы. Решения обычно прибегают к итеративным процессам проб и ошибок, которые обычно наблюдаются в искусственном интеллекте . К ним относятся динамическое программирование , обучение с подкреплением и комбинаторная оптимизация . Языки, используемые для описания планирования и составления расписаний, часто называются языками действий .
При наличии описания возможных начальных состояний мира, описания желаемых целей и описания набора возможных действий задача планирования состоит в синтезе плана, который гарантированно (при применении к любому из начальных состояний) создаст состояние, содержащее желаемые цели (такое состояние называется целевым состоянием).
Трудность планирования зависит от используемых упрощающих предположений. Можно выделить несколько классов проблем планирования в зависимости от свойств, которые проблемы имеют в нескольких измерениях.
Простейшая возможная задача планирования, известная как классическая задача планирования, определяется следующим образом:
Поскольку начальное состояние известно однозначно, а все действия детерминированы, состояние мира после любой последовательности действий может быть точно предсказано, и вопрос наблюдаемости не имеет значения для классического планирования.
Кроме того, планы можно определить как последовательность действий, поскольку всегда заранее известно, какие действия потребуются.
При недетерминированных действиях или других событиях, находящихся вне контроля агента, возможные исполнения образуют дерево, и планы должны определять соответствующие действия для каждого узла дерева.
Дискретные по времени марковские процессы принятия решений (MDP) решают задачи планирования с:
Когда полная наблюдаемость заменяется частичной наблюдаемостью, планирование соответствует частично наблюдаемому марковскому процессу принятия решений (POMDP).
Если имеется более одного агента, мы имеем многоагентное планирование , которое тесно связано с теорией игр .
При планировании ИИ планировщики обычно вводят модель домена (описание набора возможных действий, которые моделируют домен), а также конкретную проблему, которую необходимо решить, указанную начальным состоянием и целью, в отличие от тех, в которых не указан домен ввода. Такие планировщики называются «независимыми от домена», чтобы подчеркнуть тот факт, что они могут решать задачи планирования из широкого спектра доменов. Типичными примерами доменов являются укладка блоков, логистика, управление рабочим процессом и планирование задач роботов. Следовательно, один независимый от домена планировщик может использоваться для решения задач планирования во всех этих различных доменах. С другой стороны, планировщик маршрута является типичным для планировщика, специфичного для домена.
Наиболее часто используемые языки для представления областей планирования и конкретных задач планирования, такие как STRIPS и PDDL для классического планирования, основаны на переменных состояния. Каждое возможное состояние мира представляет собой присвоение значений переменным состояния, а действия определяют, как изменяются значения переменных состояния при выполнении этого действия. Поскольку набор переменных состояния индуцирует пространство состояний, размер которого экспоненциален в наборе, планирование, подобно многим другим вычислительным задачам, страдает от проклятия размерности и комбинаторного взрыва .
Альтернативным языком описания задач планирования является язык иерархических сетей задач , в котором задан набор задач, и каждая задача может быть либо реализована примитивным действием, либо разложена на набор других задач. Это не обязательно включает переменные состояния, хотя в более реалистичных приложениях переменные состояния упрощают описание сетей задач.
Временное планирование может быть решено с помощью методов, похожих на классическое планирование. Главное отличие состоит в том, что из-за возможности нескольких временно перекрывающихся действий с продолжительностью, выполняемых одновременно, определение состояния должно включать информацию о текущем абсолютном времени и о том, насколько далеко продвинулось выполнение каждого активного действия. Кроме того, при планировании с рациональным или реальным временем пространство состояний может быть бесконечным, в отличие от классического планирования или планирования с целочисленным временем. Временное планирование тесно связано с задачами планирования , когда присутствует неопределенность, и также может быть понято в терминах синхронизированных автоматов . Простая временная сеть с неопределенностью (STNU) — это задача планирования, которая включает в себя контролируемые действия, неопределенные события и временные ограничения. Динамическая управляемость для таких задач — это тип планирования, который требует стратегии временного планирования для активации контролируемых действий реактивно по мере наблюдения неопределенных событий, чтобы все ограничения были гарантированно удовлетворены. [2]
Вероятностное планирование может быть решено с помощью итеративных методов, таких как итерация значений и итерация политик , когда пространство состояний достаточно мало. При частичной наблюдаемости вероятностное планирование аналогичным образом решается с помощью итеративных методов, но с использованием представления функций значений, определенных для пространства убеждений вместо состояний.
В планировании на основе предпочтений целью является не только создание плана, но и удовлетворение предпочтений, указанных пользователем . В отличие от более распространенного планирования на основе вознаграждения, например, соответствующего MDP, предпочтения не обязательно имеют точное числовое значение.
Детерминированное планирование было введено с системой планирования STRIPS , которая является иерархическим планировщиком. Имена действий упорядочены в последовательности, и это план для робота. Иерархическое планирование можно сравнить с автоматически сгенерированным деревом поведения . [3] Недостатком является то, что обычное дерево поведения не так выразительно, как компьютерная программа. Это означает, что нотация графа поведения содержит команды действий, но не циклы или операторы if-then-. Условное планирование преодолевает узкое место и вводит сложную нотацию, которая похожа на поток управления , известный из других языков программирования, таких как Pascal . Это очень похоже на синтез программы , что означает, что планировщик генерирует исходный код, который может быть выполнен интерпретатором. [4]
Ранним примером условного планировщика является «Warplan-C», который был представлен в середине 1970-х годов. [5] В чем разница между обычной последовательностью и сложным планом, который содержит операторы «если-тогда»? Это связано с неопределенностью во время выполнения плана. Идея заключается в том, что план может реагировать на сигналы датчиков , которые неизвестны планировщику. Планировщик заранее генерирует два варианта выбора. Например, если объект обнаружен, то выполняется действие A, если объект отсутствует, то выполняется действие B. [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)конференция: Последние достижения в планировании ИИ