Algorithm design for coordination of mobile agents in connection-instable configurations

连接不稳定配置中移动代理协调的算法设计

基本信息

批准号：
21K17706
负责人：
柴田将拡
金额：
$ 3万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本研究課題では、ネットワーク中を自律的に移動するモバイルエージェント(以下、エージェント)間の協調動作を、ネットワークの構造が動的に変化する状況下でも正しく実現させるようなアルゴリズムの設計を目的とする。2022年度は均一配置問題・g-部分集合問題・探索問題を解決するアルゴリズム設計に取り組んだ。均一配置問題は、ネットワーク中に分散している複数体のエージェントが等間隔に配置するような自律的な移動を要求する問題である。この問題を 1-interval connected ring と呼ばれる、各ラウンドで高々1辺が消失しうるようなリング上で考察し、問題の可解性やアルゴリズムの性能を解明した。結果として、エージェントがノード総数の前提知識を持っている場合の方が、エージェント総数の前提知識を持っている場合よりも効率的に問題を解決できることを示した。この結果は論文誌に採録された。g-部分集合問題は、エージェントがg体以上ずつのグループに分かれて集合するような自律的な移動を要求する問題である。この問題を、各行リング・列リングが1-interval connected ringで表現されるようなn×nトーラス上で考察し、問題の可解性やアルゴリズムの性能を解明した。結果として、エージェント数がgnよりも少ない場合は問題は解決不能であることを示し、エージェント数がおよそ2gn+6nよりも大きい場合は最適な移動数(コスト)で問題が解決可能であることを示した。この結果は国際会議に採択され、現在は発表の準備中である。探索問題は各ノードが少なくとも1回はエージェントに訪問されるような移動の設計を要求する問題である。この問題をT-interval connected grid という動的グリッド上で考察し、問題が解決可能となるTの条件を解明した。この結果は国際会議へ投稿準備中という状況である。

该研究主题旨在设计一种算法，该算法可以正确地实现移动代理（以下称为代理）之间的协调操作，该算法即使在网络的结构动态变化的情况下，该算法即使在网络中自动移动。在2022年，我们致力于设计算法以解决统一的位置问题，G-Subset问题和搜索问题。统一的布局问题是一个问题，其中分布在网络中的多个代理需要自主运动，以使它们均匀间隔。在一个称为1间连接的环的环上检查了这个问题，在每个回合中最多可能会消失一个边缘，并且阐明了问题的解决方案和算法的性能。结果，我们表明，当代理具有对节点总数的假设知识时，与代理对代理总数的假设知识相比，可以更有效地解决问题。结果收集在期刊中。 G-Subset问题是一个问题，在该问题中，代理需要自主运动，以便将它们分为G型或更多。在NXN圆环上检查了这个问题，每个行环和柱环被表示为1间隔连接的环，并阐明了问题解决能力和算法的性能。结果，我们表明，如果代理的数量小于GN，则该问题是无法解决的，并且如果代理的数量大于大约2gn+6n，则该问题与最佳运动数量（成本）解决。结果在国际会议上被接受，目前正在准备演讲。搜索问题是一个需要设计运动的问题，以使每个节点至少一次访问一次。在称为T间隔连接的网格的动态网格上检查了此问题，并阐明了允许解决该问题的T条件。目前正在为国际会议提交结果。

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Visibility-optimal gathering of seven autonomous mobile robots on triangular grids

七个自主移动机器人在三角形网格上的可见性最佳聚集

DOI：
10.15803/ijnc.12.1_2
发表时间：
2022
期刊：
International Journal of Networking and Computing
影响因子：
0
作者：
Masahiro Shibata;Masaki Oyabu;Yuichi Sudo;Junya Nakamura;Yonghwan Kim;Yoshiaki Katayama,
通讯作者：
Yoshiaki Katayama,

Almost uniform deployment of mobile agents in dynamic rings

动态环中移动代理的部署几乎统一