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 ( < k ), that agents terminate in a configuration such that either at least g agents or no agent exists at each node. When k ≥ 2 g , the requirement for the partial gathering problem is strictly weaker than that for the total gathering problem, and thus it is interesting to clarify the difference in the move complexity between them. So far, the partial gathering problem has been considered in static graphs. In this paper, we start considering partial gathering in dynamic graphs. As a first step, we consider this problem in 1-interval connected rings, that is, one of the links in a ring may be missing at each time step. In such networks, focusing on the relationship between the values of k and g , we fully characterize the solvability of the partial gathering problem and analyze the move complexity of the proposed algorithms when the problem can be solved. First, we show that the g -partial gathering problem is unsolvable when k ≤ 2 g . Second, we show that the problem can be solved with O ( n log g ) time and the total number of O ( gn log g ) moves when 2 g + 1 ≤ k ≤ 3 g − 2 . Third, we show that the problem can be solved with O ( n ) time and the total number of O ( kn ) moves when 3 g − 1 ≤ k ≤ 8 g − 4 . Notice that since k = O ( g ) holds when 3 g − 1 ≤ k ≤ 8 g − 4 , the move complexity O ( kn ) in this case can be represented also as O ( gn ). Finally, we show that the problem can be solved with O ( n ) time and the total number of O ( gn ) moves when k ≥ 8 g − 3 . These results mean that the partial gathering problem can be solved also in dynamic rings when k ≥ 2 g + 1 . In addition, agents require a total number of Ω( gn ) (resp., Ω( kn )) moves to solve the partial (resp., total) gathering problem. Thus, when k ≥ 3 g − 1 , agents can solve the partial gathering problem with the asymptotically optimal total number of O ( gn ) moves, which is strictly smaller than that for the total gathering problem.

In this paper, we address the problem of uniformly deploying 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, the uniform deployment problem requires the robots to achieve one of the following configurations: (a) each node in V_L is occupied by exactly one robot, with no robots in V_R, or (b) each node in V_R is occupied by exactly one robot, with no robots in V_L. In either configuration, the distance between any two robots is 2, ensuring that the robots are uniformly deployed. In this paper, we explore the relationship between the visibility range of robots and the solvability of the uniform deployment problem. First, we characterize solvable and unsolvable initial configurations under the assumption that robots have an infinite visibility range. 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 Θ(log n) is sufficient by presenting an algorithm that solves the uniform deployment problem in O(1) rounds, starting from any solvable initial configuration. Finally, we briefly introduce an example showing that robots with a constant visibility range (which is 3 in this example) cannot solve the problem in a native way.

Abstract In this paper, we consider the partial gathering problem of mobile agents in dynamic tori. This problem requires $k$ agents distributed in the network to reach a configuration such that either at least $g$ agents or no agent exists at each node. Thus far, in dynamic graphs, partial gathering is considered in 1-interval connected rings, where one of the links in the ring may be missing at each time step. In this paper, we consider another dynamic topology. Concretely, we consider partial gathering in $n\times n$ dynamic tori such that each of the row and column rings is represented as a 1-interval connected ring. In such networks, when $k = O(gn)$, focusing on the relationship between the values of $k, n$, and $g$, we characterize the solvability of the problem and analyze the move complexity. First, we show that agents cannot solve the problem when $k = o(gn)$. Second, we show that agents can achieve partial gathering with a total number of $O(gn^{3})$ moves when $2gn+2n-1\le k \le 2gn + 6n +16g -12$. Finally, we show that agents can achieve partial gathering with a total number of $\Theta (gn^{2})$ moves when $k\ge 2gn + 6n +16g -11$.

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 Fault‐tolerance and self‐organization are critical properties in modern distributed systems. Self‐stabilization is a class of fault‐tolerant distributed algorithms which has the ability to recover from any kind and any finite number of transient faults and topology changes. In this article, we propose a self‐stabilizing distributed algorithm for the 1‐MIS problem under the unfair central daemon assuming the distance‐3 model. Here, in the distance‐3 model, each process can refer to the values of local variables of processes within three hops. Intuitively speaking, the 1‐MIS problem is a variant of the maximal independent set (MIS) problem with improved local optimizations. The time complexity (convergence time) of our algorithm is steps and the space complexity is bits, where is the number of processes. Finally, we extend the notion of 1‐MIS to ‐MIS for each nonnegative integer , and compare the set sizes of ‐MIS () and the maximum independent set.

