desihub / desimeter

DESI coordinates and transformations
BSD 3-Clause "New" or "Revised" License
2 stars 4 forks source link

Add optimal fiber matching code. #103

Closed schlafly closed 4 years ago

schlafly commented 4 years ago

This PR attempts to find the optimal matching between positioners and spots given only the centers of the positioners and their arm lengths. It also finds any fibers whose assignments are ambiguous.

The problem is rewritten as a bipartite graph matching problem, where positioners are matched to spots, for which there are fast algorithms to find global optima. The code presently lacks any notion of where fibers are expected to be, and so is useful when things have gone terribly wrong but is less useful in ordinary operations. It would be straightforward to add a mode where expected locations were given, and the edges in the graph corresponding to matching positioners to spots in the given area were given extra weight.

Example usage:

from astropy.io import ascii
metr = ascii.read('desimeter/data/lbl-petal1/fp-metrology.csv')
fvc = ascii.read('fvc.csv')
calib = ascii.read('20200624T232400+0000_posparams_for_instr.csv')
from desimeter import match_positioners
best, score, alts = match_positioners.match_positioners(fvc, metr, calib, return_alternatives=True)
best, score, alts = match_positioners.match_positioners(fvc, metr, calib, return_alternatives=True)
best, score, alts = match_positioners.match_positioners(fvc, metr, calib, return_alternatives=True)
match_positioners.plot_match(fvc, metr, best, alts)

which produces something like: image

There are a few other potential additions to get closer to actual optimality. Currently the code assumes that each spot is either reachable by each positioner or not; it doesn't deal with uncertainties in the arm lengths in a sensible way. It would be better if the code understood which positioners had broken fibers and could better remove spurious spots. In an ideal world, it would be able to pass an assignment to some mechanical model of the focal plane and see if the claimed assignment was possible or not, given the possible collisions among the positioners. But this is pretty close to ideal.

scipy version 1.4 and later has a 1000x faster implementation of the linear_sum_assignment algorithm; for version 1.3, this code runs in a few minutes on the test petal.

julienguy commented 4 years ago

This is not the ultimate method because in the case of a collided petal most positioners have ambiguities, but that's another tool in the toolkit that might prove useful. Merging.

schlafly commented 4 years ago

Thanks. I think it's close to optimal (modulo the caveats above) for back-illuminated images, but clearly there are other options for front-illuminated petals. On this collided petal, 137 fibers were ambiguous.