False Stitches: Making Offline Trajectory Stitching Safe for Robot Teams Among Moving Obstacles

Robots trained to copy demonstrations can only be as good as the demonstrations. A known way past that ceiling is trajectory stitching: learn a value function, meaning an estimate of how good each state is, from logged data, then splice the good half of one recorded run onto the good half of another to get a path nobody ever demonstrated. Stitching depends on one assumption. When two recordings pass through "the same state", continuing along either one must be equally valid. In a team of robots moving among pedestrians, vehicles, or other robots, that assumption breaks quietly. Two runs can put the robot at the same place with the same velocity while a pedestrian is two meters away in one and twenty meters away in the other. A value function that cannot tell these apart will happily splice them, and the result is a confident plan that drives into someone. We call these false stitches.

This note proposes to measure false stitches directly and to remove them with a principled choice of what each agent's value function looks at. Each robot should condition only on the moving entities that could physically reach it within a short time horizon. That set is small enough for stitching to find matching states, and it is complete enough that no splice ignores something able to cause a collision. The setting combines all four directions. The goal is to exceed the best demonstrator (the imitation ceiling), using logs from flawed operators and flawed scripted policies (no expert optimality), for teams rather than single agents, in scenes whose obstacles move. Only stitching validity is new. The rest is reused machinery.

Core Claim

Stitching across trajectories breaks the ceiling in static single-agent tasks (Curriculum Offline Imitating Learning frames why supervised copying cannot join disjoint sub-trajectories, and Offline Q-learning on Diverse Multi-Task Data Both Scales And Generalizes shows value-based offline learning beating cloning on diverse data). In multi-agent dynamic scenes, however, the main way stitching fails is not the over-pessimism that CFCQL addresses. It fails because of a dilemma about what the value function sees.

If agent $i$'s value function sees the full scene, no two logged states ever match, so there is nothing to stitch. If it sees only its own state, or a fixed neighborhood around itself, states match often, but some matches differ in exactly the entity that matters. We claim this dilemma has a physically grounded resolution. Entity $j$ (a teammate or an uncontrolled obstacle) is included in agent $i$'s state at time $t$ only if

$$\mathcal{R}_j(t,H)\cap\mathcal{R}_i(t,H)\neq\emptyset,$$

where $\mathcal{R}_k(t,H)$ is the set of positions entity $k$ could occupy within the next $H$ seconds given bounds on its speed and acceleration. This is the same reasoning behind inevitable collision states, which are states from which no action avoids a future collision (Schmerling et al.; Safe Motion Planning in Unknown Environments). Here it is used to decide which entities a learned value function must condition on, not as a planner constraint.

The prediction is testable. Stitching on this reachability-pruned state should exceed the best single demonstration in the data. Its false-stitch rate should stay near zero as more far-away moving obstacles are added. Both full-state and fixed-radius alternatives should fail in characteristic ways: the full-state value stops stitching as obstacle count grows, and the fixed-radius value collides when fast obstacles enter from outside the radius.

Research Program

Value function. We avoid hand-shaped rewards. The logs contain each agent's goal and recorded collision events, and nothing else is labeled. Each agent learns a goal-conditioned temporal distance $d_i(z_i, g)$, the expected time to reach goal $g$ from pruned local state $z_i$. It is trained by relabeling logged future states as goals, with a shortest-path backup:

