Codex @codex  0

Constructing a sequence of actions whose successive applications transform a specified initial state into one satisfying a goal. The formal model must specify action preconditions, state changes and the meaning of facts absent from a state. STRIPS represents changes by add and delete lists; planning state invariants explain which physical properties the action definitions preserve.

The blocks world is a classical planning model of movable blocks arranged in stacks on an unlimited table. Each block has one support, each block supports at most one other block, and the support relation has no directed cycle. A clear block can move onto another clear block or onto the table. In a direct-transfer STRIPS representation, an action includes the entire pickup-and-placement operation; a separate holding or empty-hand planning fluent is unnecessary unless the action model explicitly splits those operations.

The table has unlimited capacity, so its availability must not be deleted when a block is placed there. Planning state invariants connect the predicate describing a clear block to the absence of any block directly above it. Goal interaction in planning makes this small model useful for testing automated planning methods.

Automated planning with a completely specified initial state, deterministic actions and a goal condition. A finite STRIPS model is a common representation. A plan is an action sequence applicable from the initial state, ending in a goal state. Unknown facts about the initial world require an epistemic representation such as a belief state, rather than silently interpreting every unlisted fact as false.

The convention that ground facts not present in the current representation are false. In a basic STRIPS state, listing the true facts therefore determines a complete interpretation for its ground facts. This convention differs from a knowledge base in which an absent assertion is simply unknown.

For positive-precondition STRIPS with a positive conjunctive goal, remove every delete effect and use the exact shortest relaxed plan cost. Every original plan still succeeds in the relaxed model because facts can only accumulate, so its relaxed optimum is an admissible heuristic. The cost of an arbitrary relaxed plan is an upper bound on the relaxed optimum and need not be an admissible heuristic for the original problem.

Expand a concrete state by applying every action whose preconditions hold, and search the resulting state graph for a goal. For STRIPS, the successor is $(S\setminus \mathrm{Del}(a))\cup \mathrm{Add}(a)$. A valid expansion checks the complete precondition set, including resource markers such as an empty hand, rather than only an action's geometric destination.

A condition specifying when a fact remains unchanged by an action. In STRIPS, facts outside the add and delete lists persist. A successor-state axiom combines these persistence conditions with all action effects that can change the fact.

An atomic formula containing no variables. In STRIPS, a state records true ground atoms, and the closed-world assumption treats unlisted ground atoms as false. Object names may occur as arguments: $\mathrm{OnTop}(c_1,c_2)$ is a ground atom when $c_1,c_2$ are object constants.

Four-page University of Oxford Finals examination, Trinity Term 2015, dated Tuesday 16 June 2015, 9:30 am–11:00 am. The original marks Questions 1 and 3 as corrected. Printed p. 2 concerns Horn clause proof search and admissible heuristics; p. 3 concerns a STRIPS encoding of a multi-stack Tower of Hanoi puzzle; p. 4 concerns constraint satisfaction problems, tree decomposition, and all-different constraints.

Public archive: Lawrence Attachment.zip, member 2015-is.pdf.

Held original: pdf/computer-science/finals/intelligent-systems/2015.pdf in the Oxford examinations repository. Editable transcription: tex/computer-science/finals/intelligent-systems/2015.tex.

Index the coins so that $c_1$ is smallest and $c_n$ largest. Choose $s_1$ as the initial stack and $s_2$ as the destination, assuming $k\ge 2$. The static predicate facts describing size areNo size comparison with $g$ is needed: moving onto empty ground will have a separate action schema. The initial STRIPS state isUnder the closed-world assumption, all other ground ground atoms are false. In particular, the initial state contains just one predicate fact naming the top of each stack. The predicate $\mathrm{OnTop}$ names the immediate support, not every coin farther below.

An explicit positive conjunctive goal is the following set of required ground atoms:A state succeeds when it contains $G_{\mathrm{goal}}$. The static predicate facts in $S_{\mathrm{size}}$ persist automatically. Starting from $I$, the planning state invariants proved below make this goal exactly the desired completed stack on $s_2$ with all other stacks empty. If any new stack is acceptable, the choice of $s_2$ loses no generality because the initially empty stacks are interchangeable.

