In TAMP we combine a symbolic task-level model with a geometric motion model. Let \( \mathcal{C} \) denote the configuration space of the manipulator (students have seen this in motion-planning chapters), and \( \mathcal{C}\_{\text{free}} \subseteq \mathcal{C} \) the collision-free subset induced by the current world state.

\[ \mathcal{C}\_{\text{free}}(w) = \{ q \in \mathcal{C} \mid \text{CollisionFree}(q, w) \}, \]

where \( w \) is a discrete world description (poses of movable objects, grasp states, etc.). A symbolic state \( s \) is a set of logical atoms over a finite predicate set \( \mathcal{P} \), and we write the set of reachable symbolic states as \( \mathcal{S} \subseteq 2^{\mathcal{P}} \).

A sampling-based TAMP problem can be written as:

\[ \begin{aligned} &\text{Given:} \\ &\quad \text{symbolic domain } \mathcal{D}\_{\text{sym}} = (\mathcal{F}, \mathcal{A}, \mathcal{O}, \text{Init}, \text{Goal}), \\ &\quad \text{continuous space } \mathcal{C},\ \text{free sets } \mathcal{C}\_{\text{free}}(s) \text{ for each } s \in \mathcal{S}, \\ &\quad \text{sampling-based motion planner } \Pi\_{\text{motion}}. \\ &\text{Find: } \text{finite sequence of actions } \pi = (a\_0,\dots,a\_{T-1}) \in \mathcal{A}^T \\ &\quad \text{and configurations } q\_0,\dots,q\_T \in \mathcal{C}, \\ &\text{such that:} \\ &\quad s\_0 = \text{Init},\ s\_{t+1} = f(s\_t, a\_t),\ s\_T \models \text{Goal}, \\ &\quad q\_t \in \mathcal{C}\_{\text{free}}(s\_t) \text{ for all } t, \\ &\quad \Pi\_{\text{motion}} \text{ returns a collision-free path between } q\_t \text{ and } q\_{t+1} \text{ under } s\_t. \end{aligned} \]

Sampling-based TAMP algorithms explore a factored search space: (1) a discrete search over symbolic action sequences \( \pi \), and (2) a continuous search over configurations and object poses to realize those actions. PDDLStream-style representations expose this factorization by treating geometric reasoning as streams that produce discrete facts via sampling.

flowchart TD
  I["Initial symbolic state + robot config"] --> TP["Task planner over symbolic actions"]
  TP --> SKEL["Candidate plan skeleton \n(a0,...,aT-1)"]
  SKEL --> ST["Call geometric streams \n(grasps, placements, IK, paths)"]
  ST --> MP["Run sampling-based motion planner \nfor each action"]
  MP --> FEAS{"All motions feasible?"}
  FEAS -->|yes| SOL["Return full TAMP solution \n(discrete + trajectories)"]
  FEAS -->|no| REF["Refine symbolic search \nor resample streams"]
  REF --> TP
        

PDDLStream augments a classical PDDL planning domain with streams: black-box samplers that generate new objects and facts on demand. Intuitively, streams encode infinite families of geometric candidates (grasps, placements, motions) that are needed to make a pure PDDL problem solvable.

Let \( \Sigma \) denote a finite set of stream templates. For each stream \( \sigma \in \Sigma \) we have:

• An input tuple type \( \mathcal{X}\_{\sigma} = X\_1 \times \cdots \times X\_k \),
• An output tuple type \( \mathcal{Y}\_{\sigma} = Y\_1 \times \cdots \times Y\_m \),
• A precondition formula \( \text{Pre}\_{\sigma}(x) \) over existing facts,
• A finite head of atomic predicates \( \text{Head}(\sigma)(x, y) \) that become true when an output \( y \in \mathcal{Y}\_{\sigma} \) is sampled.

At the implementation level, each stream template \( \sigma \) is realized as a stochastic generator that yields a sequence of outputs \( y^{(1)}, y^{(2)},\dots \in \mathcal{Y}\_{\sigma} \) given an input \( x \in \mathcal{X}\_{\sigma} \). We can model this as a family of conditional distributions \( \mu\_{\sigma}(\cdot \mid x) \).

