CPU EDT
Lower-envelope transform · JavaScript
——
Distance field
—
CPU A* + shortcuts
—
—
OCCUPANCY → GPU DISTANCE FIELD → ROUTE → MOTION
Will the robot fit?
Click “Put a pallet on the route” to block the current path. Compare the old and new routes, check clearance, then run the mission. Or draw your own obstacles and change the robot footprint.
—REMAINING ROUTE
—ROUTE CLEARANCE LOWER BOUND
—DISTANCE FIELD + TRANSFER
—CPU A* + SHORTCUTTING
16 × 12 m / 0.125 m CELLSInitializing…
■ Obstacle■ Insufficient clearance─ Planned route● Robot / ✚ Goal┄ Before pallet■ Added pallet
Editing pauses motion immediately. Replanning uses the current robot position. Click or drag with Draw / Erase; arrow keys + Space also work.
ONE CLICK / SAME START / CHANGED MAP
A pallet appeared. What changes?
Put a 1 × 1 m pallet on the route. Motion pauses while a new route is checked from the same robot position.
REPLAN: FIELD + ROUTE—
Single wall-clock measurement, including GPU transfers when used.
ROUTE LENGTH CHANGE—
Before — → after —
SPARE CLEARANCE—
New route's minimum clearance minus (robot radius + safety margin).
Dashed amber is the previous route; green is the newly checked route. Both plans use the same start, goal and footprint. The old route may cross the pallet and must not be followed. Restore rewinds to the captured robot position and map. Editing the map, positions, footprint or backend clears this experiment. Timing excludes the input debounce, baseline plan and drawing; this is not a GPU/CPU speedup claim. A* is clearance-weighted, so route-length change is not an optimal-detour guarantee. Save plan includes both routes and the pallet result.
Does a faster field mean a faster replan?
Add a pallet first, then compare both pipelines from the captured start. The mission pauses during measurement.
| Stage | CPU brute force + CPU A* | GPU field + CPU A* |
|---|---|---|
| Distance field | — | — |
| CPU A* + shortcuts | — | — |
| Total call | — | — |
| Route result | — | — |
CPU total / GPU-field total: —
Route agreement: —
Same changed map, captured robot start, goal and footprint, even if the live robot has since moved. Three warmups, 15 alternating pairs. Each timed call builds a field and runs the identical main-thread CPU A*; the GPU does not plan the route. GPU transfers/readback and CPU allocations are included. Initialization, warmups, agreement checks, drawing and input debounce are excluded. Stages are measured within each call; their medians need not sum to the total median. Every measured pair checks all field cells plus route status, waypoint count/coordinates, length and minimum clearance (1e-6 m tolerance). A mismatch suppresses speedup. Blocked routes are valid results, not successful missions. WebGPU/JavaScript, not native CUDA/C++. JSON includes all paired routes, stage samples and the replayable map.
SAME WAREHOUSE / THREE GRID RESOLUTIONS
When does the GPU pay off?
Ready: same 16 × 12 m world at three grid resolutions. Motion pauses during measurement.
Distance field only
Median milliseconds · shorter is faster
Total: field + CPU routing
Median milliseconds · independent horizontal scale
| Grid / cell size | CPU-only A* | GPU pipeline A* | Agreement / total ratio |
|---|
No measurements yet. A faster distance field does not necessarily mean a faster total replan.
64×48 (3,072 cells), 128×96 (12,288) and 256×192 (49,152); same 16×12 m area, start, goal and footprint. Existing occupied cells are conservatively resampled; coarser cells can widen obstacles and change clearance, route geometry or reachability. Agreement is checked CPU versus GPU within each size, not across sizes. If a pallet exists, its captured start is reused. Each size gets 3 warmups and 15 alternating pairs, with field, CPU A* and total time recorded. GPU allocation/compilation, resampling, drawing and agreement checks are untimed; uploads/readback and CPU allocations are timed. Same-algorithm mode uses brute force on both backends; optimized mode uses a linear-time EDT only on the CPU, so it is not a pure hardware comparison. Independent chart axes; hover values for P10–P90, or export raw samples and all routes. Small-to-large observations on this browser are not a universal crossover threshold. GPU-unavailable devices show CPU-only data. The editor remains 128×96; scaled map exports are benchmark inputs, not editor-import files. WebGPU/JavaScript, not native CUDA or GPU A*.
THREE IMPLEMENTATIONS / SAME VERIFIED OUTPUT
Does optimizing the GPU help?
Ready: CPU EDT, reference GPU and exact GPU EDT on the same input.
This panel always compares optimized CPU EDT, reference GPU brute force and the new GPU EDT, independently of the paired-panel CPU selector. Each pipeline still runs the same CPU A*. GPU EDT uses exact grid distances, not an approximate jump-flood field.
GPU reference
Brute-force separable transform · WebGPU
——
Distance field
—
CPU A* + shortcuts
—
—
GPU EDT
Binary row sweeps + column envelope · WebGPU
——
Distance field
—
CPU A* + shortcuts
—
—
Large figures and bars are total call medians; shorter is faster. Ratios below are first / second: above 1 means the second implementation is faster, below 1 means the first is faster.
- CPU EDT / GPU reference
- —
- CPU EDT / GPU EDT
- —
- GPU reference / GPU EDT
- —
Three warmups, 15 measured calls per available implementation. Six rotating permutations balance execution positions; two available implementations alternate. All three pairings verify every field cell plus route status, waypoints, length and clearance at 1e-6 m tolerance. Mismatches suppress that pairing's ratios; blocked results are not successful missions. Setup, compilation, resampling, checks and drawing are untimed. Upload/readback, GPU scratch initialization and CPU allocations are timed. This is not a timestamp-query kernel timer or native CUDA comparison. GPU EDT performs linear total work with sequential work per row/column; limited parallelism and transfer overhead can make it slower. It is an exact implementation experiment, not a claim of the fastest GPU EDT. Coarser resampling can change reachability; the live editor and its backend remain unchanged. JSON records the source/scaled maps, algorithm identities, raw stage samples, all routes and actual call orders.
SAME MAP / VERIFIED DISTANCE OUTPUTS
GPU vs CPU, on your device.
Comparison pauses the mission. Three warmups, then 15 paired measurements of the current map.
CPU brute force—
P10–P90: —
GPU / WEBGPU + TRANSFERS—
P10–P90: —
CPU MEDIAN / GPU MEDIAN—
Result agreement: —
Shorter bars are faster. Comparison uses both available backends regardless of mission backend selection. Median wall-clock times include output allocation; GPU time includes uploads, queue submission, synchronization and readback, not just kernels. GPU buffers are reused; the CPU reference allocates temporary/output arrays per call. Compilation, warmups, A* and drawing are excluded. CPU is single-threaded JavaScript, not optimized native C++; GPU is WebGPU, not CUDA. This small grid may favour the CPU. No GPU means CPU timing only — never a simulated GPU score. Timer resolution, JIT, power settings and other tabs affect results.
01 / DESIGN THE AISLE
Add or remove obstacles, relocate the robot and set a destination. The doorway preset makes footprint limits easy to test.
02 / COMPUTE CLEARANCE
Two GPU passes compute squared Euclidean distances, one invocation per grid cell. Obstacle cells are conservatively expanded to their full area.
03 / FIND A ROUTE
CPU A* respects robot radius + safety margin. Collision-checked shortcuts reduce unnecessary corners; blocked routes stop the mission.
04 / REPRODUCE
Export the occupancy map, footprint, route coordinates and clearance report. Import the same map to compare footprint choices.
A useful planning experiment, not a robot safety system.
The robot is a kinematic disk following a geometric route at 0.8 m/s, with a 0.05 s simulation step. This is not the native CUDA/Nav2 controller, a physics simulation, SLAM, or a guarantee of safe physical deployment. GPU acceleration covers the distance field; A*, motion checks and Canvas drawing run on the CPU. Unsupported devices use the identical CPU distance-field reference.
The fixed grid is 128 × 96 cells at 0.125 m/cell. Distance values are conservative lower bounds: distance to occupied cell centres minus a half-cell diagonal, capped by map boundaries. Cell lookup also accounts for subcell position. Narrow passages can therefore be rejected conservatively. JSON import accepts this documented grid format, not arbitrary ROS maps. Exported routes are experiment data, not executable robot commands.
Native CUDA / Nav2 deployment ↗ · MPPI control lab ↗ · GPU localization ↗