Blocks World → Warehouse Robot Task Scheduling

Why Classical Planning?

When you ask a robot “put all the blue boxes on shelf A, then bring me a labeler,” how does it figure out the order of dozens of small actions—move, grasp, place—without bumping into logical contradictions (like holding two items with one gripper)? Classical planning answers this by modeling the world with facts (predicates) and actions that add/remove facts. STRIPS (Stanford Research Institute Problem Solver) is the seminal framework for this: you describe the start, the goal, and the available actions; a planner searches for a valid sequence that transforms start → goal.

You’ll first master STRIPS in the classic Blocks World toy problem (stacking blocks with a gripper). Then you’ll transfer the exact same ideas to a warehouse robot task sequencing scenario: move between stations, pick items, and place them at packing.

Theory Deep Dive

1. Formal Definition

A (deterministic, fully observable) classical planning problem can be written as:
$\langle S, A, \gamma, s_0, G \rangle$

$S$ : set of states. Each state is a set of ground predicates that are true.
$A$ : set of actions (operators). Each has preconditions and effects (add/delete lists).
$\gamma(s, a)$ : transition function applying $a$ in state $s$ to produce a successor state.
$s_0 \in S$ : initial state.
$G \subseteq \mathcal{L}$ : goal condition (set of literals) that must be true in the final state.

An action schema $a(\vec{x})$ (with parameters $\vec{x}$ ) is defined by:

Preconditions: $\text{Pre}(a)$ (facts that must hold).
Add effects: $\text{Add}(a)$ (facts made true).
Delete effects: $\text{Del}(a)$ (facts made false).

Applying an action in STRIPS-style progression:
$s' ;=; (s \setminus \text{Del}(a)) \cup \text{Add}(a)$ , valid iff $\text{Pre}(a) \subseteq s$ .

2. STRIPS assumptions & modeling choices

Closed-world assumption: any fact not listed in the state is assumed false.

Add/Del lists explicitly handle the frame problem (we say what changes; all else persists).

Propositional grounding: we ground operator schemas with concrete objects (e.g., $\text{Stack}(A, B)$ ).

Search: A plan is found by search over state space (progression) or over goals (regression). Breadth-first search (BFS) and uniform-cost search are common baselines; A* with planning heuristics is typical in practice.

3. Typical predicates & operators (Blocks World)

Predicates: $\text{On}(x, y)$ , $\text{OnTable}(x)$ , $\text{Clear}(x)$ , $\text{Holding}(x)$ , $\text{HandEmpty}$ .

Operators (schemas):

$\text{PickUp}(x)$
Pre: $\text{OnTable}(x), \text{Clear}(x), \text{HandEmpty}$
Add: $\text{Holding}(x)$
Del: $\text{OnTable}(x), \text{Clear}(x), \text{HandEmpty}$
$\text{PutDown}(x)$
Pre: $\text{Holding}(x)$
Add: $\text{OnTable}(x), \text{Clear}(x), \text{HandEmpty}$
Del: $\text{Holding}(x)$
$\text{UnStack}(x, y)$
Pre: $\text{On}(x,y), \text{Clear}(x), \text{HandEmpty}$
Add: $\text{Holding}(x), \text{Clear}(y)$
Del: $\text{On}(x,y), \text{Clear}(x), \text{HandEmpty}$
$\text{Stack}(x, y)$
Pre: $\text{Holding}(x), \text{Clear}(y)$
Add: $\text{On}(x,y), \text{Clear}(x), \text{HandEmpty}$
Del: $\text{Holding}(x), \text{Clear}(y)$

4. Complexity & heuristics (intuition)

Deciding plan existence in STRIPS is PSPACE-complete (hard in worst case), but small to moderate instances are very solvable.

Common heuristics: delete-relaxation ( $h_{add}$ , $h_{max}$ ), landmarks, planning graphs (Graphplan). You won’t implement these here, but it’s useful to know they guide A* effectively.

5. From STRIPS to PDDL (industry/academia lingua franca)

PDDL (Planning Domain Definition Language) generalizes STRIPS with types, quantifiers, numeric fluents (in extensions), etc. Most modern planners accept PDDL. Our Python code mirrors the STRIPS “feel” to ground your understanding.

