We consider linear search for an escaping target whose speed and/or initial distance from the origin may be unknown to the searcher. The searcher (an autonomous mobile agent) is initially placed at the origin of the real line and can move with maximum speed 1 in either direction along the line. The oblivious mobile target that is moving away from the origin with a constant speed v < 1 is initially placed by an adversary on the infinite line at distance d from the origin in an unknown direction. We consider four cases, depending on whether v and/or d is known to the searcher. The main contributions of this paper are new lower bounds as well as algorithms leading to new upper bounds for search in these settings. We present tight bounds for the cases when v is known. For the cases where v is unknown, we prove an optimal (up to lower order terms in the exponent) competitive ratio in the case where d is known and improved upper and lower bounds for the case where d is unknown. These results solve an open problem proposed in Coleman et al. (2022) [11] .

Consider a region that requires to be protected from unauthorized penetrations. The border of the region, modeled as a unit line segment, consists of high priority segments that require the highest level of protection separated by low priority segments that require to be visited infinitely often. We study the problem of patrolling the border with a set of k robots. The goal is to obtain strategies that minimize the maximum idle time (the time that a point is left unattended) of each point of the high priority segments while visiting each point of the low priority segments infinitely often. We use the concept of single lid cover (segments of fixed length) where each high priority point is covered with at least one lid, and then we extend it to strong double-lid cover where each high priority point is covered with at least two lids, and the unit line segment is fully covered. Let λk−1 be the minimum lid length that accepts a single λk−1-lid cover with k−1 lids and Λ2k be the minimum lid length that accepts a strong double Λ2k-lid cover with 2k lids. We show that 2min⁡(Λ2k,λk−1) is the lower bound of the idle time when the max speed of the robots is one. To compute Λ2k and λk−1, we present an algorithm with time complexity O(max⁡(k,n)log⁡n) where n is the number of high priority segments. Our algorithm improves by a factor of min⁡(n,k) the previous O(knlog⁡n) running time algorithm. For the upper bound, first we present a strategy with idle time λk−1 where robot k patrols the unit line segment, and robot i patrols the i-lid of a single λk−1-lid cover with k−1 lids. Then, we present a simple strategy with idle time 3Λ2k that splits the unit line into not-disjoint k segments of equal length that robots synchronously cover, i.e., reaching the leftmost and rightmost point simultaneously. Then, we present a complex strategy that splits the unit line into k non-disjoint segments that robots asynchronously cover. We show that the combination of strategies one and two attains an approximation of 1.5 the optimal idle time and combining strategies one and third attains an optimal idle time.

We present a synchronous robotic testbed called SyROF that allows fast implementation of robotic swarms. Our main goal is to lower the entry barriers to cooperative-robot systems for undergraduate and graduate students. The testbed provides a high-level programming environment that allows the implementation of Timed Input/Output Automata (TIOA). Sy-ROF offers the following unique characteristics: 1) a transparent mechanism to synchronize robot maneuvers, 2) a membership service with a failure detector, and 3) a transparent service to provide common knowledge in every round. These characteristics are fundamental to simplifying the implementation of robotic swarms. The software is organized in five layers: The lower layer consists of a real-time publish-subscribe system that allows efficient communication between tasks. The next layer is an implementation of a Kalman filter to estimate the position, orientation, and speed of the robot. The third layer consists of a synchronizer that synchronously executes the robot maneuvers, provides common knowledge to all the active participants, and handles failures. The fifth layer consists of the programming environment.

We study the box pushing problem with a set of robots. Robots and relocated objects are placed on opposite sides in such a way that robots have a direct view of the objects. We consider a rather weak model where robots do not have access to a localization system and are disoriented. Further, robots do not know the weight of the boxes nor of their own pushing capabilities. Robots do have access to a wireless device to communicate with other robots. The objective is to design a distributed algorithm that lets the robots self-coordinate to move the objects. We propose a synchronous algorithm that allows the robots to self-coordinate to relocate the box. We use Timed Input/Output Automata to describe the algorithms and show that the algorithm correctly completes the task. Then we extend the algorithm to deal with obstacles and robot failures. We implement the algorithm in SyRof (a testbed built at California State University Long Beach.) The testbed consists of four robots equipped with omnidirectional wheels to simulate drones and an autopilot that provides a synchronous system. The resulting implementation allows the robots to complete the task successfully.

