Uniform Deployment of Mobile Robots in Complete Bipartite Graphs

Studies about mobile robot networks have recently captured the interest of the Distributed Computing community. Typically, robots aim to achieve some (global) tasks with limited (local) capabilities. Most studies assume that robots are identical (they execute the same algorithm, and cannot be distinguished by their appearance), and oblivious (they cannot remember their past actions). In addition, it is assumed that robots cannot explicitly communicate with other robots. Instead, they communicate implicitly by observing the (relative) positions of others.

Since Suzuki and Yamashita presented a pioneering work [17] using such weak robots, many problems have been studied in various settings. A number of studies consider problem solvability both in continuous environments (a.k.a. two- or three-dimensional Euclidean space) [17, 18], and in discrete environments (a.k.a. graphs) [2, 5, 9, 12].

In the discrete setting, the uniform deployment (or uniform scattering) problem is considered a fundamental coordination problem. This problem requires robots to spread uniformly in the network. Uniform deployment is useful in practice: when robots achieve uniform deployment, they can maximize the coverage area, and later execute some related tasks such as patrolling, environment monitoring, and intruder detection efficiently [1]. In addition, when robots equipped with resources such as foods are deployed uniformly in a disaster area, victims can access to the resources quickly. So far, the uniform deployment problem for mobile robots has been considered in continuous cycles [7], discrete ring networks [6], and discrete grid networks [1, 8, 10, 11] (or grid for short). In grids, while uniform deployment is feasible by oblivious robots [1], it was shown that uniform deployment can be achieved faster [10], or better [8] using luminous robots. Luminous robots are equipped with a device that can emit a single non-volatile color from a constant number of colors visible to itself and other robots at a given time. Since the light color is non-volatile, it can be used as a constant space persistent memory. The notion of luminous robots was introduced by Das et al. [3] to circumvent impossibility results for oblivious robots in the continuous space. D’Emidio et al. [4] consider the solvability of several problems for luminous robots in graphs, focusing on the relationship between synchronicity and the necessary number of light colors to solve problems. Recently, Poudel and Sharma [11] improved the time complexity of uniform deployment on grids for robots without light (i.e., oblivious robots). Also, Shibata et al. [16] consider a weaker variant of the uniform deployment problem, called the semi-uniform deployment problem in perfect $\mathrm{\ell }$-ary trees where every intermediate node has $\mathrm{\ell }$ children and all leaf nodes have the same depth. Intuitively, this problem requires that each of the nodes with depth $s,s+d,s+2d,\mathrm{\dots }$ is occupied by a robot for some integers $s$ and $d$ (). They considered this problem for opaque robots (i.e., the robot model such that robot $r_i$ cannot observe robot $r_j$ when another robot $r_h$ exists on the path between $r_i$ and $r_j$) and clarified the relationship between the number of available light colors and the solvability of the semi-uniform deployment problem.

A separate research track considered the uniform deployment problem in ring networks for another mobile entity model called mobile agents [13, 14, 15], which have persistent memory, but cannot observe others’ positions unless they are located on the same node. Like the aforementioned works, although uniform deployment (including its variants) has been considered in various settings, to the best of our knowledge, it was not considered in graphs other than rings, grids, and perfect $\mathrm{\ell }$-ary trees.

In this paper, we consider the problem of uniform deployment for mobile robots in complete bipartite graphs. Specifically, when $n$ robots are positioned arbitrarily at distinct nodes in a complete bipartite graph $K_{n,n}$, which consists of two $n$-node sets $V_L$ and $V_R$, this problem requires the robots to achieve one of the following configurations: (a) there exists exactly one robot at every node in $V_L$, and no robot in $V_R$, or (b) there exists exactly one robot at every node in $V_R$, and no robot in $V_L$. An example of uniform deployment in a complete bipartite graph $K_{5,5}$ is presented in Fig. 1. Observe that when robots reach such a configuration, the distance between any two robots is 2, and perfect uniform deployment is achieved. We assume that robots are uniform (they execute the same algorithm), oblivious (they cannot memorize past information), cannot communicate with each other directly, and cannot detect whether their hosting node belongs to $V_L$ or to $V_R$ (that is, the nodes are not labeled).

