Planning to Stop: Factored Certification and Terminal Repair for Noncircular Robots
Organizations: North China University of Technology, 100000, Beijing, China
Abstract
Tight-space navigation requires a robot to clear obstacles and stop inside its goal despite uncertainty. We present GeoDiff, a motion-program planner coupling original-goal stopped-set inclusion, witness-guided terminal repair, and factored proof compilation. An exact feasible-translation characterization guides repair; request-local reuse reduces repeated geometric work. We establish conditions for compiler equivalence and reach-and-stop soundness. Across 11,440 floorplan-derived jobs, GeoDiff certifies 61/139 tasks at 5-cm tolerance within 15 s, versus 44/139 for the stop-set baseline. The strongest observed external certificate adapter certifies 13/139 tasks from 119/139 native routes, separating route availability from certification. On tasks derived from public BARN maps, GeoDiff certifies 202/270 at 5-cm tolerance for a Jackal-shaped body, versus 3/270 for the portal baseline. Development analyses distinguish emitter savings from solver coverage, and 1,420 route-tracking episodes characterize the execution interface. These results show how terminal reasoning and proof reuse increase finite-budget certification coverage while preserving the original physical task and goal.
Figures & tables
| External setting | Native path | Accepted certificate |
|---|---|---|
| Smac Lattice B+ | 119/139 | 13/139 |
| Smac Lattice B | 119/139 | 9/139 |
| Hybrid B+ | 124/139 | 2/139 |
| Hybrid B | 124/139 | 1/139 |
| DDR B+ | 111/139 | 9/139 |
| DDR B | 111/139 | 6/139 |
| 0.9 m door-median normalization | 0.8 m door-median normalization | |||
|---|---|---|---|---|
| Method | 0.05 m goal | 0.15 m goal | 0.05 m goal | 0.15 m goal |
| Portal-only | 27/139 (19.4) | 83/139 (59.7) | 29/118 (24.6) | 39/118 (33.1) |
| Stop-set | 44/139 (31.7) | 97/139 (69.8) | 34/118 (28.8) | 49/118 (41.5) |
| Stop-set + repair | 50/139 (36.0) | 98/139 (70.5) | 31/118 (26.3) | 50/118 (42.4) |
| Factored, no repair | 55/139 (39.6) | 102/139 (73.4) | 37/118 (31.4) | 61/118 (51.7) |
| GeoDiff | 61/139 (43.9) | 102/139 (73.4) | 37/118 (31.4) | 59/118 (50.0) |
| Reference | Difference | 95% interval | Discordance |
|---|---|---|---|
| Stop-set | +12.2 | [+6.5, +18.7] | 19/2 |
| Factored, no repair | +4.3 | [+0.0, +8.6] | 8/2 |
| Smac Hybrid B+ | +42.4 | [+33.8, +51.1] | 59/0 |
| Smac Lattice B+ | +34.5 | [+25.2, +43.9] | 55/7 |
| DDR-opt B+ | +37.4 | [+28.1, +46.8] | 57/5 |
| Body model | Goal tolerance | factored_bt | pcg_portal |
|---|---|---|---|
| Jackal-shaped | 0.05 m | 202/270 (74.8%) | 3/270 (1.1%) |
| Jackal-shaped | 0.15 m | 221/270 (81.9%) | 67/270 (24.8%) |
| Wheelchair-shaped | 0.05 m | 109/270 (40.4%) | 0/270 (0.0%) |
| Wheelchair-shaped | 0.15 m | 97/270 (35.9%) | 47/270 (17.4%) |
| Certificate-derived route tracker | Lattice + MPPI + CM | ||||||
|---|---|---|---|---|---|---|---|
| Panel | Setting | Strict | Interface | Collisions | Strict | Interface | Collisions |
| CUBI28 | Clean | 90/140 | 90/140 | 0 | 0/140 | 38/140 | 11 |
| CUBI28 | Disturbed | 88/140 | 88/140 | 2 | 0/140 | 41/140 | 9 |
| BARN43 | Clean | 120/215 | 120/215 | 0 | 0/215 | 107/215 | 10 |
| BARN43 | Disturbed | 120/215 | 120/215 | 0 | 0/215 | 102/215 | 6 |
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
| 0.9 m normalization ( ) | 0.8 m normalization ( ) | |||||||
| 0.05 goal | 0.15 goal | 0.05 goal | 0.15 goal | |||||
| Method | 5 s | 15 s | 5 s | 15 s | 5 s | 15 s | 5 s | 15 s |
| Portal-only | 3 | 27 | 10 | 83 | 1 | 29 | 3 | 39 |
| Stop-set | 13 | 44 | 37 | 97 | 5 | 34 | 15 | 49 |
| Stop-set + repair | 11 | 50 | 40 | 98 | 4 | 31 | 16 | 50 |
| Factored, no repair | 22 | 55 | 55 | 102 | 7 | 37 | 19 | 61 |
| Setting | Solver (s) | Reserve | Cap | Workers | None | Blind | Pos.-filtered | Full |
|---|---|---|---|---|---|---|---|---|
| Default | 15 | 0.2 | 3 | 20 | 55 | 59 | 69 | 70 |
| Fair principal | 15 | 0 | 3 | 28 | 52 | 44 | 57 | 63 |
| Fair cap 1 | 15 | 0 | 1 | 14 | 39 | 37 | 42 | 44 |
| Fair cap 6 | 15 | 0 | 6 | 14 | 40 | 31 | 42 | 43 |
| Short budget | 5 | – | – | 14 | 22 | 19 | 22 | 21 |
| Certificate-derived route tracker | Lattice + MPPI + CM | ||||||
|---|---|---|---|---|---|---|---|
| Panel | Setting | Strict | Interface | Collisions | Strict | Interface | Collisions |
| CUBI28 | Clean | 55/140 | 55/140 | 0 | 0/140 | 42/140 | 5 |
| CUBI28 | Disturbed | 55/140 | 55/140 | 0 | 0/140 | 38/140 | 10 |
| BARN43 | Clean | 120/215 | 120/215 | 0 | 0/215 | 101/215 | 9 |
| BARN43 | Disturbed | 120/215 | 120/215 | 0 | 0/215 | 102/215 | 9 |
Robot Motion Planning
Robot motion planning finds safe, feasible paths and trajectories for robots moving through constrained, changing environments.
See all 293 papers