Optimal transport on multi-robot coordination

Abstract

Assignment problem is the fundamental task in multi-robot system, where resource allocation encounters the capacity requirement in practice, then the optimal transport theory is linked to produce the best transportation plan. Pioneer researchers established the foundation to resolve the least-square assignment under capacity constraints, while there must exist the power diagram induced the equivalent map. In this thesis, we investigate optimal transport in discrete and semi-discrete formulation with fast computation algorithm, thus facilitate the application that aimes to minimize the cost between monitoring sites and autonomous agents.

Based on the literatures, we propose the semi-discrete optimization that involves the continuous formulation of power diagram with discrete densities, which represent the agent locations. Due to the non-convexity, we first enforce the capacity constraints with gradient-descent method, and then update the monitor locations in centroidal manner. To remedy the non-smoothness issue, we further propose the discrete optimization upon the geometric inspiration, such that the optimal assignment between two monitors can be determined by the perpendicular line that partitions the combined agents in Euclidean space. The pairwise assignment can be implemented at linear complexity, and acceleration structures are used to extract the monitor neighbors and avoid the un-necessary comparison. Extensive experiments demonstrate that our method outperforms classic algorithms and variational methods in convergence rate with a big margin. Furthermore, the deterministic algorithm can be naturally extended with abitrary metric kernel and dimension.

In addition, we propose the optimization framework under relaxed capacity constraints and allow the user-specific requirement in real-world applications. The pairwise assignment algorithm is revised with three perpendicular lines, referred to the bisector and monitor capacities, such that we obtain the optimal solution by the middle line under the relaxed constraints. Enforced with the sensing range, we iteratively add new monitor to the needed region, and then remove the redundant monitors without distance violation. Finally, we consider air-to-ground channel model to measure the path loss between aerial monitor and ground agent, and require each assignment pair to guarantee the communication quality as to SNR level. Thus we compute the metric difference to adapt the three-line algorithm with the statistical model, and select the middle location to decide the optimal assignment. Given the simulated carrier power and frequency, our method with aggressive update achieves the two-order faster convergence than the linear program solver, when the resulted assignment maps are nearly identical, according to cumulative distribution function. Moreover, our method succeeds to maintain the desirable service with the minimum number of active monitors, during the dynamic optimization for the one-week taxis GPS records, while our future work is the parallel and distributed computation.