In these settings, we explore the relationship between the visibility range of robots and the solvability of the uniform deployment problem. First, we show that there exist initial configurations from which robots cannot achieve uniform deployment even if they have an infinite visibility range. Hence, the uniform deployment problem in this paper requires robots to (i) detect whether the given initial configuration is solvable or not under the assumption that robots have an infinite visibility range, and (ii) reach a uniformly deployed configuration described above whenever the configuration is a solvable one. Next, we demonstrate that visibility range 1 (meaning robots can only observe nodes at a distance of 1 and the robots positioned on them) is insufficient, proving the impossibility of solving the problem under this constraint. Conversely, we show that visibility range $\mathrm{\Theta }(\log n)$ is sufficient by presenting a deterministic algorithm that (i) detects whether the initial configuration is solvable or not, and (ii) achieves uniform deployment in $O(1)$ round whenever the configuration is a solvable one, even if each robot’s action is executed asynchronously (robots may be scheduled freely for execution). At first glance, since the diameter of complete bipartite graphs is 2, readers may think that visibility range $\mathrm{\Theta }(\log n)$ is too large and a constant range is sufficient. In the last section, we briefly introduce an example presenting that robots with a constant visibility range (which is 3 in this example) cannot solve the problem in a naive way, and it is not easy to reduce the visibility gap.

A complete bipartite graph $K_{n,n}$ is defined as 3-tuple $K_{n,n}=(V_L,V_R,E)$, where $V_L$ (resp., $V_R$) is a left-node set (resp., right-node set) and $E=V_L\times V_R$ is a set of edges. In this paper, we assume that $|V_L|=|V_R|=n$ holds. Hence, $K_{n,n}$ in this paper has $2n$ nodes and $n^2$ edges. The distance between nodes $v$ and $v^{\prime }$ is the minimum number of edges connecting them. Notice that the maximum distance between any two nodes in $K_{n,n}$ is 2. We assume that nodes are anonymous, i.e., they do not have distinct IDs (and thus the indices of nodes are used just for the notation purpose). In addition, we assume that each edge $e$ incident to $v$ is uniquely labeled at $v$ with a label from the set $\{1,2\mathrm{\dots },n\}$. We call this label port number. Since each edge connects two nodes, it has two port numbers. Port labelings are common to robots, but they are $local$, that is, there is no coherence between the two port numbers in the edge connecting two nodes.

We consider a set of $n$ robots with the following characteristics and capabilities. Robots are uniform, that is, they execute the same algorithm and cannot be distinguished by their appearance. Note that, since robots are uniform and nodes are anonymous, robots do not know whether their hosting node belongs to $V_L$ or to $V_R$. Robots are oblivious, that is, they have no persistent memory and cannot remember their past actions. In addition, robots cannot communicate with other robots directly. However, robots have limited visibility range and they can observe the positions of other robots and port labeling within the range. This means that robots can communicate implicitly by their positions and port numbers. For example, robots with visibility range 1 can observe nodes within distance 1, that is, when a robot $r_i$ is at a node in $V_L$ (resp., $V_R$), it can observe the port labeling of edges connecting to its current node, and can detect whether each node in $V_R$ (resp., $V_L$) is occupied by a robot or not. When robots have visibility range 2, they can observe nodes and port labeling within distance 2. An example is given in Fig. 2. A number at each edge endpoint represents a port number. In each case, robot $r_i$ can observe the area of solid nodes, edges, robots, and port numbers within the range, but cannot observe the dashed area. We call the information obtained from the observable area of $r_i$ the view of $r_i$. As the figures show, $r_i$’s view can be represented as a rooted tree whose root is $r_i$’s staying node. Views for robots with visibility range more than 2 can be represented similarly. In particular, in this paper, we consider two types of robots with respect to visibility range: robots with visibility range 1 and robots with visibility range $\mathrm{\Theta }(\log n)$. Notice that the notion of the view can be used for a node with no robot (we use such views later).