\[ y \sim \mu\_{\sigma}(\cdot \mid x),\quad \text{then add all atoms in Head}(\sigma)(x,y) \text{ to the fact set.} \]

Starting from an initial set of facts \( F\_0 \) and objects \( O\_0 \), the ideal semantic closure of streams is given by:

\[ \begin{aligned} &F\_{k+1} = F\_k \cup \{ \phi(x,y) \mid \exists \sigma \in \Sigma,\ \exists x,y \\ &\qquad \text{such that }\text{Pre}\_{\sigma}(x) \subseteq F\_k \text{ and } \phi \in \text{Head}(\sigma)(x,y) \}, \\ &F\_{\infty} = \bigcup\_{k \ge 0} F\_k. \end{aligned} \]

In practice, we never materialize \( F\_{\infty} \) explicitly. Instead, streams are called lazily as needed during planning. A key assumption that underpins probabilistic completeness is a robust nonzero probability condition on streams:

\[ \forall x \in \mathcal{X}\_{\sigma} \text{ with at least one feasible output } y, \ \exists y^* \text{ such that } \mu\_{\sigma}(B\_{y^*} \mid x) > 0, \]

where \( B\_{y^*} \) is a small neighborhood of \( y^* \) in the continuous output space. This mirrors the nonzero-measure assumption used for probabilistic completeness of PRM and RRT.

A naïve algorithm that eagerly enumerates many possible stream outputs is hopelessly inefficient. Instead, PDDLStream uses a focused algorithm that alternates between:

1. Optimistic task planning: Assume stream outputs exist by introducing hypothetical objects and facts.
2. Stream realization: Given an optimistic plan, call only those streams whose outputs are required for that plan.
3. Refinement: If stream calls cannot realize the plan, refine the optimistic problem to exclude similar failures, and replan.

Let \( \Pi\_{\text{task}} \) be a sound symbolic planner for finite PDDL problems. We denote an optimistic problem by \( \mathcal{P}^{\text{opt}} \), where stream outputs are replaced by placeholder objects subject to relaxed constraints. At iteration \( n \), the algorithm:

\[ \begin{aligned} &\text{1. Build optimistic problem } \mathcal{P}^{\text{opt}}\_n \text{ using current knowledge about streams.} \\ &\text{2. Invoke } \Pi\_{\text{task}} \text{ to obtain a plan skeleton } \pi\_n. \\ &\text{3. Attempt to realize } \pi\_n \text{by calling streams and the motion planner.} \\ &\text{4. If realization fails, record explanations and update } \mathcal{P}^{\text{opt}}\_{n+1}. \\ &\text{5. Repeat until a feasible plan is found or search limits are exceeded.} \end{aligned} \]

flowchart TD
  S0["Start with PDDL + streams + initial facts"] --> O1["Construct optimistic planning problem"]
  O1 --> P["Run task planner \non optimistic problem"]
  P --> C1{"Plan skeleton found?"}
  C1 -->|no| WIDEN["Relax limits / \nexpand heuristic envelope"]
  WIDEN --> O1
  C1 -->|yes| R1["Realize skeleton: \ncall streams + motion planners"]
  R1 --> C2{"Realization succeeds?"}
  C2 -->|yes| SOL["Return full TAMP plan"]
  C2 -->|no| EX["Extract failure reasons \nand add constraints"]
  EX --> O1
        

The failure explanations added in step 4 are often additional logical facts such as (blocked-grasp g1) or (infeasible-ik pose1) that prevent the task planner from generating the same un-realizable skeleton again.

We now sketch why focused sampling-based TAMP can be probabilistically complete under assumptions analogous to PRM / RRT completeness. Consider the following conditions:

