In previous chapters, you studied motion planning in configuration space and grasp planning for manipulation. These algorithms operate on continuous state spaces such as a configuration space \( C \subseteq \mathbb{R}^n \) or a state space \( X \subseteq \mathbb{R}^m \). In contrast, a symbolic task planner reasons over discrete descriptions of the world (predicates like On(object, table)) and chooses sequences of abstract actions such as Pick(object, grasp) or Place(object, region).

Task and Motion Planning (TAMP) connects these two layers:

\[ \text{TAMP instance} = \big( \Pi_{\text{sym}}, \mathcal{M}_{\text{geom}}, \mathcal{R} \big) \]

• \( \Pi_{\text{sym}} \) is a symbolic planning problem, specified over a finite state space and discrete actions.
• \( \mathcal{M}_{\text{geom}} \) is a geometric motion planning problem over a configuration or state space (as in Chapters 1–5).
• \( \mathcal{R} \) is a refinement map from symbolic states to sets of feasible robot configurations.

Intuitively, the symbolic planner proposes a high-level plan (an action skeleton), and the geometric planner tries to realize it by computing concrete collision-free motions that respect kinematic and dynamic constraints introduced earlier in the course.

flowchart TD
  G["Task goal description (predicates)"] --> SPlan["Symbolic planner (discrete search)"]
  SPlan --> Skel["Action skeleton: pick, move, place, ..."]
  Skel --> Ref["Refinement interface (refinement map R)"]
  Ref --> Geom["Geometric motion planner in C-space"]
  Geom --> Check["Feasibility check (collision, kinematics, grasps)"]
  Check -->|feasible| Sol["Executable trajectory and control"]
  Check -->|infeasible| Back["Backtrack / new skeleton"]
  Back --> SPlan
        

We adopt a classical planning model. Let \( \mathcal{F} \) be a finite set of propositional fluents (predicates that may be true or false). A symbolic state is a truth assignment to all fluents, and the state space is

\[ S_{\text{sym}} = 2^{\mathcal{F}} = \big\{ s \subseteq \mathcal{F} \big\}, \]

where we identify a state \( s \) with the set of fluents that hold in that state.

A symbolic planning problem is a tuple

\[ \Pi_{\text{sym}} = \big( \mathcal{F}, A, I, G \big), \]

• \( \mathcal{F} \): finite set of fluents.
• \( A \): finite set of actions.
• \( I \subseteq \mathcal{F} \): initial state.
• \( G \subseteq \mathcal{F} \): goal condition (conjunction of fluents that must hold).

Each action \( a \in A \) is specified by a triple

\[ a = \langle \mathrm{pre}(a), \mathrm{add}(a), \mathrm{del}(a) \rangle, \]

where \( \mathrm{pre}(a), \mathrm{add}(a), \mathrm{del}(a) \subseteq \mathcal{F} \). An action \( a \) is applicable in state \( s \) if \( \mathrm{pre}(a) \subseteq s \). The successor state is

\[ \gamma(s,a) = \big(s \setminus \mathrm{del}(a)\big) \cup \mathrm{add}(a). \]

A symbolic plan of horizon \( T \) is a sequence \( \pi_{\text{sym}} = (a_0,\dots,a_{T-1}) \) such that

\[ s_{k+1} = \gamma(s_k,a_k) \quad \text{for } k = 0,\dots,T-1 , \]

with \( s_0 = I \) and \( G \subseteq s_T \). Classical symbolic planners (forward search, heuristic search, etc.) operate purely at this discrete level, ignoring geometry, collisions, and robot kinematics.

For TAMP, the fluents typically encode:

• Object poses at a symbolic level (e.g., On(Box1, Shelf)).
• Robot-object relations (e.g., Holding(Box1)).
• Discrete modes such as HandEmpty, GraspType(precision), or RegionFree(regionA).

From earlier chapters, a geometric motion planning problem for a robot with configuration space \( C \subseteq \mathbb{R}^n \) can be written as

\[ \mathcal{M}_{\text{geom}} = \big( C, C_{\text{free}}, q_{\text{start}}, Q_{\text{goal}} \big), \]

