Assignment Algorithms for Variable Robot Formations
Assignment Algorithms for Variable Robot Formations
复制标题
DOI：
10.1007/978-3-030-43089-4_58
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Srinivas Akella
中科院分区：
文献类型：
--
作者：
Srinivas Akella
本文介绍了算法来执行最优分配的机器人团队翻译在平面上从一个初始的形成一个可变的目标形成。我们考虑的情况下，当每个机器人被分配一个目标位置，个别机器人是可互换的，和目标形成可以缩放或translated.We计算的成本为所有候选人对初始，目标机器人分配的目标形成的参数的函数，并使用计算几何技术划分成等价类不变的成本顺序的参数空间。我们计算一个等价类的最小完成时间分配，将其表示为线性瓶颈分配问题（LBAP）。为了提高效率，我们解决了LBAP问题的每一个等价类的增量更新的解决方案，因为地层参数的变化。这项工作的动机是应用程序，包括在数字微流控芯片实验室设备中的液滴形成的运动，以及在飞机上的机器人和无人机的形成。
This paper describes algorithms to perform optimal assignment of teams of robots translating in the plane from an initial formation to a variable goal formation. We consider the case when each robot is to be assigned a goal position, the individual robots are interchangeable, and the goal formation can be scaled or translated.We compute the costs for all candidate pairs of initial, goal robot assignments as functions of the parameters of the goal formation, and partition the parameter space into equivalence classes invariant to the cost order using computational geometry techniques. We compute a minimum completion time assignment for an equivalence class by formulating it as a linear bottleneck assignment problem (LBAP). To improve efficiency, we solve the LBAP problem for each equivalence class by incrementally updating the solution as the formation parameters are varied. This work is motivated by applications that include the motion of droplet formations in digital microfluidic lab-on-a-chip devices, and of robot and drone formations in the plane.