• (C1) Task-level completeness: \( \Pi\_{\text{task}} \) is complete on any finite PDDL problem generated during the search.
• (C2) Stream nonzero success: Every stream instance used in at least one feasible TAMP solution has nonzero probability of generating a “good enough” output (as in the previous section).
• (C3) Motion planner completeness: \( \Pi\_{\text{motion}} \) is probabilistically complete for each local motion-planning query induced by an action.
• (C4) Fair search: Each finite plan skeleton and associated finite set of stream and motion queries is considered in the limit (no starvation).

Let \( A \) be a focused sampling-based TAMP algorithm satisfying (C1)–(C4). For iteration budget \( N \), define:

\[ P\_N = \Pr[\text{Algorithm } A \text{ has not found a solution after } N \text{ iterations} ]. \]

Theorem (informal). If there exists at least one TAMP solution with finite plan length and finitely many stream and motion queries, then

\[ \lim\_{N \to \infty} P\_N = 0. \]

Sketch of proof. Any feasible solution \( (\pi^*, q^*, y^*) \) induces a finite set of critical events: successful generation of a finite number of stream outputs and successful motion plans (queries to \( \Pi\_{\text{motion}} \)). By (C2) and (C3), each critical event has nonzero success probability when its corresponding sampler is invoked. By (C4), each finite set of events is attempted infinitely often as \( N \) grows. Using independence (or at least positive correlation bounds) between repeated sampling trials, the probability that all critical events never succeed decays to zero as \( N \) increases. Hence the solution is found with probability approaching one.

This argument abstracts away many engineering details (heuristics, pruning, etc.) but provides an important design guideline: do not introduce systematic bias that prevents some feasible stream or motion query from ever being attempted.

We now outline minimal implementations of a PDDLStream-like interface in several languages. In all cases, the underlying motion planning can delegate to a sampling-based library (e.g., OMPL / MoveIt for C++, OMPL/MoveIt bindings or PyBullet for Python, MATLAB Robotics System Toolbox, etc.).

5.1 Python Skeleton with Streams and RRT

In Python we can prototype a PDDLStream-like system and use ompl or moveit_commander for motion planning. Below is a simple pure-Python skeleton (no ROS assumed) where streams are callable generators.

from typing import Callable, Dict, List, Tuple, Any, Iterable
import random
import math

Fact = Tuple[str, Tuple[Any, ...]]  # e.g. ("at", ("block1", "table1"))
Plan = List[str]

class Stream:
    def __init__(self, name: str,
                 input_vars: Tuple[str, ...],
                 output_vars: Tuple[str, ...],
                 precond: Callable[[Dict[str, Any], List[Fact]], bool],
                 sampler: Callable[[Dict[str, Any]], Iterable[Dict[str, Any]]],
                 head_predicates: Callable[[Dict[str, Any]], List[Fact]]):
        self.name = name
        self.input_vars = input_vars
        self.output_vars = output_vars
        self.precond = precond
        self.sampler = sampler
        self.head_predicates = head_predicates

    def call(self, binding: Dict[str, Any], facts: List[Fact]) -> List[Fact]:
        """Return first successful sample and its derived facts, or empty list."""
        if not self.precond(binding, facts):
            return []
        for sample_binding in self.sampler(binding):
            facts_new = self.head_predicates(sample_binding)
            if facts_new:
                return facts_new
        return []

# Example: a grasp stream for a block
def grasp_precond(binding: Dict[str, Any], facts: List[Fact]) -> bool:
    block = binding["b"]
    return ("movable", (block,)) in facts

def grasp_sampler(binding: Dict[str, Any]):
    block = binding["b"]
    for _ in range(100):
        theta = random.uniform(0.0, 2.0 * math.pi)
        yield {"b": block, "g": ("top_grasp", theta)}

def grasp_head(binding: Dict[str, Any]) -> List[Fact]:
    b = binding["b"]
    g = binding["g"]
    return [("grasp", (b, g))]

grasp_stream = Stream(
    name="sample-grasp",
    input_vars=("b",),
    output_vars=("g",),
    precond=grasp_precond,
    sampler=grasp_sampler,
    head_predicates=grasp_head,
)

# Motion planning stream that calls a sampling-based planner (placeholder)
def motion_precond(binding: Dict[str, Any], facts: List[Fact]) -> bool:
    return True

