Solve a blocks-world planning problem with STRIPS operators (pickup/putdown/stack/unstack) by BFS over states, and print the action sequence.

Answer

from collections import deque # A state is a frozenset of ground predicates. def operators(state): blocks = ["A", "B", "C"] ops = [] for x in blocks: if ("clear", x) in state and ("ontable", x) in state and ("handempty",) in state: ops.append((f"pickup({x})", {("holding", x)}, {("ontable", x), ("clear", x), ("handempty",)})) if ("holding", x) in state: ops.append((f"putdown({x})", {("ontable", x), ("clear", x), ("handempty",)}, {("holding", x)})) for y in blocks: if x == y: continue if ("holding", x) in state and ("clear", y) in state: ops.append((f"stack({x},{y})", {("on", x, y), ("clear", x), ("handempty",)}, {("holding", x), ("clear", y)})) if ("on", x, y) in state and ("clear", x) in state and ("handempty",) in state: ops.append((f"unstack({x},{y})", {("holding", x), ("clear", y)}, {("on", x, y), ("clear", x), ("handempty",)})) return ops def plan(start, goal): seen = {start} q = deque([(start, [])]) while q: state, actions = q.popleft() if goal <= state: return actions for name, add, dele in operators(state): ns = frozenset((state - dele) | add) if ns not in seen: seen.add(ns) q.append((ns, actions + [name])) return None start = frozenset({ ("on", "C", "A"), ("ontable", "A"), ("ontable", "B"), ("clear", "C"), ("clear", "B"), ("handempty",), }) goal = frozenset({("on", "B", "A")}) print("plan:", plan(start, goal))