How does it compare with max-level?

Max-level takes the latest first appearance of any individual goal. Set-level additionally requires pairwise compatibility, so it cannot be smaller for the same graph and goals.

Does it always give the optimal plan length?

No. The three-goal example gives estimate two while every serial plan needs three actions.

What does an infinite estimate mean?

Under a correctly constructed standard planning graph, a required absence or mutex that persists after leveling off rules out the goal set in that model.

AI Glossary / Graphs and symbolic AI / Advanced

Set-level

Definition

Set-level is a planning-graph heuristic that estimates the distance to a conjunctive goal by finding the earliest proposition layer where every goal literal is present and no pair of those literals is mutually exclusive. It accounts for pairwise goal interactions that simpler individual-goal estimates ignore.

What it means

A planning graph alternates layers of possible facts and possible actions. It summarizes many potential developments rather than describing one chosen execution. A fact appearing in a layer therefore does not mean it can coexist with every other fact shown there.

Mutual-exclusion, or mutex, links identify certain incompatible pairs. Two facts may be mutually exclusive because they contradict one another or because every pair of actions supporting them is incompatible at the preceding layer.

Set-level asks about the goal literals as a group, using those pairwise links. It is more informative than merely asking when each goal first appears. However, passing all pairwise checks does not prove that the entire collection is jointly achievable at that layer. Larger interactions may remain unresolved.

How it works

Begin with proposition layer S0 representing the current state. Add an action layer containing actions whose preconditions are represented and satisfy the relevant compatibility checks, together with persistence actions that carry existing facts forward. Their effects form the next proposition layer.

The graph records mutex relationships caused by inconsistent effects, interference and competing preconditions. It also records incompatible fact pairs. For a specified goal set, examine successive proposition layers until all goals appear without a mutex link between any pair. That layer number is the set-level estimate.

If the graph reaches a fixed point while a required goal remains absent or a required pair remains mutex, the goal set cannot be achieved in the represented planning problem. Conversely, a finite estimate is only a lower-bound-style reachability check under the standard model, not an extracted plan. The interpretation of the number depends on whether layers permit parallel actions or enforce serial execution.

Three practical examples

A planning system uses set-level to prioritize search states whose remaining goals appear closer to compatible achievement.
A teaching exercise compares individual goal levels with mutex-aware estimates to expose interactions between otherwise easy subgoals.
A symbolic workflow prototype detects that two required final conditions remain mutually exclusive in a fully expanded planning graph.

Think of it this way

Think of checking whether all requested appointments appear available and whether any pair conflicts. That can rule out obvious problems before searching for a complete schedule.

The analogy has a strict limit: every pair fitting does not necessarily mean the whole collection fits. Three appointments may compete for capacity that permits only two. Likewise, pairwise planning-graph checks can miss interactions involving a larger group.

Worked example

Pairwise compatibility is not a complete plan

Consider an invented serial planning graph with initially false facts P, Q and R. Three actions independently establish them: MakeP, MakeQ and MakeR. Each has no preconditions and adds only its named fact. Real actions are pairwise mutex in each action layer because this graph permits only one real action per step; persistence is still allowed.

At proposition layer S1, P, Q and R all appear individually. Every pair is mutex because producing two different facts would require two real actions in the first step. At S2, each pair has compatible support: one fact can persist from the first step while the other is produced in the second.

For goal P and Q, set-level is therefore 2, and the two-action plan MakeP then MakeQ achieves it. For goal P and Q and R, set-level is also 2 because every pair is nonmutex at S2. Yet three real actions are necessary to establish all three facts. The estimate remains an optimistic bound.

Illustrative case study

Fictional case study: Cedar Workflow Lab creates a planner for independent preparation tasks. A dashboard labels the set-level estimate as “steps remaining,” and reviewers initially interpret it as a guaranteed completion schedule.

The developers use a small serial example with three independent goals to demonstrate that the estimate can be lower than the length of every valid plan. They rename the display to make its heuristic role explicit and show an executable plan separately when one has actually been found.

The team also checks whether its graph uses serial or parallel action layers. A search estimate needs a clear unit and meaning. Neither a finite level nor the absence of pairwise conflicts replaces solution extraction and validation.

Common misconceptions and mistakes

If all goals appear, they can be achieved together. Their supporting actions may conflict.
If no goal pair is mutex, a complete plan exists at that layer. Higher-order incompatibilities may remain.
Set-level counts selected actions. It counts planning-graph layers; parallel and serial graph conventions differ.
Set-level and set cover are the same heuristic. They use different abstractions.

Business use

Set-level is primarily an internal planning concept, but understanding it helps teams interpret solver progress and diagnostic displays. It can reveal impossible goal combinations early and guide search toward promising states.

When a planning vendor reports a distance estimate, ask whether it is a lower bound, a candidate plan length or an execution-time prediction. Those quantities are different. A graph built from incomplete resource constraints may overlook real conflicts, so the heuristic's formal properties apply to the encoded model rather than automatically to operations outside it.

Check your understanding

Three goal facts are present and pairwise nonmutex at layer two of a serial graph. Must a two-action plan achieve all three?

Answer: No. Pairwise support may use different combinations for different pairs. A joint plan still needs to be found, and larger interactions can require additional steps.

Related terms

Planning graph
Mutex
Graphplan
Heuristic
Level sum
max-level
serial planning graph
conjunctive goal
admissibility

Learn next

Read planning graph and mutual exclusion. Draw the first two layers of the independent P/Q/R example, including persistence actions. Identify which compatible supporting pair establishes P with Q, and why that pair alone does not establish R.

Planning graph

Sources

Russell and Norvig, Planning, section on planning graphs for heuristic estimation: https://aima.cs.berkeley.edu/newchap11.pdf. The set-level definition, serial-graph convention, mutex rules and limitation to pairwise interactions were reviewed. The independent P/Q/R construction and dashboard case are original illustrations, not examples of a deployed planning service.

Previous: Set-cover problem Next: Set of support