def motion_sampler(binding: Dict[str, Any]):
    q_start = binding["q_start"]
    q_goal = binding["q_goal"]
    # Here we would call OMPL or MoveIt and yield a trajectory if found.
    # We simulate a success with some probability.
    if random.random() < 0.7:
        yield {"traj": [q_start, q_goal]}

def motion_head(binding: Dict[str, Any]) -> List[Fact]:
    return [("reachable", (binding["q_start"], binding["q_goal"]))]

motion_stream = Stream(
    name="sample-motion",
    input_vars=("q_start", "q_goal"),
    output_vars=("traj",),
    precond=motion_precond,
    sampler=motion_sampler,
    head_predicates=motion_head,
)

# A very small "focused" loop (symbolic planner is abstracted as a function)
def focused_tamp(initial_facts: List[Fact],
                 streams: List[Stream],
                 max_iters: int = 20):
    known_facts = list(initial_facts)
    for it in range(max_iters):
        plan_skeleton, stream_calls = symbolic_planner_stub(known_facts)
        if plan_skeleton is None:
            print("No plan skeleton; stopping.")
            return None

        print(f"Iteration {it}, trying plan skeleton:", plan_skeleton)

        success = True
        for stream, binding in stream_calls:
            new_facts = stream.call(binding, known_facts)
            if not new_facts:
                # record failure as a fact and break
                fail_fact = ("failed-stream", (stream.name, tuple(binding.items())))
                known_facts.append(fail_fact)
                success = False
                break
            else:
                for f in new_facts:
                    if f not in known_facts:
                        known_facts.append(f)

        if success:
            print("Realized TAMP plan!")
            return plan_skeleton
    return None

def symbolic_planner_stub(facts: List[Fact]):
    # In practice, call a PDDL planner (FastDownward, pyperplan, etc.)
    # Here we return a dummy plan and dummy stream calls.
    if random.random() < 0.3:
        return None, []
    plan = ["pick b1", "place b1"]
    stream_calls = [
        (grasp_stream, {"b": "b1"}),
        (motion_stream, {"q_start": (0.0, 0.0), "q_goal": (1.0, 0.0)}),
    ]
    return plan, stream_calls
      

5.2 C++ Sketch with OMPL / MoveIt Integration

In C++, streams can be represented as functors that take typed objects and return new facts. Motion planning calls can be implemented using OMPL or MoveIt. The snippet below shows a minimal type structure.

#include <functional>
#include <string>
#include <unordered_map>
#include <vector>
#include <iostream>

using Object = std::string;
using Fact   = std::pair<std::string, std::vector<Object>>;
using Binding = std::unordered_map<std::string, Object>;

struct Stream {
    std::string name;
    std::function<bool(const Binding&, const std::vector<Fact>&)> precond;
    std::function<bool(const Binding&, Binding&)> sampler;
    std::function<std::vector<Fact>(const Binding&)> head;

    bool call(const Binding& b,
              const std::vector<Fact>& facts,
              std::vector<Fact>& out_facts) const {
        if (!precond(b, facts)) return false;
        Binding sample;
        if (!sampler(b, sample)) return false;
        out_facts = head(sample);
        return !out_facts.empty();
    }
};

// Example motion stream that would internally call OMPL or MoveIt
bool motion_sampler(const Binding& b, Binding& out) {
    Object q_start = b.at("q_start");
    Object q_goal  = b.at("q_goal");
    // TODO: encode q_start, q_goal as OMPL states and call a planner.
    // Here we simulate success.
    out["traj"] = "traj_" + q_start + "_" + q_goal;
    return true;
}

std::vector<Fact> motion_head(const Binding& b) {
    return { Fact{"reachable", {b.at("q_start"), b.at("q_goal")}} };
}