Toy Problem – Blocks World (3 blocks)

Data Snapshot

Objects: ${A, B, C}$
Initial state $s_0$ :
${\text{OnTable}(A), \text{OnTable}(B), \text{On}(C,A), \text{Clear}(B), \text{Clear}(C), \text{HandEmpty}}$
Goal $G$ :
${\text{On}(B,C), \text{On}(C,A), \text{OnTable}(A), \text{Clear}(B)}$

Interpretation: Build a tower $B$ on $C$ on $A$ (which is on the table), with $B$ clear at the end.

Step 1: Represent literals and states

We encode facts as tuples for fast hashing; a state is a frozenset of facts.

from collections import deque
from itertools import product

# A literal is a tuple like ('On', 'A', 'B') or ('HandEmpty',)
# A state is a frozenset of such tuples.

def lit(pred, *args):
    return (pred, *args)

def holds(state, literals):
    """Return True if all literals are in the state."""
    return all(l in state for l in literals)

Step 2: Define the Blocks World domain (schemas)

We’ll create reusable operator schemas, then “ground” them over objects (A,B,C).

class Schema:
    def __init__(self, name, params, pre, add, delete):
        self.name = name
        self.params = params  # e.g., ('x',) or ('x','y')
        self.pre = pre        # function binding -> set of literals
        self.add = add
        self.delete = delete

    def ground(self, objects):
        """Generate grounded actions by substituting params with objects."""
        domains = [objects for _ in self.params]
        for args in product(*domains):
            # simple inequality guard for x != y when both exist
            if len(args) == 2 and args[0] == args[1]:
                continue
            yield GroundAction(self, args)

class GroundAction:
    def __init__(self, schema, args):
        self.schema = schema
        self.args = args
        self.name = f"{schema.name}({', '.join(args)})"
        self.pre = schema.pre(*args)
        self.add = schema.add(*args)
        self.delete = schema.delete(*args)

Step 3: Operator schemas for Blocks World

Four canonical actions: pick from table, put on table, unstack from a block, stack onto a block.

def bw_domain():
    # Predicates: On(x,y), OnTable(x), Clear(x), Holding(x), HandEmpty

    def PickUp_pre(x):
        return {lit('OnTable', x), lit('Clear', x), lit('HandEmpty')}
    def PickUp_add(x):
        return {lit('Holding', x)}
    def PickUp_del(x):
        return {lit('OnTable', x), lit('Clear', x), lit('HandEmpty')}

    def PutDown_pre(x):
        return {lit('Holding', x)}
    def PutDown_add(x):
        return {lit('OnTable', x), lit('Clear', x), lit('HandEmpty')}
    def PutDown_del(x):
        return {lit('Holding', x)}

    def UnStack_pre(x, y):
        return {lit('On', x, y), lit('Clear', x), lit('HandEmpty')}
    def UnStack_add(x, y):
        return {lit('Holding', x), lit('Clear', y)}
    def UnStack_del(x, y):
        return {lit('On', x, y), lit('Clear', x), lit('HandEmpty')}

    def Stack_pre(x, y):
        return {lit('Holding', x), lit('Clear', y)}
    def Stack_add(x, y):
        return {lit('On', x, y), lit('Clear', x), lit('HandEmpty')}
    def Stack_del(x, y):
        return {lit('Holding', x), lit('Clear', y)}

    return [
        Schema('PickUp', ('x',), PickUp_pre, PickUp_add, PickUp_del),
        Schema('PutDown', ('x',), PutDown_pre, PutDown_add, PutDown_del),
        Schema('UnStack', ('x','y'), UnStack_pre, UnStack_add, UnStack_del),
        Schema('Stack', ('x','y'), Stack_pre, Stack_add, Stack_del)
    ]

Step 4: Apply actions & BFS planner (progression)

We do straightforward BFS over grounded actions; fine for small educational instances.

def apply_action(state, action):
    if not holds(state, action.pre):
        return None
    return frozenset((state - action.delete) | action.add)

