Can the independence estimate be too small and too large?

Yes. Interference can raise joint cost, while shared work can lower it relative to the sum.

Are different goal predicates enough to prove independence?

No. Their supporting actions, resources, and effects may still interact.

Does using exact isolated costs solve the issue?

No. Even exact individual costs can combine incorrectly, as the worked examples show.

AI Glossary / Graphs and symbolic AI / Intermediate

Subgoal independence

Definition

Subgoal independence is an assumption that the cost of achieving several goals together can be approximated by adding the costs of achieving each goal separately. In AI planning, it can simplify heuristic estimation, but goals often interact. Shared actions can make the sum too high, while interference between subplans can make it too low.

What it means

A planning goal may be a conjunction: finish task A and finish task B and finish task C. Estimating each part separately is often easier than finding the best complete plan. Subgoal independence treats the separate estimates as if they could simply be added.

The word “independence” here concerns planning costs and interactions. It does not necessarily mean statistical independence between random variables. Two goals can be described by different predicates yet still compete for a resource, require the same preparatory action, or undo one another. Different wording does not establish separate achievement costs.

How it works

For a state s and goals g1 through gn, obtain separate cost estimates h1(s) through hn(s). An additive estimate is h(s)=h1(s)+...+hn(s). The strongest simple interpretation uses the exact minimum cost of each isolated goal; practical heuristics may instead use approximate subgoal costs.

Before interpreting the sum, consider positive interaction, where work serves more than one goal, and negative interaction, where achieving one goal complicates another. Exact isolated costs still do not settle the combined problem when either interaction exists.

If the estimate is intended for an optimal-search guarantee, admissibility requires that it never exceed the true remaining cost. Blindly adding isolated costs can violate this. By contrast, the maximum of admissible individual-goal estimates is a lower bound for achieving their conjunction under the same nonnegative-cost planning model. More informative admissible sums require justified decomposition or cost accounting.

Three practical examples

Delivery planning: two destinations may share the same initial route segment, so adding separately computed delivery plans can count that travel twice.
Document preparation: one data extraction may support both a chart and a summary, making shared preparation relevant to the total effort estimate.
Robot planning: moving an object to satisfy one condition may obstruct access needed for another, requiring a planner to account for interference rather than concatenate plans blindly.

Think of it this way

Think of estimating dinner preparation by timing each dish separately. Adding the times ignores both shared chopping and competition for one oven. The analogy is limited because a planner must specify whether it measures action count, monetary cost, or elapsed time. Parallel cooking time and total work are different objectives and should not be mixed.

Worked example

Consider three original unit-cost planning examples, each starting with its goal facts false.

First, goals A and B have independent actions SetA and SetB. SetA makes A true and affects nothing else; SetB makes B true and affects nothing else. Each isolated goal costs one action, and achieving both costs two. The additive estimate is exact for this deliberately separated action model.

Second, replace those actions with one action SetBoth, which makes A and B true together. Each isolated goal still costs one action. Adding gives two, but the joint optimum is one. The sum overestimates because it counts the same useful action twice. It is not admissible for this example.

Third, let the goals be Clean and Painted. CleanSurface makes Clean true and Painted false. QuickPaint makes Painted true and Clean false. Protect requires Clean and makes Protected true. CarefulPaint requires Protected, makes Painted true, and preserves Clean. All actions cost one; initially Clean, Painted, and Protected are false.

Clean alone costs one using CleanSurface; Painted alone costs one using QuickPaint. Their sum is two. Yet neither order of those two actions leaves both goals true. The shortest successful joint plan is CleanSurface, Protect, CarefulPaint, costing three. No one-action plan achieves both, and the only action that can add Painted while preserving Clean needs the extra protection step. Here the independence estimate is too low.

Illustrative case study

Fictional case: a project-planning assistant estimates two reporting deliverables separately and adds the figures. A reviewer notices that both estimates include preparing the same dataset, while one also assumes access to a specialist occupied by the other task.

The team models the shared preparation and resource restriction before relying on the combined estimate. It retains the original figures as isolated-task estimates. This fictional case illustrates both directions of error without claiming an optimal real project plan.

Common misconceptions and mistakes

Subgoals are not independent merely because they have different names or owners. Solving each one optimally does not necessarily make the concatenated plan feasible or optimal. Positive interaction can make an additive estimate pessimistic, while negative interaction can make it optimistic.

A delete-relaxed planning problem and a subgoal-independence assumption are also distinct simplifications. Ignoring harmful effects removes some negative interactions but can leave opportunities to share actions. Consequently, combining relaxations requires its own reasoning about what the resulting number represents.

Business use

Use the assumption as an explicit modeling shortcut when a quick estimate is useful, then test representative cases with shared prerequisites and competing effects. Identify the unit being added and the reason individual estimates can or cannot share costs.

If a search system promises optimality, document the lower-bound argument for its heuristic rather than relying on an intuitive claim of separation. If the application deliberately favors faster search over optimality, a non-admissible estimate may still be useful, but that tradeoff should be stated accurately.

Check your understanding

One action achieves two required goals and costs five. Each goal alone also costs five. Is their additive cost estimate of ten a lower bound?

Answer: No. The joint goal costs five, so ten overestimates and is not an admissible lower bound for that state.

Related terms

Relaxed problem
Partial-order planning
Planning heuristic
admissibility
delete relaxation
goal interaction
action cost
cost partitioning

Learn next

Write a small action model and compute isolated and joint goal costs by hand. Add one shared action, then one harmful effect, and observe how the difference changes. Next study admissible heuristics and how cost partitioning avoids charging the same action cost repeatedly.

Sources

Russell and Norvig, Planning chapter, subgoal-independence assumption and positive and negative interactions: https://aima.cs.berkeley.edu/newchap11.pdf The three action models and reporting case are original illustrations. Costs are action counts, not elapsed-time schedules, and the stated effects exhaust the toy models.

Previous: Subdivision bifiltration Next: Subgradient