DFTSearch

Reference implementation of DFT* — Dispersive Forward Tree search — a GPU-batched, certificate-carrying kinodynamic motion planner, together with WWDFT*, its receding-horizon implementation for real-time planning among moving obstacles.

DFT* grows the complete forward tree of a locally dispersive command set, level-synchronously, with per-depth (cell, depth) dominance pruning, and terminates at the first level that touches the goal ball. There is no steering function, no weld, and no trajectory optimization: the first solution is an exact trajectory of the benchmark's own model by construction.

This repository accompanies the paper Dispersive Forward Tree Search for Optimal Control: Coverage, Complexity, and Computation.

Installation

Requires a CUDA GPU, the CUDA toolkit (nvcc) for the JIT-compiled kernels, and PyTorch with CUDA support.

pip install -e .

Reproducing the offline benchmark (paper Table 2)

Each runner ships the paper-frozen configuration as its defaults — running with no arguments reproduces the published row:

python -m dftsearch.offline.run_u1          # unicycle, first order
python -m dftsearch.offline.run_u2          # unicycle, second order
python -m dftsearch.offline.run_car1        # car with a trailer
python -m dftsearch.offline.run_quad3d_ref  # quadrotor

Results (per-task solution YAML + report.json with cost, wall time, tree size) land in results/<platform>/. Every solution is re-rolled in float64 through the benchmark's own integrator and re-validated end to end (valid_f64).

Configuration handling: defaults < --config file.yaml < explicit flags. Example:

python -m dftsearch.offline.run_u1 --rho 0.1 --max-blocks 0
python -m dftsearch.offline.run_car1 --config configs/car1.yaml

--max-blocks 8 (default) reproduces the embedded-tier SM cap; --max-blocks 0 uncaps the kernel for full-GPU wall times.

Solution costs reproduce up to the documented one-level tie-break wobble (atomic first-wins races inside a level are benign for the certificate but can move the reported cost by one window). Wall times depend on the GPU; the paper's embedded-tier numbers were measured with the 8-SM cap on an RTX 4090 host. Online travel times are similarly compute-dependent: slower GPUs finish fewer depths per 250 ms window and fall back to shorter runways more often.

The dynobench task environments are vendored unmodified under third_party/dynobench/ — see the notice there.

WWDFT*: online planning among moving obstacles

Known-map receding-horizon planning in the paper's dynamic benchmark arena (110 m corridor, static boxes + trefoil movers). The 15 exact paper scenes are vendored under scenes/dynamic/ ({easy,medium,hard}_seed{0..4}.json; 50/100/200 obstacles at a 0.65 dynamic ratio), and scenes/gen_obstacles_json.py generates new seeded scenes with the same construction.

Physical quadrotor (X500 plant, paper geometric tracker, 101-command force fan, 45-degree tilt cap, asymmetric motor lag):

python -m examples.run_online_quad \
    --scene scenes/dynamic/hard_seed0.json --out results/online_quad

Triple-integrator model (jerk-bounded chain of three integrators):

python -m examples.run_online_chain3 \
    --scene scenes/dynamic/hard_seed0.json --out results/online_chain3

Both write result.json (success, commits, travel time, safety counters, clearance audit) and the executed trajectory. Defaults reproduce the paper's operating point: inclusive growth/runway horizon 5, complete parent frontier, dominance radius 1.0 in the quantization metric, 8-SM embedded tier, 250 ms windows.

The planner API is plain Python (no ROS):

from dftsearch.online import WWDFTConfig, WWDFTPlanner
from dftsearch.platform.sim.px4_capsule import PX4PlatformCapsule

capsule = PX4PlatformCapsule.x500_reference()
config = WWDFTConfig.x500_paper_tracker(capsule)
planner = WWDFTPlanner(params=capsule.to_quad_params("cuda"),
                       world=world,            # WorldGrid occupancy
                       goal_position=goal,
                       config=config,
                       dynamic_provider=provider,
                       px4_capsule=capsule)
episode = planner.run_episode(start_state)

world is any occupancy grid (dftsearch.platform.expert.collision. WorldGrid); dynamic_provider(t, position, quaternion) returns the moving-obstacle set observed at time t (DynamicObstacles), which the planner inflates into worst-case reachable tubes for certification. dftsearch/scenes/gt_belief.py builds both from a scene JSON.

Layout

dftsearch/offline/    DFT* harness, per-platform fused CUDA kernels,
                      dispersive command-set constructions, runners
dftsearch/online/     WWDFT* (quad force-fan + chain3 backends)
dftsearch/platform/   quadrotor plant, PX4 X500 capsule, collision
dftsearch/scenes/     scene loading + seeded scene generator
scenes/dynamic/       the 15 paper benchmark scenes
third_party/dynobench/  vendored benchmark environments
configs/              paper-frozen configurations, documented
examples/             online benchmark entry points