Summary In this paper, we consider the problem of semi‐uniform deployment for mobile robots in perfect ‐ary trees. This problem requires robots to spread in the tree so that, for some positive integer and some fixed integer , each node of depth is occupied by a robot. Robots have an infinite visibility range but are opaque, and each robot can emit a light color visible to itself and other robots, taken from a set of colors, at each time step. Then, we clarify the solvability of the semi‐uniform deployment problem, focusing on the number of available light colors. First, we consider robots with . In this setting, we show that there is no collision‐free algorithm to solve the problem. Next, relax the number of available light colors, that is, we consider robots with . In this setting, we propose a collision‐free algorithm that can solve the problem. From these results, we can show that the semi‐uniform deployment problem can be solved when , and our proposed algorithm is optimal with respect to the number of used light colors (i.e., 2).

An autonomous mobile robot system consisting of many mobile computational entities (called robots) attracts much attention of researchers, and to clarify the relation between the capabilities of robots and solvability of the problems is an emerging issue for a recent couple of decades. Generally, each robot can observe all other robots as long as there are no restrictions for visibility range or obstructions, regardless of the number of robots. In this paper, we provide a new perspective on the observation by robots; a robot cannot necessarily observe all other robots regardless of distances to them. We call this new computational model defected view model. Under this model, in this paper, we consider the gathering problem that requires all the robots to gather at the same point and propose two algorithms to solve the gathering problem in the adversarial ($N$,$N-2$)-defected model for $N \geq 5$ (where each robot observes at most $N-2$ robots chosen adversarially) and the distance-based (4,2)-defected model (where each robot observes at most 2 closest robots to itself) respectively, where $N$ is the number of robots. Moreover, we present an impossibility result showing that there is no (deterministic) gathering algorithm in the adversarial or distance-based (3,1)-defected model. Moreover, we show an impossibility result for the gathering in a relaxed ($N$, $N-2$)-defected model.

In this paper, we consider the almost uniform deployment problem of mobile agents in dynamic rings, which requires all agents other than one agent to spread uniformly in the ring. In this paper, we consider this problem in 1-interval connected rings, that is, one of the links may be missing at each time step. Focusing on global knowledge given to agents, we clarify the problem solvability and the algorithm performance. First, we consider agents with knowledge of the number n of nodes. Then, we show that the problem can be solved with O(klog⁡n) memory space per agent, O(nlog⁡k) rounds, and a total number of O(kn) moves, where k is the number of agents. Next, we consider agents with knowledge of k. Then, we show that the problem can be solved with O(klog⁡n) memory space per agent, O(n2) rounds, and a total number of O(n2) moves.

In the population protocol model, many problems cannot be solved in a self-stabilizing manner. However, global knowledge, such as the number of nodes in a network, sometimes enables the design of a self-stabilizing protocol for such problems. For example, it is known that we can solve the self-stabilizing leader election in complete graphs if and only if every node knows the exact number of nodes. In this article, we investigate the effect of global knowledge on the possibility of self-stabilizing population protocols in arbitrary graphs. Specifically, we clarify the solvability of the leader election problem, the ranking problem, the degree recognition problem, and the neighbor recognition problem by self-stabilizing population protocols with knowledge of the number of nodes and/or the number of edges in a network.

We propose a self-stabilizing algorithm to construct a minimal weakly ST-reachable directed acyclic graph (DAG), which is suited for routing messages on wireless networks. Given an arbitrary, simple, connected, and undirected graph G = (V, E) and two sets of nodes, senders S(⊂ V) and targets T(⊂ V), a directed subgraph G⃗ of G is a weakly ST-reachable DAG on G, if G⃗ is a DAG and every sender can reach at least one target, and every target is reachable from at least one sender in G⃗. We say that a weakly ST-reachable DAG G⃗ on G is minimal if any proper subgraph of G⃗ is no longer a weakly ST-reachable DAG. This DAG is a relaxed version of the original (or strongly) ST-reachable DAG, where every target is reachable from every sender. This is because a strongly STreachable DAG G does not always exist; some graph has no strongly ST-reachable DAG even in the case |S| = |T | = 2. On the other hand, the proposed algorithm always constructs a weakly ST-reachable DAG for any |S| and |T |. Furthermore, the proposed algorithm is self-stabilizing; even if the constructed DAG deviates from the reachability requirement by a breakdown or exhausting the battery of a node having an arc in the DAG, this algorithm automatically reconstructs the DAG to satisfy the requirement again. The convergence time of the algorithm is O(D) asynchronous rounds, where D is the diameter of a given graph. We conduct small simulations to evaluate the performance of the proposed algorithm. The simulation result indicates that its execution time decreases when the number of sender nodes or target nodes is large.

