We introduce, as an enhancement of self-stabilization, the concept of monotonic self-stabilization for distributed systems that ensures that a certain measure of quality of state monotonically improves when the system in an illegitimate state progresses toward a legitimate state. In the concept, the quality is measured by a real-valued function that can be chosen from a certain class of functions. The concept is applied to a multi-robot pattern formation problem in which a group of autonomous mobile robots move from their respective initial positions to the goal positions like a marching band. We solve the problem by presenting two monotonic self-stabilizing pattern formation algorithms, one of which is for FSYNC model and the other is for SSYNC model. The considered real-valued functions to measure the quality take into account both the distance to the goal location and the accuracy of the formation. We present a formal proof of the algorithms' correctness and monotonic self-stability.

We revisit the problem of pursuit-evasion in a grid introduced by Sugihara and Suzuki [SIAM J. Discrete Math., 2 (1989), pp. 126–143] in the line-of-sight vision model. Consider an arbitrary evader Z with the maximum speed of 1 who moves (in a continuous way) on the streets and avenues of an $n\times n$ grid $G_n$. The cunning evader is to be captured by a group of pursuers, possibly only one. The maximum speed of the pursuers is $s\geq1$; s is a constant for each pursuit-evasion problem considered, but several values for s are studied. We prove several new results (no such algorithms were available for capture using one, two, or three pursuers having a constant maximum speed limit): (i) A randomized algorithm through which one pursuer A with a maximum speed of $s\geq3$ can capture an arbitrary evader Z in $G_n$ in expected polynomial time. For instance, the expected capture time is $O(n^{1+\log_{6/5}16})=O(n^{16.21})$ for $s=3$, $O(n^{1+\log12})=O(n^{4.59})$ for $s=4$, $O(n^{1+\log60/13})=O(n^{3.21})$ for $s=6$, and it approaches $O(n^3)$ with the further increase of s. (ii) A randomized algorithm for capturing an arbitrary evader in $O(n^3)$ expected time using two pursuers who can move slightly faster than the evader ($s=1+\varepsilon$ for any $\varepsilon>0$). (iii) Randomized algorithms for capturing a certain “passive” evader using either a single pursuer who can move slightly faster than the evader ($s=1+\varepsilon$ for any $\varepsilon>0$) or two pursuers having the same maximum speed as the evader ($s=1$). (iv) A deterministic algorithm for capturing an arbitrary evader in $O(n^2)$ time, using three pursuers having the same maximum speed as the evader ($s=1$).

Consider the following survival problem:Given a set of k trajectories (paths) with maximum unit speed in a boundedregion over a (long) time interval [0,T], find another trajectory (if itexists) subject to the same maximum unit speed limit, that avoids (that is, stays at a safe distance of)each of the other trajectories over the entire time interval. We call this variant the continuous model of the survival problem. The discrete model of this problem is: Given the trajectories (paths) of k point robots in a graph over a (long)time interval 0,1,2,...,T, find a trajectory (path) for anotherrobot, that avoids each of the other k at any time instance in thegiven time interval. We introduce the notions of survival number of a region,and that of a graph, respectively, as the maximum number oftrajectories which can be avoided in the region (resp. graph). We give the first estimates on the survival number of the n x n grid Gn, and also devise an efficient algorithm for the corresponding safepath planning problem in arbitrary graphs. We then show that our estimates on the survival number of Gn%on the number of paths that can be avoided in Gn can be extended for the survival number of a bounded (square) region.In the final part of our paper, we consider other related offlinequestions, such as the maximum number of men problem and the spy problem.

In this note we make a minor correction to a scheme for robots to broadcast their private information. All major results of the paper [I. Suzuki and M. Yamashita, SIAM J. Comput., 28 (1999), pp. 1347-1363] hold with this correction.

Polygon search is the problem of finding mobile intruders who move unpredictably in a polygonal region. In this paper, we consider a special case of this problem, called boundary search, where the searcher is allowed to move only along the boundary of the polygon. We concentrate on a single searcher with one flashlight (called a 1-searcher), but it is known that a single boundary 1-searcher has the same searching power as a single boundary searcher with 360/spl deg/ vision. Our main result is that the movement of the searcher can be controlled by a finite-state machine having only seven states. This automaton has no built-in information about the input polygon and, for any given polygon P, if P can be searched by a boundary searcher at all, then this automaton will successfully search P, no matter where on the boundary of P it is initially placed. All information about P is acquired by the automaton online, as it searches P. We also show that if P can be searched by a boundary searcher, then our automaton searches it by circling its boundary less than three times.

