INIT (joints.py) runs on the nested grids 8h, 4h, 2h, h, each grid's cheapest cost being the budget of the next, and under a budget keeps only the states that a curve within it can pass: same curves, about 5 times less INIT time.
Default run (run.py): INIT keeps the cheapest curve of at most three route classes, its last step advances each by 5 iterations of gradient projection and keeps the cheapest, and gradient projection runs once from it (--select; --select 0 = the first class as before; --top K unchanged).
On the 80 instances the default reaches the cost of the all-class run on 80 of 80 (77 of 80 before), median 0.45 / 0.69 / 0.79 / 0.92 s per instance.
reference/init.csv and init_summary.json rebuilt from this code; READMEs updated.
Docs: algorithms named, not numbered (paper: INIT Algorithm 1, repair of Eq. (5) Algorithm 2, gradient projection Algorithm 3)
Comments, docstrings, help strings, printed labels and READMEs now say INIT, the repair of Eq. (5) and gradient
projection instead of algorithm numbers, so the text does not depend on the paper's numbering. The root README
keeps one line with the paper's numbers (and the cone projection, Algorithm 4).
No code, identifier, option or result key changed. The one stored string that changed is the "algorithm" field
that globmp.synthetic.run writes for new runs; the reference files are unchanged.
Algorithm 2 as written in the paper: step 1/beta and the repair of Eq. (5)
- globmp/repair.py (new): the repair of Algorithm 2 (Algorithm 1 in the paper), Eq. (5). After a cost step Y, the
next curve is the point nearest to Y of the set where every block, linearized at the current feasible curve, is
nonnegative on its whole interval. The solve keeps a list of contacts (block, instant): find the instants at
which a linearized block is negative, add them, fit nonnegative weights of all listed contacts jointly, repeat
until none is negative. Problem.repair(Y, z, tv); Problem.repair_tol.
- globmp/gpa.py: Problem.solve repairs with it (Problem.alg2_repair = 'eq5', the default). 'restore' keeps the
restoration of restore.py as the repair; the scaling study and Maze2D set it, because their results were
obtained with it, and the 'sampled' and 'orthant' modes always use it. The restoration still makes an
infeasible seed feasible.
- Section 4.1 (globmp/synthetic/run.py): one configuration, Algorithm 2 with step 1/beta and this repair from
INIT's curve; …
Yesterday
One INIT: globmp/init.py serves the grid start and the synthetic study
- globmp/init.py: INIT (Algorithm 3) as one function, the shortest path over the joints for given
per-joint state sets, with exact piece tests, budget pruning (cost-to-go rule by default, plain
budget rule as an argument) and back-pointers.
- globmp/gridstart: instance.py supplies the grid values per joint, the piece cost and the piece
test (GridStates, grid_start); plain_grid.py holds the plain grid; init.py removed. reference/
reproduces (same z_h and test counts in 36 of 36 cases).
- globmp/synthetic: joints.py supplies the per-pair states (positions on a grid, zero derivatives),
piece cost, piece test and route label; init.py removed. Same class and joints as before on all
80 instances; INIT takes 0.5 to 1.3 s per instance (median per robot count).
- The name INIT is used everywhere; the ranking file is N*_i*_init.json.
- gridstart run.py --first-order calls the current Algorithm 2 again.
2 days ago
gridstart README: INIT and the plain grid agree in cost in 27 of 27 cases; one cost tie at N = 1, h = 1.25 gives different curves
- run.py: default picks one route class with INIT-P (init.py, h = 0.05 m) and runs one first-order
Algorithm 2 solve from it (--top K for more classes); --routes all solves every class and
reproduces reference/. Algorithm 2 uses momentum with monotone restart, Barzilai-Borwein restoration
steps in the middle stages and tolerance continuation; no Newton, SQP or polish.
- reference/: all-class results rerun with these settings (2472/2472 classes feasible and certified;
median 58/76/79/95 s per class for 2/4/6/8 robots); init.csv and init_summary.json for the default
(77/80 instances equal to the all-class best within 1e-5, the other 3 within 0.2-3.0%).
- fig_synth1 (and the project page copy) redrawn from the new results; fig_synth2 and the scaling
study are unchanged.
- READMEs updated; certify.py stays as an optional check.
globmp/gridstart reorganized: init.py holds INIT (Algorithm 3) and the plain grid only, instance.py the instance and the exact piece test, exact_repair.py the repair step and GlobMP with it; READMEs point to Algorithm 3
Grid start of Theorem 1 by a shortest path over the joints (Algorithm INIT): globmp/gridstart with the instance, INIT, the plain grid, the exact repair step and reference results
