Glossary

This glossary collects technical terms introduced throughout the textbook.

Abstraction

A mapping from the states of a transition system to a smaller set of abstract states, preserving goal states and transitions. Abstraction heuristics use the optimal goal distance in the abstract system as an admissible estimate for the real system.

Action

An operation available to an agent. In planning, actions are modeled by operators that specify when they are applicable (precondition) and how they change the world (effect).

Action Landmark

An operator that must be applied in every solution plan. A disjunctive action landmark is a set of operators of which at least one must be applied in every plan.

Admissible Heuristic

A heuristic $h$ that never overestimates the true optimal cost: $h(s) \le h^*(s)$ for all states $s$.

AND/OR Graph

A directed graph whose nodes are classified as AND nodes (all predecessors must be achieved) or OR nodes (at least one predecessor must be achieved). Relaxed task graphs are AND/OR graphs.

Atomic Projection

The transition system obtained by projecting an FDR planning task onto a single variable. Atomic projections are the starting factors in merge-and-shrink heuristics.

Bisimulation

An equivalence relation on transition-system states that preserves goal status and matching labeled transitions. In merge-and-shrink, bisimulation shrinking merges states without losing goal-distance information.

Canonical PDB Heuristic

A way to combine a collection of pattern database heuristics by taking the maximum over admissible sums of mutually orthogonal pattern groups.

Choice Function

A function that selects at most one predecessor for each OR node in an AND/OR graph, deciding how subgoals are achieved. Used to define best achievers.

Classical Planning

The offline, discrete, deterministic, fully observable, single-agent, sequential form of planning emphasized in this course.

Consistent Heuristic

