On Memory, Communication, and Synchronous Schedulers for Computational Bounds of Autonomous Mobile Robots

自主移动机器人计算界限的内存、通信和同步调度器

基本信息

批准号：
20K11685
负责人：
和田幸一
金额：
$ 2.75万
依托单位：
Hosei University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本研究は，ロボットが記憶できる能力，ロボット問の通信能力，ロボットを動作させる同期度がロボット群の計算能力に及ぼす影響を解明することを目的としている．ロボットに搭載するライトは自身も他のロボットも認識できるモデル(LUMI), 自身のライトのみを認識するモデル(FSTA)，他のロボットのみが認識できるモデル(FCOM)を考える．FSTAモデルにおいては，定数有限状態を持つだけで通信不可であると考える．また，FCOMモデルにおいては，ライトの色を見せることによって他のロボットと直榜通信可能となるが，自身のライトの色は見えないため，次のサイクルでは通信内容を忘れてしまう，すなわち，ロボットは通信可能だが無記憶であると考える．それぞれのモデルの計算能力を同期度と合わせて明らかにすることが本研究の目的である．この目的に対して，令和2年度では持続性メモリと直接通信が動作スケジュールに対してどのように影響するかを明らかにした．まず全同期(Fsynch)と半同期(Ssynch)におけるこれまでの結果をもとにSsynchとFsynchにおける持続性メモリと直接的通信による能力の限界を導出した．令和3年度では，これらの結果を拡張し，ロボットが持つ機能を限定しても同様の結果が成り立つことを示した．また,FsynchとSsynchの中間に位置するRsynchと呼ばれるクラスを導入し，Fsynch,Rsynch,Ssynchの相互関係を完全に解明した．また， Rsynchはエネルギーを制限したロボット群の能力と一致することを示し，エネルギーの制限されたロボット群の計算能力を議論できる枠組みを与え，エネルギー無制限のロボット群との能力の差を明らかにした．令和4年度は，非同期スケジューラ(Asynch)と各ロボットモデル間の関係を明らかにした．

本研究的目的是阐明机器人的记忆能力、机器人之间的通信能力以及机器人动作的同步对一组机器人的计算能力的影响。我们考虑安装在机器人上的灯可以被自身和其他机器人识别的模型（LUMI），仅可以识别其自身灯的模型（FSTA），以及只有其他机器人可以识别它的模型（外交部）。在 FSTA 模型中，假设仅通过恒定的有限状态不可能进行通信。另外，在FCOM模型中，可以通过显示光的颜色来直接与其他机器人进行通信，但由于自身光的颜色不可见，因此考虑到机器人会忘记下一个周期的通信内容。可以交流，但没有记忆。这项研究的目的是阐明每个模型的计算能力以及同步程度。为此，我们在 2020 年阐明了持久内存和直接通信如何影响操作计划。首先，根据之前全同步（Fsynch）和半同步（Ssynch）的结果，我们得出了Ssynch和Fsynch由于持久内存和直接通信的能力限制。在 2021 财年，我们扩展了这些结果，并表明即使机器人的功能有限，类似的结果也成立。我们还引入了一个名为Rsynch的类，它位于Fsynch和Ssynch之间，彻底理清了Fsynch、Rsynch和Ssynch之间的相互关系。此外，Rsynch 还被证明可以匹配一组能量有限的机器人的能力，为讨论一组能量有限的机器人的计算能力提供了一个框架，并阐明了一组能量无限的机器人的能力差异．．在2020财年，我们明确了异步调度器（Asynch）和每个机器人模型之间的关系。

项目成果

期刊论文数量（24）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Using model checking to formally verify rendezvous algorithms for robots with lights in Euclidean space

使用模型检查正式验证欧几里得空间中带灯机器人的交会算法

DOI：
10.1016/j.robot.2023.104378
发表时间：
2023
期刊：
Robotics and Autonomous Systems
影响因子：
4.3
作者：
Defago Xavier;Heriban Adam;Tixeuil Sebastien;Wada Koichi
通讯作者：
Wada Koichi

Efficient deterministic MapReduce algorithms for parallelizable problems

针对可并行问题的高效确定性 MapReduce 算法

DOI：
10.1016/j.jpdc.2023.02.010
发表时间：
2023
期刊：
Journal of Parallel and Distributed Computing
影响因子：
3.8
作者：
Frei Fabian;Wada Koichi
通讯作者：
Wada Koichi

Autonomous Mobile Robots: Refining the Computational Landscape

自主移动机器人：完善计算环境

DOI：
10.1109/ipdpsw52791.2021.00091
发表时间：
2021
期刊：
2021 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)
影响因子：
0
作者：
K. Buchin;P. Flocchini;I. Kostitsyna;T. Peters;N. Santoro;K. Wada
通讯作者：
K. Wada

Gathering problems for autonomous mobile robots with lights

收集带灯自主移动机器人的问题