In this paper, we introduce a new graph structure named an ST-reachable directed acyclic graph which is a directed acyclic graph (DAG) that guarantees reachability from every sender to every target (i.e., a directed path exists). When an arbitrary connected undirected graph G=(V,E) and two sets of the vertices, senders S (⊂ V) and targets T (⊂ V), are given, we consider construction of a minimal ST-reachable DAG by changing some undirected edges to arcs and removing the remaining edges. This implies that every node in T is reachable from every node in S on the constructed ST-reachable DAG. In particular, our goals are (1) to find the necessary and sufficient condition that an ST-reachable DAG can be constructed, and (2) to design a self-stabilizing algorithm for constructing a minimal ST-reachable DAG (if exists). In this paper, we present the necessary and sufficient condition that a minimal ST-reachable DAG can be constructed when S ≤ 2 and |T| ≤ 2, and propose a self-stabilizing algorithm to construct an ST-reachable DAG (if exists) when an arbitrary connected undirected graph, S (|S| ≤ 2) and T (|T| ≤ 2) are given. Moreover, our proposed algorithm can detect the non-existence of ST-reachable DAG if there exists no ST-reachable DAG of the given graph and two sets of vertices, S and T.

In this paper, we consider the uniform deployment problem of mobile agents in asynchronous unidirectional rings, which requires the agents to uniformly spread in the ring. The uniform deployment problem is in striking contrast to the rendezvous problem which requires the agents to meet at the same node. While rendezvous aims to break the symmetry, uniform deployment aims to attain the symmetry. It is well known that the symmetry breaking is difficult in distributed systems and the rendezvous problem cannot be solved from some initial configurations . Hence, we are interested in clarifying what difference the uniform deployment problem has on the solvability and the number of agent moves compared to the rendezvous problem. We consider two problem settings, with knowledge of k (or n ) and without knowledge of k or n where k is the number of agents and n is the number of nodes. First, we consider agents with knowledge of k (or n since k and n can be easily obtained if one of them is given). In this case, we propose two algorithms. The first algorithm solves the uniform deployment problem with termination detection. This algorithm requires O ( k log n ) memory space per agent, O ( n ) time, and O ( k n ) total moves. The second algorithm also solves the uniform deployment problem with termination detection. This algorithm reduces the memory space per agent to O ( log n ) , but uses O ( n log k ) time, and requires O ( k n ) total moves. Both algorithms are asymptotically optimal in terms of total moves since there are some initial configurations such that agents require Ω ( k n ) total moves to solve the problem. Next, we consider agents with no knowledge of k or n . In this case, we show that, when termination detection is required, there exists no algorithm to solve the uniform deployment problem. For this reason, we consider the relaxed uniform deployment problem that does not require termination detection, and we propose an algorithm to solve the relaxed uniform deployment problem. This algorithm requires O ( ( k ∕ l ) log ( n ∕ l ) ) memory space per agent, O ( n ∕ l ) time, and O ( k n ∕ l ) total moves when the initial configuration has symmetry degree l . This means that the algorithm can solve the problem more efficiently when the initial configuration has higher symmetric degree (i.e., is closer to uniform deployment). Note that all the proposed algorithms achieve uniform deployment from any initial configuration, which is a striking difference from the rendezvous problem because the rendezvous problem is not solvable from some initial configurations .

