Finite-Domain Representation

Source slide: E1 Planning Tasks in Finite-Domain Representation

The propositional representation used earlier in the course is mathematically clean: every state variable is either true or false. But many planning domains are not naturally Boolean. A robot is in exactly one room. A package is at exactly one location. A block is either on the table or on one other block, not on several places at once.

Finite-domain representation, usually abbreviated FDR, models such choices directly. Instead of encoding each possible value as a separate Boolean variable, FDR uses variables with finite sets of possible values. This often gives a smaller and more faithful state space, which is especially important before introducing abstraction and pattern database heuristics.

Why Boolean Variables Can Be Wasteful

Consider a block $A$ whose position can be the table, block $B$, or block $C$. A propositional encoding might use atoms such as $\mathit{on}(A,\mathit{table})$, $\mathit{on}(A,B)$, and $\mathit{on}(A,C)$. The intended meaning is that exactly one of these atoms should be true.

However, the propositional state space itself does not know that. It also contains syntactic states where two of these atoms are true, or none of them is true. Those states may be unreachable or physically meaningless, but a planner or heuristic may still need to account for them unless additional constraints are derived.

FDR builds the exclusivity into the representation. We use one variable, say $\mathit{pos}_A$, whose domain is

$$\mathsf{dom}(\mathit{pos}_A) = \{\mathit{table}, B, C\}.$$

A state assigns exactly one value to $\mathit{pos}_A$. The impossible combinations are no longer syntactic states.

Finite-Domain State Variables

The basic object in FDR is a variable with a finite non-empty domain.

Definition: Finite-domain state variable

A finite-domain state variable $v$ is a state variable together with a finite non-empty set $\mathsf{dom}(v)$ of possible values. In every state, $v$ has exactly one value from $\mathsf{dom}(v)$.

Boolean variables are the special case where $\mathsf{dom}(v)=\{\top,\bot\}$. FDR simply allows larger finite domains.

A state is a total assignment:

$$s : V \to \bigcup_{v \in V} \mathsf{dom}(v), \qquad s(v) \in \mathsf{dom}(v) \text{ for every } v \in V.$$

The condition $s(v) \in \mathsf{dom}(v)$ is important. It says that the value assigned to each variable must come from that variable’s own domain, not merely from some domain somewhere in the task.

Atoms and Formulas

In propositional planning, an atom is a Boolean variable. In FDR, an atom states that a finite-domain variable has a particular value.

Definition: FDR atom

An FDR atom has the form $v=d$, where $v \in V$ and $d \in \mathsf{dom}(v)$. A state $s$ satisfies the atom $v=d$ exactly when $s(v)=d$.

For example, $\mathit{pos}_A=B$ says that block $A$ is on block $B$. The atom is true in a state if the variable $\mathit{pos}_A$ is assigned the value $B$ in that state.

Formulas are built from such atoms using the usual logical connectives. We write $s \models \varphi$ when formula $\varphi$ is true in state $s$. This satisfaction relation works just as before, except that the atomic tests are equalities of the form $v=d$.

Propositional atoms can be seen as abbreviations: $p$ corresponds to $p=\top$, and $\neg p$ corresponds to $p=\bot$.

Effects as Assignments

The main syntactic change in operators is that effects assign values rather than setting Boolean facts to true or false.

An atomic FDR effect has the form:

$$v := d.$$

It means that after the operator is applied, variable $v$ has value $d$. Variables not mentioned in the effect keep their old values. This is the same frame assumption as in the propositional setting: an action changes only what its effect says it changes.

For example, an operator that moves a robot from room $r_1$ to room $r_2$ might have the effect

$$\mathit{loc} := r_2.$$

There is no separate delete effect saying that the robot is no longer at $r_1$. Since $\mathit{loc}$ has exactly one value, assigning $r_2$ automatically replaces the previous value.

Conflict-Free Effects

An operator effect must not assign two different values to the same variable at the same time. Otherwise, the successor state would be ambiguous.

Definition: Conflict-free effect

An FDR effect is conflict-free if, for every variable $v$, it contains at most one atomic assignment $v := d$.

Thus the effect

$$\mathit{loc} := r_2 \land \mathit{battery} := \mathit{low}$$

is conflict-free, because it assigns different variables. But

$$\mathit{loc} := r_2 \land \mathit{loc} := r_3$$

is not conflict-free when $r_2 \ne r_3$.

This restriction is the FDR analogue of avoiding contradictory add and delete effects. It ensures that applying an applicable operator produces one well-defined successor state.

FDR Planning Tasks

The planning-task tuple keeps the same shape as before. The difference is in the meaning of variables, atoms, and effects.

Definition: FDR planning task

An FDR planning task is a tuple

$$\Pi = \langle V,I,O,\gamma\rangle$$

where:

• $V$ is a finite set of finite-domain state variables;
• $I$ is an initial state, assigning one value to each variable in $V$;
• $O$ is a finite set of operators with preconditions and conflict-free effects over FDR atoms;
• $\gamma$ is a goal formula over FDR atoms.