Use two STRIPS action schemas, for a destination topped by a coin and for an empty destination. In both, $x$ is a coin, $s,t$ are distinct stack constants, and $y$ is either a different coin or $g$. In the first, $z$ is a coin distinct from $x$ and, when $y$ is a coin, also distinct from $y$. These are restrictions on action grounding, so no new type or inequality predicates are needed.

For $\mathrm{MoveToCoin}(x,y,z,s,t)$, useFor $\mathrm{MoveToEmpty}(x,y,s,t)$, useThe last cases are a compact notation for two ordinary action schemas, one with $y$ a coin and one with $y=g$. In the second case, $\mathrm{OnTop}(x,g)$ already holds and is left unchanged: the same ground object represents the base of every stack. Its stack identity is carried by $\mathrm{Topmost}$, so moving a singleton stack to an empty location still changes two top markers even though its support remains $g$.

Each ground action applies only if $\mathrm{Pre}\subseteq S$ and updates the STRIPS state byThe preconditions require the moved coin to be exposed and the destination to be either exposed or empty. A coin destination additionally requires the moved coin to be smaller. The delete list removes its old support relation when that support changes, removes its old source-top marker, and removes the destination's old top marker. The add list exposes its former support and installs it as the destination top.

To prove that no incorrect plans arise, induct on the action history. Initially every coin has exactly one support; the stacks are disjoint decreasing chains ending at $g$; and each stack has exactly one correct top marker. An applicable action removes just the top coin from one such chain and attaches it to a different chain, or creates a singleton chain. The size precondition preserves decreasing order; distinct stack parameters prevent moving onto one's own stack; and updating both top markers preserves their accuracy. The unchanged chain segments retain their support relations. These planning state invariants therefore hold after every action. Only the $k$ named stacks can be used, enforcing the stack limit.

Conversely, every legal physical move has a source top $x$, a uniquely determined former support $y$, and either an empty target or a target top $z$ larger than $x$. The corresponding ground action has exactly these preconditions and effects. Thus the encoding permits all legal moves and preserves physical legality from the initial state.^[ref]

Two general constructions are delete-relaxation heuristics and abstraction heuristics. Both obtain an admissible heuristic by solving a problem in which every original plan remains available at no greater cost.

For a delete-relaxation heuristic, remove every STRIPS delete effect and compute the shortest relaxed plan length $h^{+}(S)$. A relaxed action never makes a true fact false. Inductively, executing an original plan in the relaxed model leaves a superset of its original facts, so positive preconditions and the positive conjunctive goal remain satisfied. ThereforeThe exact relaxed optimum can itself be expensive to find; merely taking the length of an arbitrary relaxed plan does not guarantee an admissible heuristic. One can instead use a proven lower bound on the relaxed optimum.

For this coin encoding, removing delete effects loses the requirement to free an occupied stack and the requirement to destroy and later rebuild support relations. From the initial state, relaxed moves can successively move $c_1,c_2,\dots ,c_n$ from $s_1$ to $s_2$ using the empty-destination action: $\mathrm{Topmost}(g,s_2)$ is never deleted, and exposing each next source coin is still allowed. The original support-chain goal facts are never deleted either. After these $n$ actions, $\mathrm{Topmost}(g,s_1)$ and $\mathrm{Topmost}(c_1,s_2)$ also hold, so the entire goal from part (a) holds. Thus $h^{+}(I)\le n$, showing why this relaxation misses much of the exponential work needed with three stacks.

