Искусственный интеллект. Современный подход

Алгоритм Graphplan

В данном подразделе показано, как извлечь план непосредственно из графа планирования, а не просто использовать этот граф для получения эвристики. Алгоритм Graphplan (листинг 11.6) имеет два основных этапа, каждый из которых чередуется в цикле. Прежде всего в этом алгоритме проверяется, присутствуют ли все целевые литералы на текущем уровне без взаимно исключающих связей между любой парой из них. Если это требование соблюдается, то в текущем графе может существовать решение, поэтому в алгоритме выполняется попытка извлечь это решение. В противном случае граф расширяется путем добавления действий для текущего уровня и литералов состояния для следующего уровня. Процесс продолжается до тех пор, пока либо не обнаруживается решение, либо не выясняется, что решения не существует.
Листинг 11.6. Алгоритм Graphplan. В алгоритме Graphplan чередуются этап извлечения решения и этап расширения графа. Функция Extract-Solution определяет, может ли быть найден план, начиная с конца и выполняя поиск в обратном направлении. Функция Expand-Graph добавляет действия для текущего уровня и литералы состояния для следующего уровня
function Graphplan[problem) returns решение solution или индикатор неудачи failure graph solution <— Extract-Solution (graph, goals, Length (graph) )
if solution Ф failure then return solution else if No-Solution-Possible(graph) then return failure graph Теперь проследим за функционированием алгоритма Graphplan на примере задачи замены колеса, рассматриваемой в разделе 11.1. Полный граф показан на рис. 11.7. В первой строке алгоритма Graphplan граф планирования инициализируется значением одноуровневого графа (50), состоящего из пяти литералов, взятых из начального состояния. Целевой литерал At (Spare, Axle) в состоянии S0 отсутствует, поэтому не требуется вызывать функцию Extract-Solution — мы можем быть уверены, что решение еще не существует. Вместо этого вызывается функция
Expand-Graph, добавляющая три действия, предусловия которых существуют на уровне S0 (т.е. все действия, за исключением PutOn(Spare,Axle)), наряду с сохраняющими действиями для всех литералов в s0. Результаты действий добавляются на уровне Si. Затем функция Expand-Graph отыскивает взаимно исключающие отношения и добавляет их к графу.
В состоянии Si литерал At (Spare, Axle) все еще не присутствует, поэтому функция Extract-Solution снова не вызывается. Вызов функции Expand-Graph приводит к получению графа планирования, показанного на рис. 11.7. Теперь, после получения полного комплекта действий, целесообразно рассмотреть некоторые примеры взаимно исключающих отношений и их причин, как показано ниже.
• Несогласованные результаты. Литерал Remove (Spare, Trunk) является взаимно исключающим по отношению к LeaveOvernight, поскольку один из них имеет своим результатом литерал A t (Spare, Ground), а другой — его отрицание.
• Вмешательство. Литерал Remove (Flat, Axlе) является взаимно исключающим по отношению к LeaveOvernight, поскольку один из них имеет своим предусловием At (Flat, Axl е), а другой имеет своим результатом его отрицание.
• Конкурирующие потребности. Литерал PutOn (Spare, Axle) является взаимно исключающим по отношению к Remove (Flat, Axle), поскольку один из них имеет в качестве предусловия литерал At (Flat, Axle), а другой — его отрицание.
• Несогласованная поддержка. Литерал A t (Spare, Axl е) является взаимно исключающим по отношению к At (Flat, Axlе) на уровне S2, поскольку единственным способом достижения цели At (Spare, Axle) является выполнение действия PutOn (Spare, Axle), а оно является взаимно исключающим с сохраняющим действием, которое представляет собой единственный способ достижения литерала At (Flat, Axle). Таким образом, взаимно исключающие отношения позволяют обнаруживать непосредственные конфликты, которые становятся следствием попыток поместить два объекта в одно и то же место одновременно.
После того как мы снова перейдем в начало цикла, на этот раз на уровне S2 будут присутствовать все литералы из цели и ни один из них не будет взаимно исключающим по отношению к любому другому. Это означает, что может существовать решение и в функции Extract-Solution будет предпринята попытка его найти. По сути, функция Extract-Solution решает булеву задачу CSP, переменными которой являются действия на каждом уровне, а значениями для каждой переменной служат индикаторы, показывающие, принадлежит ли она или не принадлежит к плану. Для этого можно воспользоваться стандартными алгоритмами CSP или определить функцию Extract-Solution как задачу поиска, в которой каждое состояние в поиске содержит указатель на уровень в графе планирования и множество невыполненных целей. Определим эту задачу поиска, как описано ниже.
• Первоначальным состоянием является последний уровень графа планирования, 5П, наряду с множеством целей из задачи планирования.
• Действия, доступные в любом состоянии на уровне Siy должны выбирать любое бесконфликтное подмножество действий на уровне л, результаты которых покрывают цели в этом состоянии. Результирующее состояние имеет уровень и включает в качестве своего множества целей все предусловия для выбранного множества действий. Под термином "бесконфликтный" подразумевается множество таких действий, что никакие два из них не являются взаимно исключающими и никакие два из их предусловий не являются взаимно исключающими.
• Задача состоит в том, чтобы достичь на уровне S0 такого состояния, чтобы все цели были выполнены.
• Стоимость каждого действия равна 1.
При решении данной конкретной задачи начнем с уровня s2, где имеется цель At (Spare, Axle). Единственным вариантом, который может применяться для достижения этого множества целей, является PutOn [Spare, Axle). В результате мы переходим в состояние поиска на уровне Sx с целями At (Spare, Ground) и -iAt {Flat, Axle). Первой цели можно достичь только с помощью действия Remove(Spare, Trunk), а последней— с помощью либо Remove(Flat, Axle), либо LeaveOvernight. Но действие LeaveOvernight является взаимно исключающим по отношению к Remove (Spare, Trunk), поэтому единственное решение состоит в том, чтобы выбрать Remove(Spare, Trunk) и Remove (Flat, Axle). В результате мы переходим в состояние поиска на уровне S0 с целями At (Spare, Trunk) и At (Flat, Axle). Обе из этих целей присутствуют в данном состоянии, поэтому налицо готовое решение: действия Remove ( Spare, Trunk) и Remove (Flat, Axle) на уровне A0, за которыми следует действие PutOn (Spare, Axle) на уровне А±.
Известно, что задача планирования является PSPACE-полной и что для построения графа планирования требуется полиномиальное время, поэтому в наихудшем случае может возникнуть ситуация, в которой извлечение решения окажется неосуществимым. Таким образом, потребуется определенное эвристическое руководство при выборе среди действий в ходе обратного поиска. Одним из подходов, хорошо зарекомендовавших себя на практике, является жадный алгоритм, основанный на учете уровневой стоимости литералов. Для каждого набора целей применение этой эвристики осуществляется в описанном ниже порядке.
1. Определить литерал с максимальной уровневой стоимостью.
2. Чтобы достичь этого литерала, выбрать в первую очередь действие с самыми легкими для выполнения предусловиями. Это означает, что действие нужно выбирать так, чтобы сумма (или максимум) уровневых стоимостей его предусловий была минимальной.