• \( C \): configuration space.
• \( C_{\text{free}} \subseteq C \): collision-free configurations (with respect to robot and environment).
• \( q_{\text{start}} \in C_{\text{free}} \): start configuration.
• \( Q_{\text{goal}} \subseteq C_{\text{free}} \): set of goal configurations (e.g., end-effector pose at a target grasp).

A feasible trajectory is a continuous map \( q : [0,1] \to C_{\text{free}} \) such that \( q(0) = q_{\text{start}} \) and \( q(1) \in Q_{\text{goal}} \). In kinodynamic settings you studied earlier, the state space becomes \( X \subseteq \mathbb{R}^m \) and trajectories must satisfy differential constraints

\[ \dot{x}(t) = f\big(x(t),u(t)\big), \quad x(t) \in X_{\text{free}}, \quad u(t) \in U, \]

but the core idea is the same: geometric motion planning concerns existence and computation of continuous paths that remain feasible in \( C_{\text{free}} \) or \( X_{\text{free}} \).

Pure motion planners (PRM, RRT, TrajOpt, etc.) answer queries of the form:

\[ \text{Given } (q_{\text{start}}, Q_{\text{goal}}), \; \text{compute } q(\cdot) \text{ with } q(0) = q_{\text{start}}, \; q(1) \in Q_{\text{goal}}, \; q(t) \in C_{\text{free}} \ \forall t. \]

They do not, by themselves, decide which objects to move or in what high-level order.

The central mathematical bridge in TAMP is the refinement map. Let \( S_{\text{sym}} \) be the symbolic state space and \( C \) the configuration space of the robot (possibly extended with object poses for movable objects).

A refinement map is a function

\[ \mathcal{R} : S_{\text{sym}} \to 2^{C} \]

that associates to each symbolic state \( s \) a set of feasible configurations \( \mathcal{R}(s) \subseteq C \) that are geometrically consistent with the symbolic description. For example:

• If On(Box1, Shelf) is true in \( s \), then every configuration in \( \mathcal{R}(s) \) must place the pose of Box1 on the shelf region.
• If Holding(Box1) is true, then the configuration must realize a kinematically feasible grasp of Box1 by the robot gripper.
• Collisions are disallowed, so \( \mathcal{R}(s) \subseteq C_{\text{free}} \).