In this paper, we address a number of issues related to motion planning and analysis of rectangular metamorphic robotic systems. We first present a distributed algorithm for reconfiguration that applies to a relatively large subclass of configurations, called horizontally convex configurations. We then discuss several fundamental questions in the analysis of metamorphic systems. In particular, the following two questions are shown to be decidable: 1) whether a given set of motion rules maintains connectivity; 2) whether a goal configuration is reachable from a given initial configuration (at specified locations). In the general case in which each module has an internal state, the following is shown to be undecidable: given a set of motion rules, whether there exists a certain type of configuration called a uniform straight-chain configuration that yields a disconnected configuration.

We examine the problem of dynamic self-reconfiguration of a modular robotic system (frequently referred to as self-reconfigurable or metamorphic system), to a formation aimed at reaching a specified target position with one of the modules as quickly as possible. We present a number of high speed formations for both rectangular and hexagonal systems, and prove upper and lower bounds on the speed of locomotion. In particular, the formations presented achieve constant ratio guarantee on the time to reach a given target in the asymptotic sense.

We consider the problem of transporting a long object, such as a ladder, through a 90 degree corner in a corridor using two omnidirectional robots that do not necessarily have identical characteristics. A distributed algorithm is presented in which each robot computes its own motion based on the current and goal positions of the ladder, the locations of the walls, and the motion of the other robot observed indirectly through the link between the robot and the ladder. We evaluate the performance and robustness of the algorithm using extensive computer simulation by changing several parameter values that affect the key characteristics of the robots, including the maximum speed, the guide path through a corner, and the sensitivity and reaction to the motion of the other robot. The simulation results indicate that if the parameter values are chosen within certain reasonable ranges, then overall the algorithm works quite well even for robots having difficult characteristics. It is also shown that the robustness of the algorithm critically depends on the differences between the robots in the values of two parameters.

Consider a system of multiple mobile robots in which each robot, at infinitely many unpredictable time instants, observes the positions of all the robots and moves to a new position determined by the given algorithm. The robots are anonymous in the sense that they all execute the same algorithm and they cannot be distinguished by their appearances. Initially they do not have a common x-y coordinate system. Such a system can be viewed as a distributed system of anonymous mobile processes in which the processes (i.e., robots) can "communicate" with each other only by means of their moves. In this paper we investigate a number of formation problems of geometric patterns in the plane by the robots. Specifically, we present algorithms for converging the robots to a single point and moving the robots to a single point in finite steps. We also characterize the class of geometric patterns that the robots can form in terms of their initial configuration. Some impossibility results are also presented.

We present a distributed algorithm for converging autonomous mobile robots with limited visibility toward a single point. Each robot is an omnidirectional mobile processor that repeatedly: 1) observes the relative positions of those robots that are visible; 2) computes its new position based on the observation using the given algorithm; 3) moves to that position. The robots' visibility is limited so that two robots can see each other if and only if they are within distance V of each other and there are no other robots between them. Our algorithm is memoryless in the sense that the next position of a robot is determined entirely from the positions of the robots that it can see at that moment. The correctness of the algorithm is proved formally under an abstract model of the robot system in which: 1) each robot is represented by a point that does not obstruct the view of other robots; 2) the robots' motion is instantaneous; 3) there are no sensor and control error; 4) the issue of collision is ignored. The results of computer simulation under a more realistic model give convincing indication that the algorithm, if implemented on physical robots, will be robust against sensor and control error.

Using a model based on the omni-directional robots developed at the Institute of Physical and Chemical Research (RIKEN), we discuss the possibility of automatically generating a collision avoidance algorithm for autonomous mobile robots. To this end, we show that an effective collision avoidance algorithm for two robots can be generated by a very simple learning algorithm that simulates a naive human trial-and-error learning process, using only the robots' sensor outputs and a suitable reward function, where the exact form of the reward function is also learned autonomously by the robots. We also discuss how a robot can use its "experience" gained in a simple environment to adjust itself to a more complex environment, by automatically generating a collision avoidance algorithm for a three-robot situation utilizing a reduced state space resulting from the learning process for the case of two robots. The results of computer simulation and the experiments conducted at RIKEN using physical robots demonstrate the effectiveness of the collision avoidance algorithms generated and our learning-based approach.

We consider the problem of computing a time-optimal motion for two omnidirectional robots carrying a ladder from an initial position to a final position in a plane without obstacles. At any moment during the motion, the distance between the robots remains unchanged and the speed of each robot must be either a given constant /spl upsi/, or O. A trivial lower bound on time for the robots to complete the motion is the time needed for the robot farther away from its destination to move to the destination along a straight line at a constant speed of /spl upsi/. This lower bound may or may not be achievable, however, since the other robot may not have sufficient time to complete the necessary rotation around the first robot (that is moving along a straight line at speed v) within the given time. We first derive, by solving an ordinary differential equation, a necessary and sufficient condition under which this lower bound is achievable. If the condition is satisfied, then a time-optimal motion of the robots is computed by solving another differential equation numerically. Next, we consider the case when this condition is not satisfied, and show that a time-optimal motion can be computed by taking the length of the trajectory of one of the robots as a functional and then applying the method of variational calculus. Several optimal paths that have been computed using the above methods are presented.

