Neural Sync Active

🤖 Automated Planning

Registry Synced

🤖 Automated Planning

361 words

2 min read

Reading compass

Now · 1. 🎯 Learning Objectives

🤖 Automated Planning

1. 🎯 Learning Objectives

Distinguish FSSP (forward) from BSSP (backward) planning
Trace Goal Stack Planning (GSP) with push/pop operations
Solve Blocks World problems using GSP
Identify non-serializable subgoals

2. 📖 Core Content

3.1 What is Planning?

Planning finds a sequence of actions that transforms the world from initial state to goal state. Unlike general search, planning exploits action structure (preconditions and effects).

3.2 FSSP (Forward State Space Planning)

Forward search from initial state, applying applicable actions (all preconditions satisfied). Branching factor: Number of applicable actions at each state. Can be very high.

3.3 BSSP (Backward State Space Planning)

Backward search from goal state, finding relevant actions (effect achieves at least one goal condition). Spurious subgoals: May generate irrelevant preconditions that don't actually help reach the goal.

3.4 Goal Stack Planning (GSP)


text
GSP(initial_state, goal, actions):
    stack = [goal]
    plan = []
    current_state = initial_state
    while stack is not empty:
        top = peek(stack)
        if top satisfied: pop(stack)
        elif top is a condition:
            find action achieving it, push action
        elif top is an action:
            if preconditions satisfied: apply, pop, plan.append
            else: push unsatisfied preconditions
        elif top is a conjunction:
            push individual subgoals in reverse order

3.5 Blocks World Example

Initial: onTable(A), onTable(B), clear(A), clear(B), armEmpty Goal: on(A,B) Actions: stack(x,y), unstack(x,y), pickup(x), putdown(x) GSP Trace:

Goal: on(A,B). Push stack(A,B).
stack(A,B) needs holding(A), clear(B). Push holding(A).
holding(A): push pickup(A).
pickup(A) needs onTable(A), clear(A), armEmpty. All satisfied → apply.
holding(A) satisfied. Now stack(A,B) satisfied → apply.
on(A,B) satisfied. Done! Plan: [pickup(A), stack(A,B)]

3.6 Non-Serializable Subgoals

Some subgoal sets cannot be achieved independently. The Sussman Anomaly: Goal: on(A,B) AND on(B,C) Problem: Achieving one may undo the other. Solution: Interleave — achieve both simultaneously through careful ordering.

4. 📝 Practice Questions

Q1: In Blocks World, initial state onTable(A), onTable(B), clear(A), clear(B), armEmpty. Goal on(B,A). Trace GSP.

Answer: Goal on(B,A) → push stack(B,A). Needs holding(B), clear(A). holding(B) → pickup(B). Preconditions met → apply pickup(B). holding(B) satisfied. stack(B,A): holding(B) ✓, clear(A) ✓ → apply stack(B,A). Plan: [pickup(B), stack(B,A)]. Join Discord PreviousSSS* AlgorithmNextBlocks World