Motivation
A system that stores facts must distinguish what it knows from what it merely fails to know. If a database contains no statement that a room is occupied, this does not by itself prove that the room is empty. A system that acts needs a second distinction: a statement true before an action may become false afterwards. Combining reasoning and action therefore requires both a semantics for knowledge and a semantics for change.
Consider a service robot moving parcels between rooms. A rule can express that a parcel is accessible when it is in the robot's room. An action can move the robot while leaving the parcel in its old room. If every fact were simply accumulated forever, the robot would soon appear to occupy several rooms at once. Conversely, deleting every old fact would lose information about parcels unaffected by the move. A representation must say what an action changes and what it preserves.
This unit develops a deliberately restricted setting in which the main correctness arguments can be proved in full. Finite ground Horn rules provide a transparent inference procedure, and propositional STRIPS provides an explicit transition model. These fragments do not solve unrestricted first-order reasoning or every planning problem. They expose the assumptions that more expressive systems must manage.
Definitions
Definition 2.1.1
(First-order languages and interpretations)
A first-order language contains constants, variables, function symbols and predicate symbols of specified arities. Terms name objects relative to an interpretation. An atomic formula such as asserts a relation; formulas are built using logical connectives and quantifiers. An interpretation specifies a nonempty domain, meanings for constants and functions, and relations for predicates. A variable assignment supplies values for free variables. A sentence has no free variables and has a truth value in an interpretation.
Definition 2.1.2
(Entailment, derivation, soundness and completeness)
A knowledge base entails a sentence , written , if every interpretation satisfying all sentences in also satisfies . A proof system derives , written , by applying its syntactic rules. Soundness means derivability implies entailment. Completeness means entailment implies derivability for the stated language and procedure. Neither property means that every sentence is either entailed or refuted by an incomplete knowledge base.
Quantifier order matters. The sentence allows the witness to depend on . The sentence requires one shared witness. Substitution must also avoid capture: replacing a free variable by a term containing a variable that becomes bound can change the assertion.
Definition 2.1.3
(Definite Horn rules, forward chaining and models)
For a finite computable fragment, fix a finite set of ground atoms and rules
These are definite Horn rules. A fact is a rule with no premises. Let be the given facts. Starting at , define
A model of these rules is a subset containing the facts and closed under every rule. Atoms in are true; the others are false in that propositional interpretation. This definition provides semantics for the finite fragment without claiming to enumerate arbitrary first-order interpretations.
Definition 2.1.4
(STRIPS states, actions and plans)
For planning, fix a finite set of fluents. A fully specified state is a subset , using a closed-world convention: a fluent outside is false in that state. An action has positive preconditions , add effects and delete effects , with disjoint add and delete sets. It is applicable when , and its successor is
A plan is a finite applicable action sequence. It achieves positive goal set when the final state contains . Preconditions and goals with arbitrary negation, conditional effects or uncertain outcomes lie outside this basic formalism. The closed-world state convention is a modeling choice, distinct from open-world entailment in a general knowledge base.
Theorem/Proposition
Theorem 2.1.5
(Finite forward chaining reaches the least model)
For a finite ground definite-Horn knowledge base over , the increasing sequence stabilizes after at most strict expansions. Its fixed point is the least model under inclusion. A ground atom belongs to if and only if it is true in every propositional model of the facts and rules.
Proposition 2.1.6
(Regression verifies a final planning step)
Let be an action with disjoint add and delete sets, a positive goal set, and a state. If , no application of can achieve . Otherwise define
Then holds exactly when is applicable in and .
Regression replaces a desired final state condition by a condition before an action. It does not certify that the predecessor condition is reachable from the initial state. Searching backwards still needs a reachability argument, just as searching forwards still needs applicable transitions.
Proof sketch or proof idea
Proof
(The closure is a model below every model)
The sets are increasing by definition. Each strict change inserts at least one previously absent atom, so at most strict changes are possible. At a fixed point every rule whose premises are present has its conclusion present, so the fixed point is a model containing .
To prove leastness, take any model . Since , the inclusion holds. If , every rule fired in the next round has all premises in and hence its head in . Therefore . Induction gives . An atom in is consequently true in every model. If an atom is absent from , this fixed point itself is a model in which it is false, so it is not entailed. This proves the equivalence as well as soundness of the finite procedure.
Proof X-ray
Completeness comes from constructing a countermodel
Soundness alone follows from checking that each rule application preserves truth. The reverse direction requires something stronger: the final closure must itself be an admissible model. That construction provides a countermodel for every underived atom. It works for definite Horn rules; adding arbitrary negation or disjunction changes the argument and can destroy the least-model property.
Proof
(Goals made by the action and goals that persist)
For the regression theorem, suppose a goal atom belongs to the delete set. The disjointness assumption means it is not re-added, so it is absent after the action. Achievement is impossible. Otherwise take an applicable action. A goal atom in the add set is guaranteed after the transition. A goal atom outside the add set must have been true beforehand and, by compatibility, is not deleted. Thus achieving is equivalent to already containing . Including the preconditions gives exactly . The same reasoning in reverse proves sufficiency.
By induction on sequence length, repeatedly checking applicability and applying produces exactly the state described by this STRIPS model. This is a verification theorem about the model, not proof that a physical robot's sensors and actuators satisfy it. If a move can fail, its deterministic transition should not silently be treated as a real-world certainty.
One useful planning invariant is “the robot occupies exactly one location.” Suppose this holds initially. If every move has a precondition specifying its current location, deletes that location and adds one distinct new location, and no other action changes robot-location fluents, then the invariant is preserved. The induction uses the initial uniqueness to exclude any third location surviving the move. Merely adding a new location without deleting the old one would fail the invariant immediately.
Worked examples
Worked example 2.1.7
(Deriving accessibility without reversing a rule)
Let facts be and , and let a ground rule say their conjunction implies . Forward chaining adds accessibility in one round. If the only fact were , the rule would not justify either location fact: implication is not equivalence. There are models where accessibility is true and both premises are false. Storing the rule therefore licenses the forward inference, not the converse inference.
Worked example 2.1.8
(A three-action transport plan)
Use fluents , meaning robot at room A or B, parcel at A or B, and robot carrying the parcel. Initially . Pickup has preconditions , adds and deletes . Move has precondition , adds and deletes . Drop has preconditions , adds and deletes . The sequence pickup, move, drop produces , then , then . The goal is achieved. There is one room-to-room move and three actions in total.
Worked example 2.1.9
(Regressing a delivery goal)
For the preceding drop action and , no goal is deleted. Since drop adds , regression yields . Regressing that set through move removes the added and adds its precondition, giving . Regressing once more through pickup yields , exactly the initial state. In contrast, regressing through drop fails: drop deletes . One cannot demand both continued carrying and completed dropping in this model.
Common mistakes
Counterexample mode
An existential witness need not be shared
Take domain and let mean . Every has a matching , so is true. There is no one equal to both and , so is false. The repair is to preserve quantifier order and record which earlier variables a witness may depend on.
Common mistake
(Failing to derive an atom is not deriving its negation)
Do not confuse a least-model inference result with a universal closed-world policy. Failure to derive means is not entailed in the Horn fragment; it does not mean the original facts entail . The least model makes false, but another model may make it true. Inconsistent general classical knowledge bases create another issue: if there are no models, every sentence is vacuously entailed. Consistency checks are therefore substantive when using entailment for decision making.
Common mistake
(Links and slots need an explicit semantics)
Semantic networks and frames organize related knowledge, but arrows and slots need an explicit semantics. A link “penguin is-a bird” and a default slot “birds fly” cannot both be read as unconditional universal implications if penguins are intended exceptions. Scripts describe typical event sequences, not necessarily every legal sequence. They can be useful representations while requiring separate rules for exceptions, missing steps and temporal order.
Concept lensStructural
Planning as graph search
The STRIPS state space is a directed graph with at most states. Applicable actions generate its edges, and a goal set specifies many acceptable vertices. Forward search operates on complete states; regression operates on sufficient conditions for reaching a goal. This connects planning to search without confusing a partial goal condition with one fully specified state.
The frame problem asks how to represent what remains unchanged. The transition formula answers it within this restricted setting by preserving fluents outside the delete set. It does not by itself address unmodeled indirect effects. For example, deleting “support under object” may require a separate account of falling; a bare add/delete list does not invent physical consequences.
Variables over finitely many constants still ground out finitely, but function symbols can make the closure infinite.
A path to generalization
What changes when rules contain variables?
Variables over finitely many constants still ground out finitely, but function symbols can make the closure infinite.
A rule with variables over a finite set of constants stands for finitely many ground rules, so the finite theorem applies after grounding. Adding a function symbol changes this: from the fact and the rule , forward chaining derives for every , so the closure is infinite and no round is the last.
Summary
Entailment quantifies over models; derivation manipulates sentences using rules. Finite Horn closure is sound and complete for ground atomic consequences because it constructs a least model. STRIPS makes action effects explicit, while regression moves positive goal requirements backwards through a chosen action. Both inference and planning are reliable only relative to their representation assumptions. Check quantifiers, state conventions and invariants before trusting a computed answer.
Exercises
Quick check
(Let facts be and rules be , , , and . Compute the synchronous closure sequence and prove whether is entailed. What changes if the initial fact is removed?)
Apply the rules round by round, using only the previous layer.
Solution · Answer
The synchronous sets are , , , , after which nothing changes. The theorem shows is entailed. Without the initial fact, the empty set is already closed: no rule has all its premises present. The cycles do not generate their own supporting evidence, and is not entailed. A model containing every atom can still exist; leastness, rather than uniqueness of all models, is what matters.
Quick check
(Give a model in which and hold but does not. Use it to distinguish affirming the consequent from a sound inference. Then show that together with entails in classical logic.)
Look for a valuation that makes the premise false and the conclusion true.
Solution · Answer
Take the valuation , . The implication and conclusion hold, but its premise fails, so the proposed reverse inference has a countermodel. For the second assertion, any model satisfying has false. If it made true, would be false. Hence every model of the two premises makes false, proving entailment of .
Quick check
(An action has preconditions , adds and deletes . Regress goals and . For the compatible goal, identify exactly which predecessor states suffice.)
Apply the regression formula to each goal and test the delete condition first.
Solution · Answer
For the delete set is disjoint from the goal, and regression is . Exactly states containing both and suffice; the truth of or beforehand is irrelevant. For the action deletes the desired without re-adding it, so no predecessor state can achieve the goal by this final action. This does not imply that the goal is unreachable using a different final action.
Exercise 2.1.10
(Prove that a robot-location invariant is preserved by the move action in the text, then construct a concrete initial state and faulty action that violate it when the delete effect is omitted. Explain why a precondition alone cannot repair that omission.)
Core
Solution(4)
- 1
Assume one location and an applicable move
Assume exactly one robot-location fluent is true and that an applicable move goes from to . Its precondition ensures that is that unique true fluent.
- 2
Delete the old location and add the new one
Key step
Deleting removes it, and adding creates exactly one location; all other location fluents remain false. Other actions preserve the invariant by assumption, so induction on plan length handles a whole plan.
- 3
Omit the delete effect
The faulty move from that only adds produces : two locations, so the invariant fails.
- 4
Why a precondition cannot repair the omission
The precondition was satisfied and therefore does not prevent the error. A precondition constrains when an action may start, while delete effects determine what ceases to hold.