Simultaneous Optimization of Assignments and Goal Formations for Multiple Robots
Simultaneous Optimization of Assignments and Goal Formations for Multiple Robots
复制标题
DOI：
10.1109/icra.2018.8460542
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
S. Agarwal;Srinivas Akella
中科院分区：
文献类型：
--
作者：
S. Agarwal;Srinivas Akella
本文提出的算法，同时计算的最佳分配和形成参数的一队机器人从一个给定的初始形成一个可变的目标形成（目标形成的形状是给定的，其规模和位置参数必须优化）。我们假设$n$机器人是相同的球体。我们使用旅行距离的平方和作为目标函数被最小化，这也确保了轨迹是无碰撞的。我们发现，这种分配与可变目标编队问题可以转化为一个线性和分配问题（LSAP），我们建立的伪成本是独立的编队参数。最后的问题可以用匈牙利算法在O（n3）时间内解决。因此，使用这种新方法的分配问题与固定目标编队的标准分配问题具有相同的O（n3）时间复杂度。200和600机器人的仿真结果表明，该算法是足够快的实际应用。
This paper presents algorithms to simultaneously compute the optimal assignments and formation parameters for a team of robots from a given initial formation to a variable goal formation (where the shape of the goal formation is given, and its scale and location parameters must be optimized). We assume the $n$ robots are identical spheres. We use the sum of squared travel distances as the objective function to be minimized, which also ensures that the trajectories are collision free. We show that this assignment with variable goal formation problem can be transformed to a linear sum assignment problem (LSAP) with pseudo costs that we establish are independent of the formation parameters. The transformed problem can then be solved using the Hungarian algorithm in O (n3) time. Thus the assignment problem with variable goal formations using this new approach has the same O (n3) time complexity as the standard assignment problem with fixed goal formations. Results from simulations on 200 and 600 robots are presented to show the algorithm is sufficiently fast for practical applications.