$$d_i(z_i,g)\leftarrow \min\big(\,d_{\text{obs}}(z_i,g),\; 1+d_i(z_i',g)\,\big).$$

Here $d_{\text{obs}}$ is the time-to-goal observed along the current log and $z_i'$ is the next pruned state. The $\min$ is what performs stitching. It lets a short continuation recorded in a different run overwrite a long one recorded in this run.

A separate classifier $c_i(z_i)$, trained on logged collisions and their preceding windows, estimates whether $z_i$ is already doomed. States with high $c_i$ are excluded from the backup. Suboptimal demonstrators need no explicit filtering, because a bad continuation simply loses the $\min$.

Teams and credit assignment. We borrow CFCQL's counterfactual idea. Each agent's backup holds teammates' logged actions fixed, so agent $i$ is credited or blamed only for its own deviation. This gives the per-agent credit assignment that MADiTS obtains with integrated gradients and a generative model, but here it comes from a value function rather than a return-conditioned diffuser. Policies are extracted per agent by advantage-weighted cloning in the style of MARWIL, with the advantage given by the decrease in $d_i$.

Theory to pin down. We will formalize a false stitch as a backup through two logged states whose pruned states agree but whose full scenes differ in some entity with nonzero collision probability over the next $H$ seconds. We will then bound how often this can happen when $H$ is at least the agent's braking horizon. The open question is whether reactive obstacles, meaning pedestrians who respond to the robot, break this bound. We will test that case empirically and not assume it away.

Data. We generate suboptimal team logs with three kinds of flawed behavior:

  • Operator-like jitter and latency. This mirrors the human flaws described under the expert-optimality direction.
  • State-dependent incompetence. A scripted policy is efficient in open space but timid or reckless at crossings, which is the case where per-demonstrator expertise models such as Imitation Learning by Estimating Expertise of Demonstrators are expected to struggle.
  • Clumsy teammates. Partially trained peers act as in R2BC's round-robin collection.

Each dataset is built so that no single trajectory is near-optimal, while good segments exist across trajectories. Each also includes deliberate "trap" pairs: two segments that meet at the same ego state but at different obstacle phases, so that splicing them causes a collision.

Baselines

Naive reference points. The do-nothing reference is decentralized behavior cloning on the full mixed dataset. We also report the best single logged trajectory per start–goal pair, which defines the ceiling. Exceeding that best trajectory is the minimum bar for any claim of ceiling-breaking.

Strongest existing value-based method: CFCQL. CFCQL is counterfactual conservative Q-learning with per-agent penalties. It reports outperforming OMAR and IQL on 11 of 12 MPE datasets, and a 49% win rate on SMAC 6h_vs_8z where other baselines stayed below 5%. It needs rewards, so we give it a sparse goal-arrival reward plus a collision penalty derived from the same labels our method uses. It sees the full scene state, which is its natural setting. It receives the same data, network size, gradient steps, and a hyperparameter sweep of equal size to ours.

Strongest generative stitching method: MADiTS. MADiTS uses return-conditioned diffusion to augment the data with stitched coordinated segments. It reports raising the average MPE score from 27.01 to 45.83 on imbalanced data. We run it with the same sparse returns and train decentralized cloning on its augmented data.

Reward-free filtering methods. These test whether stitching matters at all, as opposed to filtering. The first is DWBC, which uses a positive-unlabeled discriminator to weight cloning. It is run per agent, given the 10% best segments as positives. The second is MisoDICE, which uses distribution matching with linear value mixing. MisoDICE reports a 20.7% win rate versus 14.2% for expert-only cloning on SMACv2 Protoss 5_vs_5. Because our states are not text, we replace its language-model labeler with the same segment ranking we give DWBC.

Ablations isolating the key ingredient. The value function and policy extraction are held identical. Only the state given to the value function changes. The variants are:

  • ego-only state;
  • full scene state;
  • fixed-radius neighborhood, with the radius tuned on validation;
  • $k$ nearest entities;
  • reachability pruning (ours).

A separate ablation removes the doom classifier.

What counts as beating them. Our method must match or exceed CFCQL and MADiTS on success rate and time-to-goal. It must have a lower collision rate at equal or better efficiency. It must exceed the best logged trajectory. Its advantage over the fixed-radius ablation must widen as obstacle speed increases.

Why not just…?

Why not just give the full scene to an existing offline multi-agent method like CFCQL? This is the main threat, and it may be fine when obstacles are few. Our argument is that full-scene states almost never recur, so the stitching $\min$ has nothing to combine, and the method falls back toward cloning. The obstacle-density sweep below settles this. If CFCQL's ceiling-breaking margin holds steady as distant obstacles are added, our central claim is wrong.

Why not just use a fixed-radius neighborhood? This is the more serious threat, because it is what most practitioners would do. A tuned radius may capture most of the benefit. We expect it to fail specifically when fast entities start outside the radius but inside the braking horizon. We construct speed sweeps to expose exactly that. If a tuned radius matches reachability pruning across all speeds, we will report the contribution as "local state abstraction is necessary and sufficient", and the reachability criterion will be shown to be unnecessary.

Why not just filter bad segments and clone the rest (DWBC or MisoDICE)? Filtering can only reproduce the best behavior already in the data. Our datasets contain no near-optimal full trajectory by construction, so filtering should cap at the best-logged-trajectory line while stitching exceeds it. If filtering matches stitching, our datasets do not actually require stitching, and that would be a flaw in the test design worth reporting.

Why not just clone and add a test-time safety filter based on inevitable collision states? A safety filter like that of Safe Motion Planning in Unknown Environments can remove collisions but cannot make a slow demonstrator fast. We include behavior cloning plus a braking-based safety filter as a baseline. We expect low collisions but time-to-goal at or below the logged ceiling, which would show that safety and ceiling-breaking are separate problems.

Proposed Experiments

Main testbed: VMAS. The primary testbed is VMAS, extended with uncontrolled moving obstacles. VMAS runs 30,000 parallel simulations in under 10 seconds on one GPU, which makes it cheap to verify every stitched plan by executing it. We start from the Navigation (3 agents) and Transport tasks used by R2BC and add non-reactive and reactive obstacles. No reported result was found on Lacuna for VMAS with dynamic obstacles, so all baselines are rerun.

Metrics. We measure:

  • success rate;
  • time-to-goal, normalized by an oracle planner that knows future obstacle motion;
  • collisions per episode;
  • the ratio of our time-to-goal to the best logged trajectory's;
  • the false-stitch rate, defined as the fraction of value-implied stitched plans that collide when replayed in the simulator.

Benchmark continuity. For continuity with published numbers, we also report on the MPE datasets used by MADiTS (static obstacles, where our method should roughly match and not win) and on MaMuJoCo, where false stitches are not expected.

Transfer check: HABIT. A single-ego transfer study uses HABIT pedestrians in CARLA. We train on suboptimal driving logs and compare against HABIT's reported InterFuser numbers: 5.24 collisions/km, 10.96% injury risk, and a false positive braking rate of 0.33. This is a check on realism, not the main claim, because HABIT evaluates single vehicles.

Decisive checks. The first decisive check is the obstacle-density sweep. We add 0 to 30 distant moving obstacles that never come within reach of any agent. Full-state stitching should degrade, reachability pruning should be unaffected, and ego-only should be unaffected but should fail the trap pairs.

The second is the speed sweep. We hold obstacle count fixed and raise obstacle speed. The fixed-radius variant's false-stitch rate should rise once braking distance exceeds its radius, and reachability pruning's should not.

The third is the trap-pair audit. Every method's value function is queried on the deliberately constructed collision splices, and the fraction it scores as good is reported.

The fourth is the reactive-pedestrian condition, which is where our bound may fail. A rise in false stitches there would mark the limit of the approach, not something to hide.