int main() {
    Stream motion_stream{
        "sample-motion",
        [](const Binding&, const std::vector<Fact>&) { return true; },
        motion_sampler,
        motion_head
    };

    std::vector<Fact> facts;
    Binding b;
    b["q_start"] = "q0";
    b["q_goal"]  = "q1";
    std::vector<Fact> new_facts;
    if (motion_stream.call(b, facts, new_facts)) {
        std::cout << "Stream succeeded, new facts:\n";
        for (auto& f : new_facts) {
            std::cout << f.first << " ";
            for (auto& o : f.second) std::cout << o << " ";
            std::cout << "\n";
        }
    }
    return 0;
}
      

In a full implementation, motion_sampler would create an OMPL SpaceInformation for the robot, configure a planner (e.g., ompl::geometric::RRTConnect), and run it until a path is found or a timeout occurs.

5.3 Java Sketch (Object-Oriented Streams)

Java is less common for robotics, but the same abstractions apply. This snippet shows the interface-style representation of streams; motion planning can call into native libraries via JNI or use Java wrappers of physics engines (e.g., jBullet) for collision checking.

import java.util.*;

class Fact {
    public final String name;
    public final List<String> args;
    public Fact(String name, List<String> args) {
        this.name = name;
        this.args = args;
    }
}

interface Stream {
    String getName();
    boolean precond(Map<String, String> binding, List<Fact> facts);
    Optional<List<Fact>> call(Map<String, String> binding,
                                   List<Fact> facts);
}

class MotionStream implements Stream {
    private final String name;
    public MotionStream(String name) {
        this.name = name;
    }
    @Override
    public String getName() { return name; }

    @Override
    public boolean precond(Map<String, String> binding, List<Fact> facts) {
        return true;
    }

    @Override
    public Optional<List<Fact>> call(Map<String, String> binding,
                                           List<Fact> facts) {
        String qStart = binding.get("q_start");
        String qGoal  = binding.get("q_goal");
        // TODO: Call native motion planner here.
        // Simulate success:
        List<Fact> out = new ArrayList<>();
        out.add(new Fact("reachable", Arrays.asList(qStart, qGoal)));
        return Optional.of(out);
    }
}

public class FocusedTAMP {
    public static void main(String[] args) {
        Stream motion = new MotionStream("sample-motion");
        Map<String, String> binding = new HashMap<>();
        binding.put("q_start", "q0");
        binding.put("q_goal", "q1");
        List<Fact> facts = new ArrayList<>();
        if (motion.precond(binding, facts)) {
            Optional<List<Fact>> maybeFacts = motion.call(binding, facts);
            if (maybeFacts.isPresent()) {
                for (Fact f : maybeFacts.get()) {
                    System.out.println(f.name + " " + f.args);
                }
            }
        }
    }
}
      

5.4 MATLAB / Simulink Skeleton

MATLAB, together with Robotics System Toolbox and Navigation Toolbox, can host both streams and motion planning. Below is a minimal script that defines a grasp sampler and a motion-planning “stream” using RRT (e.g., plannerRRT* with a rigidBodyTree).

function facts_out = call_grasp_stream(block, facts_in)
    if ~ismember({"movable", block}, facts_in)
        facts_out = {};
        return;
    end
    theta = 2*pi*rand();
    g = {"top_grasp", theta};
    facts_out = ;
end

function facts_out = call_motion_stream(q_start, q_goal, robot, env)
    % robot: rigidBodyTree, env: collision world
    ss = stateSpaceRigidBodyTree(robot);
    sv = validatorRigidBodyTree(ss, "Environment", env);
    planner = plannerRRTStar(ss, sv);
    planner.MaxConnectionDistance = 0.1;
    planner.MaxIterations = 300;
    [pthObj, solInfo] = plan(planner, q_start, q_goal);
    if solInfo.IsPathFound
        facts_out = ;
    else
        facts_out = {};
    end
end

