2018/01/31 by Jingjin Yu, Yu, Jingjin · 1 citation
Computer Science · Engineering · #Optimization and Search Problems #Robotic Path Planning Algorithms #Advanced Manufacturing and Logistics Optimization
paper · pdf · doi:10.48550/arxiv.1801.10465
Let G = (V, E) be an m1 × … × mk grid. Assuming that each v ∈ V is occupied by a robot and a robot may move to a neighboring vertex in a step via synchronized rotations along cycles of G, we first establish that the arbitrary reconfiguration of labeled robots on G can be performed in O(k∑i mi) makespan and requires O(|V|2) running time in the worst case and o(|V|2) when G is non-degenerate (in the current context, a grid is degenerate if it is nearly one dimensional). The resulting algorithm, iSAG, provides average case O(1)-approximate (i.e., constant-factor) time optimality guarantee. When all dimensions are of similar size O(|V|(1)/(k)), the running time of iSAG approaches a linear O(|V|). Define dg(p) as the largest distance between individual initial and goal configurations over all robots for a given problem instance p, building on iSAG, we develop the PartitionAndFlow (PAF) algorithm that computes O(dg(p)) makespan solutions for arbitrary fixed k ≥ 2, using mostly o(|V|2) running time. PAF provides worst case O(1)-approximation regarding solution time optimality. We note that the worst case running time for the problem is Ω(|V|2).