The vast majority of existing Distributed Computing literature about mobile robotic swarms considers computability issues: characterizing the set of system hypotheses that enables problem solvability. By contrast, the focus of this work is to investigate complexity issues: obtaining quantitative results about a given problem that admits solutions. Our quantitative measurements rely on a newly developed simulation framework to benchmark pen and paper designs. First, we consider the maximum traveled distance when gathering robots at a given location, not known beforehand (both in the two robots and in the n robots settings) in the classical OBLOT model, for the FSYNC, SSYNC, and ASYNC schedulers. This particular metric appears relevant as it correlates closely to what would be real world fuel consumption. Then, we introduce the possibility of errors in the vision of robots, and assess the behavior of known rendezvous (aka two robots gathering) and leader election protocols when sensors are unreliable. We also introduce two new algorithms, one for fuel efficient convergence, and one for leader election, that operate reliably despite unreliable sensors.
翻译:绝大多数关于移动机器人群的分布式计算机现有文献都考虑了可计算性问题:将一套系统假设描述成能够造成问题溶解的系统假设特征。 相反,这项工作的重点是调查复杂问题:获得对特定问题的量化结果,从而承认解决办法。我们的定量测量依靠新开发的模拟框架来确定笔和纸张设计的基准。首先,我们考虑在特定地点收集机器人时的最大距离,这些机器人事先没有在传统OBLOT模型(FSYNC、SSYNC和ASYNC调度器)中(在两个机器人和n机器人设置中)被识别。这一特定指标似乎与现实世界燃料消耗密切相关。然后,我们在机器人的愿景中引入错误的可能性,并在传感器不可靠的情况下评估已知的集合(两个机器人聚集)和领导选举协议的行为。我们还引入了两种新的算法,一种是燃料高效融合法,另一种是领导人选举法,尽管传感器不可靠,但操作可靠。