A group of autonomous agents can agree on a set of "social laws" in advance in order to reduce the complexity of conflict resolution later in the field when they are dispatched to achieve the given task. However, it is conceivable that under certain situations, the agents may have to violate the social laws to carry out the task more efficiently or even survive in the field. We thus consider the issue of fusing the social laws and a set of "super rules" for handling exceptions in the context of dynamic path planning for a group of autonomous mobile robots. We report some results that indicate that a fusion of social laws and super rules can help us to design effective algorithms.

Presents a new structural induction theorem for rings consisting of identical components that are modeled using a Petri net and a temporal logic formula. The theorem gives a condition in terms of the behavior of the rings of sizes k/spl minus/1 and k, k/spl ges/5, under which all rings of size k/spl minus/1 or greater exhibit "similar" behavior. Using the example of demand-driven token circulation, we show how the theorem can be applied to formally infer the correctness of a ring of any large size from that of a ring having fewer components.>

The problem of searching for a mobile intruder in a simple polygon by a single mobile searcher is considered. This paper investigates the capabilities of searchers having different degrees of visibility by introducing the searcher having k flashlights whose visibility is limited to k rays emanating from his position, and the searcher having a point light source who can see in all directions simultaneously. This paper presents necessary and sufficient conditions for a polygon to be searchable by various searchers. The paper also introduces a class of polygons for which the searcher having two flashlights is as capable as the searcher having a point light source, and it gives a simple necessary and sufficient condition for such polygons to be searchable by the searcher having two flashlights. The complexity of generating a search schedule under some of these conditions is also discussed. Many of the results are proved using chord systems that represent the visibility relations among the vertices and edges of the given polygon.

The problem of searching for a mobile robber in a simple polygon by a number of searchlights is considered. A searchlight is a stationary point which emits a single ray that cannot penetrate the boundary of the polygon. The direction of the ray can be changed continuously, and a point is detected by a searchlight at a given time if and only if it is on the ray. A robber is a point that can move continuously with unbounded speed. First, it is shown that the problem of obtaining a search schedule for an instance having at least one searchlight on the polygon boundary can be reduced to that for instances having no searchlight on the polygon boundary. The reduction is achieved by a recursive search strategy called the one-way sweep strategy. Then various sufficient conditions for the existence of a search schedule are presented by using the concept of a searchlight visibility graph. Finally, a simple necessary and sufficient condition for the existence of a search schedule for instances having exactly two searchlights in the interior is presented.

Temporal Petri nets are Petri nets in which certain restrictions on the firings of transitions are represented by formulas containing temporal operators. The use of temporal Petri nets for formal specification and verification of the alternating bit protocol is discussed. The temporal Petri net which models the protocol is analyzed formally using the existing theory of omega -regular expressions and Buchi-automata.>

This paper discusses a problem of searching for and capturing a fugitive by a team of searchers in an $N \times N \,\text{grid}\,G_N $ representing a system of Navenues and Nstreets which a searcher can “see” a fugitive if and only if both are on the same avenue or the same street. A $0.5N^2 + O(N)$ time algorithm is presented for searching $G_N $ by a team of two searchers in order to decide whether there exists a fugitive in $G_N $. The algorithm is shown to be (1) optimal with respect to the number of searchers required for the case in which the fugitive can move at least as fast as the searchers, and (2) asymptotically optimal with respect to the worst case time complexity. An $O(N^2 )$ time algorithm is also presented for capturing a fugitive in $G_N $ by a team of four searchers. The algorithm is shown to be asymptotically optimal with respect to the worst case time complexity.

A class of Petri nets called temporal Petri nets is introduced, in which timing constraints are represented by the operators of temporal logic. Due to the versatility of the temporal logic operations to express temporal assertions, temporal Petri nets can describe clearly and compactly causal and temporal relationships between the events of a system, including eventuality and fairness. The use of temporal Petri nets is illustrated with a nontrivial example of modeling and analysis of a handshake daisy-chain arbiter.>

A distributed algorithm is presented that realizes mutual exclusion among N nodes in a computer network. The algorithm requires at most N message exchanges for one mutual exclusion invocation. Accordingly, the delay to invoke mutual exclusion is smaller than in an algorithm of Ricart and Agrawala, which requires 2*( N - 1) message exchanges per invocation. A drawback of the algorithm is that the sequence numbers contained in the messages are unbounded. It is shown that this problem can be overcome by slightly increasing the number of message exchanges.