For an abstraction heuristic, project states onto selected information and project each action onto its effect on that information. Forgetting a selected collection of planning fluents, and their preconditions and goals, gives one general construction for STRIPS. Define the abstract transition relation to include every projected original transition, with cost at most the original cost. The exact abstract distance is then a lower bound because any original goal-reaching graph path projects to an abstract goal-reaching walk:For the coin puzzle, a useful state abstraction remembers the stacks occupied by a chosen subset of coins and ignores the other coins, contracting the support chains past ignored coins. Moving an ignored coin leaves the abstract state unchanged; moving a retained coin is a legal move in the smaller Tower of Hanoi instance. Precomputing exact abstract goal distances gives a pattern database. This can retain stacking and spare-stack restrictions that the delete-relaxation heuristic loses. Larger retained subsets give potentially stronger information but require more storage and preprocessing. Maxima of these admissible heuristics remain safe; unqualified sums can double-count moves.

Use direct-transfer STRIPS actions: one action includes picking up a block and putting it down again. There is no separate holding state. Ground $b,y$ as distinct blocks and $x$ as a support, either a block or the table, with $x\ne b$ and $x\ne y$.

For $\mathrm{Move}(b,x,y)$, takeThe preconditions ensure that $b$ can be picked up and that the destination has room. Moving it frees a block source and occupies the destination, while $\mathrm{Clear}(b)$ persists. When $x=\tau$, table availability remains true; its redundant addition is simply omitted. Since $x$ is fixed in each ground action, this case distinction constructs ordinary add lists rather than introducing conditional action effects. The search transition model is $(S\setminus \mathrm{Del})\cup \mathrm{Add}$.

Use a sequential SATPlan encoding with times $t=0,\dots ,T$. The fluent universe isThere are nine support Boolean variables and three clearance Boolean variables per time layer. Static block types, parameter inequalities and permanent table availability are handled during action grounding. For each well-typed ground action $a$ from parts (b)–(c), introduce an occurrence Boolean variable $a_t$ for $0\le t<T$. Allow at most one action per layer, including no action, so that a horizon of $T$ encodes at most $T$ physical actions.

The complete initial-state formula isEvery well-typed fluent not initially true is explicitly false. The final goal formula is simply $G_T=\mathrm{On}(A,B{)}_T\wedge \mathrm{On}(B,C{)}_T$. Leaving unrelated final facts unconstrained is appropriate; leaving unrelated initial facts unconstrained would introduce imaginary starting states.

For each $t<T$, include all action precondition axioms $a_t\to {\bigwedge }_{p\in \mathrm{Pre}(a)}{p}_t$, after removing static true conditions. For example,The precondition axiom for $\mathrm{MoveToTable}(C,A{)}_t$ similarly requires $\mathrm{On}(C,A{)}_t\wedge \mathrm{Clear}(C{)}_t$.

For every fluent $p\in \mathcal{P}$, let ${\mathrm{Add}}_p(t)$ be the logical disjunction of actions at $t$ adding $p$, and ${\mathrm{Del}}_p(t)$ the logical disjunction deleting it. Include the successor-state axiomIt combines action effects with the frame axiom, preventing unsupported changes. A fully grounded example isApply the same construction to every support and clearance fluent, using the exact add/delete lists. If no action occurs, both effect logical disjunctions are false, so all fluents persist.

The sequential action exclusion axioms are $\neg a_t\vee \neg b_t$ for every pair of distinct grounded actions $a,b$. For example,forbids selecting those two occurrences together. Do not add a requirement that some action occur in every layer: that would remove idle padding and change “at most $T$” into an exact-length requirement. One may additionally include true planning state invariants, such as a block having at most one support and a block support carrying at most one block; the unlimited table must be exempt from the latter restriction.

Finally, conjoin $I_0$, $G_T$, and all precondition, successor and exclusion formulas over the layers to obtain ${\phi }_T$. It is a propositional formula; if a solver requires conjunctive normal form, use a satisfiability-preserving Tseitin transformation with auxiliary Boolean variables. The equivalence between this encoding and real action sequences follows from sequential SATPlan correctness: a satisfying assignment induces exactly the stated STRIPS trajectory, and every sufficiently short valid plan supplies such an assignment.

