Can a pessimistic description be exact?

Yes. Its guaranteed outcomes and cost bounds may coincide with the exact description.

Can it provide no useful guarantee?

Yes. A vacuous description may leave all outcomes unbounded, though it offers little help in certifying a plan.

Does pessimistic mean low probability?

No. The term refers to a sound abstraction or bound, not a likelihood estimate.

AI Glossary / Graphs and symbolic AI / Advanced

Pessimistic description

Definition

A pessimistic description is a conservative description of a high-level action in angelic hierarchical planning. It identifies outcomes that some permitted refinement can actually achieve and can provide upper bounds on the cost of reaching those outcomes.

What it means

A high-level action such as move-to-storage stands for several possible sequences of lower-level actions. An exact description would characterize everything achievable by those refinements and their best costs, but computing that description can be expensive.

A pessimistic description deliberately makes fewer claims. If it says a state is reachable with cost at most a stated bound, that claim must be supported by the action's refinement semantics. It may omit other reachable states or give a loose cost bound.

Pessimistic does not mean assuming that every possible refinement fails or taking the worst outcome of an adversarial environment. In angelic planning, the agent chooses the refinement. The description concerns what it can ensure by choosing appropriately within the modeled hierarchy.

How it works

Define the high-level action's permitted refinements and the initial state. The exact reachable set consists of states produced by some valid primitive refinement. A pessimistic reachable-set description selects a subset for which reachability is guaranteed by the abstraction's semantics.

In a cost-based formulation, the exact value for a target state is the minimum cost of a refinement reaching it. A pessimistic value is at least that minimum. A finite pessimistic value therefore certifies an achievable cost bound, while an infinite value may merely mean that the description supplies no guarantee.

An optimistic description provides the complementary type of bound: it can include possible outcomes not actually reachable and underestimate cost. Comparing the two helps decide whether to refine further, reject a candidate or certify properties of an abstract plan.

These guarantees depend on sound descriptions, valid composition and the underlying action model. Calling an estimate conservative does not prove that it satisfies the required inequalities.

Three practical examples

1. Hierarchical navigation: A planner knows a straightforward permitted route reaches a destination within 12 cost units, even though another refinement might do better. That route supports a pessimistic bound.

2. Task decomposition: A high-level packing action guarantees one supported arrangement while leaving other arrangements unspecified. Omitting them does not prove they are impossible.

3. Search control: A planner compares a candidate's optimistic lower bound with another candidate's supported upper bound to identify where further refinement can still improve the answer.

Think of it this way

Think of a planner saying, “I can definitely provide this option within this budget,” while leaving open the possibility of more options or a lower price.

The analogy concerns a mathematical guarantee under a model. It is not a probability forecast, a promise about unmodeled disruptions or a statement that every implementation of the high-level action stays within the budget.

Worked example

Suppose a high-level action has permitted refinements that reach state G with costs 8 and 11, and state H with cost 13. No refinement reaches J. The exact minimum costs are therefore G: 8, H: 13 and J: infinity.

A valid pessimistic description could give G: 11 and H: infinity, leaving J at infinity. The bound 11 is conservative because a permitted refinement reaches G within that cost. Reporting infinity for H withholds a guarantee; it does not deny the known refinement of cost 13.

A purported pessimistic bound of G: 6 would be invalid because no permitted refinement reaches G that cheaply. A finite bound for J would also be invalid.

If an optimistic description gives G a lower bound of 5, the optimal refinement cost lies between 5 and 11. Refining the description to establish both bounds at 8 would certify the optimum for that target under the model.

Illustrative case study

In a fictional project, Cedar Planning uses hierarchical delivery actions. An engineer initially treats every destination omitted from a pessimistic description as unreachable and discards several tasks prematurely.

The team separates “not guaranteed by this description” from “proven impossible.” It uses optimistic information for impossibility tests where justified and refines uncertain high-level actions when further detail could resolve the question.

The case illustrates the direction of the abstraction. A conservative guarantee supports positive claims about some achievable outcomes; its silence is not a complete description of everything the action can do.

Common misconceptions and mistakes

Pessimistic means every refinement has the stated outcome. The relevant guarantee can be the existence of a suitable refinement chosen by the agent.
Omitted states are necessarily unreachable. The description may be deliberately incomplete.
A pessimistic cost is a lower bound. In cost-minimization formulations, it is an upper bound on the best achievable cost.
Pessimistic descriptions model an adversary's worst outcome. Angelic refinement choice has different semantics.
A loose estimate is automatically sound. It must still respect the model's reachability and bound requirements.

Business use

The concept matters when assessing claims that a planner can reason correctly without expanding every abstract action into detailed steps. The useful question is what the abstraction guarantees and how those guarantees are preserved through composition.

Request a clear distinction between optimistic possibilities, pessimistic guarantees and exact primitive plans. Confirm whether the planner proves goal reachability, bounds cost, produces an executable refinement or only guides further search.

For practical use, verify that the hierarchy permits the actions needed for the task. A guarantee relative to a restrictive hierarchy is not a guarantee of optimality among every imaginable real-world plan. Changed action costs or effects can invalidate previously sound descriptions.

Check your understanding

Why does H having an infinite pessimistic value not prove that H is unreachable in the example?

Answer: Infinity means this description supplies no finite guarantee for H. The permitted refinement reaching H at cost 13 still exists.

Related terms

Angelic semantics
High-level action
Reachable set
Admissible heuristic
hierarchical planning
refinement
optimistic description
upper bound

Learn next

List several primitive refinements of one abstract action with their outcomes and costs. Construct an incomplete but sound pessimistic description, then deliberately propose an invalid cost bound and explain precisely which refinement evidence it contradicts.

Sources

Marthi, Russell and Wolfe define optimistic and pessimistic descriptions and their composed cost bounds in the revised technical report: https://aima.cs.berkeley.edu/~russell/papers/tr-hlastar-revised.pdf

The three-state cost table and Cedar Planning case are original illustrations. They concern the report's angelic hierarchical-planning semantics, not general risk forecasting.

Previous: Perturb-and-MAP sampling Next: Phase-based magnification