% Focused loop (symbolic planner not implemented here)
knownFacts = ;
for it = 1:10
    % symbolic planner stub
    planSkeleton = {"pick b1", "place b1"};
    % stream calls
    facts_new = call_grasp_stream("b1", knownFacts);
    if isempty(facts_new)
        knownFacts{end+1} = {"failed-stream", "grasp-b1"};
        continue;
    end
    knownFacts = [knownFacts, facts_new]; %#ok<AGROW>
    % Suppose we have robot, env, q_start, q_goal defined in workspace
    facts_new = call_motion_stream(q_start, q_goal, robot, env);
    if isempty(facts_new)
        knownFacts{end+1} = {"failed-stream", "motion-b1"};
    else
        knownFacts = [knownFacts, facts_new]; %#ok<AGROW>
        disp("Realized TAMP plan.");
        break;
    end
end
      

A Simulink implementation would encapsulate each stream as a MATLAB Function block, with bus signals carrying symbolic facts and geometric parameters. The dispatcher block would implement the focused TAMP loop, calling streams and a motion-planning block (built from Robotics System Toolbox) as needed.

5.5 Wolfram Mathematica Prototype

Mathematica can prototype TAMP by treating streams as pure functions that return new atoms. Collision and kinematics can be approximated using geometric regions and distance computations.

ClearAll[makeGraspStream, makeMotionStream];

makeGraspStream[block_Symbol] := Module[{},
  Function[{facts},
    If[MemberQ[facts, {"movable", block}],
      Module[{theta = RandomReal[{0, 2 Pi}], g},
        g = {"top_grasp", theta};
        
      ],
      {}
    ]
  ]
];

makeMotionStream[] := Module[{},
  Function[{qStart, qGoal, facts},
    (* Placeholder: here you would test for collision-free path between qStart and qGoal *)
    If[RandomReal[] < 0.7,
      ,
      {}
    ]
  ]
];

graspStreamB1 = makeGraspStream[b1];
motionStream = makeMotionStream[];

facts = ;
newFacts1 = graspStreamB1[facts];
facts = Join[facts, newFacts1];

q0 = {0., 0., 0.};
q1 = {1., 0., 0.};
newFacts2 = motionStream[q0, q1, facts];
facts = Join[facts, newFacts2];
Print[facts];
      

Mathematica is not a standard robotics platform, but this style of high-level prototyping can be used to study the logic of TAMP algorithms and visualize configuration spaces symbolically.

Problem 1 (Joint Search Graph): Consider a TAMP problem with symbolic state set \( \mathcal{S} \) and configuration space \( \mathcal{C} \). Define a directed graph \( G = (V,E) \) that captures both symbolic transitions and feasible motions. Give a mathematical definition of \( V \) and \( E \), and show that any complete TAMP solution corresponds to a path in \( G \).

Solution. Define the vertex set

\[ V = \{ (s, q) \mid s \in \mathcal{S},\ q \in \mathcal{C}\_{\text{free}}(s) \}, \]

i.e., vertices pair a symbolic state with a collision-free configuration compatible with that state. For each action \( a \in \mathcal{A} \), define the symbolic transition function \( f(s,a) \) (possibly undefined). Let \( \mathcal{M}(s,a,q) \) denote the set of feasible terminal configurations reached by executing \( a \) from \( (s,q) \) using low-level controllers and motion planning. Then define directed edges

\[ E = \{ ((s,q),(s',q')) \mid \exists a \in \mathcal{A}\ \text{s.t. } s' = f(s,a), \ q' \in \mathcal{M}(s,a,q) \}. \]

Any TAMP solution consists of a sequence \( s\_0,a\_0,s\_1,\dots,s\_T \) and corresponding configurations \( q\_0,\dots,q\_T \) such that each \( q\_{t+1} \in \mathcal{M}(s\_t,a\_t,q\_t) \). By construction, \( ((s\_t,q\_t),(s\_{t+1},q\_{t+1})) \in E \), hence the sequence of pairs \( (s\_0,q\_0),\dots,(s\_T,q\_T) \) is a path in \( G \). Conversely, any path in \( G \) that starts at \( (\text{Init},q\_0) \) and ends at a vertex whose symbolic component satisfies the goal corresponds to a feasible TAMP solution.

Problem 2 (Monotonicity of Stream Closure): Let \( F\_0 \) be the initial fact set and define \( F\_{k+1} \) as in Section 2. Prove that the sequence \( (F\_k)\_{k \ge 0} \) is monotonically non-decreasing and stabilizes after at most countably many steps if each stream generates at most countably many distinct atoms.