A heuristic $h$ satisfying $h(s) \le \mathit{cost}(o) + h(s')$ for every transition $s \xrightarrow{o} s'$. Consistency implies admissibility.

Cost Partitioning

A method for combining multiple admissible heuristics additively by distributing operator costs among them such that each operator’s total partitioned cost does not exceed its original cost.

Disjunctive Action Landmark

A set of operators such that every valid plan must contain at least one operator from the set.

Delete Relaxation

A simplification of a planning task (in positive normal form) where all negative (delete) effects are removed. Variables can only become true, never false, making the relaxed task easier to solve.

Effect

A structured description of how an operator changes the state. Effects can be empty ($\top$), atomic ($v$ or $\neg v$), conjunctive ($e \land e'$), or conditional ($\chi \triangleright e$).

Fact Landmark

An atomic proposition (or variable-value pair in FDR) that must be true in at least one state along every solution path.

Factored Transition System

A representation of a transition system as a collection of smaller transition systems, called factors, that can be combined by synchronized product.

Finite-Domain Representation (FDR)

A planning task representation using state variables with arbitrary finite domains (not just Boolean). Often more compact than propositional representation.

Formula Landmark

A logical formula that must be satisfied in at least one state along every solution path.

Goal

A condition or set of conditions that a plan should make true.

Heuristic

A function $h : S \to \mathbb{N}_0 \cup \{\infty\}$ estimating the cost of reaching a goal from a given state. Used to guide search.

h⁺

The optimal delete-relaxation heuristic: the cost of an optimal plan for the delete-relaxed task. Admissible but NP-hard to compute.

h^add

A delete-relaxation heuristic that sums costs at AND nodes in the relaxed task graph. Safe and goal-aware but not admissible (prone to overcounting).

h^FF

The FF heuristic: fixes $h^{\mathrm{add}}$‘s overcounting by counting each effect node in the best achiever graph only once. Not admissible but highly effective in practice.

h^max

A delete-relaxation heuristic that takes the maximum at AND nodes in the relaxed task graph. Admissible but often a weak lower bound.

Landmark

A property that must hold in every solution of a planning task. See also: fact landmark, action landmark, disjunctive action landmark.

Label Reduction

A merge-and-shrink technique that combines labels with equal cost and identical behavior in the current factors, enabling stronger later shrinking.

LM-Cut

An admissible delete-relaxation heuristic that repeatedly extracts cut landmarks from a relaxed task graph, charges the minimum cut cost, reduces action costs, and continues until the relaxed goal cost becomes zero.

Merge-and-Shrink

An abstraction framework that starts from atomic projections and iteratively merges (synchronized product) and shrinks (abstracts) factors to produce an admissible heuristic. Generalizes pattern databases.

Minimum Hitting Set

A set that intersects every set in a family of sets. In planning, minimum hitting set heuristics choose a cheapest set of actions that hits all known disjunctive action landmarks.

Model-Based Approach

An approach that reasons from an explicit description of how the world works, rather than relying only on observed data.

Network Flow Heuristic

A constraint-based heuristic that writes production-consumption balance constraints over operator counts and minimizes total operator cost subject to those constraints.

Operator

A structured object with a precondition (formula), effect, and cost. Operators are the formal representation of actions in a planning task.

Operator Counting

A constraint-based heuristic framework that introduces variables $\mathrm{Count}_o$ for how often each operator is used and minimizes total cost subject to linear constraints that hold in every solution.

Orthogonal Abstractions

Abstractions that charge disjoint parts of the planning task, commonly disjoint variable sets in unit-cost pattern databases, so their heuristic values can be safely added.

Optimal Planning

Finding a plan with minimum cost among all valid plans for a planning task.

Pattern Database (PDB)

A heuristic obtained by projecting the state space onto a subset of variables (the pattern), computing all goal distances in the abstract space, and storing them in a lookup table.

Plan

A sequence of operators that transforms the initial state into a goal state.

Planning

The task of automatically deciding which actions should be applied, and in which order, to reach a goal.

Planning Task

A formal description $\Pi = \langle V, I, O, \gamma \rangle$ of a planning problem: state variables, initial state, operators, and goal formula.

Post-Hoc Optimization

A method for combining abstraction heuristics by solving for the best cost partition for the current state at heuristic-evaluation time.

Potential Heuristic

A heuristic $h^{\mathrm{pot}}(s) = \sum_{v,d} \mathit{pot}(v,d) \cdot [s(v) = d]$ where potentials are optimized via linear programming to ensure admissibility. The dual of operator counting.

Progression

Forward search from the initial state toward the goal. The search space coincides with the planning task’s state space.

Propositional Logic

A formal logic over atomic propositions with connectives $\neg$, $\land$, $\lor$, $\to$, $\leftrightarrow$. Used to compactly represent sets of states and operator conditions.

Propositional State Variable

A Boolean state variable (true or false). States are truth assignments to a set of such variables.

Positive Normal Form (PNF)

A normal form for planning tasks where no negation symbols appear in preconditions, effect conditions, or the goal, and all effects are flat.

Regression

Backward search from the goal toward the initial state. Each search state is a formula representing a set of world states.

Relaxed Planning Task

A planning task obtained by applying delete relaxation. Plans for relaxed tasks (relaxed plans) can be used to derive heuristics.

Relaxed Task Graph (RTG)

An AND/OR graph encoding the structure of a delete-relaxed planning task. Used to compute $h^{\max}$, $h^{\mathrm{add}}$, and $h^{\mathrm{FF}}$.

Satisficing Planning

Finding any valid plan for a planning task, without guaranteeing optimality.

SAT Planning

A planning approach that encodes the existence of a plan of a fixed horizon as a propositional satisfiability problem and searches over increasing horizons.

SAS⁺

The FDR analogue of STRIPS: operators have conjunctive preconditions and conflict-free conjunctive effects over finite-domain variables.

State

A representation of the relevant facts about the world at a point in time. Formally, an assignment to a set of state variables.

State Explosion Problem

The phenomenon that the number of states in a planning task grows exponentially with the size of the input description.

State-Space Search

Search in a graph where states are nodes and action applications are edges.

STRIPS

A restricted form of planning tasks where operators have conjunctive preconditions and conflict-free atomic effects, and the goal is a conjunction of atoms. Named after the STanford Research Institute Problem Solver.

Symbolic Search

A search approach that manipulates compact representations of sets of states, such as BDDs, instead of enumerating individual states one at a time.

Synchronized Product

An operation that combines two transition systems by taking the Cartesian product of their state spaces and requiring both to agree on label transitions. Used in merge-and-shrink abstractions.

Transition System

A mathematical model $\mathcal{T} = \langle S, L, c, T, s_0, S_\star \rangle$ consisting of states, labels, costs, transitions, an initial state, and goal states. Also called a state space.