def bfs_plan(initial, goal, actions):
    """Return a list of actions reaching any state that satisfies goal."""
    if holds(initial, goal):
        return []

    frontier = deque([initial])
    parent = {initial: None}
    used_action = {initial: None}

    while frontier:
        s = frontier.popleft()
        for a in actions:
            s2 = apply_action(s, a)
            if s2 is None or s2 in parent:
                continue
            parent[s2] = s
            used_action[s2] = a
            if holds(s2, goal):
                # reconstruct plan
                plan = []
                cur = s2
                while used_action[cur] is not None:
                    plan.append(used_action[cur])
                    cur = parent[cur]
                return list(reversed(plan))
            frontier.append(s2)
    return None

Step 5: Instantiate the problem and solve

Ground the domain, define the instance, then search. You’ll see a valid stacking sequence printed.

# Objects and domain
objects = ('A','B','C')
schemas = bw_domain()
grounded = []
for sch in schemas:
    grounded.extend(list(sch.ground(objects)))

# Initial & goal states
s0 = frozenset({
    lit('OnTable','A'),
    lit('OnTable','B'),
    lit('On','C','A'),
    lit('Clear','B'),
    lit('Clear','C'),
    lit('HandEmpty')
})
goal = {
    lit('On','B','C'),
    lit('On','C','A'),
    lit('OnTable','A'),
    lit('Clear','B')
}

plan = bfs_plan(s0, goal, grounded)
for step, act in enumerate(plan or [], 1):
    print(f"{step:02d}. {act.name}")

Quick Reference: Full Code

from collections import deque
from itertools import product

def lit(pred, *args): return (pred, *args)
def holds(state, literals): return all(l in state for l in literals)

class Schema:
    def __init__(self, name, params, pre, add, delete):
        self.name, self.params, self.pre, self.add, self.delete = name, params, pre, add, delete
    def ground(self, objects):
        domains = [objects for _ in self.params]
        for args in product(*domains):
            if len(args) == 2 and args[0] == args[1]: continue
            yield GroundAction(self, args)

class GroundAction:
    def __init__(self, schema, args):
        self.schema, self.args = schema, args
        self.name = f"{schema.name}({', '.join(args)})"
        self.pre = schema.pre(*args); self.add = schema.add(*args); self.delete = schema.delete(*args)

def bw_domain():
    def PickUp_pre(x):  return {lit('OnTable', x), lit('Clear', x), lit('HandEmpty')}
    def PickUp_add(x):  return {lit('Holding', x)}
    def PickUp_del(x):  return {lit('OnTable', x), lit('Clear', x), lit('HandEmpty')}
    def PutDown_pre(x): return {lit('Holding', x)}
    def PutDown_add(x): return {lit('OnTable', x), lit('Clear', x), lit('HandEmpty')}
    def PutDown_del(x): return {lit('Holding', x)}
    def UnStack_pre(x,y): return {lit('On', x, y), lit('Clear', x), lit('HandEmpty')}
    def UnStack_add(x,y): return {lit('Holding', x), lit('Clear', y)}
    def UnStack_del(x,y): return {lit('On', x, y), lit('Clear', x), lit('HandEmpty')}
    def Stack_pre(x,y):   return {lit('Holding', x), lit('Clear', y)}
    def Stack_add(x,y):   return {lit('On', x, y), lit('Clear', x), lit('HandEmpty')}
    def Stack_del(x,y):   return {lit('Holding', x), lit('Clear', y)}
    return [
        Schema('PickUp', ('x',), PickUp_pre, PickUp_add, PickUp_del),
        Schema('PutDown', ('x',), PutDown_pre, PutDown_add, PutDown_del),
        Schema('UnStack', ('x','y'), UnStack_pre, UnStack_add, UnStack_del),
        Schema('Stack', ('x','y'), Stack_pre, Stack_add, Stack_del)
    ]

def apply_action(state, action):
    if not holds(state, action.pre): return None
    return frozenset((state - action.delete) | action.add)