Solution. By definition,

\[ F\_{k+1} = F\_k \cup G\_k, \]

where \( G\_k \) is a set of newly generated atoms. Thus \( F\_k \subseteq F\_{k+1} \) for all \( k \), so the sequence is monotonically non-decreasing with respect to set inclusion. Moreover, each stream template applied to any fixed input can only generate countably many distinct atoms (because each run yields a finite tuple of real parameters, and the set of all finite sequences over a countable alphabet is countable). Since the number of stream templates and the domain of their discrete inputs are countable, the total number of distinct atoms that can ever be produced is countable. A monotone chain of subsets of a countable set stabilizes after at most countably many steps, i.e., there exists some \( K \) with \( F\_K = F\_{K+1} = \cdots = F\_{\infty} \).

Problem 3 (Expected Stream Trials): Suppose a feasible TAMP solution requires successful sampling from a single stream instance with success probability \( p \in (0,1) \) on each independent trial (e.g., sampling a collision-free placement). What is the expected number of stream calls required to obtain a successful output? How does this extend if a solution needs \( n \) independent stream successes with probabilities \( p\_1,\dots,p\_n \)?

Solution. For a single stream instance with success probability \( p \), the number of trials until first success is a geometric random variable \( T \) with \( \Pr[T = k] = (1-p)^{k-1} p \). Its expectation is

\[ \mathbb{E}[T] = \sum\_{k=1}^{\infty} k (1-p)^{k-1} p = \frac{1}{p}. \]

If a solution requires \( n \) independent stream successes with probabilities \( p\_i \), and the algorithm samples each instance until success, the total number of calls \( T\_{\text{tot}} = \sum\_{i=1}^n T\_i \) has

\[ \mathbb{E}[T\_{\text{tot}}] = \sum\_{i=1}^n \mathbb{E}[T\_i] = \sum\_{i=1}^n \frac{1}{p\_i}. \]

This shows that rare events (small \( p\_i \)) dominate the expected runtime and motivates designing streams with as high success probabilities as possible (e.g., informed sampling).

Problem 4 (Soundness of Stream-Based Realization): Assume that every stream is sound in the sense that any atom \( \phi \) it produces is true in the underlying geometric world model (e.g., if it outputs (reachable q0 q1), then a collision-free path exists). Prove that any TAMP plan found by the focused algorithm (which calls only these streams and a sound motion planner) is geometrically feasible.

Solution. Consider a TAMP plan consisting of a symbolic action sequence \( \pi = (a\_0,\dots,a\_{T-1}) \) and associated stream outputs and motion plans. The focused algorithm builds this plan by successively:

• calling streams and adding their output atoms to the fact set, and
• verifying motion feasibility through a sound motion planner (by assumption, if it returns a path, the path is collision-free and respects kinematic constraints).

Let \( \phi\_1,\dots,\phi\_m \) be all atoms produced by streams in constructing the plan. By stream soundness, each \( \phi\_i \) is true in the underlying geometric world. The preconditions of each action \( a\_t \) are logical formulas built from initial atoms and stream-generated atoms; thus all preconditions hold in the real world. Additionally, for each motion segment, the motion planner returns a path that is geometrically feasible. Therefore, executing \( \pi \) with the obtained trajectories satisfies both symbolic and geometric constraints, so the plan is geometrically feasible.

In this lesson we formulated sampling-based TAMP as a joint search over symbolic states and geometric configurations, and introduced PDDLStream-style streams as a unifying abstraction connecting logical reasoning with black-box samplers for grasps, placements, IK solutions, and motion plans. We described the focused algorithm that alternates between optimistic symbolic planning and lazy stream realization, and sketched conditions under which such algorithms are probabilistically complete. Finally, we outlined multi-language implementations that interface with robotics libraries (OMPL, MoveIt, MATLAB Robotics System Toolbox, etc.), providing a practical bridge between the theory of TAMP and real robot software stacks.