Fukuhito Ooshita

Abstract 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).

We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: Minit, which denotes the number of nodes between two border nodes, and Ninit, which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that may see other robots on exactly one side. Our main contribution is to prove that, if Minit or Ninit is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.

We investigate crash-tolerant perpetual exploration algorithms by myopic luminous robots on ring networks. Myopic robots mean that they can observe nodes only within a certain fixed distance ϕ, and luminous robots mean that they have light devices that can emit a color from a set of colors. The goal of perpetual exploration is to ensure that robots, starting from specific initial positions and colors, move in such a way that every node is visited by at least one robot infinitely often. As a main contribution, we clarify the tight necessary and sufficient number of robots to realize perpetual exploration when at most f robots crash. In the fully synchronous model, we prove that f+2 robots are necessary and sufficient for any ϕ ≥ 1. In the semi-synchronous and asynchronous models, we prove that 3f+3 (resp., 2f+2) robots are necessary and sufficient if ϕ = 1 (resp., ϕ ≥ 2).

Summary In this work, we study the gathering problem to make multiple agents, who are initially scattered in arbitrary networks, meet at the same node. The network has agents with unique identifiers (IDs), and of them are weakly Byzantine agents that behave arbitrarily, except for falsifying their identifiers. These agents behave in synchronous rounds, and they may start an algorithm at different rounds. Each agent cannot leave information at a node. We propose herein a deterministic algorithm that efficiently achieves gathering with a simultaneous termination having a small number of non‐Byzantine agents. The proposed algorithm concretely works in rounds if the agents know the upper bound on the number of nodes, and at least non‐Byzantine agents exist, where is the length of the largest ID among agents, and is the number of rounds required to explore any network composed of nodes. The literature presents two efficient gathering algorithms with a simultaneous termination. The first algorithm assumes that agents know the number of nodes and achieves the gathering in rounds in the presence of any number of Byzantine agents, where is the length of the largest ID among non‐Byzantine agents. The second algorithm assumes both that agents know and that at least non‐Byzantine agents exist, and it achieves the gathering in rounds. The proposed algorithm is faster than the first existing algorithm and requires fewer non‐Byzantine agents than the second existing algorithm if is given to agents. We propose herein a new technique to simulate a Byzantine consensus algorithm for synchronous message‐passing systems on agent systems to reduce the number of agents.

The researches about a mobile entity (called agent) on dynamic networks have attracted a lot of attention in recent years. Exploration which requires an agent to visit all the nodes in the network is one of the most fundamental problems. While the exploration of dynamic networks with complete information or with no information about network changes has been studied, an agent with partial information about the network changes has not been considered yet despite its practical importance. In this paper, we consider the exploration of dynamic networks by a single agent with partial information about network changes. To the best of our knowledge, this is the very first work to investigate the exploration problem with such partial information. As a first step in this research direction, we focus on 1-interval connected rings as dynamic networks in this paper. We assume that the single agent has partial information called the ( H , S ) view by which it always knows whether or not each of the links within H hops is available in each of the next S time steps. In this setting, we show that H + S ≥ n and S ≥ ⌈ n / 2 ⌉ (n is the size of the network) are necessary and sufficient conditions to explore 1-interval connected rings. Moreover, we investigate the upper and lower bounds of the exploration time. It is proven that the exploration time is O ( n 2 ) for ⌈ n / 2 ⌉ ≤ S < 2 H ′ − 1 , O ( n 2 / H + n H ) for S ≥ max ( ⌈ n / 2 ⌉ , 2 H ′ − 1 ) , O ( n 2 / H + n log H ) for S ≥ n − 1 , and Ω ( n 2 / H ) for any S where H ′ = min ( H , ⌊ n / 2 ⌋ ) .