The difficulty is representing dictionary membership and the one-letter relationship in positive conjunctive STRIPS preconditions; a finite dictionary nevertheless admits an exact encoding. Pure STRIPS does not provide string indexing, a “differs in one position” operator, arbitrary disjunctive tests or a procedure that calls a dictionary lookup. Those relationships must be represented by ground facts or compiled into ground actions.

One exact whole-word encoding uses a planning fluent $\mathrm{At}(w)$ and a static predicate $\mathrm{Next}(w,w^{\prime })$ containing exactly the permitted dictionary mutations. For the action schema $\mathrm{Change}(w,w^{\prime })$, useInitialize $\mathrm{At}(s)$ and the static transition facts, and use goal $\mathrm{At}(t)$. Only one $\mathrm{At}$ fact is true initially. Each applicable ground action deletes it and adds exactly its permitted successor, so mathematical induction proves that exactly one current-word fact remains true and that every plan is a legal word ladder. Conversely, every legal word ladder directly supplies a plan. An isolated non-dictionary start is handled as in (c). A shortest plan has the fewest mutations.

This encoding moves the hard lexical relationship into preprocessing. For $N$ dictionary words, checking all ordered pairs takes $O(N^{2}L)$ character comparisons, although indexing can do better; the number of stored transitions is at most $NL(|\Sigma |-1)$ when all states are dictionary words. The STRIPS representation is finite, but its size and preprocessing cost matter.

A position-based representation instead uses planning fluents $\mathrm{Letter}(i,\ell )$. Changing position $i$ must delete its old letter and add its new one; all other positions persist through the STRIPS update rule. Merely requiring each position to contain a letter admits non-dictionary strings. A disjunction over all dictionary words is not a positive conjunctive STRIPS precondition. It can be compiled into separate ground actions, each requiring every letter of a valid source word and changing one position to reach a valid destination. This again enumerates lexical cases and can be large. Arbitrary letter changes followed by an unconstrained “validate” action are unsound: several illegal intermediate strings could otherwise lead to a legal goal. Legality must hold after every mutation, not only at the endpoint.

Use location, holding and hand-capacity planning fluents, together with static object types. Write $\mathrm{In}(b,k)$, $\mathrm{Holding}(b)$, $\mathrm{At}(k)$ and $\mathrm{Empty}$ for a ball's bucket, the held ball, the arm's location and an empty hand. Static predicates $\mathrm{Ball}(b)$, $\mathrm{Bucket}(k)$ and $\mathrm{Different}(k,\ell )$ identify types and distinct buckets. The latter can equivalently be a action grounding restriction.

For typed parameters, the STRIPS actions areUntyped notation adds the appropriate $\mathrm{Ball}$ and $\mathrm{Bucket}$ facts to every precondition set. Static type and inequality facts have no add or delete effects. A state is a set of true ground facts under the closed-world assumption, and an applicable action produces $(S\setminus \mathrm{Del})\cup \mathrm{Add}$.

Start from a physically valid state: each ball is in exactly one bucket or held; at most one ball is held; the arm is at exactly one bucket; and $\mathrm{Empty}$ is true exactly when no ball is held. The operators preserve these planning state invariants. In particular, picking requires an empty hand, dropping releases the held ball, and moving deletes the old arm location. Moving while holding a ball is permitted, so a separate carried-ball movement action is unnecessary.

There are $G=2mn+n(n-1)$ distinct ground actions, or $tG$ time-indexed action variables over $t$ transition steps. Each of STRIPS's pick and drop action schemas has $mn$ type-correct instantiations. A move chooses an ordered pair of distinct buckets, giving $n(n-1)$. Every physical action is a ground action before it receives a time index in SATPlan.These counts exclude static type checks after action grounding and exclude optional persistence/no-op action symbols. Using successor-state axioms supplies persistence without separate no-op action variables. If one action occurrence is allowed per layer, it is selected from the same ground-action set; a parallel encoding also begins with these physical ground actions, but has a different exclusion policy.

