Завершение работы алгоритма Graphplan
До сих пор мы обходили проблему завершения работы алгоритма. Если задача не имеет решения, можно ли быть уверенным в том, что алгоритм Graphplan не будет проходить по циклу до бесконечности, расширяя граф планирования при каждой итерации? Ответ на этот вопрос является положительным, но полное доказательство такого утверждения выходит за рамки настоящей книги. Здесь мы кратко опишем основные идеи, особенно те, которые проливают свет на графы планирования в целом.
На первом этапе необходимо отметить, что характеристики некоторых свойств графов планирования монотонно увеличиваются или уменьшаются. Выражение "характеристика X увеличивается монотонно" означает, что множество экземпляров X на уровне i + 1 является надмножеством (необязательно строгим) множества на уровне 1. Соответствующие свойства графов перечислены ниже.
• Количество литералов увеличивается монотонно. После того как некоторый литерал появляется на данном конкретном уровне, он будет появляться на всех последующих уровнях. Это связано с наличием сохраняющих действий; после того как литерал появляется, сохраняющие действия вызывают его сохранение навечно.
• Количество действий увеличивается монотонно. После того как некоторое действие появляется на данном конкретном уровне, оно будет появляться на всех последующих уровнях. Это — следствие увеличения количества литералов: если предусловия некоторого действия появляются на одном уровне, они будут появляться и на последующих уровнях и поэтому то же происходит и с действиями.
• Количество взаимно исключающих связей уменьшается монотонно. Если два действия на данном конкретном уровне AL являются взаимно исключающими, то они должны также быть взаимно исключающими на всех предыдущих уровнях, на которых они появлялись вместе. То же утверждение остается справедливым и по отношению к взаимно исключающим связям между литералами. Это не означает, что взаимно исключающие связи характеризуются такими же особенностями и на рисунках с изображением графов планирования, поскольку на рисунках допускаются упрощения: на них не показывают ни литералов, которые не могут быть истинными на уровне Si5 ни действий, которые не могут быть выполнены на уровне AL. Можно убедиться в справедливости утверждения, что "количество взаимно исключающих связей уменьшается монотонно", если учесть, что эти невидимые литералы и действия являются взаимно исключающими по отношению ко всем прочим.
Доказательство этих утверждений является довольно сложным, но может быть выполнено путем анализа отдельных случаев: если действия А и В являются взаимно исключающими на уровне Аь то должны быть таковыми из-за наличия одного из трех типов взаимно исключающих связей. Первые два из них, несогласованные результаты и вмешательство, обусловлены свойствами самих действий, поэтому, если действия являются взаимно исключающими на уровне Ai9 то будут взаимно исключающими на каждом уровне. Третий случай, с конкурирующими потребностями, зависит от условий на уровне S. этот уровень должен содержать предусловие действия А, которое является взаимно исключающим по отношению к предусловию действия в. Теперь отметим, что эти два предусловия могут быть взаимно исключающими, если они являются отрицаниями друг друга (и в этом случае они будут взаимно исключающими на каждом уровне) или все действия по достижении одного из них являются взаимно исключающими по отношению ко всем действиям, необходимым для достижения другого. Но мы уже знаем, что количество допустимых действий увеличивается монотонно, поэтому по индукции количество взаимно исключающих связей должно уменьшаться.
Поскольку количество действий и литералов увеличивается, а количество взаимно исключающих связей уменьшается, и поскольку имеется только конечное количество действий и литералов, каждый граф планирования в конечном итоге выравнивается — все последующие уровни в нем становятся идентичными. После того как граф выровнялся, он может быть проанализирован, и если в нем отсутствует одна из целей задачи или две цели являются взаимно исключающими, то данная задача никогда не может быть решена, поэтому мы можем остановить работу алгоритма Graphplan и вернуть индикатор неудачи. Если же граф выравнивается со всеми присутствующими и не взаимно исключающими целями, но функция Extract-Solution оказывается не в состоянии найти решения, то может потребоваться снова расширить граф конечное количество раз, но так или иначе мы имеем возможность остановить работу алгоритма. Последний вариант завершения является более сложным и здесь не рассматривается.