Symbolic Planner

Introduction

A symbolic planner is an AI system that figures out how to achieve a goal by reasoning about actions and their effects. Given a starting state, a goal, and a set of possible actions, the planner finds a sequence of actions that transforms the start into the goal.

For example, in the classic 'blocks world' problem, you might have blocks stacked in one configuration and want them in another. The planner determines which blocks to move and in what order.

Key Components

• Initial state — what's true at the start (e.g., Block A is on Block B)
• Goal state — what should be true at the end (e.g., Block A is on the table)
• Actions — operations that change the state (e.g., Move block X from Y to Z)
• Plan — the output sequence of actions that achieves the goal

Symbolic planning process.

A-Star Search Algorithm

The planner uses A-Star search to find optimal plans. A-Star balances two factors: the cost already spent to reach a state (g-score) and an estimate of the remaining cost to the goal (h-score, the heuristic). States are explored in order of f = g + h, prioritizing paths that seem most promising.

The heuristic counts how many goal conditions aren't yet satisfied. This is admissible (never overestimates) since each unsatisfied condition requires at least one action to fix. An admissible heuristic guarantees A-Star finds optimal solutions.

• g-score — number of actions taken so far
• h-score — number of unsatisfied goal conditions (heuristic)
• f-score — g + h, used to prioritize which state to explore next

Implementation Details

Two key functions drive the search: is_goal() checks if the current state satisfies all goal conditions, and heuristic() estimates how far we are from the goal by counting unsatisfied conditions.

1bool is_goal(const Node &currNode) {
2    // Check if all goal conditions exist in current state
3    for (auto &goalCond : goal.grounded_conditions) {
4        if (currNode.state.find(goalCond) == currNode.state.end())
5            return false;
6    }
7    return true;
8}
9
10int heuristic(const State &state) {
11    // Count unsatisfied goal conditions
12    int unmet = 0;
13    for (auto &goalCond : goal.grounded_conditions) {
14        if (state.find(goalCond) == state.end()) unmet++;
15    }
16    return unmet;
17}

State Expansion

State expansion generates all possible next states from the current state. For each action, the planner tries all valid argument combinations (grounding), checks if preconditions are met, and if so, applies the action's effects to create a new state.

For example, a Move(block, from, to) action might be grounded as Move(A, B, Table). If preconditions hold (A is on B, A is clear, Table is clear), the action creates a new state where A is now on Table.

1vector<State> expand_state(State &currState) {
2    vector<State> successors;
3    for (const Action &action : actions) {
4        // Try all argument permutations
5        for (auto &args : get_action_arg_permutations(action)) {
6            auto preconditions = ground_preconditions(action, args);
7            if (check_conditions(preconditions, currState)) {
8                auto effects = ground_effects(action, args);
9                successors.push_back(apply_action(effects, currState));
10            }
11        }
12    }
13    return successors;
14}

Action Grounding

Actions are defined with symbolic parameters like Move(b, x, y). Grounding replaces these with concrete objects: if we have blocks A, B, C and Table, then Move(b, x, y) grounds to Move(A, B, Table), Move(A, C, Table), etc.

The planner generates all permutations of available symbols for each action's argument count, then filters by checking preconditions. Only valid groundings produce successor states.

1bool check_conditions(vector<Condition> &preconditions, State &state) {
2    for (auto &cond : preconditions) {
3        bool found = state.conditions.count(cond) > 0;
4        if (cond.is_positive() != found) return false;
5    }
6    return true;
7}

Example: Blocks World

The classic blocks world problem demonstrates symbolic planning. Given blocks A, B, C initially stacked, the goal is to rearrange them into a target configuration.

1Initial: On(A,B) On(B,Table) On(C,Table) Clear(A) Clear(C)
2Goal:    On(A,Table) On(C,A) On(B,C)
3
4Actions:
5  Move(b,x,y):     On(b,x) Clear(b) Clear(y) → On(b,y) Clear(x)
6  MoveToTable(b,x): On(b,x) Clear(b) → On(b,Table) Clear(x)
7
8Plan found:
9  1. MoveToTable(A,B)  — A from B to Table
10  2. Move(C,Table,A)   — C from Table to A
11  3. Move(B,Table,C)   — B from Table to C

The planner recognizes that A must be moved first (it's blocking B), then builds the target stack from the bottom up.

Example: Fire Extinguisher

A more complex scenario: a quadcopter must extinguish a fire by making multiple trips to fill water and recharge batteries. This demonstrates planning with resource management.

1Initial: Quad(Q) At(Q,B) At(R,A) Fire(F) InAir(Q) EmptyTank(Q) HighCharge(Q)
2Goal:    ExtThree(F)  — fire fully extinguished after 3 pours
3
4Key Actions:
5  PourOnce/Twice/Thrice(x) — requires FullTank, HighCharge, empties tank
6  FillWater(Q)             — fill tank at water location W
7  Charge(Q)                — recharge battery while on robot
8  MoveTogether(x,y)        — robot carries quadcopter between locations
9
10Plan found (21 actions):
11  MoveToLoc(A,B) → LandOnRob(B) → MoveTogether(B,W) → FillWater(Q)
12  → MoveTogether(W,F) → TakeOffFromRob(F) → PourOnce(F)
13  → LandOnRob(F) → Charge(Q) → MoveTogether(F,W) → FillWater(Q)
14  → MoveTogether(W,F) → TakeOffFromRob(F) → PourTwice(F)
15  → LandOnRob(F) → Charge(Q) → MoveTogether(F,W) → FillWater(Q)
16  → MoveTogether(W,F) → TakeOffFromRob(F) → PourThrice(F)

The planner handles the constraint that the quadcopter can only pour once per tank and needs to recharge between pours, automatically generating a multi-trip plan.

Performance

The planner was tested with and without the heuristic to measure its impact on search efficiency.

Evaluation Metrics

• States expanded — how many states were explored before finding a solution
• Plan length — number of actions in the solution
• Wall clock time — total time to find the plan

With the heuristic enabled, the planner expanded significantly fewer states and found solutions faster. The heuristic's guidance is especially important in larger state spaces where uninformed search becomes intractable.

Conclusion

The symbolic planner successfully solves a variety of planning problems using A-Star search. The heuristic function proved critical for efficiency—without it, the planner struggles with larger state spaces.

• A-Star with admissible heuristic — guarantees optimal plans
• State expansion — tries all valid action groundings from current state
• Scalability challenge — large domains require better heuristics or alternative approaches