Graphplan - Википедия - Graphplan

Графплан является алгоритм за автоматизированное планирование разработан Аврим Блюм и Меррик Ферст в 1995 году. Graphplan принимает в качестве входных данных задачу планирования, выраженную в Полоски и производит, если это возможно, последовательность операций для достижения целевого состояния.

Название графикплан связан с использованием романа планирование график, чтобы сократить объем поиска, необходимый для поиска решения путем простого исследования граф пространства состояний.

в граф пространства состояний:

  • узлы - возможные состояния,
  • а края указывают на достижимость посредством определенного действия.

Напротив, в Graphplan график планирования:

  • узлы - это действия и атомарные факты, расположенные на чередующихся уровнях,
  • и края бывают двух видов:
    1. от атомарного факта к действиям, для которых он является условием,
    2. от действия до элементарных фактов, которые он делает истинным или ложным.

первый уровень содержит истинные атомарные факты, идентифицирующие начальное состояние.

Также ведутся списки несовместимых фактов, которые не могут быть истинными одновременно, и несовместимых действий, которые невозможно выполнить вместе.

Затем алгоритм итеративно расширяет граф планирования, доказывая, что не существует решений длины l-1, прежде чем искать планы длина l путем обратной цепочки: предполагая, что цели верны, Graphplan ищет действия и предыдущие состояния, из которых могут быть достигнуты цели, сокращая как можно больше из них благодаря информации о несовместимости.

Тесно связанный подход к планированию - это планирование как выполнение (Satplan ). Оба сводят задачу автоматического планирования к поиску планов с разной фиксированной длиной горизонта.

Рекомендации

внешняя ссылка