Fundamentals of Planning in AI: STRIPS, State-Space Search and a Worked Blocks World Plan

You may recognise words such as state, goal and action, yet still be unsure whether an action is applicable or whether a sequence is a valid plan. Planning uses a precise problem model, STRIPS operators, a six-action Blocks World plan, and both progression and regression. The central idea is simple: planning searches for an action sequence whose successive effects transform the initial state into any state satisfying the goal conditions.

Fundamentals of planning in AI: the problem model

A classical planning problem can be written as P = (F, A, s0, G, c). Here, F is a finite set of propositional facts, A is the set of grounded actions, s0 is the initial state, G is the set of goal literals, and c(a) is the cost of action a. A state is the set of facts currently true. Under the closed-world reading used here, any ground fact absent from that set is false.

An action a is applicable in state s when every positive precondition is in s and every negative precondition, if any, is absent. A STRIPS action has an add list Add(a) and delete list Del(a):

Result(s,a) = (s - Del(a)) union Add(a)

A plan pi = <a1,...,ak> is valid when each action is applicable in sequence and the final state contains every goal literal. Assume one agent, finite discrete states and actions, full observability, deterministic effects, no exogenous state changes during planning, and unit costs. Validity asks whether a plan reaches the goal. Optimality asks whether its stated total cost is least among valid plans.

STRIPS action representation: preconditions, add lists and delete lists

For blocks A, B, C and table T, use On(x,y), Clear(x), Holding(x) and HandEmpty. Predicates describe a state; an operator schema describes a family of legal state changes. If predicates and logical conditions need revision, start with Propositional and Predicate Logic: Truth Tables, Quantifiers.

Stack(x,y) deletes Clear(y) because y gains a block above it. Unstack(x,y) adds Clear(y) because that block is removed. Always check every precondition in the old state before applying any effect.

Blocks World planning problem: exact initial state and goal

Initially, C is on A; A and B are on the table; C and B are clear; and the hand is empty:

s0 = {On(C,A), On(A,T), On(B,T), Clear(C), Clear(B), HandEmpty}

Clear(A) is absent, so Pickup(A) is not initially applicable. The partial goal is G = {On(A,B), On(B,C)}, meaning a tower A on B on C. It does not require On(C,T), Clear(A) or HandEmpty. A goal normally describes conditions to satisfy, not the only acceptable complete world. Every grounded action costs 1, so action count and cumulative cost coincide in this example.

Worked STRIPS plan: six actions from initial state to goal

Use pi = <Unstack(C,A), Putdown(C), Pickup(B), Stack(B,C), Pickup(A), Stack(A,B)>. The trace applies deletes before adds when displaying each resulting set.

Both goal facts, On(A,B) and On(B,C), occur in s6, so G is a subset of s6. There are six actions at unit cost, giving total cost 6.

The plan is also optimal under these operators. Exposing A requires Unstack(C,A), then putting C down frees the only hand and makes C the support. Placing B on C requires Pickup(B) and Stack(B,C). Placing A on B requires Pickup(A) and Stack(A,B). These six necessary moves match the plan, so no lower-cost unit-action plan exists.

Planning as state-space search: progression, regression and plan space

Forward progression starts at s0. Each edge is an action applicable in the current complete state, and the child comes from the STRIPS transition rule. The goal test asks whether G is contained in that child. Thus Pickup(A) is not an outgoing edge from s0, but Unstack(C,A) is.

Regression reasons backwards from desired conditions; it does not run actions backwards. Regressing On(A,B) through Stack(A,B) replaces that achieved literal with Holding(A) and Clear(B), while retaining compatible goal On(B,C). Stack(B,C) must establish both On(B,C) and Clear(B) before the final stack. Earlier, Unstack(C,A) establishes Clear(A) for Pickup(A). These causal requirements recover the ordering in the six-step plan.

A state-space node is a complete world state. A plan-space node is a partial plan containing actions, ordering constraints and causal links. The Graph Algorithms: BFS, DFS and Shortest Paths guide covers the underlying search machinery. A planner additionally handles applicability, goal tests, repeated states and often planning heuristics.

Fundamentals of planning traps: where a plausible plan becomes invalid

Planning is not merely prediction. It selects actions to achieve a goal under a transition model. It is also broader than path finding: the same physical location can belong to different symbolic states when facts such as Holding(B) or Clear(C) differ.

Fundamentals of planning: how assessment questions test the topic

Common tasks ask you to identify the components of P, test a grounded action's applicability, calculate a next state from add and delete lists, validate an action sequence, distinguish progression from regression and plan-space search, or compare valid, shortest and least-cost plans.

Use these four checks immediately:

1. Is Pickup(A) applicable in s0? No. Clear(A) is false under the stated closed-world state.

2. What later makes it applicable? At s4, Clear(A) is still present and HandEmpty has been restored, so all three preconditions hold.

3. Which step first satisfies On(B,C)? Step 4, Stack(B,C).

4. What are the final action count and cost? Six actions and cost 6 under unit costs.

For the surrounding syllabus and a practice route through the rest of the paper, use UGC NET CS Exam Preparation. For current marks, weightage and paper pattern, check the official UGC NET information bulletin.

Fundamentals of planning in AI: the short version and next step

Remember the chain: a state contains currently true facts; an action needs satisfied preconditions; STRIPS adds some facts and deletes others; and a valid plan reaches any state satisfying the goal. Progression searches from s0, regression reasons back from G, and optimality depends on the cost function.

For mastery, reconstruct s0, all four schemas and the six actions from memory. Verify G is a subset of s6, explain the cost of 6, and state why Pickup(A) is illegal at step 0 but legal after step 4. The NTA-UGC-NET Paper - 2 course is the structured route, and its curriculum covers Artificial Intelligence and Planning.