For an action \( a \), a symbolic transition \( s' = \gamma(s,a) \) is geometrically feasible if there exist \( q \in \mathcal{R}(s) \) and \( q' \in \mathcal{R}(s') \) and a continuous path \( q_{\text{seg}} : [0,1] \to C_{\text{free}} \) with

\[ q_{\text{seg}}(0) = q, \quad q_{\text{seg}}(1) = q', \quad q_{\text{seg}}(t) \in C_{\text{free}} \ \forall t. \]

A symbolic plan \( \pi_{\text{sym}} = (a_0,\dots,a_{T-1}) \) with state sequence \( (s_0,\dots,s_T) \) is geometrically realizable if there exist

\[ q_k \in \mathcal{R}(s_k), \quad q^{(k)} : [0,1] \to C_{\text{free}} \quad \text{for } k=0,\dots,T-1, \]

such that \( q^{(k)}(0) = q_k \), \( q^{(k)}(1) = q_{k+1} \), and each segment respects the semantics of action \( a_k \) (e.g., the grasp closes only during a Pick action).

flowchart TD
  SS["Symbolic state s_k"] --> R1["Refinement set R(s_k) in C-space"]
  SSN["Symbolic state s_(k+1)"] --> R2["Refinement set R(s_(k+1))"]
  R1 --> Pth["Motion planner: path from q in R(s_k) to q' in R(s_(k+1))"]
  R2 --> Pth
  Pth --> Feas["Transition geometrically feasible"]
        

Let a TAMP algorithm take as input \( (\Pi_{\text{sym}}, \mathcal{M}_{\text{geom}}, \mathcal{R}) \) and output either failure or a pair

\[ \big(\pi_{\text{sym}}, \; q(\cdot)\big), \]

where \( \pi_{\text{sym}} \) is a symbolic plan and \( q(\cdot) \) a continuous trajectory. We can define:

• Task-level soundness. Every returned pair is physically feasible and achieves the goal.
• Task-level completeness. If there exists some physically feasible combination of a symbolic plan and trajectory, the algorithm will eventually find one.

A refinement map \( \mathcal{R} \) is geometrically sound if, whenever \( q \in \mathcal{R}(s) \), the geometric scene implied by \( q \) truly satisfies all fluents in \( s \). Formally, if \( \Phi(q) \subseteq \mathcal{F} \) denotes the set of fluents that hold in the world at configuration \( q \), then

\[ \mathcal{R} \text{ is sound if } q \in \mathcal{R}(s) \Rightarrow s \subseteq \Phi(q) \quad \forall s \in S_{\text{sym}}, \; q \in C. \]

A simple but important theorem is:

Theorem (Soundness of Refinement-Based TAMP).

Suppose (i) the refinement map \( \mathcal{R} \) is geometrically sound, (ii) all geometric motion planners invoked inside the TAMP algorithm are collision-free and respect kinematic constraints, and (iii) action-specific geometric constraints (grasps, placements, etc.) are encoded correctly in the refinement sets. Then every solution produced by the algorithm is task-level sound.

Sketch of proof.

1. Let \( (\pi_{\text{sym}}, q(\cdot)) \) be the returned solution with state sequence \( (s_0,\dots,s_T) \) and segment endpoints \( q_k = q(t_k) \in \mathcal{R}(s_k) \).
2. By geometric soundness of \( \mathcal{R} \), \( s_k \subseteq \Phi(q_k) \) for all \( k \).
3. For each action \( a_k \), the segment \( q|_{[t_k,t_{k+1}]} \) satisfies the kinematic and collision constraints, and ensures that the effect of \( a_k \) matches the transition \( s_k \to s_{k+1} \).
4. By induction on \( k \), the executed trajectory enforces the same state sequence at the geometric level.
5. Since \( G \subseteq s_T \subseteq \Phi(q_T) \), the goal condition holds at the final configuration.

Completeness is much harder to guarantee in practice, because the search over both symbolic plans and geometric realizations is extremely large. Many TAMP algorithms settle for probabilistic completeness under simplifying assumptions (e.g., sampling-based geometric planners and bounded branching symbolic search).

We build a toy TAMP skeleton that combines:

• A symbolic planner over a small planning problem represented in Python.
• A geometric feasibility check over a 2D configuration space \( C \subseteq \mathbb{R}^2 \).

In real systems, the geometric planner would call libraries such as ompl or moveit_commander via ROS. Here we implement a simple straight-line collision check.

from dataclasses import dataclass, field
from typing import FrozenSet, Tuple, List, Callable, Optional
import math

# ----------------------------------------------------------------------
# Symbolic planning structures
# ----------------------------------------------------------------------

Fluent = str
State = FrozenSet[Fluent]

@dataclass(frozen=True)
class Action:
    name: str
    pre: FrozenSet[Fluent]
    add: FrozenSet[Fluent]
    delete: FrozenSet[Fluent]

    def applicable(self, s: State) -> bool:
        return self.pre.issubset(s)

    def apply(self, s: State) -> State:
        assert self.applicable(s)
        return (s - self.delete) | self.add

# Example domain: pick-and-place of one object from table to shelf
FLUENTS = {
    "HandEmpty",
    "On(Box,Table)",
    "On(Box,Shelf)",
    "Holding(Box)",
}

ACTIONS = [
    Action(
        name="PickFromTable",
        pre=frozenset({"HandEmpty", "On(Box,Table)"}),
        add=frozenset({"Holding(Box)"}),
        delete=frozenset({"HandEmpty", "On(Box,Table)"}),
    ),
    Action(
        name="PlaceOnShelf",
        pre=frozenset({"Holding(Box)"}),
        add=frozenset({"On(Box,Shelf)", "HandEmpty"}),
        delete=frozenset({"Holding(Box)"}),
    ),
]

INIT: State = frozenset({"HandEmpty", "On(Box,Table)"})
GOAL: State = frozenset({"On(Box,Shelf)"})

# ----------------------------------------------------------------------
# Geometric layer: 2D point robot with circular obstacles
# ----------------------------------------------------------------------

Config = Tuple[float, float]

OBSTACLES = [
    ((0.5, 0.5), 0.2),  # center, radius
]

def in_collision(q: Config) -> bool:
    x, y = q
    for (cx, cy), r in OBSTACLES:
        if math.hypot(x - cx, y - cy) <= r:
            return True
    return False

def straight_line_collision_free(q_start: Config, q_goal: Config, steps: int = 50) -> bool:
    for i in range(steps + 1):
        alpha = i / steps
        x = (1 - alpha) * q_start[0] + alpha * q_goal[0]
        y = (1 - alpha) * q_start[1] + alpha * q_goal[1]
        if in_collision((x, y)):
            return False
    return True

# ----------------------------------------------------------------------
# Refinement map R(s): here we hard-code representative configurations
# ----------------------------------------------------------------------

REFINEMENT = {
    # Robot at table, box on table
    frozenset({"HandEmpty", "On(Box,Table)"}): (0.1, 0.1),
    # Robot grasps box near table
    frozenset({"Holding(Box)"}): (0.2, 0.2),
    # Robot at shelf, box on shelf, hand empty
    frozenset({"HandEmpty", "On(Box,Shelf)"}): (0.9, 0.9),
}

def refine_state(s: State) -> Optional[Config]:
    """
    Very coarse refinement: pick a nominal configuration for state s,
    or return None if unknown.
    """
    # Use subset matching to deal with extra fluents like HandEmpty
    for key_state, q in REFINEMENT.items():
        if key_state.issubset(s):
            return q
    return None

def geom_feasible_transition(s: State, a: Action, s_next: State) -> bool:
    """
    Check if symbolic transition s -a-> s_next has a straight-line
    geometric realization between representative configurations.
    """
    q = refine_state(s)
    q_next = refine_state(s_next)
    if q is None or q_next is None:
        return False
    if in_collision(q) or in_collision(q_next):
        return False
    return straight_line_collision_free(q, q_next)

# ----------------------------------------------------------------------
# Integrated search: BFS over symbolic states with geometric pruning
# ----------------------------------------------------------------------

@dataclass
class Node:
    state: State
    plan: List[Action] = field(default_factory=list)

def tamp_bfs(init: State, goal: State, actions: List[Action]) -> Optional[Node]:
    from collections import deque
    frontier = deque([Node(state=init, plan=[])])
    visited = {init}
    while frontier:
        node = frontier.popleft()
        if goal.issubset(node.state):
            return node
        for a in actions:
            if not a.applicable(node.state):
                continue
            s_next = a.apply(node.state)
            if s_next in visited:
                continue
            # Geometric feasibility pruning
            if not geom_feasible_transition(node.state, a, s_next):
                continue
            visited.add(s_next)
            frontier.append(Node(state=s_next, plan=node.plan + [a]))
    return None

if __name__ == "__main__":
    sol = tamp_bfs(INIT, GOAL, ACTIONS)
    if sol is None:
        print("No TAMP solution found.")
    else:
        print("Symbolic plan:")
        for a in sol.plan:
            print(" -", a.name)
        print("Final state:", sol.state)
      

This toy example demonstrates the idea of geometric pruning: symbolic successors that cannot be realized by a collision-free motion between their representative configurations are discarded.

Many robotics frameworks (e.g., OMPL, MoveIt) expose C++ APIs for motion planning. Below is a sketch of how one could structure symbolic actions together with a refinement map in modern C++.

#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <unordered_map>
#include <optional>
#include <cmath>

using Fluent = std::string;
using State  = std::set<Fluent>;

struct Action {
    std::string name;
    State pre;
    State add;
    State del;

    bool applicable(const State& s) const {
        for (const auto& f : pre) {
            if (!s.count(f)) return false;
        }
        return true;
    }

    State apply(const State& s) const {
        State out = s;
        for (const auto& f : del) out.erase(f);
        for (const auto& f : add) out.insert(f);
        return out;
    }
};

struct Config2D {
    double x{0.0}, y{0.0};
};

bool inCollision(const Config2D& q) {
    const Config2D c{0.5, 0.5};
    const double r = 0.2;
    const double dx = q.x - c.x;
    const double dy = q.y - c.y;
    return std::sqrt(dx * dx + dy * dy) <= r;
}

bool straightLineFree(const Config2D& q0, const Config2D& q1, int steps = 50) {
    for (int i = 0; i <= steps; ++i) {
        double alpha = static_cast<double>(i) / steps;
        Config2D q{(1 - alpha) * q0.x + alpha * q1.x,
                   (1 - alpha) * q0.y + alpha * q1.y};
        if (inCollision(q)) return false;
    }
    return true;
}

// Refinement table
struct StateHash {
    std::size_t operator()(State const& s) const noexcept {
        std::size_t h = 0;
        for (const auto& f : s) {
            h ^= std::hash<std::string>{}(f) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
        }
        return h;
    }
};

struct StateEq {
    bool operator()(State const& a, State const& b) const noexcept {
        return a == b;
    }
};

std::unordered_map<State, Config2D, StateHash, StateEq> Rtable;

std::optional<Config2D> refine(const State& s) {
    for (const auto& kv : Rtable) {
        const State& key = kv.first;
        bool subset = true;
        for (const auto& f : key) {
            if (!s.count(f)) { subset = false; break; }
        }
        if (subset) return kv.second;
    }
    return std::nullopt;
}

bool geomFeasible(const State& s, const Action& a, const State& sNext) {
    auto q  = refine(s);
    auto qn = refine(sNext);
    if (!q || !qn) return false;
    if (inCollision(*q) || inCollision(*qn)) return false;
    return straightLineFree(*q, *qn);
}
      

In a full implementation, straightLineFree would be replaced by calls to OMPL or MoveIt planners that operate in high-dimensional configuration spaces.

Java is less common in low-level motion planning but appears in some middleware (e.g., ROSJava) and simulation environments. Below is a simple symbolic planner skeleton that could be combined with a geometry server written in C++.

import java.util.*;

class Action {
    public final String name;
    public final Set<String> pre;
    public final Set<String> add;
    public final Set<String> del;

    public Action(String name, Set<String> pre, Set<String> add, Set<String> del) {
        this.name = name;
        this.pre = pre;
        this.add = add;
        this.del = del;
    }

    public boolean applicable(Set<String> s) {
        return s.containsAll(pre);
    }

    public Set<String> apply(Set<String> s) {
        Set<String> out = new HashSet<>(s);
        out.removeAll(del);
        out.addAll(add);
        return out;
    }
}

class Node {
    public final Set<String> state;
    public final List<Action> plan;

    public Node(Set<String> state, List<Action> plan) {
        this.state = state;
        this.plan = plan;
    }
}

public class TAMPPlanner {

    // Stub for geometric feasibility: in practice this would call a C++ node
    // via ROS services or gRPC to check motion-planning feasibility.
    public static boolean geomFeasible(Set<String> s, Action a, Set<String> sNext) {
        // TODO: connect to geometric planner; here we just return true
        return true;
    }

    public static Node bfs(Set<String> init, Set<String> goal, List<Action> actions) {
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(init, new ArrayList<>()));
        Set<Set<String>> visited = new HashSet<>();
        visited.add(init);
        while (!q.isEmpty()) {
            Node n = q.remove();
            if (n.state.containsAll(goal)) {
                return n;
            }
            for (Action a : actions) {
                if (!a.applicable(n.state)) continue;
                Set<String> sNext = a.apply(n.state);
                if (visited.contains(sNext)) continue;
                if (!geomFeasible(n.state, a, sNext)) continue;
                visited.add(sNext);
                List<Action> newPlan = new ArrayList<>(n.plan);
                newPlan.add(a);
                q.add(new Node(sNext, newPlan));
            }
        }
        return null;
    }

    public static void main(String[] args) {
        Set<String> init = new HashSet<>(Arrays.asList("HandEmpty", "On(Box,Table)"));
        Set<String> goal = new HashSet<>(Arrays.asList("On(Box,Shelf)"));
        List<Action> actions = new ArrayList<>();
        actions.add(new Action(
                "PickFromTable",
                new HashSet<>(Arrays.asList("HandEmpty", "On(Box,Table)")),
                new HashSet<>(Arrays.asList("Holding(Box)")),
                new HashSet<>(Arrays.asList("HandEmpty", "On(Box,Table)"))
        ));
        actions.add(new Action(
                "PlaceOnShelf",
                new HashSet<>(Arrays.asList("Holding(Box)")),
                new HashSet<>(Arrays.asList("On(Box,Shelf)", "HandEmpty")),
                new HashSet<>(Arrays.asList("Holding(Box)"))
        ));

        Node sol = bfs(init, goal, actions);
        if (sol == null) {
            System.out.println("No plan found.");
        } else {
            System.out.println("Plan:");
            for (Action a : sol.plan) {
                System.out.println(" - " + a.name);
            }
        }
    }
}
      

The geometric feasibility check here is a stub; in a full TAMP system, geomFeasible would communicate with a geometric planner to ensure the action transition is realizable.

MATLAB, together with Robotics System Toolbox, provides planners such as manipulatorRRT and plannerRRT. The following script shows how one might connect a symbolic state machine to a geometric planner, using a function handle checkGeomTransition.

function tamp_demo()
    % Symbolic states encoded as integer ids for simplicity
    % 1: HandEmpty & On(Box,Table)
    % 2: Holding(Box)
    % 3: HandEmpty & On(Box,Shelf)
    INIT = 1;
    GOAL = 3;

    % Actions: [preState nextState id]
    actions = [...
        1 2 1;  % PickFromTable
        2 3 2   % PlaceOnShelf
    ];

    plan = breadthFirstTAMP(INIT, GOAL, actions);
    disp('Symbolic action ids:'), disp(plan);
end

function plan = breadthFirstTAMP(initState, goalState, actions)
    queue = {struct('state', initState, 'plan', [])};
    visited = initState;
    head = 1;
    plan = [];
    while head <= numel(queue)
        node = queue{head}; head = head + 1;
        if node.state == goalState
            plan = node.plan;
            return;
        end
        for i = 1:size(actions,1)
            a = actions(i,:);
            pre = a(1); nxt = a(2); aid = a(3);
            if pre ~= node.state
                continue;
            end
            if ismember(nxt, visited)
                continue;
            end
            if ~checkGeomTransition(node.state, nxt, aid)
                continue;
            end
            visited(end+1) = nxt; %#ok<AGROW>
            child.state = nxt;
            child.plan  = [node.plan, aid];
            queue{end+1} = child; %#ok<AGROW>
        end
    end
end

function ok = checkGeomTransition(s, sNext, aid)
    % In a full implementation, this would:
    % 1) Map symbolic states s, sNext to robot configurations using a
    %    refinement map.
    % 2) Invoke a motion planner (e.g. manipulatorRRT) to check whether
    %    a collision-free path exists.
    % Here we just return true as a placeholder.
    ok = true;
