Автоматизированное планирование и составление графиков

Автоматизированное планирование и составление графиков , иногда называемое просто планированием с использованием ИИ . ^[1] — это отрасль искусственного интеллекта , которая занимается реализацией стратегий или последовательностей действий, обычно выполняемых интеллектуальными агентами , автономными роботами и беспилотными транспортными средствами . В отличие от классических задач управления и классификации , решения сложны и должны быть найдены и оптимизированы в многомерном пространстве. Планирование также связано с теорией принятия решений .

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

Обзор

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

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

Являются ли действия детерминированными или недетерминированными? Доступны ли соответствующие вероятности для недетерминированных действий?
Являются ли переменные состояния дискретными или непрерывными? Если они дискретны, имеют ли они лишь конечное число возможных значений?
Можно ли однозначно оценить нынешнее состояние? Наблюдаемость может быть полной и частичной.
Сколько существует начальных состояний: конечное или произвольное?
Есть ли у действий продолжительность?
Могут ли одновременно выполняться несколько действий или одновременно возможно только одно действие?
Целью плана является достижение заданного целевого состояния или максимизация функции вознаграждения ?
Агент только один или агентов несколько? Агенты готовы сотрудничать или эгоистичны? Все ли агенты составляют свои собственные планы отдельно или планы составляются централизованно для всех агентов?

Простейшая возможная задача планирования, известная как классическая задача планирования, определяется:

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

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

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

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

в дискретном времени Марковские процессы принятия решений (MDP) решают проблемы планирования с:

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

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

Если агентов более одного, мы имеем мультиагентное планирование , которое тесно связано с теорией игр .

Независимое от домена планирование

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

Планирование языков моделирования предметной области

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

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

Алгоритмы планирования

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

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

Сокращение к другим проблемам

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

Временное планирование

Временное планирование можно решить методами, аналогичными классическому планированию. Основное отличие состоит в том, что из-за возможности одновременного выполнения нескольких перекрывающихся во времени действий с продолжительностью определение состояния должно включать информацию о текущем абсолютном времени и о том, как далеко продолжалось выполнение каждого активного действия. Кроме того, при планировании с рациональным или реальным временем пространство состояний может быть бесконечным, в отличие от классического планирования или планирования с целочисленным временем. Временное планирование тесно связано с проблемами планирования , когда присутствует неопределенность, и его также можно понимать с точки зрения синхронизированных автоматов . Простая временная сеть с неопределенностью (STNU) — это задача планирования, которая включает в себя контролируемые действия, неопределенные события и временные ограничения. Динамическая управляемость для таких задач — это тип планирования, который требует стратегии временного планирования для реактивной активации управляемых действий по мере наблюдения неопределенных событий, чтобы гарантировать выполнение всех ограничений. ^[2]

Вероятностное планирование

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

Планирование на основе предпочтений

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

Условное планирование

Детерминистическое планирование было введено в систему планирования STRIPS , которая представляет собой иерархический планировщик. Названия действий упорядочены в последовательности и это план робота. Иерархическое планирование можно сравнить с автоматически создаваемым деревом поведения . ^[3] Недостаток в том, что обычное дерево поведения не так выразительно, как компьютерная программа. Это означает, что нотация графа поведения содержит команды действий, но не содержит циклов или операторов if-then. Условное планирование устраняет узкое место и вводит сложную систему обозначений, аналогичную потоку управления , известную из других языков программирования, таких как Паскаль . Это очень похоже на синтез программ , что означает, что планировщик генерирует исходный код, который может быть выполнен интерпретатором. ^[4]

Ранним примером условного планировщика является Warplan-C, представленный в середине 1970-х годов. ^[5] В чем разница между обычной последовательностью и сложным планом, содержащим операторы «если-то»? Это связано с неопределенностью во время выполнения плана. Идея состоит в том, что план может реагировать на сигналы датчиков , неизвестные планировщику. Планировщик заранее генерирует два варианта выбора. Например, если объект был обнаружен, то выполняется действие А, если объект отсутствует, то выполняется действие Б. ^[6] Главным преимуществом условного планирования является возможность обработки частичных планов . ^[7] Агент не обязан планировать все от начала до конца, он может разделить проблему на части . Это помогает уменьшить пространство состояний и решает гораздо более сложные проблемы.

Планирование на случай непредвиденных обстоятельств

Мы говорим о «планировании на случай обстоятельств», когда окружающую среду можно наблюдать с помощью датчиков, которые могут быть неисправными. Таким образом, это ситуация, когда агент планирования действует на основе неполной информации. Для задачи условного планирования план больше не является последовательностью действий, а является деревом решений , поскольку каждый шаг плана представлен набором состояний, а не одним совершенно наблюдаемым состоянием, как в случае классического планирования. ^[8] Выбранные действия зависят от состояния системы. Например, если идет дождь, агент решает взять зонтик, а если нет, то он может не брать его.

