До сих пор мы обходили проблему завершения работы алгоритма. Если задача не имеет решения, можно ли быть уверенным в том, что алгоритм Graphplan не будет проходить по циклу до бесконечности, расширяя граф планирования при каждой итерации? Ответ на этот вопрос является положительным, но полное доказательство такого утверждения выходит за рамки настоящей книги. Здесь мы кратко опишем основные идеи, особенно те, которые проливают свет на графы планирования в целом.

На первом этапе необходимо отметить, что характеристики некоторых свойств графов планирования монотонно увеличиваются или уменьшаются. Выражение "характеристика X увеличивается монотонно" означает, что множество экземпляров X на уровне i + 1 является надмножеством (необязательно строгим) множества на уровне i. Соответствующие свойства графов перечислены ниже.

•    Количество литералов увеличивается монотонно. После того как некоторый литерал появляется на данном конкретном уровне, он будет появляться на всех последующих уровнях. Это связано с наличием сохраняющих действий; после того как литерал появляется, сохраняющие действия вызывают его сохранение навечно.

•    Количество действий увеличивается монотонно. После того как некоторое действие появляется на данном конкретном уровне, оно будет появляться на всех последующих уровнях. Это — следствие увеличения количества литералов: если предусловия некоторого действия появляются на одном уровне, они будут появляться и на последующих уровнях и поэтому то же происходит и с действиями.

•    Количество взаимно исключающих связей уменьшается монотонно. Если два действия на данном конкретном уровне Ai являются взаимно исключающими, то они должны также быть взаимно исключающими на всех предыдущих уровнях, на которых они появлялись вместе. То же утверждение остается справедливым и по отношению к взаимно исключающим связям между литералами. Это не означает, что взаимно исключающие связи характеризуются такими же особенностями и на рисунках с изображением графов планирования, поскольку на рисунках допускаются упрощения: на них не показывают ни литералов, которые не могут быть истинными на уровне Si, ни действий, которые не могут быть выполнены на уровне Ai. Можно убедиться в справедливости утверждения, что "количество взаимно исключающих связей уменьшается монотонно", если учесть, что эти невидимые литералы и действия являются взаимно исключающими по отношению ко всем прочим.