Topological Reachable-Set Coverage Scheduler

Implementation

coverage_scheduler_experiment.py uses the unit square as an exactly known reachable set and an exact 1-Lipschitz radial residual

r_L(x) = margin + L ||x-(0.5,0.5)||, with margin=0.05.

The scheduler starts from four corners and either samples uniformly at random or greedily selects the point maximizing the prescribed coverage score. Coverage is measured exactly over a dense grid using a KD-tree. Results are in results.json.

Stage-1 mechanism checks

1. Lipschitz bound prediction: for every tested L in {0.25, 0.5, 1, 2, 4} and all 4 random seeds, the computed lower bound min_sample_residual - L*delta was no greater than the true grid minimum. Observed bound validity: 100% (80/80).

2. Certification threshold prediction: certification should occur when delta < epsilon/L, with epsilon=0.04. The observed crossing ratios delta/(epsilon/L) were approximately 0.2357--0.2485, hence below 1 (the coarse grid causes a substantial discrete jump). For L=0.25, adaptive sampling reached certification in median 36 samples, versus 93 for random; for L=0.5, adaptive reached it in 88, while random's successful runs required median 266.5. At L=1, neither method reached the threshold within 300 samples on this grid, consistent with the tighter predicted radius 0.15.

3. Lipschitz scaling prediction: at fixed sample geometry, the median residual gap divided by L remained constant at 0.141421, while median L*delta scaled from 0.08333 at L=.25 to 1.33333 at L=4. This is the predicted linear scaling, and the bound remained conservative (gap <= L*delta).

Secondary equal-budget comparison

At L=1, median coverage radius for adaptive versus random was:

• 12 samples: 0.32998 vs 0.43013
• 25 samples: 0.18856 vs 0.32473
• 50 samples: 0.10541 vs 0.22326
• 80 samples: 0.10000 vs 0.17309

Thus the adaptive/farthest scheduler gives a clear coverage win in this toy geometry.

Reproduction

/home/maxwelhelp/main/bin/python3 coverage_scheduler_experiment.py

Limitations

This is not a neural-policy or physical simulator experiment: the reachable set is known, two-dimensional, static, and sampled from a finite grid. The residual is analytically Lipschitz, the adaptive score's low-margin term is inactive because all true residuals exceed the chosen epsilon, and no learned policy, estimated reachable-set error, noisy residual, latent metric, or finite-sample confidence interval was tested.