Майкл Л. Литтман показал в 1998 году, что при ветвлении действий задача планирования становится EXPTIME -завершенной. ^[9]^[10] Частный случай непрерывного планирования представляют задачи ФОНД – для «полностью наблюдаемых и недетерминированных». Если цель указана в LTLf (логика линейного времени на конечной трассе), то проблема всегда EXPTIME-полная. ^[11] и 2EXPTIME-complete, если цель указана с помощью LDLf.

Соответствующее планирование

Согласованное планирование — это когда агент не уверен в состоянии системы и не может делать никаких наблюдений. Тогда у агента есть убеждения о реальном мире, но он не может проверить их, например, с помощью ощущений. Эти проблемы решаются методами, аналогичными методам классического планирования. ^[12]^[13] но где пространство состояний экспоненциально зависит от размера проблемы из-за неопределенности относительно текущего состояния. Решение задачи согласованного планирования — это последовательность действий. Хаслум и Йонссон продемонстрировали, что проблема согласованного планирования является EXPSPACE -полной, ^[14] и 2EXPTIME – завершение, когда исходная ситуация неопределенна и имеется недетерминированность результатов действий. ^[10]

Внедрение систем планирования

использует Космический телескоп Хаббл краткосрочную систему SPSS и систему долгосрочного планирования Spike. ^{[ нужна ссылка ]}.

См. также

Списки

Ссылки