end
      

In Simulink, one could implement the symbolic controller as a Stateflow chart and connect it to a motion-planning block or MATLAB Function block that performs the geometric check.

Wolfram Mathematica is well-suited to symbolic manipulation of planning domains. Below is a simple representation of states and actions using replacement rules.

ClearAll[applyAction, applicableQ];

(* State as a list of atoms, e.g. {HandEmpty, On[Box, Table]} *)
applicableQ[action_, state_List] := 
 Module[{pre},
  pre = action["Pre"];
  SubsetQ[state, pre]
 ]

applyAction[action_, state_List] /; applicableQ[action, state] := 
 Module[{del, add},
  del = action["Del"];
  add = action["Add"];
  Union[Complement[state, del], add]
 ]

(* Define actions *)
pickFromTable = <|
  "Name" -> "PickFromTable",
  "Pre"  -> {HandEmpty, On[Box, Table]},
  "Add"  -> {Holding[Box]},
  "Del"  -> {HandEmpty, On[Box, Table]}
|>;

placeOnShelf = <|
  "Name" -> "PlaceOnShelf",
  "Pre"  -> {Holding[Box]},
  "Add"  -> {On[Box, Shelf], HandEmpty},
  "Del"  -> {Holding[Box]}
|>;

init  = {HandEmpty, On[Box, Table]};
goal  = {On[Box, Shelf]};

