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）的模型，以及只能被其他机器人（FCOM）识别的模型。在FSTA模型中，由于它具有恒定的有限状态，因此认为通信被认为是不可能的。此外，在FCOM模型中，通过显示光的颜色，可以直接与其他机器人通信，但是由于光的颜色不可见，因此在下一个周期中会忘记通信的内容，这意味着机器人能够通信，但没有内存。这项研究的目的是阐明每个模型的计算能力以及同步程度。为了解决此目的，在2020财年，我们阐明了可持续记忆和直接沟通如何影响运营时间表。首先，基于所有同步（FSYNC）和半同步（SSYNC）的先前结果，我们通过持续的内存和直接通信得出了Ssync和Fsync功能的限制。在2021年，即使机器人的功能受到限制，这些结果也扩大了，并且表明相似的结果也是正确的。此外，引入了位于Fsync和Ssync之间的一个名为Rsync的类，并完全阐明了Fsync，Rsync和Ssync之间的相互关系。此外，Rsync表明它与能量受限机器人组的能力相吻合，提供了讨论能量受限机器人组的计算能力的框架，揭示了它们之间的能力和无限机器人组的差异。在2022年，阐明了异步调度程序（异步）与每个机器人模型之间的关系。

项目成果

期刊论文数量（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

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