Each robot executes the algorithm by repeating Look-Compute-Move (LCM) cycles. At the beginning of each cycle, the robot observes positions of the other robots and port labeling within its visibility range (Look phase). According to the observation, the robot computes the destination to move (possibly the current node, which implies the agent stays at the node) (Compute phase). If the robot decides to move, it moves to the node by the end of the cycle (Move phase). To analyze the asynchronous behavior of robots, we introduce the notion of a scheduler that decides when each robot executes the phases. When the scheduler makes robot $r$ execute some phases, we say the scheduler activates $r$. There are three types of synchronicity: the FSYNC (fully synchronous), the SSYNC (semi-synchronous), and the ASYNC (asynchronous) model. In the FSYNC model, at each time step, all robots are activated and they execute an LCM cycle synchronously and concurrently. In the SSYNC model, at each time step, a scheduler activates a non-empty set of robots and the selected robots execute the cycle synchronously and concurrently. In the ASYNC model, cycles of robots are executed asynchronously; each phase of a cycle can be executed at arbitrary time. Hence, in the ASYNC model, each robot can move based on an outdated view that the robot observed before, and a robot may exist on some edge in the view. On the other hand, in the FSYNC and SSYNC model, since they move synchronously and concurrently, robots can move based on the latest view and robots always exist at nodes in the view. When considering the SSYNC or ASYNC model, we assume that the scheduler is fair, that is, each robot is activated infinitely often. We consider the scheduler as an adversary, that is, we assume that the scheduler is omniscient (it knows robot positions, algorithms, etc.), and tries to activate robots in such a way that they fail to execute the task.

A configuration $𝒞$ of the system is defined by the positions of all robots. We call a node hosting a robot (resp., not hosting a robot) an occupied node (resp., an empty node). For an infinite sequence of configurations $E=C_0,C_1,\mathrm{\dots },C_t,\mathrm{\dots }$, we say $E$ is an execution from initial configuration $C_0$ if, for every instant $t$, $C_{t+1}$ is obtained from $C_t$ after all the activated robots execute an action each. We say $C_i$ is the $i$-th configuration of execution $E$. In initial configuration $C_0$, we assume that robots are arbitrarily positioned at distinct nodes, and the positions are determined by the adversary.

The uniform deployment problem in complete bipartite graphs requires robots to achieve one of the following configurations: (a) there exists exactly one robot at every node in $V_L$, and no robot in $V_R$, or (b) there exists exactly one robot at every node in $V_R$, and no robot in $V_L$. Observe that when robots reach such a configuration, the distance between any two robots is 2, and perfect uniform deployment is achieved. Conversely, perfect uniform deployment is achieved only if the robots reach such a configuration. However, as shown in the next section, there exist configurations from which robots cannot achieve perfect uniform deployment even if they have an infinite visibility range. Let $S_h$ be the set of configurations from which, according to some algorithm, the robots with visibility range $h$ achieve perfect uniform deployment even in the ASYNC model, and $\overline{S_h}$ be the set of configurations not in $S_h$. Then, the uniform deployment problem is defined as follows.

In this paper, we evaluate the algorithm performances by the number of rounds for robots to solve the problem. Here, a round is defined as the shortest fragment of an execution where every robot is activated at least once.