def bfs_plan(initial, goal, actions):
    if holds(initial, goal): return []
    frontier = deque([initial]); parent = {initial: None}; used_action = {initial: None}
    while frontier:
        s = frontier.popleft()
        for a in actions:
            s2 = apply_action(s, a)
            if s2 is None or s2 in parent: continue
            parent[s2] = s; used_action[s2] = a
            if holds(s2, goal):
                plan = []; cur = s2
                while used_action[cur] is not None:
                    plan.append(used_action[cur]); cur = parent[cur]
                return list(reversed(plan))
            frontier.append(s2)
    return None

# ----- Instance -----
objects = ('A','B','C')
grounded = [ga for sch in bw_domain() for ga in sch.ground(objects)]
s0 = frozenset({lit('OnTable','A'), lit('OnTable','B'), lit('On','C','A'), lit('Clear','B'), lit('Clear','C'), lit('HandEmpty')})
goal = {lit('On','B','C'), lit('On','C','A'), lit('OnTable','A'), lit('Clear','B')}
plan = bfs_plan(s0, goal, grounded)
for i, a in enumerate(plan or [], 1): print(f"{i:02d}. {a.name}")

Real‑World Application — Warehouse Robot Task Sequencing

A mobile robot must:

Move between stations: ${\text{dock}, \text{rack_A}, \text{rack_B}, \text{pack}}$ .
Pick items at racks and place them at the packing station.
Respect gripper capacity (one item).
Only move along connected edges.

Initial: Robot at dock; $\text{At}(\text{item1}, \text{rack_A})$ , $\text{At}(\text{item2}, \text{rack_B})$ , gripper empty.
Goal: $\text{At}(\text{item1}, \text{pack}) \wedge \text{At}(\text{item2}, \text{pack})$ .

We’ll reuse the same STRIPS engine with a domain customized for navigation and manipulation.

Step 1: Define warehouse predicates & schemas

Three operator schemas: move, pick, place—minimal yet expressive for many warehouse tasks.

def wh_domain(locations, connectivity):
    # Predicates: At(robot, L), At(item, L), Connected(L1, L2), GripperEmpty, Holding(item)

    # Move(robot, l1, l2): requires robot at l1 and Connected(l1,l2)
    def Move_pre(l1, l2):
        return {lit('AtRobot', l1), lit('Connected', l1, l2)}
    def Move_add(l1, l2):
        return {lit('AtRobot', l2)}
    def Move_del(l1, l2):
        return {lit('AtRobot', l1)}

    # Pick(item, l): robot at l, item at l, gripper empty
    def Pick_pre(item, l):
        return {lit('AtRobot', l), lit('At', item, l), lit('GripperEmpty')}
    def Pick_add(item, l):
        return {lit('Holding', item)}
    def Pick_del(item, l):
        return {lit('At', item, l), lit('GripperEmpty')}

    # Place(item, l): robot at l, holding item
    def Place_pre(item, l):
        return {lit('AtRobot', l), lit('Holding', item)}
    def Place_add(item, l):
        return {lit('At', item, l), lit('GripperEmpty')}
    def Place_del(item, l):
        return {lit('Holding', item)}

    # Build schemas
    schemas = [
        Schema('Move', ('l1','l2'), Move_pre, Move_add, Move_del),
        Schema('Pick', ('item','l'), Pick_pre, Pick_add, Pick_del),
        Schema('Place', ('item','l'), Place_pre, Place_add, Place_del)
    ]

    # Pre-encode Connected facts into the initial state later.
    return schemas

Step 2: Ground domain and build the initial state

We add Connected facts to the state so Move actions know what edges exist.

# Locations and connectivity (undirected)
locations = ('dock','rack_A','rack_B','pack')
edges = {('dock','rack_A'), ('rack_A','pack'), ('dock','rack_B'), ('rack_B','pack')}
conn = set()
for u,v in edges:
    conn.add(lit('Connected', u, v))
    conn.add(lit('Connected', v, u))  # undirected

items = ('item1','item2')

schemas = wh_domain(locations, conn)
# Objects for grounding: we include all symbols; schemas will only be applicable when preconditions hold.
objects = tuple(set(locations) | set(items))

grounded = []
for sch in schemas:
    grounded.extend(list(sch.ground(objects)))

# Initial state
s0_wh = frozenset(
    {lit('AtRobot','dock'), lit('GripperEmpty')} |
    {lit('At','item1','rack_A'), lit('At','item2','rack_B')} |
    conn  # bake connectivity into the state
)

