Автоматизоване планування та диспетчеризація

Автоматичне планування та диспетчеризація, є підвидом artificial intelligence, що стосується реалізації strategies або спосліовності дій типових для intelligent agents, autonomous robots і unmanned vehicles. На відмінну від control і classification, рішення є комплексними та мають бути виявлені і оптимізовані для мультивимірного простору. Планування також має відношення до decision theory.

У відомих середовища з наявними моделями, планування може бути виконане без доступу до мережі Інтернет. Рішення можуть бути знайдені та оцінені до виконання. В невідомих середовищах, стратегія часто повинна бути переглянута онлайн. Моделі та політики мають бути адаптованими. Програмні рішення часто вдаються до ітеративного методу спроб та помилок, який часто зустрічається при створенні штучних інтелектів . Він включає dynamic programming, reinforcement learning і combinatorial optimization. Мови, що використовуються для опису планування та диспетчеризації, часто називають action languages.

Огляд

Беручи до уваги опис можливих початкових станів світу, опис бажаних цілей, а також опис набору можливих дій, проблема планування полягає у знаходженні плану, який гарантовано створить (від будь-якого з початкових станів) послідовність дій, що приведуть до однієї з цілей.

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

Найбільш проста проблема планування, більш відома як класична проблема планування або класичне планування, визначається за допомогою:

• унікально відомий початковий стан,
• детермінованими діями,
• які можуть бути виконаними лише одна водночас,
• одним агентом.

Мови планування

Найбільш розповсюджені мови для представлення проблеми планування, такі як STRIPS і PDDL для класичного планування, базуються на змінних стану. Кожен з можливих станів світу є присвоєнням значень змінним стану та діями, що визначають, які ці змінні видозмінються, коли запланована дія відбувається. Так як набір змінних станів створює множину станів, розмір якої є експоненційний в наборі, планування потерпає від curse of dimensionality і combinatorial explosion.

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

Класичне планування

• forward chaining state space search, з можливість покращення на базі heuristics алгоритмів
• backward chaining пошук, з можливістю покращення на базі виділення обмежувачів станів (дивись STRIPS, graphplan),
• partial-order planning (на противагу до Noninterleaved planning).

Зведення до інших проблем

• зведення до проблеми propositional satisfiability (satplan).
• зведення до проблеми Model checking — обоє є важливими проблемами обходу простору станів, а також класична проблема планування відповідає підкласу задач перевірка моделей.

Тимчасове планування

Тимчасове планування може бути вирішена за допомогою методів, аналогічних до класичного планування. Основна відмінність полягає в тому, що через можливість декількох подій, що перекриваються в часі, тобто виконуються паралельно, визначення стану повинна включати в себе інформацію про поточний абсолютний час і як далеко виконання кожної активності просунулося. Крім того, при такому плануванні простір станів може бути нескінченним, на відміну від класичного планування або планування з явним часом. Тимчасове планування тісно пов'язане з scheduling problems. Тимчасове планування також можна зрозуміти у термінах timed automata.

Ймовірісне планування

Імовірнісний планування може бути вирішена за допомогою ітераційних методів, таких як value iteration і policy iteration, коли простір станів є відносно малий. Ймовірнісне планування аналогічно вирішується ітераційним методом, але з використанням представлення функцій значень, визначених для простору переконань, а не станів.

Розгортання системи планування

• Hubble Space Telescope використовує короткотривалу систему планування SPSS і довготривалу систему Spike.

Див. також

• Action description language
• Actor model
• Applications of artificial intelligence
• Constraint satisfaction problem
• Reactive planning
• Scheduling (computing)
• Strategy (game theory)

Списки

• List of SMT solvers
• List of constraint programming languages
• List of emerging technologies
• Outline of artificial intelligence

Посилання

• Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Automated Planning: Theory and Practice, Morgan Kaufmann, ISBN 1-55860-856-7, архів оригіналу за 24 серпня 2009, процитовано 27 грудня 2016 {{citation}}: Вказано більш, ніж один |ISBN= та |isbn= (довідка)Вказано більш, ніж один |ISBN= та |isbn= (довідка)

Наступне до прочитання

• Vlahavas, I. Planning and Scheduling. Архів оригіналу за 22 грудня 2013. Процитовано 27 грудня 2016.

Посилання

• International Conference on Automated Planning and Scheduling [Архівовано 2 січня 2017 у Wayback Machine.]