In this subsection, we show that visibility range $\mathrm{\Theta }(\log n)$ is sufficient for detecting whether or not the current configuration is view-symmetric in an infinite visibility range and thus an unsolvable one. Let ${\text{view}}_h(v)$ be the view of node $v$ in visibility range $h$. Notice that $v$ may be an empty node. When two nodes $v$ and $v^{\prime }$ have the same view of range $h$, we express the relationship by ${\text{view}}_h(v)={\text{view}}_h(v^{\prime })$. Then, we partition nodes into several groups with the same view of range $h$. That is, let $ℱ𝒩$${}_{}{}^h{}_L{}^{}$ =$\{{\text{NL}}_1^h,{\text{NL}}_2^h,\mathrm{\dots }{\text{NL}}_{k_h}^h\}(1\le k_h\le n)$ (resp., $ℱ𝒩$${}_{}{}^h{}_R{}^{}$ =$\{{\text{NR}}_1^h,{\text{NR}}_2^h,\mathrm{\dots }{\text{NR}}_{k_h}^h\}$ $(1\le k_h\le n)$) be a family of sets in the left-node set (resp., the right-node set) such that each node in ${\text{NL}}_{\mathrm{\ell }}^h(1\le \mathrm{\ell }\le k_h)$ (resp., ${\text{NR}}_{\mathrm{\ell }}^h(1\le \mathrm{\ell }\le k_h)$) has the same view in visibility range $h$ (i.e., ${\text{view}}_h(v)={\text{view}}_h(v^{\prime })$ holds for any $v,v^{\prime }\in {\text{NL}}_{\mathrm{\ell }}^h$). For example, when there exist six nodes $v_L^1,v_L^2,v_L^3,v_L^4,v_L^5,$ and $v_L^6$ in $V_L$, nodes $v_L^1,v_L^2$, and $v_L^5$ have the same view, and when $v_L^3$ and $v_L^6$ have the same view in the visibility range $h$, then $ℱ𝒩$${}_L{}^h=\{\{v_L^1,v_L^2,v_L^5\}$, $\{v_L^3,v_L^6\}$, $\{v_L^4\}\}$ holds. Moreover, we say that the configuration is view-symmetric within visibility range $h$ if there is a bijection function $f:V_L\to V_R$ such that, for any $v_L^i\in V_L$, $f(v_L^i)=v_R^i\in V_R$ has the same view in visibility range within $h$.

Then, we have the following lemma.

In this section, we propose a deterministic algorithm for robots with visibility range $\mathrm{\Theta }(\log n)$ such that (i) detects that uniform deployment is impossible when the given initial configuration is in $\overline{S_{\mathrm{\infty }}}$ and hence an unsolvable (i.e., view-symmetric in an infinite visibility range) one, and (ii) achieves uniform deployment in $O(1)$ rounds whenever the given initial configuration is not view-symmetric in an infinite visibility range (this algorithm works correctly even in the ASYNC model). By these results, we can characterize that $S_{\mathrm{\infty }}$ (resp., $\overline{S_{\mathrm{\infty }}}$) is the set comprising all initial configurations each of which is view-symmetric (resp., not view-symmetric) in an infinite visibility range. When the configuration is view-symmetric in an infinite visibility range, by Theorem 7, robots with visibility range $\mathrm{\Theta }(\log n)$ can detect the fact. Hence, in this case, robots recognize that the problem cannot be solved from the given initial configuration and terminate the algorithm execution. In the following, we explain how robots behave to solve the problem from solvable (or non-view-symmetrc in in an infinite visibility range) configurations¹¹1When robots can detect that the given initial configuration is not view-symmetric in some visibility range $o(\log n)$, actually visibility range $o(\log n)$ (e.g., some constant) is sufficient. However, to detect the (un)solvability of any given initial configuration, at this stage we assume the visibility range $\mathrm{\Theta }(\log n)$..

Let $n_L$ (resp., $n_R$) be the number of robots existing in $V_L$ (resp., $V_R$) in the initial configuration $C_0$. Notice that no robot exists on an edge in $C_0$. Then, the basic idea is, based on $n_L$, $n_R$, and views, to determine which robots in $V_L$ or $V_R$ should move. We assume that two or more views can be compared and determined which one is smaller (or the smallest) one in some way. We consider the cases that (a) $n_L\ne n_R$, and (b) $n_L=n_R$ in this order. Notice that, in the ASYNC model, robots may be on edges when observed by some robots. We also treat this asynchronicity in cases (a) and (b).