goal_wh = {lit('At','item1','pack'), lit('At','item2','pack')}

Step 3: Plan and print a readable schedule

Expect a sequence like Move(dock, rack_A) → Pick(item1, rack_A) → Move(rack_A, pack) → Place(item1, pack) → ….

plan_wh = bfs_plan(s0_wh, goal_wh, grounded)

def pretty(a):
    return a.name.replace('AtRobot','At(robot)').replace('rack_','rack-')

for i, a in enumerate(plan_wh or [], 1):
    print(f"{i:02d}. {pretty(a)}")

Quick Reference: Full API (`app.py`)

from collections import deque
from itertools import product

def lit(pred, *args): return (pred, *args)
def holds(state, literals): return all(l in state for l in literals)

class Schema:
    def __init__(self, name, params, pre, add, delete):
        self.name, self.params, self.pre, self.add, self.delete = name, params, pre, add, delete
    def ground(self, objects):
        domains = [objects for _ in self.params]
        for args in product(*domains):
            if len(args) == 2 and args[0] == args[1]: continue
            yield GroundAction(self, args)

class GroundAction:
    def __init__(self, schema, args):
        self.schema, self.args = schema, args
        self.name = f"{schema.name}({', '.join(args)})"
        self.pre = schema.pre(*args); self.add = schema.add(*args); self.delete = schema.delete(*args)

def apply_action(state, action):
    if not holds(state, action.pre): return None
    return frozenset((state - action.delete) | action.add)

def bfs_plan(initial, goal, actions):
    if holds(initial, goal): return []
    frontier = deque([initial]); parent = {initial: None}; used_action = {initial: None}
    while frontier:
        s = frontier.popleft()
        for a in actions:
            s2 = apply_action(s, a)
            if s2 is None or s2 in parent: continue
            parent[s2] = s; used_action[s2] = a
            if holds(s2, goal):
                plan = []; cur = s2
                while used_action[cur] is not None:
                    plan.append(used_action[cur]); cur = parent[cur]
                return list(reversed(plan))
            frontier.append(s2)
    return None

def wh_domain(locations, connectivity):
    def Move_pre(l1, l2):  return {lit('AtRobot', l1), lit('Connected', l1, l2)}
    def Move_add(l1, l2):  return {lit('AtRobot', l2)}
    def Move_del(l1, l2):  return {lit('AtRobot', l1)}
    def Pick_pre(item, l): return {lit('AtRobot', l), lit('At', item, l), lit('GripperEmpty')}
    def Pick_add(item, l): return {lit('Holding', item)}
    def Pick_del(item, l): return {lit('At', item, l), lit('GripperEmpty')}
    def Place_pre(item, l): return {lit('AtRobot', l), lit('Holding', item)}
    def Place_add(item, l): return {lit('At', item, l), lit('GripperEmpty')}
    def Place_del(item, l): return {lit('Holding', item)}
    return [
        Schema('Move', ('l1','l2'), Move_pre, Move_add, Move_del),
        Schema('Pick', ('item','l'), Pick_pre, Pick_add, Pick_del),
        Schema('Place', ('item','l'), Place_pre, Place_add, Place_del)
    ]

# ----- Instance -----
locations = ('dock','rack_A','rack_B','pack')
edges = {('dock','rack_A'), ('rack_A','pack'), ('dock','rack_B'), ('rack_B','pack')}
conn = set()
for u,v in edges:
    conn.add(lit('Connected', u, v)); conn.add(lit('Connected', v, u))

items = ('item1','item2')
schemas = wh_domain(locations, conn)
objects = tuple(set(locations) | set(items))
grounded = [ga for sch in schemas for ga in sch.ground(objects)]

s0_wh = frozenset({lit('AtRobot','dock'), lit('GripperEmpty'), lit('At','item1','rack_A'), lit('At','item2','rack_B')} | conn)
goal_wh = {lit('At','item1','pack'), lit('At','item2','pack')}

plan = bfs_plan(s0_wh, goal_wh, grounded)
for i, a in enumerate(plan or [], 1): print(f"{i:02d}. {a.name}")

