Abstract:
We propose a new approach to the simultaneous cooperative localization of a very large group of simple robots capable of performing dead-reckoning and sensing the relative position of nearby robots. In the last decade, the use of distributed optimal Kalman filters (KF) to address this problem has been studied extensively. In this paper, we propose to use a very simple encounter based averaging process (denoted by EA). The idea behind EA is the following: every time two robots meet, they simply average their location estimates.
We assume that two robots meet whenever they are close enough to allow relative location estimation and communication. At each meeting event, the robots average their location estimations thus reducing the localization error. Naturally, the frequency of the meetings affects the localization quality. The meetings are determined by the robots? movement pattern. In this work we consider movement patterns which are ?well mixing? i.e. every robot meets other robots and eventually all of the robots frequently. For such a movement pattern, the time course of the expected localization error is derived. We prove that EA is asymptotically optimal and requires significantly less computation and communication resources than KF.
Abstract:
A source seeking process for a pair of simple, low capability robots using only point measurements is proposed and analyzed. The robots are assumed to be memoryless, to lack the capability of performing complex computations and to have no direct communication abilities. Their only implicit form of communication is by sensing their relative position and the only response of a robot to the point measurement it makes is by moving to adjust its distance to the other robot according to a predetermined rule. The proposed algorithm is robust: we prove that the algorithm performs correctly even when the robots frequently err due to noisy sensor readings.
Abstract:
We consider two variants of the task of spreading a swarm of agents uniformly on a ring graph. Ant-like oblivious agents having limited capabilities are considered. The agents are assumed to have little memory, they all execute the same algorithm and no direct communication is allowed between them. Furthermore, the agents do not possess any global information. In particular, the size of the ring (n) and the number of agents in the swarm (k) are unknown to them. The agents are assumed to operate on an unweighted ring graph. Every agent can measure the distance to his two neighbors on the ring, up to a limited range of V edges. The first task considered, is dynamical (i.e. in motion) uniform deployment on the ring. We show that if either the ring is unoriented, or the visibility range is less than [left floor]n/k[right floor], this is an impossible mission for the agents. Then, for an oriented ring and V>=[left ceiling]n/k[right ceiling], we propose an algorithm which achieves the deployment task in optimal time. The second task discussed, called quiescent spread, requires the agents to spread uniformly over the ring and stop moving. We prove that under our model, in which every agent can measure the distance only to his two neighbors, this task is impossible. Subsequently, we propose an algorithm which achieves quiescent but only almost uniform spread. The algorithms we present are scalable and robust. In case the environment (the size of the ring) or the number of agents changes during the run, the swarm adapts and re-deploys without requiring any outside interference.
Abstract:
We consider two variants of the task of spreading a swarm of agents uniformly on a ring graph. Let n be the size of the ring and k the size of the swarm. Ant-like oblivious agents having limited capabilities are considered. The agents are assumed to have little memory, they all execute the same algorithm and no direct communication is allowed between them. Furthermore, the agents do not possess any global information. In particular n and k are unknown to them. The agents operate on an unweighted ring graph. Every agent can measure the distance to his two neighbors on the ring up to a limited range of V edges. In the first task considered, the agents are required to spread uniformly over the ring. We show that if the ring is unoriented or Vceil(n/k), an algorithm which achieves the task within the optimal time is presented. The second task discussed requires the agents to spread uniformly over the ring and stop moving. This is called quiescent spread. We prove that under our model in which every agent can measure the distance of only his two closest neighbors, this task is impossible. Instead, an algorithm which achieves quiescent and (almost) uniform spread is proposed. Abstract. The algorithms presented are scalable and robust. In case the environment (the size of the ring) or the number of agents change during the run, the swarm adapts and re-deploys without requiring any outside interference.
Abstract:
We introduce a novel multi-agent patrolling strategy. By assumption, the swarm of agents performing the task consists of very low capability ant-like agents. The agents have little memory, they can not communicate and their sensing abilities are local. Furthermore, the agents do not posses any knowledge regarding the graph or the swarm size. However, the agents may mark the graph vertices with pheromone stamps which can later be sensed. These markings are used as a primitive form of distributed memory and communication. The proposed strategy is a bundle of two algorithms. A single agent (the "leader") is responsible of finding a short cycle which covers the graph, and this is achieved using a "cycle finding" algorithm. All other agents follow that cycle while maintaining even gaps between them using a "spreading algorithm". We prove that the algorithms converge within a finite expected time. After convergence, the maximum time lag between two successive visits to any vertex using the proposed strategy is at most 4k/(k-1)*l_max/l_min times the optimal, where the optimal time is bounded from below by n*l_min/k, and where l_max (l_min) is the longest (shortest) edge in the graph and k is the swarm size. The proposed strategy is scalable and robust. In case the number of agents changes during run (e.g. as a result of an agent break down) the agents autonomously redeploy uniformly over the cycle. In case the graph changes, the leader autonomously finds a new patrolling route.
Abstract:
We propose a new approach to the simultaneous cooperative localization of a group of robots capable of sensing their own motion and the relative position of nearby robots. In the last decade, the use of distributed optimal Kalman filters (KF) to solve this problem have been studied extensively. In this paper, we propose to use a sub-optimal Kalman filter (denoted by EA). EA requires significantly less computation and communication resources then KF. Furthermore, in some cases, EA provides better localization. In this paper EA is analyzed in a soft "thermodynamic" fashion i.e. relaxing assumptions are used during the analysis. The goal is not to derive hard lower or upper bounds but rather to characterize the robots expected behavior. In particular, to predict the expected localization error. The predictions were validated using simulations. We believe that this kind of analysis can be beneficial in many other cases.
Abstract:
We introduce a novel multi agent patrolling algorithm inspired by the behavior of gas filled balloons. Very low capability ant-like agents are considered with the task of patrolling an unknown area modeled as a graph. While executing the proposed algorithm, the agents dynamically partition the graph between them using simple local interactions, every agent assuming the responsibility for patrolling his subgraph. Balanced graph partition is an emergent behavior due to the local interactions between the agents in the swarm. Extensive simulations on various graphs (environments) showed that the average time to reach a balanced partition is linear with the graph size. The simulations yielded a convincing argument for conjecturing that if the graph being patrolled contains a balanced partition, the agents will find it. However, we could not prove this. Nevertheless, we have proved that if a balanced partition is reached, the maximum time lag between two successive visits to any vertex using the proposed strategy is at most twice the optimal so the patrol quality is at least half the optimal. In case of weighted graphs the patrol quality is at least 1 2 lmin/lmax of the optimal where lmax (lmin) is the longest (shortest) edge in the graph.
Abstract:
In this follow-up to an ANTS 2004 paper we continue to investigate the problem of gathering a swarm of multiple robotic agents on the plane using very limited local sensing capabilities. In our previous work, we assumed that the agents cannot measure their distance to neighboring agents at all. In this paper, we consider a crude rangelimited sensing capability that can only tell if neighboring agents are either near or far. We introduce two new variants of our previously proposed algorithm that utilize this capability. We prove the correctness of our algorithms, and show that the newly added capability can improve the performance of the algorithm significantly.
Abstract:
We experimentally demonstrate a phasematching technique for frequency conversion in nonlinear semiconductor structures by employing linear long-period gratings. We designed a specific semiconductor photonic device for second harmonic generation using coupled-mode equations with parameters extracted from beam propagation method simulations. Optical frequency converters were fabricated according to the design with the main feature; linear long-period weak gratings imprinted on semiconductor waveguides, providing the required photon momentum difference for matching the phases of the different-wavelength photons. The measured nonlinear conversion efficiency and its spectrum comply with our theoretical predictions.
Abstract:
We present a model for calculating the Spatial Frequency Response (SFR) for Bayer pattern color detectors. The model is based on the color detector response to B/W scenes. When a Bayer color detector is compared to a B/W detector, SFR difference results from the interpolation process. This process exists only in the Bayer pattern detectors. In this work we ascribe the MTF and the spurious response to the interpolation process. The model may be applied to any linear interpolation. Although the interpolation is linear, it is not Shift Invariant (SI). Therefore, calculating the interpolation MTF is not a trivial task. Furthermore, the interpolation creates a spurious response. In order to calculate the interpolation SFR, we introduce a separable constraint (for x and y directions) by using a scene that varies only on one axis and is fixed on the other. We further assume integration in the direction of the fixed axis. By using these two assumptions, we have been able to separate the response into two axes and calculate the SFR. For distant scenes, colors saturation decreases, the colors are less visible and mostly grey colors are sensed. In these cases the Johnson Criterion can be roughly applied. In order to apply the Johnson Criterion it is required to know the MTF of the sensing system. The sensing system MTF includes the interpolation MTF. We show that the interpolation process degrades the system performance compared to B/W sensor. Another application of the model is in comparing different interpolation algorithms.