An operator $o$ is applicable in state $s$ when $s \models \mathit{pre}(o)$. If $o$ is applicable, its successor state $s'$ is obtained by applying its assignments:

$$s'(v) = \begin{cases} d & \text{if } v := d \text{ occurs in } \mathit{eff}(o),\\ s(v) & \text{otherwise}. \end{cases}$$

A plan is a sequence of operators $\pi=\langle o_1,\ldots,o_n\rangle$ such that repeated application from $I$ reaches a state satisfying $\gamma$.

A Small Blocks-World Comparison

The slides use blocks world to show why FDR can be much more compact. With three blocks, a propositional encoding may introduce one Boolean variable for each relevant “block is at location” claim. This creates a large syntactic space because each Boolean variable can independently be true or false.

The problem is that these choices are not actually independent. A block cannot be on two different supports at the same time. If the encoding has nine Boolean atoms, it has up to $2^9=512$ syntactic truth assignments, even though most do not describe legal blocks-world configurations.

An FDR encoding instead uses one position variable per block. If each block has three relevant position values, the syntactic state space has $3^3=27$ assignments. This is still larger than the number of physically reachable states, but it is far closer to the intended domain; the most obvious exclusivity constraints are represented by construction.

The lesson is not that FDR magically removes all impossible states. Some invariants, such as whether two blocks are stacked on the same block, may still require additional structure. The point is that multi-valued variables capture many common exclusivity constraints directly.

SAS Plus Operators

Just as propositional planning has STRIPS as a simple and important normal form, FDR has SAS$^+$.

Definition: SAS$^+$ operator

A SAS$^+$ operator has a precondition that is a conjunction of atoms $v=d$ and an effect that is a conflict-free conjunction of assignments $v:=d$.

There are no disjunctions or negations in the precondition, and no conditional effects in the basic SAS$^+$ form. This makes operators easy for algorithms to inspect: preconditions are required variable-value pairs, and effects are replacement assignments.

For example, a move operator might be written informally as:

$$\mathit{pre}(o) = (\mathit{loc}=r_1) \land (\mathit{clearPath}= \mathit{yes}),$$ $$\mathit{eff}(o) = (\mathit{loc}:=r_2).$$

The operator says: if the robot is at $r_1$ and the path is clear, then after moving, its location is $r_2$. Other variables, such as battery level or package positions, are unchanged unless mentioned.

Expressiveness and Translation

FDR and propositional planning can represent the same classical planning problems, but they organize the information differently.

A propositional task can be viewed as an FDR task by treating each Boolean variable as a finite-domain variable with domain $\{\top,\bot\}$. In the other direction, an FDR atom $v=d$ can be translated into a propositional atom, with extra constraints ensuring that exactly one value of $v$ holds at a time.

In practice, planners often obtain FDR tasks through domain analysis or invariant synthesis. The translator detects groups of mutually exclusive propositions and turns them into multi-valued variables. This is one reason FDR is common in modern classical planning systems: it exposes structure that would otherwise be hidden in a flat propositional encoding.

Normal Form

For algorithmic work, it is convenient to assume that operators are in a clean normal form. Informally, this means that the same variable is not repeated in incompatible ways inside a precondition or effect.

In a normalized FDR operator:

• the precondition does not require two different values for the same variable;
• the effect is conflict-free;
• redundant repeated atoms are removed.

This is mostly a bookkeeping issue, but it prevents accidental ambiguity. If a precondition contained both $v=a$ and $v=b$ with $a \ne b$, the operator could never be applicable. If an effect assigned both $v:=a$ and $v:=b$, the successor would not be defined. Normalization makes these cases explicit.

Common Mistakes

The most common mistake is to treat FDR variables as if their possible values were independent Boolean facts. They are not. The statement $v=d$ being true already means that $v=d'$ is false for every other value $d' \ne d$ in the same domain.

A second mistake is to think that FDR only saves memory. The compactness also changes what structure is visible to heuristics. Abstraction methods, especially pattern databases, rely on projecting over variables. Projecting a meaningful multi-valued variable is often cleaner than projecting a collection of Boolean atoms plus hidden mutex constraints.

Finally, remember that FDR reduces useless syntactic states but does not necessarily remove all unreachable states. Reachability still depends on the operators.

Chapter Summary

Finite-domain representation generalizes propositional planning by allowing each state variable to take one value from a finite domain. FDR atoms have the form $v=d$, and effects assign values with $v:=d$. A conflict-free effect assigns at most one value to each variable, ensuring a unique successor state. SAS$^+$ is the simple FDR analogue of STRIPS, with conjunctive preconditions and conflict-free conjunctive effects. The main advantage of FDR is that it captures common exclusivity constraints directly, producing more compact and more informative representations for later heuristic methods.

Check Your Understanding

1. How does the atom $v=d$ differ from a propositional atom?
2. Why does assigning $\mathit{loc}:=r_2$ automatically mean the robot is no longer at its previous location?
3. What can go wrong if an effect is not conflict-free?
4. In the three-block example, why does the propositional encoding contain many meaningless syntactic states?
5. Why is FDR a natural preparation for abstraction and pattern database heuristics?