Графплан - Graphplan
Графплан является алгоритм за автоматизированное планирование разработан Аврим Блюм и Меррик Ферст в 1995 году. Graphplan принимает в качестве входных данных задачу планирования, выраженную в Полоски и производит, если это возможно, последовательность операций для достижения целевого состояния.
Название графикплан связан с использованием романа планирование график, чтобы сократить объем поиска, необходимый для поиска решения путем простого исследования граф пространства состояний.
в граф пространства состояний:
- узлы - возможные состояния,
- а края указывают на достижимость посредством определенного действия.
Напротив, в Graphplan график планирования:
- узлы - это действия и атомарные факты, расположенные на чередующихся уровнях,
- и края бывают двух видов:
- от атомарного факта к действиям, для которых он является условием,
- от действия до элементарных фактов, которые он делает истинным или ложным.
первый уровень содержит истинные атомарные факты, идентифицирующие начальное состояние.
Также ведутся списки несовместимых фактов, которые не могут быть истинными одновременно, и несовместимых действий, которые невозможно выполнить вместе.
Затем алгоритм итеративно расширяет граф планирования, доказывая, что не существует решений длины l-1, прежде чем искать планы длина l путем обратной цепочки: предполагая, что цели верны, Graphplan ищет действия и предыдущие состояния, из которых могут быть достигнуты цели, сокращая как можно больше из них благодаря информации о несовместимости.
Тесно связанный подход к планированию - это планирование как выполнение (Satplan ). Оба сводят задачу автоматического планирования к поиску планов с разной фиксированной длиной горизонта.
Рекомендации
- А. Блюм и М. Ферст (1997). Быстрое планирование за счет анализа графика планирования. Искусственный интеллект. 90: 281-300.