  Minimising the longest travel distance for a group of mobile robots with
interchangeable goals requires knowledge of the shortest length paths between
all robots and goal destinations. Determining the exact length of the shortest
paths in an environment with obstacles is NP-hard however. In this paper, we
investigate when polynomial-time approximations of the shortest path search are
sufficient to determine the optimal assignment of robots to goals. In
particular, we propose an algorithm in which the accuracy of the path planning
is iteratively increased. The approach provides a certificate when the
uncertainties on estimates of the shortest paths become small enough to
guarantee the optimality of the goal assignment. To this end, we apply results
from assignment sensitivity assuming upper and lower bounds on the length of
the shortest paths. We then provide polynomial-time methods to find such bounds
by applying sampling-based path planning. The upper bounds are given by
feasible paths, the lower bounds are obtained by expanding the sample set and
leveraging the knowledge of the sample dispersion. We demonstrate the
application of the proposed method with a multi-robot path-planning case study.