plan = {pickFromTable, placeOnShelf};

Fold[applyAction, init, plan]
      

A geometric layer could be modeled using regions in configuration space and Mathematica's path planning tools, with consistency constraints between regions and symbolic states implemented similarly to the refinement map \( \mathcal{R} \).

Problem 1 (Symbolic vs Geometric Feasibility). Consider a planar 2-DOF robot arm with configuration space \( C = [0,2\pi] \times [0,2\pi] \) and obstacle-free workspace. A symbolic plan instructs the robot to execute the sequence of actions MoveTo(q1), MoveTo(q2), MoveTo(q3), where the action MoveTo(q) is modeled symbolically as having no preconditions and an effect At(q).

(a) Define a symbolic planning problem \( \Pi_{\text{sym}} \) for this scenario.
(b) Suppose the refinement map is

\[ \mathcal{R}(s) = \big\{ q \in C \mid \text{At}(q) \in s \big\}. \]

Show that every symbolic plan in this domain is geometrically realizable (assuming no obstacles and continuous joint motion).

Solution.

(a) Let the set of fluents be \( \mathcal{F} = \{\text{At}(q) \mid q \in C\} \). A symbolic state \( s \subseteq \mathcal{F} \) must contain exactly one fluent of the form At(q). For each configuration \( q \in C \), define an action

