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