В данном подразделе показано, как извлечь план непосредственно из графа планирования, а не просто использовать этот граф для получения эвристики. Алгоритм Graphplan (листинг 11.6) имеет два основных этапа, каждый из которых чередуется в цикле. Прежде всего в этом алгоритме проверяется, присутствуют ли все целевые литералы на текущем уровне без взаимно исключающих связей между любой парой из них. Если это требование соблюдается, то в текущем графе может существовать решение, поэтому в алгоритме выполняется попытка извлечь это решение. В противном случае граф расширяется путем добавления действий для текущего уровня и литералов состояния для следующего уровня. Процесс продолжается до тех пор, пока либо не обнаруживается решение, либо не выясняется, что решения не существует.

Листинг 11.6. Алгоритм Graphplan. В алгоритме Graphplan чередуются этап извлечения решения и этап расширения графа. Функция Extract-Solution определяет, может ли быть найден план, начиная с конца и выполняя поиск в обратном направлении. Функция Expand-Graph добавляет действия для текущего уровня и литералы состояния для следующего уровня

Теперь проследим за функционированием алгоритма Graphplan на примере задачи замены колеса, рассматриваемой в разделе 11.1. Полный граф показан на рис. 11.7. В первой строке алгоритма Graphplan граф планирования инициализируется значением одноуровневого графа (S0), состоящего из пяти литералов, взятых из начального состояния. Целевой литерал At (Spare, Axle) в состоянии S0 отсутствует, поэтому не требуется вызывать функцию Extract-Solution— мы можем быть уверены, что решение еще не существует. Вместо этого вызывается функция