In this paper, we consider the partial gathering problem of mobile agents in asynchronous tree networks. The partial gathering problem is a generalization of the classical gathering problem, which requires that all the agents meet at the same node. The partial gathering problem requires, for a given positive integer g, that each agent should move to a node and terminate so that at least g agents should meet at each of the nodes they terminate at. The requirement for the partial gathering problem is weaker than that for the (well-investigated) classical gathering problem, and thus, we clarify the difference on the move complexity between them. We consider two multiplicity detection models: weak multiplicity detection and strong multiplicity detection models. In the weak multiplicity detection model, each agent can detect whether another agent exists at the current node or not but cannot count the exact number of the agents. In the strong multiplicity detection model, each agent can count the number of agents at the current node. In addition, we consider two token models: non-token model and removable token model. In the non-token model, agents cannot mark the nodes or the edges in any way. In the removable-token model, each agent initially leaves a token on its initial node, and agents can remove the tokens. Our contribution is as follows. First, we show that for the non-token model agents require Ω(kn) total moves to solve the partial gathering problem, where n is the number of nodes and k is the number of agents. Second, we consider the weak multiplicity detection and non-token model. In this model, for asymmetric trees, by a previous result agents can achieve the partial gathering in O(kn) total moves, which is asymptotically optimal in terms of total moves. In addition, for symmetric trees we show that there exist no algorithms to solve the partial gathering problem. Third, we consider the strong multiplicity detection and non-token model. In this model, for any trees we propose an algorithm to achieve the partial gathering in O(kn) total moves, which is asymptotically optimal in terms of total moves. At last, we consider the weak multiplicity detection and removable-token model. In this model, we propose an algorithm to achieve the partial gathering in O(gn) total moves. Note that in this model, agents require Ω(gn) total moves to solve the partial gathering problem. Hence, the second proposed algorithm is also asymptotically optimal in terms of total moves.

In this paper, we consider the uniform deployment problem of mobile agents in asynchronous unidirectional rings, which requires the agents to uniformly spread in the ring. The uniform deployment problem is striking contrast to the rendezvous problem which requires the agents to meet at the same node. While the rendezvous aims to break the symmetry, the uniform deployment aims to attain the symmetry. Hence, we are interested in clarifying how easily the uniform deployment problem can be solved compared to the rendezvous problem. We consider two problem settings. First, we consider agents with knowledge of k, where k is the number of agents. In this case, our proposed algorithm solves the uniform deployment problem with termination detection. This algorithm requires O(log n) memory per agent, O(n log k) time, and O(kn) total moves, where n is the number of nodes. Next, we consider agents with no knowledge of k or n. In this case, we show that, when termination detection is required, there exists no algorithm to solve the uniform deployment problem. For this reason, we consider the relaxed uniform deployment problem that does not require termination detection, and we propose an algorithm to solve the relaxed uniform deployment problem. This algorithm requires O(k/l log (n/l)) memory per agent, O(n/l) time, and O(kn/l) total moves, where l is the symmetry degree of the initial configuration (l ≥ 1). Note that both the algorithms achieve the uniform deployment from any initial configuration, which is a striking difference from the rendezvous problem because the rendezvous problem is not solvable from some initial configurations.

In this paper, we consider the partial gathering problem of mobile agents in asynchronous unidirectional rings equipped with whiteboards on nodes. The partial gathering problem is a new generalization of the total gathering problem. The partial gathering problem requires, for a given integer g, that each agent should move to a node and terminate so that at least g agents should meet at the same node. The requirement for the partial gathering problem is weaker than that for the (well-investigated) total gathering problem, and thus, we have interests in clarifying the difference on the move complexity between them. We propose three algorithms to solve the partial gathering problem. The first algorithm is deterministic but requires unique ID of each agent. This algorithm achieves the partial gathering in O(gn) total moves, where n is the number of nodes. The second algorithm is randomized and requires no unique ID of each agent (i.e., anonymous). This algorithm achieves the partial gathering in expected O(gn) total moves. The third algorithm is deterministic and requires no unique ID of each agent. For this case, we show that there exist initial configurations in which no algorithm can solve the problem and agents can achieve the partial gathering in O(kn) total moves for solvable initial configurations, where k is the number of agents. Note that the total gathering problem requires Ω(kn) total moves, while the partial gathering problem requires Ω(gn) total moves in each model. Hence, we show that the move complexity of the first and second algorithms is asymptotically optimal.

