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