\[ a_q = \langle \{\}, \{\text{At}(q)\}, \{\text{At}(q') \mid \text{At}(q') \in \mathcal{F}\} \rangle. \]

The initial state is \( I = \{\text{At}(q_{\text{start}})\} \), and the goal is \( G = \{\text{At}(q_{\text{goal}})\} \). A symbolic plan is any sequence of actions \( (a_{q_1},\dots,a_{q_T}) \) that ends in a state containing \( \text{At}(q_{\text{goal}}) \).

(b) For any consecutive pair \( s_k, s_{k+1} \) in a plan, we have \( s_k = \{\text{At}(q_k)\} \) and \( s_{k+1} = \{\text{At}(q_{k+1})\} \) for some configurations \( q_k, q_{k+1} \in C \). The refinement sets are singletons:

\[ \mathcal{R}(s_k) = \{q_k\}, \quad \mathcal{R}(s_{k+1}) = \{q_{k+1}\}. \]

Because there are no obstacles and joint limits are trivial (full torus), there exists a continuous path connecting \( q_k \) to \( q_{k+1} \) in \( C \), for example the straight line in joint space. Thus each symbolic transition is geometrically feasible, and the concatenation of these segments yields a continuous trajectory realizing the entire plan.

Problem 2 (Non-Sound Refinement Map). Consider an environment with a table and a wall. The symbolic fluent On(Box,Table) ignores whether the robot base collides with the wall. Suppose the refinement map for any state \( s \) containing On(Box,Table) picks a configuration \( q \) that is in collision with the wall.