In the case of (a) $n_L\ne n_R$, we first consider the case where no robot exists on an edge and then consider the case where some robot exists on edges. When no robot exists on an edge, robots in the node set with fewer robots move to an empty node in another node set with more robots. Without loss of generality, we assume that holds. In this case, robots at nodes in $V_R$ need not move anymore and hence terminate the algorithm execution. On the other hand, each robot in $V_L$ tries to move to an empty node in $V_R$, with avoiding a collision. Here, a collision means that several robots stay at the same node. When a collision occurs, from then the two or more robots at the same node behave in exactly the same way since they have the same view. Hence, they will never stay at different nodes, which means that uniform deployment cannot be achieved. Thus, to achieve uniform deployment without a collision, robots with smaller views preferentially determine their destinations and move there. Recall that since robots in this section have visibility range $\mathrm{\Theta }(\log n)$, each robot can get views within visibility range $\mathrm{\Theta }(\log n)$ for each of the other nodes, compare them, and also calculate candidate destination nodes for each robot using the views. Let $V_{\mathrm{𝑒𝑚𝑝}}$ be the set of empty nodes in the other side ($V_R$ in this case) and we assume that $n_L$ robots $r_L^1,r_L^2,\mathrm{\dots },r_L^{nL}$ in $V_L$ are arranged in the non-decreasing order in terms of their views. Then, $r_L^i$ chooses its destination node with avoiding a collision, by calculating destinations of $r_L^1,r_L^2,\mathrm{\dots }{r}_L^{i-1}$ beforehand. Concretely, $r_L^i$ first virtually calculates $r_L^1$’s destination node $v_d^1$ as the empty node led by the lexicographically minimum port pair $(p_L^{{\mathrm{𝑚𝑖𝑛}}_1},p_R^{{\mathrm{𝑚𝑖𝑛}}_1}$) among pairs connecting to $r_L^1$’s currently staying node to an empty node. Then, $r_i$ updates the candidate destination nodes (i.e., $V_{\mathrm{𝑒𝑚𝑝}}$) to $V_{\mathrm{𝑒𝑚𝑝}}\backslash \{v_d^1\}$. Next, $r_i$ similarly calculates $r_L^2$’s destination node $v_d^2$ but among the candidate nodes $V_{\mathrm{𝑒𝑚𝑝}}\backslash \{v_d^1\}$. Likewise, $r_i$ calculates destination nodes $v_d^1,v_d^2,\mathrm{\dots },v_d^{i-1}$ of robots $r_L^1,r_L^2,\mathrm{\dots }{r}_L^{i-1}$ one by one, and then calculates its destination node $v_d^i$ among the candidate empty nodes $V_{\mathrm{𝑒𝑚𝑝}}\backslash \{v_d^1,v_d^2,\mathrm{\dots },v_d^{i-1}\}$ and moves there. When reaching $v_d^i$, $r_i$ terminates the algorithm execution. By this behavior, since each robot $r_L^i$’s destination node $v_d^i$ is not chosen by any other robot $r_L^{i^{\prime }}(1\le i^{\prime }\le i-1)$ with a smaller view than that of $r_L^i$, or $r_L^{i^{\prime \prime }}(i+1\le i^{\prime \prime }\le n_L)$ with a larger view, $r_i$ can stay at $v_d^i$ without a collision. Notice that there may exist several robots $r_L^{\mathrm{\ell }}$ and $r_L^{{\mathrm{\ell }}^{\prime }}$ with the same view in $V_L$. In this case, each of them recognizes that it has a smaller view than the other. Then, $r_L^{\mathrm{\ell }}$ and $r_L^{{\mathrm{\ell }}^{\prime }}$ use the same port pair $(p_L^{{\mathrm{𝑚𝑖𝑛}}_{\mathrm{\ell }}},p_R^{{\mathrm{𝑚𝑖𝑛}}_{\mathrm{\ell }}}$) (=$(p_L^{{\mathrm{𝑚𝑖𝑛}}_{{\mathrm{\ell }}^{\prime }}},p_R^{{\mathrm{𝑚𝑖𝑛}}_{{\mathrm{\ell }}^{\prime }}}$)), which means that they choose different destination nodes because of $p_R^{{\mathrm{𝑚𝑖𝑛}}_{\mathrm{\ell }}}=p_R^{{\mathrm{𝑚𝑖𝑛}}_{{\mathrm{\ell }}^{\prime }}}$. The case where more than two robots have the same view can be treated similarly.