^ Галлаб, Малик; Нау, Дана С.; Траверсо, Паоло (2004), Автоматизированное планирование: теория и практика , Морган Кауфманн , ISBN 1-55860-856-7 , заархивировано из оригинала 24 августа 2009 г. , получено 20 августа 2008 г.
^ Видаль, Тьерри (январь 1999 г.). «Обработка непредвиденных обстоятельств в сетях временных ограничений: от согласованности к управляемости». Журнал экспериментального и теоретического искусственного интеллекта . 11 (1): 23--45. CiteSeerX 10.1.1.107.1065 . дои : 10.1080/095281399146607 .
^ Нойфельд, Ксения и Мостагим, Саназ и Санчо-Прадель, Дарио и Бранд, Сэнди (2017). «Создание планировщика: обзор систем планирования, используемых в коммерческих видеоиграх». Транзакции IEEE в играх . IEEE. {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Санелли, Валерио и Кэшмор, Майкл и Магаццени, Даниэле и Иокки, Лука (2017). Краткосрочное взаимодействие человека-робота посредством условного планирования и исполнения . Учеб. Международной конференции по автоматизированному планированию и составлению графиков (ICAPS). Архивировано из оригинала 16 августа 2019 г. Проверено 16 августа 2019 г. {{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Пеот, Марк А. и Смит, Дэвид Э. (1992). Условное нелинейное планирование (PDF) . Системы планирования искусственного интеллекта. Эльзевир. стр. 189–197. {{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Карлссон, Ларс (2001). Условное прогрессивное планирование в условиях неопределенности . IJCAI. стр. 431–438.
^ Лю, Дафна Хао (2008). Обзор планирования в интеллектуальных агентах: от внешне мотивированных к внутренне мотивированным системам (Технический отчет). Технический отчет TR-2008-936, факультет компьютерных наук, Рочестерский университет. Архивировано из оригинала 15 марта 2023 г. Проверено 16 августа 2019 г.
^ Александр Альборе; Гектор Паласиос; Гектор Геффнер (2009). Подход к планированию непредвиденных обстоятельств, основанный на переводе . Международная совместная конференция по искусственному интеллекту (IJCAI). Пасадена, Калифорния: AAAI. Архивировано из оригинала 3 июля 2019 г. Проверено 03 июля 2019 г.
^ Литтман, Майкл Л. (1997). Вероятностное пропозициональное планирование: представления и сложность . Четырнадцатая национальная конференция по искусственному интеллекту. МТИ Пресс. стр. 748–754. Архивировано из оригинала 12 февраля 2019 г. Проверено 10 февраля 2019 г.
^ Jump up to: ^а ^б Юсси Ринтанен (2004). Сложность планирования с частичной наблюдаемостью (PDF) . Межд. Конф. Автоматизированное планирование и планирование. АААИ. Архивировано (PDF) из оригинала 31 октября 2020 г. Проверено 03 июля 2019 г.
^ Де Джакомо, Джузеппе; Рубин, Саша (2018). Автоматно-теоретические основы планирования ФОНД для целей LTLf и LDLf . IJCAI. Архивировано из оригинала 17 июля 2018 г. Проверено 17 июля 2018 г.
^ Паласиос, Гектор; Геффнер, Гектор (2009). «Устранение неопределенности в соответствующих задачах планирования с ограниченной шириной» . Журнал исследований искусственного интеллекта . 35 : 623–675. arXiv : 1401.3468 . дои : 10.1613/jair.2708 . Архивировано из оригинала 27 апреля 2020 г. Проверено 16 августа 2019 г.
^ Альборе, Александр; Рамирес, Микель; Геффнер, Гектор (2011). Эффективная эвристика и отслеживание убеждений для планирования с неполной информацией . Двадцать первая международная конференция по автоматизированному планированию и составлению графиков (ICAPS). Архивировано из оригинала 6 июля 2017 г. Проверено 16 августа 2019 г.
^ Хаслум, Патрик; Йонссон, Питер (2000). Некоторые результаты о сложности планирования при неполной информации . Конспекты лекций по информатике. Том. 1809. Шпрингер Берлин Гейдельберг. стр. 308–318. дои : 10.1007/10720246_24 . ISBN 9783540446576 . конференция: Последние достижения в планировании искусственного интеллекта

Дальнейшее чтение

Влахавас, И. «Планирование и составление графиков» . ЭЕТН . Архивировано из оригинала 22 декабря 2013 г.

Внешние ссылки

Международная конференция по автоматизированному планированию и составлению графиков

[1] Галлаб, Малик; Нау, Дана С.; Траверсо, Паоло (2004), Автоматизированное планирование: теория и практика , Морган Кауфманн , ISBN 1-55860-856-7 , заархивировано из оригинала 24 августа 2009 г. , получено 20 августа 2008 г.

[2] Видаль, Тьерри (январь 1999 г.). «Обработка непредвиденных обстоятельств в сетях временных ограничений: от согласованности к управляемости». Журнал экспериментального и теоретического искусственного интеллекта . 11 (1): 23--45. CiteSeerX 10.1.1.107.1065 . дои : 10.1080/095281399146607 .

[3] Нойфельд, Ксения и Мостагим, Саназ и Санчо-Прадель, Дарио и Бранд, Сэнди (2017). «Создание планировщика: обзор систем планирования, используемых в коммерческих видеоиграх». Транзакции IEEE в играх . IEEE. {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[4] Санелли, Валерио и Кэшмор, Майкл и Магаццени, Даниэле и Иокки, Лука (2017). Краткосрочное взаимодействие человека-робота посредством условного планирования и исполнения . Учеб. Международной конференции по автоматизированному планированию и составлению графиков (ICAPS). Архивировано из оригинала 16 августа 2019 г. Проверено 16 августа 2019 г. {{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )

[5] Пеот, Марк А. и Смит, Дэвид Э. (1992). Условное нелинейное планирование (PDF) . Системы планирования искусственного интеллекта. Эльзевир. стр. 189–197. {{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )

[6] Карлссон, Ларс (2001). Условное прогрессивное планирование в условиях неопределенности . IJCAI. стр. 431–438.

[7] Лю, Дафна Хао (2008). Обзор планирования в интеллектуальных агентах: от внешне мотивированных к внутренне мотивированным системам (Технический отчет). Технический отчет TR-2008-936, факультет компьютерных наук, Рочестерский университет. Архивировано из оригинала 15 марта 2023 г. Проверено 16 августа 2019 г.

[8] Александр Альборе; Гектор Паласиос; Гектор Геффнер (2009). Подход к планированию непредвиденных обстоятельств, основанный на переводе . Международная совместная конференция по искусственному интеллекту (IJCAI). Пасадена, Калифорния: AAAI. Архивировано из оригинала 3 июля 2019 г. Проверено 03 июля 2019 г.

[9] Литтман, Майкл Л. (1997). Вероятностное пропозициональное планирование: представления и сложность . Четырнадцатая национальная конференция по искусственному интеллекту. МТИ Пресс. стр. 748–754. Архивировано из оригинала 12 февраля 2019 г. Проверено 10 февраля 2019 г.

[rintanen04-10] Jump up to: ^а ^б Юсси Ринтанен (2004). Сложность планирования с частичной наблюдаемостью (PDF) . Межд. Конф. Автоматизированное планирование и планирование. АААИ. Архивировано (PDF) из оригинала 31 октября 2020 г. Проверено 03 июля 2019 г.

[11] Де Джакомо, Джузеппе; Рубин, Саша (2018). Автоматно-теоретические основы планирования ФОНД для целей LTLf и LDLf . IJCAI. Архивировано из оригинала 17 июля 2018 г. Проверено 17 июля 2018 г.

[12] Паласиос, Гектор; Геффнер, Гектор (2009). «Устранение неопределенности в соответствующих задачах планирования с ограниченной шириной» . Журнал исследований искусственного интеллекта . 35 : 623–675. arXiv : 1401.3468 . дои : 10.1613/jair.2708 . Архивировано из оригинала 27 апреля 2020 г. Проверено 16 августа 2019 г.

[13] Альборе, Александр; Рамирес, Микель; Геффнер, Гектор (2011). Эффективная эвристика и отслеживание убеждений для планирования с неполной информацией . Двадцать первая международная конференция по автоматизированному планированию и составлению графиков (ICAPS). Архивировано из оригинала 6 июля 2017 г. Проверено 16 августа 2019 г.

[14] Хаслум, Патрик; Йонссон, Питер (2000). Некоторые результаты о сложности планирования при неполной информации . Конспекты лекций по информатике. Том. 1809. Шпрингер Берлин Гейдельберг. стр. 308–318. дои : 10.1007/10720246_24 . ISBN 9783540446576 . конференция: Последние достижения в планировании искусственного интеллекта

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]