(a) Argue that \( \mathcal{R} \) is not geometrically sound.
(b) Explain how this can cause a TAMP algorithm to violate task-level soundness even if the motion planner reports collision-free paths in \( C_{\text{free}} \).

Solution.

(a) By definition, \( \mathcal{R} \) is sound if \( s \subseteq \Phi(q) \) for all \( q \in \mathcal{R}(s) \). In this scenario, \( q \) lies in collision with the wall, so \( q \notin C_{\text{free}} \). If the real-world semantics of fluents implicitly require collision freedom (which is standard in manipulation domains), then \( \Phi(q) \) should not contain any fluent describing a valid placement of the box on the table in a collision-free world. Hence On(Box,Table) belongs to \( s \) but not to \( \Phi(q) \), violating \( s \subseteq \Phi(q) \).

(b) If the TAMP algorithm accepts symbolic plans whenever it finds geometric paths between the representative configurations \( q_k \in \mathcal{R}(s_k) \), then it may produce a trajectory that starts or ends in a configuration in collision with the wall. The motion planner may still consider each segment collision-free because it only checks paths inside \( C_{\text{free}} \), but the mis-specified refinement map allowed an endpoint \( q_k \notin C_{\text{free}} \), hence the resulting plan is physically invalid. Task-level soundness is thus broken by the unsound refinement map.

