Computing the k-resilience of a synchronized multi-robot system
Computing the k-resilience of a synchronized multi-robot system
复制标题
计算同步多机器人系统的 k-弹性
DOI：
10.1007/s10878-018-0297-3
复制
发表时间：
2018
影响因子：
1
通讯作者：
Lopez, Mario A.
中科院分区：
文献类型：
--
作者：
Bereg, Sergey;Caraballo, Luis-Evaristo;Díaz-Báñez, José-Miguel;Lopez, Mario A.
我们研究了多机器人系统的覆盖策略设计中出现的优化问题。考虑一组相互协作的机器人沿沿着预定的封闭且不相交的轨迹运动。每个机器人都需要定期与附近的机器人进行信息通信。在两个轨迹处于彼此范围内的地方，建立通信链路，允许两个机器人交换信息，前提是它们是“同步的”，即，他们同时访问链接。在这种设置中，定义了一个通信图，如果每对邻居都是同步的，那么一个机器人系统就被称为同步的。如果一个或多个机器人离开系统，那么一些轨迹将无人看管。为了在同步系统中处理这种情况，当现场机器人到达通信链路并检测到邻居的不存在时，它转移到相邻的轨迹以承担无人值守的任务。如果足够多的机器人离开，可能会发生一个活的机器人进入饥饿状态，在飞行过程中无法永久满足其他机器人。为了衡量系统在这种现象下的容忍度，我们将k-饥饿度定义为移除可能导致k个幸存机器人进入饥饿状态的机器人的最小数量。我们表明，计算k-弹性的问题是NP-难的，如果是输入的一部分，即使通信图是一棵树。我们提出了算法来计算k-弹性的常数值ofkin一般的通信图，并显示更有效的算法，其通信图是一棵树的系统。
We study an optimization problem that arises in the design of covering strategies for multi-robot systems. Consider a team ofncooperating robots traveling along predetermined closed and disjoint trajectories. Each robot needs to periodically communicate information to nearby robots. At places where two trajectories are within range of each other, a communication link is established, allowing two robots to exchange information, provided they are “synchronized”, i.e., they visit the link at the same time. In this setting a communication graph is defined and a system of robots is calledsynchronizedif every pair of neighbors is synchronized. If one or more robots leave the system, then some trajectories are left unattended. To handle such cases in a synchronized system, when a live robot arrives to a communication link and detects the absence of the neighbor, it shifts to the neighboring trajectory to assume the unattended task. If enough robots leave, it may occur that a live robot enters a state ofstarvation, failing to permanently meet other robots during flight. To measure the tolerance of the system under this phenomenon we define thek-resilienceas the minimum number of robots whose removal may causeksurviving robots to enter a state of starvation. We show that the problem of computing thek-resilience is NP-hard ifkis part of the input, even if the communication graph is a tree. We propose algorithms to compute thek-resilience for constant values ofkin general communication graphs and show more efficient algorithms for systems whose communication graph is a tree.
登录
查看更多内容
通信约束下空中机器人间信息交换的同步问题
DOI：
10.1109/icra.2015.7139843
发表时间：
2015
期刊：
2015 IEEE International Conference on Robotics and Automation (ICRA)
影响因子：
--
作者：
J. Díaz;L. Caraballo;M. Lopez;S. Bereg;Iván Maza;A. Ollero
通讯作者：
A. Ollero
正方形中等圆的堆积
影响因子：
--
作者：
M. Goldberg
通讯作者：
M. Goldberg
DOI：
10.1007/978-1-4613-0295-7_15
发表时间：
2001
期刊：
--
影响因子：
--
作者：
L. G. Casado;I. García;P. Szabó;T. Csendes
通讯作者：
L. G. Casado;I. García;P. Szabó;T. Csendes
视野障碍问题
影响因子：
0.8
作者：
T. Cusick
通讯作者：
T. Cusick
多飞行器共享空域冲突解决的速度分配问题
影响因子：
3.3
作者：
D. Alejo;J. Díaz;J. A. Cobano;P. Pérez;A. Ollero
通讯作者：
A. Ollero