Strengths & Limitations

Strengths

Clarity & verifiability: Symbolic models are interpretable; you can inspect goals, preconditions, and effects.
Reusability: Domain models (operators) can be reused across many problem instances (different initial/goal states).
Generalization: A single planner solves many tasks in the same domain without retraining.

Limitations

Modeling effort: Requires hand-crafted predicates and operators; missing effects cause brittle plans.
Scalability: State/action blow-up; naive search can be slow without heuristics or decomposition.
Assumptions: Deterministic, fully observable, static environments; real world often violates these (uncertainty, continuous dynamics).

Final Notes

You learned how to encode the world as facts and actions as transitions and then let a search procedure find a valid sequence from start to goal. You implemented STRIPS-style planning twice: first in Blocks World, then in a warehouse robot scenario—demonstrating direct transfer from toy to applied setting.

This foundation powers many practical systems, from task-level robot control to automated process orchestration.

Next Steps for You:

Upgrade the search: Replace BFS with A* and experiment with simple heuristics (e.g., number of unsatisfied goal literals; delete-relaxation approximations).

Richer domains: Add capacities (e.g., carts), deadlines, or costs; try multi-item batching and introduce Uniform-Cost Search or A* with edge costs.

(Optional bonus) Try PDDL: Model the warehouse in PDDL and run an off-the-shelf planner (e.g., Fast Downward) to compare plans and performance.

References

[1] R. E. Fikes and N. J. Nilsson, “STRIPS: A new approach to the application of theorem proving to problem solving,” Artificial Intelligence, vol. 2, no. 3–4, pp. 189–208, 1971.
[2] S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2020.
[3] M. Ghallab, D. Nau, and P. Traverso, Automated Planning: Theory and Practice. Morgan Kaufmann, 2004.
[4] A. Coles, A. Coles, M. Fox, and D. Long, “Forward-chaining partial-order planning,” ICAPS, 2010.
[5] A. Blum and M. Furst, “Fast planning through planning graph analysis,” Artificial Intelligence, vol. 90, no. 1–2, pp. 281–300, 1997.

Classical Planning (STRIPS): From Symbols to Sequencing

Why Classical Planning?

Theory Deep Dive

1. Formal Definition

2. STRIPS assumptions & modeling choices

3. Typical predicates & operators (Blocks World)

4. Complexity & heuristics (intuition)

5. From STRIPS to PDDL (industry/academia lingua franca)

Toy Problem – Blocks World (3 blocks)

Data Snapshot

Step 1: Represent literals and states

Step 2: Define the Blocks World domain (schemas)

Step 3: Operator schemas for Blocks World

Step 4: Apply actions & BFS planner (progression)

Step 5: Instantiate the problem and solve

Quick Reference: Full Code

Real‑World Application — Warehouse Robot Task Sequencing

Step 1: Define warehouse predicates & schemas

Step 2: Ground domain and build the initial state

Step 3: Plan and print a readable schedule

Quick Reference: Full API (`app.py`)

Strengths & Limitations

Strengths

Limitations

Final Notes

References

Leave a comment Cancel reply

Classical Planning (STRIPS): From Symbols to Sequencing

Why Classical Planning?

Theory Deep Dive

1. Formal Definition

2. STRIPS assumptions & modeling choices

3. Typical predicates & operators (Blocks World)

4. Complexity & heuristics (intuition)

5. From STRIPS to PDDL (industry/academia lingua franca)

Toy Problem – Blocks World (3 blocks)

Data Snapshot

Step 1: Represent literals and states

Step 2: Define the Blocks World domain (schemas)

Step 3: Operator schemas for Blocks World

Step 4: Apply actions & BFS planner (progression)

Step 5: Instantiate the problem and solve

Quick Reference: Full Code

Real‑World Application — Warehouse Robot Task Sequencing

Step 1: Define warehouse predicates & schemas

Step 2: Ground domain and build the initial state

Step 3: Plan and print a readable schedule

Quick Reference: Full API (app.py)

Strengths & Limitations

Strengths

Limitations

Final Notes

References

Share this:

Leave a comment Cancel reply

Quick Reference: Full API (`app.py`)