Problem 3 (Action Skeletons and Geometric Search Space). Let a symbolic plan have horizon \( T \). For each symbolic transition \( s_k \to s_{k+1} \), suppose the geometric planner must choose a configuration \( q_k \in \mathcal{R}(s_k) \) and \( q_{k+1} \in \mathcal{R}(s_{k+1}) \). Assume each refinement set is a compact subset of \( C \).

(a) Describe the combined continuous search space for realizing an entire action skeleton of length \( T \).
(b) Explain qualitatively why it may be easier to search over symbolic plans first and then refine them geometrically, instead of searching jointly over symbolic and geometric variables from scratch.

Solution.

(a) The tuple \( (q_0,\dots,q_T) \) must satisfy \( q_k \in \mathcal{R}(s_k) \) for each \( k \). Therefore the feasible set of waypoints lies in the product space

\[ \mathcal{Q} = \mathcal{R}(s_0) \times \mathcal{R}(s_1) \times \dots \times \mathcal{R}(s_T) \subseteq C^{T+1}. \]

Each candidate element of \( \mathcal{Q} \) induces \( T \) geometric motion-planning problems between consecutive waypoints.

(b) The dimension of \( \mathcal{Q} \) scales as \( (T+1) \dim(C) \), which is very large for high-DOF robots and long-horizon tasks. Searching jointly over action choices and all continuous waypoints becomes intractable. By decoupling the problem into (1) a symbolic search over a finite branching tree of actions and (2) continuous motion planning for each promising skeleton, we reduce the continuous search to a manageable per-skeleton refinement problem. This hierarchical decomposition is a core design principle of TAMP.

Problem 4 (Sufficient Condition for Realizability). Let \( \pi_{\text{sym}} = (a_0,\dots,a_{T-1}) \) be a symbolic plan with state sequence \( (s_0,\dots,s_T) \). Suppose that for every \( k \) there exists at least one pair \( (q_k,q_{k+1}) \in \mathcal{R}(s_k) \times \mathcal{R}(s_{k+1}) \) such that a collision-free path exists between them. Show that under these assumptions the plan is geometrically realizable in the sense of Section 4.

Solution.

By assumption, for each \( k \) there exists a feasible pair \( (q_k,q_{k+1}) \) and a continuous path \( q^{(k)} : [0,1] \to C_{\text{free}} \) connecting them. Concatenate the segments by defining a global trajectory \( q : [0,T] \to C_{\text{free}} \) via

\[ q(t) = q^{(k)}(t-k) \quad \text{for } t \in [k,k+1], \; k=0,\dots,T-1. \]

Each \( q^{(k)} \) is continuous and takes values in \( C_{\text{free}} \), so \( q \) is continuous and collision-free on \( [0,T] \). By construction, \( q(k) = q_k \in \mathcal{R}(s_k) \) and \( q(k+1) = q_{k+1} \in \mathcal{R}(s_{k+1}) \). Hence the plan meets the realizability definition: there exists a continuous trajectory that visits a configuration in each refinement set at the appropriate stage of the plan.

In this lesson, we formally separated symbolic task planning from geometric motion planning and introduced the refinement map \( \mathcal{R} \) as the mathematical link between them. Symbolic planners operate over finite sets of fluents and actions, while geometric planners work in continuous configuration spaces. TAMP systems combine these levels by generating action skeletons and checking their geometric realizability via sampling-based or optimization-based motion planners. We discussed soundness and completeness notions, illustrated how unsound refinement maps can break correctness, and provided multi-language programming sketches that encode the coupling between symbolic transitions and geometric feasibility.