Графический план
-
Основы Graphplan
- Алгоритм автоматизированного планирования, разработанный в 1995 году
- Принимает задачу планирования в виде полос и выдает последовательность операций для достижения цели
-
Структура графа пространства состояний
- Узлы — возможные состояния, края указывают на достижимость
- В Graphplan узлы — действия и факты на разных уровнях
- Первый уровень содержит атомарные факты для начального состояния
- Ведется список несовместимых фактов и действий
-
Итеративный поиск решений
- Алгоритм исключает планы длиной l-1, прежде чем искать планы длины l
- Поиск осуществляется через обратную цепочку, учитывая несовместимость фактов и действий
-
Сравнение с планированием как осуществимость (Satplan)
- Оба подхода сводят задачу планирования к поиску планов с фиксированной длиной горизонта
-
Дополнительные ресурсы
- Ссылки на публикации Блюма и Ферста, а также на реализации Graphplan на разных языках программирования
- Лекция по OpenCourseWare Массачусетского технологического института о GraphPlan