This paper investigates modeling and control of a limit cycle walker that walks sliding on the ice. We introduce the model of an underactuated spoked walker for analysis and analyze the collision model on the assumption of sliding contact with the ground to identify the condition for achieving instantaneous exchange of the stance leg. We also develop the equation of motion incorporating dynamic friction in sliding contact. Numerical simulations show that the walker can generate stable walking gaits by applying a simple control of the torso.

On-demand services for TV program, which provide users with past programs on demand, are becoming popular. It is therefore necessary to find a means of efficiently searching for programs that users want to view, from huge program archives. This paper proposes an automatic method of retrieving programs related to the one being viewed by the user. To that end, we compute similarity between program summaries and closed captions obtained from broadcasting by weighting significant words such as compound words and named entities. Additionally our method provides inter-program relationship labels to indicate why the results of relevant programs were chosen. The results of an evaluation showed that the method recommended relevant programs with higher accuracy than baseline methods and indicated appropriate relationship labels for related programs.

Pose-invariant face recognition systems for multimedia indexing require the prior registration of face images at multiple poses in a database, but it can be problematic and laborious to obtain and register appropriate imagery. We aim to automate the process by constructing 3D face models from the imagery available for registration, and then using the constructed models to generate templates for the face recognition system. The first step in the model construction process is the estimation of the generalized pose (scale, position, 3D orientation relative to the camera) of the face in each frame of the registration imagery, and the 3D positions of a number of feature points on the face. This is followed by warping the 3D model to fit the estimated 3D feature points, and mapping facial texture from the registration imagery onto the model. In this paper we outline (i) an algorithm for estimating the generalized pose and shape (3D feature point locations) from 2D feature point tracking data, and (ii) a texture mapping algorithm that combines texture regions from all of the available imagery. We show experimental results and discuss issues that remain in applying the method in practice as part of a multimedia indexing system.

In this paper, we describe the latest specifications of the Metadata Production Framework (MPF) and its reference software with which the basic functionality of MPF can be tested over networks. MPF was originally designed as an efficient environment for generating metadata for TV programs from the viewpoint of the broadcaster, but recent developments indicate that the domains where MPF can be applied have expanded to include even ordinary households. This trend suggests that the metadata market might be much bigger in the near future, and we believe MPF can become an infrastructure standard in these circumstances.

To examine the large drop of partial oxygen pressure (PO2) in arterioles, the O2consumption rates of arteriolar walls were determined under physiological conditions. A phosphorescence quenching technique was used to quantify the intra- and perivascular PO2values in rat cremaster arterioles. Using the measured PO2values, and a theoretical model, the O2consumption rates of the arteriolar walls were then estimated. We found that the O2consumption rate of arterioles was 100 times greater than that seen in in vitro experiments, and the O2consumption rate under normal conditions was significantly higher than that during vasodilation. Furthermore, the O2consumption rate was the highest in the upstream arterioles. These findings suggest that the high O2consumption rates of arteriolar walls depend on the workload of the smooth muscle.

Here, we propose a technique to acquire knowledge for baseball digest video production using an inductive inference approach. We integrated the concept of inductive logic programming (ILP) and baseball game metadata to enable learning of the highlight scene definition from digest video produced by a TV director.ILP is a learning method formed at the intersection of machine learning and logic programming, and ILP processor can acquire the highlight scene definition by inductive learning from scenes that are selected as highlights in sports news. This technique makes it possible to generate a semantic digest automatically, which includes not only score scenes but also attractive scenes reflecting the director's intention.

This paper describes a method to generate metadata for TV programs in real-time by utilizing acoustic and speech data in live broadcasting. Various styles of watching TV programs can be provided by using metadata related to the content of the program. The acoustic data to be processed in our case is crowd noise in a football (soccer) stadium, and the speech data is an announcer's voice. The crowd noise is closely related to not only spectator emotions but also their attention and expectations. In other words, a part in which the crowd noise rises corresponds to an important event in the game. Because the crowd noise conveys no further information about what happened in the scene, the announcer's voice, after speech-to-text conversion, is processed to extract further meaning. By combining these two processes of identifying and extracting, content-based segment metadata is generated automatically. This method was applied to generating metadata for six professional football games, by which its effectiveness was verified.