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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Автоматичне планування та диспетчеризація, є підвидом 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.

Див. також

[ред. | ред. код]
Списки

Посилання

[ред. | ред. код]
  • 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= (довідка)

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

[ред. | ред. код]

Посилання

[ред. | ред. код]