Optimal Patrolling of High Priority Segments While Visiting the Unit Interval with a Set of Mobile Robots 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 a strategy that minimizes the maximum idle time (the time that a point is left unattended) of the high priority points while visiting the low priority points 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 doublelid cover where each high priority point is covered with at least two lids, and the unit line segment is fully covered. Let lambda_k1 be the minimum lid length that accepts a single lambda_k1lid cover with k1 lids and Lambda_2k be the minimum lid length that accepts a strong double Lambda_2klid cover with 2k lids. We show that 2min(Lambda_2k, lambda_k1) is the lower bound of the idle time when the max speed of the robots is one. To compute Lambda_2k and lambda_k1, we present an algorithm with time complexity O(max(k, n)logn) where n is the number of high priority sections. For the upper bound, first we present a strategy with idle time lambda_k1 where one robot covers the unit line, and the remaining robots cover the lids of a single lambda_k1lid cover with k1 lids. Then, we present a simple strategy with idle time 3Lambda_2k that splits the unit line into notdisjoint k segments of equal length that robots synchronously cover. Then, we present a complex strategy that split the unit line into k nondisjoint segments that robots asynchronously cover.

TimeVarying Graph Patrolling Against Attackers with Locally Limited and Imperfect Observation Models The use of autonomous robots for surveillance is one of the most interesting applications of graphpatrolling algorithms. In recent years, considerable effort has been devoted to tackling the problem of efficiently computing effective patrolling strategies. One of the mainstream approaches is adversarial patrolling, where a model of a strategic attacker is explicitly taken into account. A common assumption made by these techniques is to consider a worstcase attacker, characterized by ubiquitous and perfect observation capabilities. Motivated by the domain of robotic applications, we instead consider a more realistic and limited attacker model capable of gathering noisy observations in a locally limited range of the environment. We assume that the modeled attacker follows a behavior induced by its observations. Thus, we devise a randomized patrolling strategy based on Markov chains that makes observations reveal very little information, while still maintaining a reasonable level of protection in the environment. Our experimental results obtained in simulation confirm timevariance as a practical approach for our objective.