Is level sum always a lower bound?

No. It can overestimate when one action contributes to multiple goals.

Can it underestimate too?

Yes. It can ignore additional work caused by interactions or resource conflicts.

Does a finite sum mean all goals are jointly reachable?

No. Each goal may be individually reachable while their conjunction is impossible.

AI Glossary / Graphs and symbolic AI / Intermediate

Level sum

Definition

Level sum is a planning-graph heuristic that adds the individual level costs of a set of goal literals. Each literal's level cost is the first proposition level at which it appears. The sum provides a simple estimate of the effort needed to achieve all the goals, but it does not fully account for shared actions or conflicts between goals.

What it means

Suppose one goal first appears at level one and another at level three. Their level sum is four. That arithmetic is straightforward, but the interpretation requires care: the goals may share useful actions, interfere with each other, or be impossible to achieve together.
The heuristic uses an independence-style approximation by adding separate estimates. It differs from max level, which takes the largest individual level cost, and set level, which asks when all goals appear without pairwise mutex conflicts. These measures extract different information from the same planning graph and need not produce the same number.

How it works

Build a planning graph from the state being evaluated and determine the first appearance of each required goal literal. Add those level indices to obtain the level-sum estimate. Goals true initially contribute zero when the initial proposition layer is S0.
The method is inexpensive once the graph is available, but simple addition can double-count shared work and ignore negative interactions. It is therefore not generally admissible: it can exceed the true optimal unit-action cost. It can also underestimate that cost. The graph's serial or parallel convention and the task's actual cost model must be stated before interpreting the result.

Three practical examples

A planner ranks candidate states using the summed first-appearance levels of their remaining goals.
A planning tutorial compares level sum with max level on goals that can be achieved together by one action.
A search analysis checks whether an optimistic summed estimate overlooks competition for a consumable resource.

Think of it this way

Think of adding separate estimates for preparing several parts of an event. The sum can be too high when one activity serves two purposes, or too low when activities compete for the same resource. The analogy is limited because level sum adds planning-graph indices, not actual quoted prices or measured durations.

Worked example

First consider an invented unit-cost action, PrepareKit, with no unsatisfied preconditions and two effects: Packed and Labeled. Neither goal is initially true. Both first appear in S1, so their individual level costs are 1 and 1. Level sum is 2.
Yet the single action PrepareKit achieves both goals, making the true optimal action count 1. The estimate of 2 overcounts shared work and demonstrates why level sum is not generally admissible.
Now consider a separate domain with initial fact TokenAvailable. MakeP requires the token, consumes it, and establishes P. MakeQ likewise consumes the token and establishes Q. Recharge restores TokenAvailable without deleting P or Q. Assume these are the only relevant actions and each costs one.
Individually, P and Q each first appear at level one, so level sum is again 2. Achieving both requires three actions: MakeP, Recharge, MakeQ, or the reverse order of MakeP and MakeQ around Recharge. The estimate now undercounts required work. If Recharge is removed and there is no other way to restore the token, the joint goal becomes impossible even though each individual level cost remains one. These examples isolate shared benefits and resource interference rather than reporting a real planner's performance.

Illustrative case study

In a fictional planning system, Rowan Kits uses level sum to guide search and initially describes it to users as the exact number of remaining actions. A test case includes one action that satisfies two goals, revealing that the displayed number can be too high.
Another case includes a shared resource and shows the opposite error. The team retains the heuristic for search guidance but relabels it as an estimate and checks complete plans before reporting action counts. This invented case illustrates correct interpretation, not a claim that level sum should never be used.

Common misconceptions and mistakes

Level sum is not the same as counting unsatisfied goals: goals can first appear at different depths. It is also not simply the depth of the planning graph or the earliest level containing the whole goal set.
Do not assume that summing individually optimistic estimates preserves optimism for a joint task. Shared actions can make the sum larger than the true combined cost. Conversely, conflicts can make the sum too small or finite when the conjunction is unreachable. A finite level sum is therefore not a certificate of solvability, and an inadmissible heuristic must not be presented as supporting optimality guarantees that require admissibility.

Business use

The heuristic is primarily a tool for planning-system design, where speed and guidance quality can matter more than exact estimation at every search state. Its usefulness depends on how strongly the goals interact and what guarantees the chosen search method requires.
Evaluate it on representative planning problems, including shared-action and shared-resource cases. Document whether search seeks any valid plan or an optimal plan and whether heuristic properties support that goal. Keep the heuristic value separate from user-facing estimates of time, money, or remaining work. A complete plan can be evaluated with the actual cost model after it is found.

Check your understanding

Why does PrepareKit give a level sum of 2 when only one action is needed?

Answer: Packed and Labeled each contribute a level cost of 1, so the heuristic adds them separately. It does not recognize in that addition that the same action achieves both.

Related terms

Learn next

Create a planning example with three goals, two of which share an achieving action. Compute individual level costs, their maximum, and their sum. Then compare those values with the cost of an explicit valid plan and identify any double counting.

Sources

Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach, Planning chapter, Planning graphs for heuristic estimation: https://aima.cs.berkeley.edu/newchap11.pdf

Previous: Level-set method Next: Levels