However, we need to consider the case where robots are on edges because of the ASYNC model. In this case, since robot $r_m$ during the movement determined to move due to (i.e., the number of robots at its side is smaller than that of the other side), robots at nodes determine whether they should move or stay using the above facts. That is, when some robot $r_m$ is on an edge, each robot $r_i$ staying at a node in $V_L$ calculates the number $n_L^{\prime }$ (resp., $n_R^{\prime }$) of robots at nodes in $V_L$ (resp., $V_R$), ignoring the existence of $r_m$. Then, obviously holds by the moving tactics of robots. In this case, $r_i$ can recognize which node in $V_L$ the robot $r_m$ previously stayed at, calculate $r_m$’s view (and how small it is among robots in $V_L$), and the port pair it selected. Thus, since $r_i$ can recognize $r_m$’s destination node $v_d^m$, $r_i$ chooses its destination with avoiding $v_d^m$. If robot $r_i$ stays at a node in $V_R$, it terminates the algorithm execution since it initially stays at a node in a node set with more robots. The case where several robots are during the movements are treated similarly.

For example, in Fig. 7, we assume that seven robots exist in a complete bipartite graph $K_{7,7}$, three robots exist in $V_L$, and four robots exist in $V_R$. However, we only show three robots in $V_L$ and three empty nodes in $V_R$ for simplicity. In addition, we assume that $r_i$ (resp., $r_h$ and $r_j$) has the smallest (resp., have the second smallest and the third smallest) view among the three robots. Then, in Fig. 7 (a), robots $r_h$ and $r_i$ are led to the same empty node by their minimum port pairs (2,4) and (1,2), respectively. In this case, since $r_i$ has the smallest view, it moves to and stays at $v_d^i$ (Fig. 7 (b)). Then, $r_h$ and $r_j$ recognize that $r_i$ is during the movement and it previously stayed at a node in their side. Hence, $r_h$ and $r_k$ respectively determine their destinations $v_d^h$ and $v_d^j$ among empty nodes other than $v_d^i$, and move there (Fig. 7 (c)). After the movement, robots achieve uniform deployment.

Next, in the case of (b) $n_L=n_R$, robots compare views of $V_L$ and those of $V_R$, and determine whether robots in $V_L$ or $V_R$ should move. Concretely, robots arrange views ${\text{views}}_L$ of $V_L$ in ascending order and similarly arrange views ${\text{views}}_R$ of $V_R$. Notice that views of nodes without a robot are also included in ${\text{views}}_L$ and ${\text{views}}_R$. Then, ${\text{views}}_L\ne {\text{views}}_R$ holds since the configuration is not view-symmetric in an infinite visibility range. Since robots with visibility range $\mathrm{\Theta }(\log n)$ in this section can detect the fact by Theorem 7, using the information, robots in the node set with smaller views can determine to move and select their destination nodes by the method explained in the case (a) $n_L\ne n_R$. Therefore, they can achieve uniform deployment by repeating the behaviors for the case (a).

The pseudocode is described in Algorithm 1. Concerning the algorithm, we have the following theorem.