STRIPS

A representation for automated planning in which a state $S$ is a set of true ground facts and an action has a positive precondition set $P$, add set $A$ and delete set $D$. Under the closed-world assumption, facts absent from $S$ are false. The action applies when $P\subseteq S$ and producesNegative effects are delete-list entries; they do not require negative preconditions. A movement action must delete an object's old location as well as add its destination. Capacity and safety restrictions require explicit action conditions or auxiliary planning fluents; they do not follow automatically from an intended physical interpretation.

Automated planning with ground actions that are always applicable because their precondition sets are empty. Delete effects are still permitted, so taking the union of all add effects does not decide reachability. With a positive conjunctive goal, the last-achiever algorithm for precondition-free planning gives a polynomial-time algorithm.

Start with required facts $R=G$. If $R\subseteq I$, the empty prefix suffices. Otherwise choose an action adding a member of $R$ and deleting none of $R$, record it as a final action, and remove its add effects from $R$. Repeat and reverse the recorded actions when the residual requirements hold initially. Reject if no permitted action exists.

Soundness follows because each recorded last action supplies its removed requirements without deleting the remaining ones. If a plan satisfies a residual $R$ not contained in $I$, its last action affecting $R$ cannot delete an $R$-fact and must add one; therefore a candidate exists. Any selected candidate leaves a smaller required set, which is no harder to achieve than $R$. This proves completeness by mathematical induction. Every selection removes a required fact, so there are at most $|G|$ selections and a scan of all effect lists at each step gives polynomial time.

A parameterized action definition with typed parameters, preconditions, add effects and delete effects. Replacing its parameters by type-correct objects yields a ground action. Type restrictions and static inequalities can remove invalid instantiations before the action is considered by a search algorithm or SATPlan.

An action with no unbound object variables. Its precondition and effect sets consist of fixed ground facts. Action grounding an action schema over a finite object universe creates one candidate action for each type-correct parameter tuple, after any static filtering; a time-indexed encoding then creates copies or variables for individual action occurrences.

Substituting object names for all parameters in an action schema, retaining the type-correct tuples and any required static restrictions. The result is a collection of ground actions.

A predicate whose ground facts are unchanged by every action in a planning model. Object types and a fixed adjacency relation are common examples. Static conditions can filter ground actions before search; they need not acquire a separate truth variable at every time layer. A planning fluent can instead be added or deleted by actions.