可視領域が狭い自律分散ロボット群による協調動作実現のためのアルゴリズム設計

项目来源

日本学术振兴会基金(JSPS)

项目主持人

柴田 将拡

项目受资助机构

九州工業大学

项目编号

25K14995

立项年度

2025

立项时间

未公开

项目级别

国家级

研究期限

未知 / 未知

受资助金额

4550000.00日元

学科

情報学基礎論関連

学科代码

未公开

基金类别

基盤研究(C)

关键词

自律分散システム ; 自律分散ロボット群 ; 集合問題 ; 均一配置問題 ; 可視領域 ;

参与者

未公开

参与机构

九州工業大学,大学院情報工学研究院

项目标书摘要:Outline of Research at the Start:自律分散ロボット群は周囲の観測・目的地の計算・移動を繰り返すハードウェアのモデル化したものである。申請者はこれまでにロボットの可視領域が非常に制限された状況下での一点集合や均一配置等の協調動作実現のための問題についての不可能性・可解性を解明してきた。これまでは過去情報を用いず現在の観測情報のみを基に移動を繰り返すモデルを用いたが、ロボット群に少量の過去情報の記憶を許す等、追加能力を付与すれば、従来では実現不可能だった状況からでも協調動作が実現できる可能性がある。本申請では、追加能力の付与により可視領域の狭いロボット群が様々な状況から協調動作が可能となるようなアルゴリズムの設計を行う。

  • 排序方式:
  • 1
  • /
  • 1.Stand-up indulgent gathering on lines for myopic luminous robots

    • 关键词:
    • MOBILE ROBOTS
    • Bramas, Quentin;Kakugawa, Hirotsugu;Kamei, Sayaka;Lamani, Anissa;Ooshita, Fukuhito;Shibata, Masahiro;Tixeuil, Sebastien
    • 《COMPUTER JOURNAL》
    • 2026年
    • 期刊

    We consider a strong variant of the crash fault-tolerant gathering problem called Stand-Up Indulgent Gathering (SUIG), by robots endowed with limited visibility sensors and lights on line-shaped networks. In this problem, a group of mobile robots must eventually gather at a single location, not known beforehand, regardless of the occurrence of crashes. Differently from previous work that considered unlimited visibility, we assume that robots can observe nodes only within a certain fixed distance (i.e. they are myopic), and emit a visible color from a fixed set (i.e. they are luminous), without multiplicity detection. We consider algorithms depending on two parameters related to the initial configuration: $M_{\mathrm{init}}$, which denotes the number of nodes between two border nodes, and $O_{\mathrm{init}}$, which denotes the number of nodes hosting robots. Then, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if $M_{\mathrm{init}}$ or $O_{\mathrm{init}}$ is odd, SUIG can be solved in the fully synchronous model even if crashes occur at a node at any phase of execution (i.e. including within the LCM cycle).

    ...
  • 2.Partial gathering of mobile agents in dynamic rings

    • 关键词:
    • Computational complexity;Computational methods;Distributed computer systems;Dynamics;Bi-directional rings;Distributed systems;Dynamic graph;Dynamic ring;Gathering problem;Generalisation;Partial gathering problem;Positive integers;Ring networks;Synchronous dynamics
    • Shibata, Masahiro;Sudo, Yuichi;Nakamura, Junya;Kim, Yonghwan
    • 《Theoretical Computer Science》
    • 2026年
    • 1063卷
    • 期刊

    In this paper, we consider the partial gathering problem of mobile agents in synchronous dynamic bidirectional ring networks. The partial gathering problem is a generalization of the (well-investigated) total gathering problem, which requires that all k agents distributed in the network terminate at a non-predetermined single node. The partial gathering problem requires, for a given positive integer g (© 2025 The Authors

    ...
  • 排序方式:
  • 1
  • /