Уровень А0 содержит все действия, которые могут произойти в состоянии S0, но столь же важно то, что он показывает конфликты между действиями, способные воспрепятствовать тому, чтобы эти действия выполнялись вместе. Серыми линиями на рис. 11.6 показаны взаимно исключающие связи (или связи, ^ характеризующиеся взаимным исключением — mutual exclusive, mutex). Например, действие Ea t (Cake) является взаимно исключающим с действием, обеспечивающим сохранение состояния, вызванного действием Have (Cake) или. Вскоре будет показано, как происходит вычисление взаимно исключающих связей.

На уровне s1 находятся все литералы, которые могут стать результатом принятия к исполнению любого подмножества действий уровня а0. На этом уровне показаны также взаимно исключающие связи (серые линии), обозначающие литералы, которые не могут появляться вместе, независимо от выбора действий. Например, взаимно исключающими являются литералы Have (Cake) и Eaten {Cake): в зависимости от выбора действий на уровне А0 результатом может стать один из них или другой, но не оба. Иными словами, на уровне Si представлено несколько состояний, точно так же, как и при регрессивном поиске в пространстве состояний, а взаимно исключающие связи представляют собой ограничения, которые определяют множество возможных состояний.

Построение плана продолжается таким же образом, с чередованием между уровнями состояния Si и уровнями действия Ai до тех пор, пока не будет достигнут уровень, на котором два последовательных уровня становятся идентичными. После достижения такой точки граф называется выровненным (leveled off). Каждый последующий уровень будет оставаться неизменным, поэтому дальнейшее развертывание не имеет смысла.

В конечном итоге образуется структура, в которой каждый уровень Ai содержит все действия, применимые на уровне Si, наряду с ограничениями, указывающими, какие пары действий не могут выполняться одновременно. Каждый уровень Si содержит все литералы, которые могут стать результатом любого возможного выбора действий на уровне Ai-1, наряду с ограничениями, указывающими, какие пары литералов недопустимы. Важно отметить, что процесс построения графа планирования не требует выбора среди действий, который потребовал бы комбинаторного поиска. Вместо этого в графе просто регистрируется невозможность осуществления некоторых выборов с использованием взаимно исключающих связей. Сложность формирования графа планирования оценивается полиномиальной зависимостью низкого порядка от количества действий и литералов, тогда как размеры пространства состояний определяются экспоненциальной зависимостью от количества литералов.