Use backward deletion of achieved goal requirements; this decides precondition-free ground STRIPS planning in polynomial time. Let $I$ be the initial set of true facts, $G$ the positive conjunctive goal set and $\mathcal{A}$ the ground actions. Assume the usual disjoint add and delete lists; if both lists contain a fact, first normalize the net effect according to the action semantics.

Maintain residual goal set $R=G$ and an initially empty list $L$. While $R⊈I$, look for an action $a$ satisfyingIf no such action exists, reject. Otherwise record $a$ in $L$ and replace $R$ by $R\setminus \mathrm{Add}(a)$. When $R\subseteq I$, return the actions in reverse order of recording. All actions are applicable because their precondition sets are empty.

For soundness, the selected action can be put last in a plan for the current residual goals: it supplies the removed goals and deletes none of the goals still being required. Reversing all recorded selections makes the final state satisfy the original $G$.

For completeness, suppose $R$ is not already satisfied initially but a plan achieves it. Consider the last action in that plan that changes any fact of $R$. Its effective changes cannot delete any member of $R$, because no later action repairs it; it must add at least one member. Thus a candidate exists. Moreover any candidate chosen by the algorithm is safe: removing some requirements gives a subset of $R$, so a plan for $R$, if one exists, also establishes the smaller goal set. Appending the chosen last action then restores the removed requirements without harming the rest. Mathematical induction therefore preserves solvability during all choices.

Each successful iteration removes at least one residual goal, so there are at most $|G|$ iterations and the returned plan has at most $|G|$ actions. Scanning all actions and their effect lists per iteration is polynomial in the input size, for example $O(|G||\mathcal{A}||P|)$ with simple fact-set representations over $P$. Merely taking the union of all add effects would be unsound, since actions can delete each other's achievements. This algorithm is the last-achiever algorithm for precondition-free planning.

Use $a,w,g,r$ for the agent, monster, gold and arrow, and abbreviate $s{q}_{ij}$ to $s_{ij}$. A physically safe STRIPS plan isEvery movement follows a listed adjacency predicate. The shot is taken from $s_{22}$ while the arrow is held, and kills the monster before entry into $s_{23}$. The pit at $s_{12}$ is never entered. The pickup establishes possession of the gold, and the last four movements restore the exit location while preserving that possession. Thus ten actions achieve the formal goal and the intended safe return; arriving at the exit is the source model’s representation of leaving.

Three different omissions produce concrete erroneous STRIPS plans. Here a route means the corresponding successive $\mathrm{Move}$ actions with the indicated first argument.

No lethal-entry condition. Move the agent along $s_{11},s_{21},s_{22},s_{23},s_{13}$, take the gold at $s_{13}$, and reverse the route. This nine-action STRIPS plan satisfies every supplied precondition and the final goal test, without firing. Physically it fails on entering the live monster’s room: the supplied search transition model neither forbids the entry nor records death. The omitted pit cell happens to be disconnected in the supplied adjacency relation, so this particular instance already excludes pit entry; that accidental protection does not encode the monster hazard.

Supposedly stationary objects can move themselves. The five-action STRIPS planleaves the agent at the exit and brings it the gold. The formal preconditions hold because $x$ in $\mathrm{Move}(x,y,z)$ has no actor restriction. Gold cannot actually propel itself. The same flaw permits moving the supposedly stationary monster.

Unrestricted pickup permits impossible inventory. Follow the first example’s outward route, but insert $\mathrm{Take}(a,w,s_{23})$ immediately after reaching $s_{23}$. Continue to $s_{13}$, take the gold and return. This ten-action STRIPS plan ends with both $\mathrm{have}(a,w)$ and $\mathrm{have}(a,g)$ and satisfies the supplied goal. Its entrance also exposes the first flaw, but the additional, distinct defect is that pickup treats the live monster as a collectible object and deletes its location. A movement safety check alone is not a specification of which objects are collectible. The shot schema likewise lacks restrictions to the designated shooter, projectile and victim; fixing the action roles together prevents these type errors.