Precondition

A precondition is a set of logical propositions, or facts, that must be conjunctively true in the current world state for an action to be applicable. In formalisms like STRIPS, these are represented as a list of literals. For example, the action Stack(BlockA, BlockB) has the precondition {Clear(BlockB), Holding(BlockA)}. If Clear(BlockB) is false, the action is inapplicable, regardless of other conditions.

Preconditions act as a filter on the state space, drastically reducing the branching factor for forward search algorithms. From any given state, the planner only considers actions whose preconditions are a subset of that state's true facts. This prevents the generation of physically or logically impossible successor states, such as trying to drive a car without fuel or edit a file that is not open.

Preconditions are formally defined within a planning domain using a language like PDDL. They are expressed using the domain's predicates and objects. For instance, in a logistics domain: (when (at ?truck ?loc) (can-unload ?package ?truck ?loc)). This formal specification allows for automated plan validation, where a verifier can check if every action's preconditions were met at the time of its simulated execution.

It is critical to distinguish preconditions from an action's effects. Preconditions specify what must be true before execution, while effects specify what changes after execution.

• Precondition: HasKey(Door1)
• Effect (Add): Open(Door1)
• Effect (Delete): Locked(Door1) Confusing these leads to incorrect domain models where actions can create their own prerequisites, breaking causal logic.

In regression planning (backward search), preconditions define the subgoals that must be achieved. The planner starts from the goal state and selects an action whose effects achieve a goal fact. The preconditions of that action then become the new subgoals to regress from. This process continues recursively until all subgoals are satisfied by the initial state, constructing the plan in reverse order.

Advanced planning formalisms extend simple conjunctive preconditions:

• Conditional Preconditions: An action's applicability may depend on a complex logical formula (e.g., if (P and not Q) then R must hold).
• Quantified Preconditions: Require the existence or universality of objects (e.g., (exists (?c - Container) (inside ?package ?c))). These increase expressive power but also computational complexity, requiring more sophisticated satisfiability checking during search.

An effect is the change an action makes to the state of the world when executed. It is the logical consequence of applying an action whose preconditions were satisfied. Effects are typically divided into:

• Add Effects: Propositions that become true.
• Delete Effects: Propositions that become false (in STRIPS-style representations).

Together, preconditions and effects form the complete action schema, defining what is required for an action and what it accomplishes. For example, the action Stack(A, B) might have the effect On(A, B) and Clear(A).

STRIPS (Stanford Research Institute Problem Solver) is the foundational formalism that introduced the standard representation for actions using preconditions and effects. In STRIPS:

• A state is a set of ground logical propositions.
• An action is defined by three lists:
  • Precondition List: Propositions that must be true for the action to be applicable.
  • Add List: Propositions the action makes true.
  • Delete List: Propositions the action makes false.

This representation explicitly solves part of the frame problem by specifying only what changes, implicitly stating everything else remains unchanged.

Plan validation is the process of verifying that a proposed sequence of actions, when executed from a known initial state, will achieve all goal conditions. This is a critical check for correctness. The validator:

1. Starts at the initial state.
2. For each action in the plan, checks if its preconditions are satisfied in the current state.
3. If satisfied, applies the action's effects to produce the next state.
4. Repeats until the final state is reached, then checks if it satisfies the goal.

Validation ensures logical soundness before costly execution, catching plans where an action's preconditions are violated mid-sequence.

The state space is the set of all possible configurations (states) that the world can be in, given a set of objects and predicates. In planning, search algorithms navigate this space:

• Nodes represent states.
• Edges represent state transitions caused by executing an action.

An action's preconditions act as a filter on outgoing edges from a node; only actions whose preconditions match the current state generate valid successor nodes. The size of the state space is a primary driver of planning complexity, making efficient search and informed heuristics essential.

PDDL (Planning Domain Definition Language) is the standard language for formally defining planning problems. It extends STRIPS with richer expressivity. An action is defined in a :action block containing:

• :parameters - The objects the action operates on.
• :precondition - A logical formula that must hold for the action to be applicable.
• :effect - The logical formula describing the state change.

For example, a drive action in PDDL would have a precondition like (at ?truck ?location) and an effect like (not (at ?truck ?location)) (at ?truck ?destination). PDDL enables precise, machine-readable specification of preconditions for use by planners like FastDownward.

The frame problem is the challenge of efficiently representing and reasoning about which aspects of the world remain unchanged when an action is performed. A naive representation would require stating all unaffected facts for every action, leading to exponential complexity.

The STRIPS representation provides a solution: by defining actions solely with preconditions, add effects, and delete effects, it adopts the STRIPS assumption (or closed-world assumption for effects). This means any fact not listed in an action's effects is assumed to persist unchanged. Preconditions are central to this; they specify only what must be true for change, not what remains invariant.