We study the barrier coverage problem using relocatable sensor nodes. We assume each sensor can sense an intruder or event inside its sensing range. Sensors are initially located at arbitrary positions on the barrier and can move along the barrier. The goal is to find final positions for sensors so that the entire barrier is covered. In recent years, the problem has been studied extensively in the centralized setting. In this paper, we study the problem in the distributed setting. We assume each sensor repeatedly executes a Look-Compute-Move cycle: based on what it sees in its vicinity, it makes a decision on where to move, and moves to its next position. We make two strong but realistic restrictions on the capabilities of sensors: they have a constant visibility range and can move only a constant distance in every cycle. In this model, we give the first two distributed algorithms that achieve barrier coverage for a line segment barrier when there are enough nodes in the network to cover the entire barrier. Our algorithms are synchronous, and local in the sense that sensors make their decisions independently based only on what they see within their constant visibility range. One of our algorithms is oblivious whereas the other uses two bits of memory at each sensor to store the type of move made in the previous step. We show that our oblivious algorithm terminates within Θ(n2) steps with the barrier fully covered, while the constant-memory algorithm is shown to take Θ(n) steps to terminate in the worst case. Since any algorithm that can only move a constant distance in one step requires Ω(n) steps on some inputs, our second algorithm is asymptotically optimal. Finally, both our algorithms are self-stabilizing, and can be easily extended to the case of non-homogeneous sensors, and for the case when the barrier is a circle.

A set of mobile robots is deployed on a simple curve of finite length, composed of a finite set of vital segments separated by neutral segments. The robots have to patrol the vital segments by perpetually moving on the curve, without exceeding their uniform maximum speeds. The quality of patrolling is measured by the idleness, i.e., the longest time period during which any vital point on the curve is not visited by any robot. Given a configuration of vital segments, our goal is to provide algorithms describing the movement of the robots along the curve so as to minimize the idleness.

Assume that n sensors with identical range r = f(n)⁄2n, for some f(n) ≥ 1 for all n, are thrown randomly and independently with the uniform distribution in the unit interval [0, 1]. They are required to move to new positions so as to cover the entire unit interval in the sense that every point in the interval is within the range of a sensor. We obtain tradeoffs between the expected sum and maximum of displacements of the sensors and their range required to accomplish this task. In particular, when f(n) -- 1 the expected total displacement is shown to be Θ(√n). For senors with larger ranges we present two algorithms that prove the upper bound for the sum drops sharply as f(n) increases. The first of these holds for f(n) ≥ 6 and shows the total movement of the sensors is O(√ ln n/f(n)) while the second holds for 12 ≤ f(n) ≤ ln n -- 2 ln ln n and gives an upper bound of O(lnn⁄ f(n)ef(n)/2). Note that the second algorithm improves upon the first for f(n) > ln ln n -- ln ln ln n. Further we show a lower bound, for any 1 < f(n) < √n of Ω(εf(n)ε--(1+ε)f(n)), ε > 0.

We consider a 3D antenna orientation problem for maintaining connectivity of a wireless network in 3D space using only directional antennae. Sensors are located at points in 3D space and are equipped with directional antennae. The strong connectivity antenna orientation problem is concerned with deciding whether or not for given solid angle Ω and range r it is possible to orient the antennae so as to ensure that the sensor network resulting from the induced transmissions is strongly connected. In this paper we 1) present an algorithm ensuring optimal antenna range for the case when Ω ≥ 18π/5, 2) show that determining whether or not there exists a strong orientation of directional sensors of solid angle Ω; 0, and 3) provide an algorithm for approximating the antennae range so as to ensure strong connectivity of the resulting graph, provided the solid angle of the antennae is 2π ≤ Ω <; 18π/5· In addition, we study the effect of replacing omnidirectional antennae with directional antennae on the hop stretch factor of the resulting network of directional antennae and present some simulation results on the variation of hop stretch factor with different network sizes and solid angles of directional antennae. This is the first paper concerning the strong connectivity antennae orientation problem in 3D space.