What is the level cost of a goal true initially?

Zero, when the initial proposition layer is numbered S0.

Does level cost count every action needed?

Not necessarily. A parallel graph can place several independent actions in one layer.

Does a finite level cost prove an executable plan exists?

No. It is optimistic graph information; further consistency checks and plan extraction may still fail.

AI Glossary / Graphs and symbolic AI / Intermediate

Level cost

Definition

Level cost is a planning-graph heuristic that assigns a goal literal the index of the first proposition level at which it appears. A goal already true in the initial level has level cost zero. The measure estimates how far away the goal is in the graph's action layers, rather than directly measuring money, elapsed time, or arbitrary action costs.

What it means

A planning graph alternates proposition levels, which contain literals, and action levels, which contain actions that may be applicable. It also records certain mutual exclusions, or mutex relationships. These help identify combinations that cannot hold together under the graph's current information.
Level cost concerns an individual goal literal. It should not be confused with level sum, which adds individual level costs, or set level, which considers when a group of goals appears without pairwise mutex conflicts. The meaning of the number also depends on whether the graph permits parallel actions or represents serial action steps.

How it works

Construct the planning graph from the state being evaluated. The initial proposition level is S0. Applicable actions form the next action level, and their effects, along with persistence, form S1. Continue expanding while recording the required exclusions.
For a goal literal g, find the smallest i such that g occurs in Si. That i is its level cost. Under the standard unit-step planning assumptions, it supplies an optimistic estimate for achieving the individual goal. If a literal never appears after the graph has leveled off, it is unreachable in that model. Mere appearance, however, does not guarantee that a complete executable plan can be extracted at that level.

Three practical examples

A classical planner prioritizes a state using how early a needed condition appears in its planning graph.
A planning lesson compares the first appearance of an initial fact with the first appearance of a fact requiring several dependent actions.
A search debugger checks whether an apparently easy goal is only easy because the graph allows independent actions in the same layer.

Think of it this way

Think of noting the earliest round in which a required result becomes possible on a dependency chart. The analogy is limited because a planning graph is a relaxed representation with mutex information, not a complete schedule. Its rounds do not automatically correspond to equal durations, resource-feasible execution periods, or the true cost of a finished plan.

Worked example

Consider an invented assembly domain. Initially, raw parts and a digital design are available. CutParts requires raw parts and produces CutReady. PrintGuide requires the design and produces GuideReady. Assemble requires both CutReady and GuideReady and produces Finished. Assume CutParts and PrintGuide do not interfere, and every action has unit step cost.
In a parallel planning graph, CutParts and PrintGuide can occur in the first action layer. Their effects first appear in S1. Assemble can then occur in the next action layer, so Finished first appears in S2. Its level cost is 2.
An actual serial execution needs three actions: CutParts, PrintGuide, and Assemble, with the first two in either order. Thus the parallel level cost of 2 does not count the three individual actions. It measures two action layers in this example.
If a serial planning graph makes distinct non-persistence actions mutually exclusive within a layer, the two preparation actions cannot be performed together. Their effects can coexist after separate steps, and Finished first becomes available at S3. Its serial-graph level cost is then 3. This example deliberately excludes other actions, shared-resource conflicts, and unequal costs so that the difference between layers and action counts is clear.

Illustrative case study

In a fictional planning prototype, Cedar Kits displays a goal's level cost as “minutes to completion.” Reviewers discover that the graph contains unit action layers while real operations have different durations and resource requirements.
The team relabels the display as a search estimate and uses an appropriate scheduling model for elapsed-time estimates. The invented case illustrates a units error. It does not claim that planning graphs are unsuitable for all scheduling work, only that the basic level-cost number cannot be relabeled as time without supporting assumptions.

Common misconceptions and mistakes

Level cost is not necessarily the exact shortest plan length. A planning graph can allow optimistic combinations that fail during full plan extraction. Nor does the presence of every goal individually mean they can all be achieved together.
Do not apply unit-step claims automatically to actions with arbitrary costs or durations. Also, failure to find a literal in a graph expanded for only a few levels does not prove permanent unreachability; the graph may need further expansion. The stronger unreachable conclusion applies when the relevant graph has leveled off without the literal appearing.

Business use

Level cost is mainly useful inside planning and search systems as a relatively inexpensive estimate. It can help compare candidate states or prioritize difficult subgoals, but the application still needs a procedure that establishes a valid plan.
Document the graph convention, initial level numbering, treatment of persistence, and whether the intended objective is serial actions, parallel steps, or something else. Keep displayed business commitments separate from internal heuristic values. When a plan involves actual time, resource use, or financial cost, use a model that represents those quantities instead of assuming a graph level measures them.

Check your understanding

Why does Finished have parallel level cost 2 even though the example needs three serial actions?

Answer: CutParts and PrintGuide share the first action layer because they are independent. Assemble occupies the second layer, so three actions fit into two parallel layers.

Related terms

Planning graph
Mutex
Graphplan
Heuristic
Level sum
goal literal
max-level heuristic
set-level heuristic
serial planning graph

Learn next

Add another independent preparation action required by Assemble and compare the parallel level cost with the serial action count. Then add a genuine interference between preparation actions and inspect how mutex information changes the graph.

Mutex

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: Lesk algorithm Next: Level of abstraction