Andrew Collins

Jurek Czyzowicz

Adrian Kosowski

Evangelos Kranakis

Danny Krizanc

Russell Martin

Oscar Morales Ponce

Optimal Patrolling of Fragmented Boundaries

Keywords: ESA 2011] Algorithms, Mobile robots, Boundary patrolling, Idleness, Cycle

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 maximum speed. 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.

Our main contribution is a proof that the optimal solution to the patrolling problem is attained either by the cyclic strategy, in which all the robots move in one direction around the curve, or by the partition strategy, in which the curve is partitioned into sections which are patrolled separately by individual robots. These two fundamental types of strategies were studied in the past in the robotics community in different theoretical and experimental settings. However, to our knowledge, this is the first theoretical analysis proving optimality in such a general scenario. Throughout the paper we assume that all robots have the same maximum speed. In fact, the claim is known to be invalid when this assumption does not hold, cf. [Czyzowicz et al., Proc.

Introduction

Protecting an environment by a set of stationary or mobile point-guards has been studied before in many various scenarios. The problem of patrolling a one-dimensional boundary using mobile robots has many real-world applications, and is extensively studied under the names of boundary patrolling and fence patrolling in the robotics literature. In order to prevent an intruder from penetrating into a protected region, the boundary of the region must be patrolled. Some parts of the boundary may be monitored with stationary devices like sensors or cameras (or they do not need to be monitored at all), while other portions require the aid of moving robots such as walking guards, illumination rays, mobile robotic devices, etc. Since the feasibility of an intrusion likely depends on the time during which the intruder remains undiscovered, it is important to design patrolling protocols which minimize the time during which boundary points are unprotected.

Some portions of the boundary may be unpenetrable at all, or they may be monitored with stationary devices like sensors or cameras. This paper is devoted to the scenario in which only a finite set of boundary segments, referred to as vital regions, need to be patrolled by a set of k mobile robots. The remaining part of the boundary, called neutral regions, do not have to be monitored by the mobile robots, but may nevertheless be traversed by a robot since this may be the way to reach one vital region from another. We study the problem of patrolling with the goal of minimizing the idleness of points located in the vital regions, i.e., the longest time during which such a point remains unvisited by a robot. We assume that at any time during the traversal the speed of each robot cannot exceed a certain maximum value, identical for all robots. Our goal is to define a set of functions describing the trajectories of all the robots in time.

The most common heuristics adopted in the past to solve a variety of patrolling problems include the cyclic strategy, where robots move in one direction around the cycle covering the environment, and the partition strategy, in which the environment is partitioned into sections patrolled separately by individual robots (or subsets of robots), using the terminology introduced in [START_REF] Chevaleyre | Theoretical analysis of the multi-agent patrolling problem[END_REF]. However, to the best of our knowledge, no theoretical studies formally proving the optimality of such approaches in this setting were done in the past.

It is worth noting, that in the more heterogeneous scenario where robots have different maximum speeds, neither the cyclic strategy nor the partition strategy leads to the optimal performance. In fact, it has been shown in [START_REF] Czyzowicz | Boundary patrolling by mobile agents with distinct maximal speeds[END_REF] that for the case of 3 mobile robots with different maximal speeds patrolling a cycle (forming a single vital region), neither a partition strategy nor a cyclic strategy is optimal. It turns out that a specific hybrid strategy is better than each of these two fundamental approaches.

Model, Preliminaries, and Notation

We consider k ≥ 1 mobile robots traversing a continuous rectifiable curve C. Definition 1.1 (Traversal strategy (or schedule) on a curve) Consider a rectifiable curve C. A traversal strategy for a single mobile robot is a continuous function f : [0, +∞) → C such that t → f (t), whereby f (t) is the position of the robot on the curve at time t ≥ 0. More generally, for k mobile robots, a traversal strategy consists of k such continuous functions, one for each mobile robot.

Without loss of generality, we will assume that C is either a segment of unit length (in the case when C is an open curve), or a cycle of unit perimeter (when C is a closed curve). In both cases, we will use the notation [0, 1] to parameterize the curve, noting that in the case of the cycle, points 0 and 1 are identified with each other. All robots may move along C at speeds not exceeding a given maximum value. For simplicity of notation, we set a unit of speed for which this maximum speed is equal to 1. Definition 1.2 (Unit maximum speed) Let dist(p, q) denote the distance between points p, q ∈ C along the curve C. We say that the traversal strategy for k robots respects the robots' unit maximum speed if for any 1 ≤ r ≤ k and any t 1 , t 2 ∈ [0, +∞) we have dist(fr(t 1 ),fr(t 2 ))

|t 1 -t 2 | ≤ 1.
We remark that since the distance metric dist(p, q) only needs to capture the time required for a robot to travel between p and q, and does not have to correspond to the physical distance between points in a real-world setting, the above definition takes into account non-uniform terrains (boundaries with corridors, stair-cases, etc.), in which robots move along some parts of the terrain more quickly than along others. However, we do not take into account scenarios in which some robots move faster through a given section of the terrain than other robots.

The task of the robots is to patrol, so called, vital regions, located in the unit-length curve C (along which the robots move), so as to minimize the idleness of the points in the vital regions.

Definition 1.3 (Vital and neutral regions)

The curve C contains n disjoint, consecutive, closed vital intervals V 1 , V 2 , . . . , V n , separated by neutral intervals. Throughout the paper, we will write C = (V, N ), where [0, 1] ⊇ V = n i=1 V i , and N = [0, 1] \ V . In the case when C is the unit segment [0, 1], we have

V i = [b i , e i ] and e i < b i+1 for 1 ≤ i ≤ n -1, with b 1 = 0 and e n ≤ 1.

Definition 1.4 (Idleness)

Let A be a traversal strategy consisting of k continuous functions f i for a system of k mobile robots, respectively, and traversing the given curve.

1. The idleness induced by A at a point x of the curve, denoted by I x (A), is the supremum of the length of time intervals during which point x remains unvisited by any agent:

I x (A) = sup {0≤T 1 <T 2 : ∀i∀t∈[T 1 ,T 2 ] f i (t) =x} (T 2 -T 1 ).
2. The idleness of the system of k mobile robots induced by A is defined by I(A) = sup x∈V I x (A), the supremum taken over all vital points of the curve.

3. Finally, the idleness of the system of k mobile robots is defined by I opt = inf A I(A), the infimum taken over all traversal strategies A.

We can now formulate the main question we will address in this paper. Question. Suppose that we have k mobile robots traversing a given rectifiable open curve (resp., closed curve) C = (V, N ), represented w.l.o.g. as the unit-length segment (resp., the unit-perimeter cycle). What traversal strategy should the mobile robots follow so as to minimize the idleness of the system?

In order to describe the region patrolled by a single robot in the partition strategies we propose, we will frequently refer to the concept of a lid. Definition 1.5 ((d,k)-Lid cover) A d-lid is a contiguous interval on the curve of length d. We say that a curve C = (V, E) has a (d, k)-lid cover if all of its vital regions can be covered by some set of k (not necessarily disjoint) d-lids.

Related work

The patrolling problem may be viewed as a version of an art gallery question, in which a set of stationary or mobile guards have to protect a given geometric environment (see [START_REF] Mitchell | Geometric shortest paths and network optimization[END_REF][START_REF] O'rourke | Art Gallery Theorems and Algorithms[END_REF][START_REF] Shermer | Recent results in art galleries[END_REF]). In the setting with stationary guards, in most research papers the number of guards, needed to view the entire environment, has to be minimized. The problem is NP-hard and many approximation and inapproximability results were obtained (cf. [START_REF] Eidenbenz | Inapproximability results for guarding polygons and terrains[END_REF][START_REF] Ghosh | Approximation algorithms for art gallery problems in polygons and terrains[END_REF]). For the case of mobile guards, often known as the watchman route problem, the question of a single watchman was most often addressed. The optimization criterion is the path length traversed by the watchman, so that every point of the environment is seen from some position on the path. This is closely related to the traveling salesman problem. Unsurprisingly, many general watchman route problems are NP-hard (e.g. watchman tours of simple polygon with holes, suggested in [START_REF] Chin | Optimal watchman routes[END_REF] and corrected in [START_REF] Dumitrescu | Watchman tours for polygons with holes[END_REF]), touring a sequence of non-convex polygons [START_REF] Dror | Touring a sequence of polygons[END_REF], or link-distance watchman tours of simple polygon with holes [START_REF] Arkin | Minimum-link watchman tours[END_REF]). However, for many specific cases, polynomial algorithmic solutions are available. The solution for simple polygons was proposed by [START_REF] Chin | Shortest watchman routes in simple polygons[END_REF], while [START_REF] Chin | The zookeeper route problem[END_REF], [START_REF] Ntafos | Watchman routes under limited visibility[END_REF] and [START_REF] Czyzowicz | The aquarium keeper's problem[END_REF] solve, respectively, the "zookeeper route", "safari route" and "aquarium keeper" problems.

In the m-watchmen routes problem, the sum S of m path-lengths must be minimized, so that each point of the environment must be seen from some position of one of the watchmen (cf., e.g. [START_REF] Nilsson | Guarding art galleries; Methods for mobile guards[END_REF][START_REF] Packer | Computing multiple watchman routes[END_REF]). Clearly S decreases with increasing m. Hence at one extremity, we obtain the case when m is large enough to have S = 0 (m stationary guards for art gallery are sufficient) and on the other extremity the single watchman question arises. As m-watchmen routes problem is NP-hard for simple polygons (cf. [START_REF] Ponce | The Art Gallery Theorem and Algorithm[END_REF]) some restricted classes of polygons were considered in [START_REF] Carlsson | Optimum guard covers and m-watchmen routes for restricted polygons[END_REF][START_REF] Nilsson | Optimum watchmen route in spiral polygons[END_REF].

Central to the watchman route problem is the notion of visibility. Some papers (e.g. [START_REF] Kazazakis | Fast positioning of limited-visibility guards for the inspection of 2d workspaces[END_REF][START_REF] Ntafos | Watchman routes under limited visibility[END_REF]), considered limited visibility of the mobile (e.g. [START_REF] Ntafos | Watchman routes under limited visibility[END_REF]), or stationary (e.g. [START_REF] Kazazakis | Fast positioning of limited-visibility guards for the inspection of 2d workspaces[END_REF]) guards. Our work corresponds to the case of zero visibility, in which the robot sees only the point of the environment at which it is currently present, giving rise to so-called patrolling problems. Clearly, in finite time, the mobile robots may only patrol a geometric environment given as a union of paths of bounded total length.

The act of patrolling is defined as the perpetual process of surveillance consisting of walking around a terrain in order to protect or supervise it; it is performed either in a static or in a dynamically changing environment. It has been studied extensively in robotics literature (cf. [START_REF] Almeida | Recent advances on multi-agent patrolling[END_REF][START_REF] Chevaleyre | Theoretical analysis of the multi-agent patrolling problem[END_REF][START_REF] Easton | A coverage algorithm for multi-robot boundary inspection[END_REF][START_REF] Elmaliach | Multi-robot area patrol under frequency constraints[END_REF][START_REF] Elmaliach | A realistic model of frequency-based multi-robot polyline patrolling[END_REF][START_REF] Hazon | On redundancy, efficiency, and robustness in coverage for multiple robots[END_REF][START_REF] Machado | Multi-agent patrolling: An empirical analysis of alternative architectures[END_REF][START_REF] Yanovski | A distributed ant algorithm for efficiently patrolling a network[END_REF]) and it is sometimes viewed as a variant of coverage -a central task in robotics. Patrolling can be useful in settings where objects or humans need to be rescued from a disaster environment, but also network administrators may use mobile robot patrols to detect network failures or to discover web pages which need to be indexed by search engines, cf. [START_REF] Machado | Multi-agent patrolling: An empirical analysis of alternative architectures[END_REF].

Similarly, boundary patrolling may be motivated by the task of detecting intruders (from the exterior) in a two dimensional terrain by patrolling its boundary. There exist several studies on boundary patrolling (cf. [START_REF] Agmon | Multi-robot perimeter patrol in adversarial settings[END_REF][START_REF] Elmaliach | Multi-robot area patrol under frequency constraints[END_REF][START_REF] Elmaliach | A realistic model of frequency-based multi-robot polyline patrolling[END_REF][START_REF] Pasqualetti | On optimal cooperative patrolling[END_REF]); often the approach followed is ad hoc, emphasizing either experimental results (e.g. [START_REF] Machado | Multi-agent patrolling: An empirical analysis of alternative architectures[END_REF]), or uncertainty of the model and robustness of the solutions when failures are possible (e.g., [START_REF] Elmaliach | Multi-robot area patrol under frequency constraints[END_REF][START_REF] Elmaliach | A realistic model of frequency-based multi-robot polyline patrolling[END_REF][START_REF] Hazon | On redundancy, efficiency, and robustness in coverage for multiple robots[END_REF]), or non-deterministic solutions (e.g. [START_REF] Agmon | Multi-robot perimeter patrol in adversarial settings[END_REF]).

The fundamental measure for evaluating the efficiency of patrolling is the criterion of idleness, first introduced in [START_REF] Machado | Multi-agent patrolling: An empirical analysis of alternative architectures[END_REF]. The general idea is to measure frequency of visits of the points of the environment by incoming robots (cf. [START_REF] Almeida | Recent advances on multi-agent patrolling[END_REF][START_REF] Chevaleyre | Theoretical analysis of the multi-agent patrolling problem[END_REF][START_REF] Elmaliach | Multi-robot area patrol under frequency constraints[END_REF][START_REF] Elmaliach | A realistic model of frequency-based multi-robot polyline patrolling[END_REF][START_REF] Machado | Multi-agent patrolling: An empirical analysis of alternative architectures[END_REF]). As such the idleness is sometimes viewed as the average (cf. [START_REF] Elmaliach | Multi-robot area patrol under frequency constraints[END_REF]), worst-case (cf. [START_REF] Yanovski | A distributed ant algorithm for efficiently patrolling a network[END_REF]), probabilistic (cf. [START_REF] Agmon | Multi-robot perimeter patrol in adversarial settings[END_REF]) or experimentally verified (cf. [START_REF] Machado | Multi-agent patrolling: An empirical analysis of alternative architectures[END_REF]) time elapsed since the last visit of a node (cf. [START_REF] Almeida | Recent advances on multi-agent patrolling[END_REF][START_REF] Chevaleyre | Theoretical analysis of the multi-agent patrolling problem[END_REF]). Also, in some papers the terms of blanket time (cf. [START_REF] Yanovski | A distributed ant algorithm for efficiently patrolling a network[END_REF]) or refresh time (cf. [START_REF] Pasqualetti | On optimal cooperative patrolling[END_REF]) are being used instead, so as to indicate a similar measure of algorithm efficiency. Several approaches to patrolling based on idleness criteria were surveyed in [START_REF] Almeida | Recent advances on multi-agent patrolling[END_REF], including machine learning, negotiation mechanisms for generating paths, heuristics based on local idleness, as well as approximation to the Traveling Salesmen Problem (TSP). Some papers study patrolling based on swarm or ant-based algorithms (cf. [START_REF] Elor | Autonomous multi-agent cycle based patrolling[END_REF][START_REF] Marino | Behavioral control for multi-robot perimeter patrol: A finite state automata approach[END_REF][START_REF] Yanovski | A distributed ant algorithm for efficiently patrolling a network[END_REF]) and explore various robot capabilities (sensing, memory, locomotion, etc). The skeletonization technique, where a terrain is first partitioned into cells is often applied in geometric environments prior to employing graph-theoretic methods in discrete time. In graph environments, cyclic strategies often rely on either TSP-related solutions or spanning tree-based approaches ( [START_REF] Gabriely | Spanning-tree based coverage of continuous areas by a mobile robot[END_REF][START_REF] Pasqualetti | On optimal cooperative patrolling[END_REF]). For the case of boundary patrolling where the robots maintain distinct maximal speeds, only partial solutions for small numbers of robots were proposed (cf. [START_REF] Czyzowicz | Boundary patrolling by mobile agents with distinct maximal speeds[END_REF]).

One may also consider as a variant of patrolling the problem of searching a graph or polygon by teams of mobile robots (cf., e.g. [START_REF] Fomin | How to guard a graph?[END_REF][START_REF] Yamashita | Searching for mobile intruders in a polygonal region by a group of mobile searchers[END_REF]), which are looking for a stationary or mobile intruder. This falls into the vastly investigated domain of cops and robbers (see [START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF]).

Outline and results of the paper

We start by recalling the partition strategy of patrolling in Section 2, in which each robot traverses some sub-interval of the curve back and forth. This strategy is always optimal on open curves (i.e., on the unit segment), but it need not be optimal for closed curves (i.e., for the unit cycle).

Our main results concern closed curves, and are given in Section 3. We prove that the optimal idleness for patrolling the boundary is always attained by the better of two strategies: the before-mentioned partition strategy, and the cyclic strategy, in which equally-spaced robots patrol the cycle, moving in the same direction. The choice of the strategy and the robots' responsibilities depends on the arrangement of the vital regions around the boundary. Our approach consists in showing that finding the optimal idleness for k robots and for any set of n vital intervals may be reduced to finding the idleness for some critical set of 2k + 1 vital points (always resulting in the cyclic strategy) or of a critical set of k + 1 vital points (resulting in either the cyclic or the partition strategy).

Finally, in Section 4, we propose an O(kn log n) algorithm for designing traversal strategies with optimal idleness for robots on both open and closed curves.

Optimal Patrolling Strategy for the Segment

We start by studying the patrolling problem for k mobile robots on a curve C = (V, N ) consisting of n vital regions on the unit interval [0, 1].

A natural approach to patrolling the segment is based on the partition strategy, in which each of the robots patrols exactly one of the k lids of the lid cover of minimum lid size L. The robot moves back and forth between its endpoints at maximum speed.

Partition strategy

1. Compute a (L, k)-lid cover of C, where L is chosen as the minimum lid length for which C admits such a lid cover. Let the i-th lid, 1 ≤ i ≤ k, be a segment of the form

[c i , c i + L].
2. Deploy the i-th mobile robot so that at time t = 2Lj + τ , where j is a non-negative integer and -L ≤ τ < L, the position f i (t) of this robot on the lid is

f i (t) = c i + |τ |.
We observe that each of the points of every lid, and consequently every vital point of the segment, is visited at least once during each time interval of size 2L. So, for this strategy we have an idleness of I ≤ 2L. The idleness of the partition strategy is, in fact, optimal.

Theorem 2.1 (Idleness for k mobile robots on a segment) The optimal idleness for k mobile robots moving at speed at most 1 on a unit segment is given by I = 2L, where L is the minimum value such that the terrain admits a (L, k)-lid cover.

The proof of Theorem 2.1 relies on the observation that, due to the fact that robots are indistinguishable, there exists an optimal solution in which the robots do not change their relative order on the segment, throughout the traversal (details are provided in the Appendix).

The complexity of computing the optimal lid cover for the partition strategy is discussed in detail in Section 4.

Optimal Patrolling Strategy for the Cycle

We are interested in computing the optimal idleness for k mobile robots traversing a unit-perimeter cycle C = (V, N ) with vital and neutral regions. The class of strategies under consideration in a cycle is larger than in the case of a segment due to the ability of the robots to traverse the perimeter of the cycle. In particular, the robots on the cycle can also apply a cyclic strategy, performing clockwise rotations around the cycle with even time spacing.

Cyclic strategy (on the cycle)

1. Deploy the i-th mobile robot at time 0 at position i/k along the circumference of the cycle.

2. Release all robots at their maximum speed to perform a clockwise traversal of the cycle.

Observation 3.1 The idleness of the cyclic strategy on the cycle is I = 1/k, for any (non-empty) set of vital regions.

At the same time, we observe that the partition strategy introduced in the previous section is also applicable in the cycle, achieving an idleness of I = 2L, where L is the size of the minimum lid cover of the vital regions of the cycle with k lids. Depending on the configuration of the vital regions, one or the other of these two strategies may prove superior. In one extremal case when the cycle has no neutral regions, the cyclic strategy achieves an idleness of 1/k, while the partition strategy has an idleness of 2/k. At the other extreme, for vital regions consisting of k discrete points, the idleness of the cyclic strategy is still 1/k, but the partition strategy has an idleness of 0. This leads us naturally to a strategy which selects the better of the two approaches.

Combined strategy (on the cycle)

1. Let L be the lid size of the minimum (with respect to lid size) lid cover of the vital regions of the cycle with k lids.

2. If 2L < 1/k, apply Partition strategy. This claim gives rise to the following natural question: Does there exist any other strategy which can achieve better idleness than both the partition and cyclic approaches? Such a question admits a positive answer for the cycle in the scenario where robots have different speeds [START_REF] Czyzowicz | Boundary patrolling by mobile agents with distinct maximal speeds[END_REF], even when neutral regions are not present. In our scenario, with neutral regions but for robots with equal maximal speeds, the combined strategy turns out to be optimal. The proof of this fact is surprisingly involved. The rest of this section is devoted to the proof of Theorem 3.3, which proceeds in three technical lemmas. First, we show that for any cycle with neutral regions we can find a subset of either exactly k + 1 or exactly 2k + 1 (discrete) vital points that satisfy specific properties. Then, we show that the lower bound can be proved simply by considering the patrolling problem on the selected subset of points. The proofs of all the Lemmas are omitted or provided as sketches. For complete proofs, the reader is referred to the Appendix. (1) If B ≥ 1/(2k), then there exists a set of k + 1 vital points {v 0 , . . . , v k } ⊆ V , ordered clockwise, s.t. min 0≤i≤k dist(v i , v (i+1) mod (k+1) ) ≥ min{1/(2k), L}.

Else, apply

(2) If B < 1/(2k), then there exists a set of 2k + 1 vital points {v 0 , . . . ,

v 2k } ⊆ V , ordered clockwise, s.t. min 0≤i≤2k dist(v i , v (i+2) mod (2k+1) ) > 1/(2k). Lemma 3.5 (k + 1 point lemma) Let (v 0 , v 1 , . . . , v k
) be a set of k + 1 points chosen from vital regions of the terrain, arranged in clockwise order along the cycle. The idleness I(A) of any traversal strategy A for k mobile robots in this terrain satisfies I(A) ≥ min 1 k , 2s , where: s = min 0≤i =j≤k dist(v i , v j ).

Proof. (sketch) The intuition of the proof is the following. First, we show that w.l.o.g. one can restrict the class of considered strategies in which the robots do not perform unnecessary movements within neutral regions. Subject to this assumption and supposing that for some strategy A, I(A) < 2s, we show that if we fix a sufficiently long time interval, then the number of times the robots traverse each arc of the cycle between two adjacent vital points is roughly the same for all such arcs. Finally, by applying a global counting argument, we prove that we must then have I(A) ≥ 1/k. In the argument, we capture the intuition that each robot has to perform a (1/k)-th part of the patrolling task. In particular, waiting at vital points cannot improve the performance of the strategy, since then each robot only protects 1 out of k + 1 vital points. We will show the claim holds even if points {v 0 , v 1 , . . . , v k }, satisfying dist(v i , v (i+1) ) ≥ s, for 0 ≤ i ≤ k, are the only vital points of the cycle. Indices of points and robots are understood modulo k + 1.

Fix > 0. Consider a strategy A such that I(A) < 2s -2 . To prove the lemma, we will show there exists a point v i , 0 ≤ i ≤ k, such that the time between some two consecutive visits of a robot to point v i is greater than τ = 1 k -. By appropriately modifying the trajectories of the robots, we can convert a strategy A into another strategy A so that the following properties are satisfied by A :

(i) if a robot following A leaves some vital point v i , then it does not reenter v i before reaching some other vital point first (namely, Since no two robots following A ever meet by (ii), we can denote an arbitrarily chosen robot by r 1 , and the other robots by r 2 , . . . , r k in clockwise order; this order never changes throughout the traversal. Suppose that at some time t, some robot r j leaves point v i on the arc towards point v i+1 . By (i), the next vital point it reaches has to be point v i+1 . Therefore, robot r j cannot reenter point v i before time t + 2dist(v i , v i+1 ) ≥ t + 2s > t + I(A ). It follows that within the time interval [t, t + I(A )], robot r j-1 entered node v i . Before this visit, the previous vital point visited by r j-1 must have been v i-1 . It follows that to each traversal of the arc (v i , v i+1 ) by robot r j that starts at some time t, we can assign a distinct traversal of the arc (v i-1 , v i ) by robot r j-1 that ends within the time interval [t, t + I(A )]. Fix two values of time T 1 and T 2 , 0 ≤ T 1 < T 2 . From now on, we will apply certain counting arguments within the time interval [T 1 , T 2 ]; for the sake of intuition, one can see this interval as sufficiently long (T 1 = 0 and T 2 → ∞). Let C j (i, i + 1) denote the number of traversals of arc (v i , v i+1 ) by robot r j starting in the time interval [T 1 , T 2 ]. Since only the first and last traversals of (v i , v i+1 ) by robot r j within this time interval may by unmatched by corresponding traversals of (v i-1 , v i ) by robot r j-1 within the same time interval, we have

v i-1 or v i+1 ), (
C j (i, i + 1) -C j-1 (i -1, i) ≤ 2. Let C(i, i + 1) = k j=1 C j (i, i + 1)
be the total number of traversals of the arc (v i , v i+1 ) by all robots starting within the time interval [T 1 , T 2 ]. Summing the above inequalities, we have: C(i, i+1)-C(i-1, i) ≤ 2k, and analogously for the counter-clockwise direction, C(i, i -1) -C(i + 1, i) ≤ 2k. The above inequalities hold for all i, hence the difference between C(i 1 , i 1 + 1) and C(i 2 , i 2 + 1) (respectively, C(i 1 , i 1 -1) and C(i 2 , i 2 -1)) can be bounded for any i 1 and i 2 on the cycle. Denoting C cw = min 0≤i≤k C(i, i + 1) and C cc = min 0≤i≤k C(i + 1, i), we have for all i:

C(i, i + 1) ≤ C cw + 2k 2 , C(i + 1, i) ≤ C cc + 2k 2
. Now, denote by W j (i) ≥ 0 the total time spent by robot r j at point v i within the time interval [T 1 , T 2 ], and let W (i) = k j=1 W j (i). Without loss of generality, let v 0 be a vital point with the minimal total waiting time, i.e., W (0) = min 0≤i≤k W (i). With respect to point v 0 , the trajectory of each robot r j within the time interval [T 1 , T 2 ] can be described by an ordered sequence of time moments (e 1 j , l 1 j , e 2 j , l 2 j , . . . , l

n j j )
, where e p j is the time at which robot r j enters point v 0 for the p-th time, whereas l p j is the time at which robot r j leaves point v 0 for the p-th time. We assume that T 1 ≤ e 1 j ≤ l 1 j < e 2 j ≤ l 2 j < . . . < e

n j j ≤ l n j j ≤ T 2 ,
where we put e 1 j = T 1 if robot r j was located at node v 0 at time T 1 , and l n j j = T 2 if robot r j was located at node v 0 at time T 2 . For the sake of notation, let l 0 j = T 1 and e n j +1 j = T 2 . During the time interval [T 1 , T 2 ], point v 0 is covered by a robot during the set of moments X given as: X = k j=1 n j p=1 [e p j , l p j ], such that |X| = W (0). During the remaining time, i.e. X = [T 1 , T 2 ] \ X, no robot is located at v 0 . We observe that X is a union of at most 1 + k j=1 n j intervals. Hence, there exists some time interval of length τ , during which v 0 remains unvisited, where:

τ ≥ |X| 1+ k j=1 n j = (T 2 -T 1 )-|X| 1+ k j=1 n j = (T 2 -T 1 )-W (0) 1+ k j=1 n j (1)
Notice that each robot r j leaves point v 0 at least n j -1 times in the time interval [T 1 , T 2 ], going towards either point v 1 or point v k . Thus, we have:

C(0, 1) + C(0, k) ≥ k j=1 (n j -1) = k j=1 n j -k. Taking into account that C(0, 1) ≤ C cw + 2k 2 and C(0, k) ≤ C cc + 2k 2 , we have: k j=1 n j ≤ C cw + C cc + 4k 2 + k.
(2) Moreover, since each arc of the cycle is traversed in either direction a total of at least C cw + C cc times, the total distance covered by all the robots is at least C cw + C cc . Thus, the total time of movement of all k robots within the time interval [T 1 , T 2 ] is at least C cw + C cc , and we have the inequality

C cw + C cc + k i=0 W (i) ≤ k(T 2 -T 1 )
, which yields:

C cw + C cc ≤ k(T 2 -T 1 ) -(k + 1)W (0). (3)
Combining inequalities (1), (2), and (3), after several transformations we obtain τ > 1 k -

4k 2 +k+1 (T 2 -T 1 )-(4k 2 +k+1
) . Now, suppose that T 2 is chosen to be sufficiently large so that 4k 2 +k+1 (T 2 -T 1 )-(4k 2 +k+1) < 2 . We then have τ ≥ 1 k -2 , and so there exists a vital point on the cycle such that the time between some two successive visits of robots following A to this point is greater than 1 k -2 , which is what we needed to prove. Proof. (sketch) Let (v 0 , v 1 , . . . , v 2k ) be 2k + 1 vital points chosen in accordance with the assumptions of the lemma. For the proof of the lower bound, we introduce the concept of a shadow robot, which can be seen as an auxiliary robot which temporarily appears in the system and assists robots in their patrolling task. More precisely, given a strategy A, consider the trajectory of a robot r j . Suppose that the robot leaves a vital point v i at some time t a , moves to an adjacent vital point v i 1 ∈ {v i-1 , v i+1 } and then returns to point v i at time t b , without encountering any other vital points within the interval [t a , t b ].

We say that a shadow robot r i * j is created at time t a at point v i , waits at v i protecting it until time t b , and then disappears. The addition of such a shadow robot, obviously, cannot increase the idleness of the strategy. The proof now proceeds by similar (though slightly more technical) arguments as the proof of Lemma 3.5, subject to the inclusion of shadow robots in the team of patrolling robots. The details are provided in the Appendix.

To complete the proof of Theorem 3.3, we consider an arbitrary terrain C = (V, N ). Let B be the length of the longest neutral interval of C, as defined in Lemma 3.3. We have two cases to consider.

• If B ≥ 1/(2k), then by clause (1) of Lemma 3.4, there exists a subset of k + 1 vital points {v 0 , . . . , v k } ⊆ V such that for these points, in Lemma 3.5 we have s = min{1/(2k), L}. Now, by Lemma 3.5 we obtain that for any strategy A, the idleness is lower bounded by I(A) ≥ min{1/k, 2s} = min{1/k, 2L}.

• If B < 1/(2k), then by clause (2) of Lemma 3.4, there exists a subset of 2k + 1 vital points {v 0 , . . . , v 2k } ⊆ V that satisfies the assumptions of Lemma 3.6. Thus, by Lemma 3.6 we obtain that for any strategy A, the idleness is lower bounded by I(A) ≥ 1/k.

In either case, we obtain that the idleness of any strategy patrolling C is at least min{1/k, 2L}, which proves the claim of the Theorem.

Computing Optimal Robot Trajectories

Let C = (V, N ) be the unit segment [0, 1] with vital and neutral regions. Assume w.l.o.g. that the vital intervals in C are arranged in a data structure from left to right as

V i = [b i , e i ], for i = 1, 2, . . . , n where b 1 = 0, b i ≤ e i < b i+1 .
We assume that arithmetic operations involving these values can be performed in unit time.

Recall that in this case the solution is based on the use of lids, where with each lid we associate a different robot. We show first that one can test in time O(min{n, k log n}) whether for a collection of k lids each of length d can cover all vital points in [0, 1].

We propose a recursive procedure T estLidSize(k, d, p) that operates on sub-intervals of the form [p, 1] of C, where k stands for the number of available lids and d ≤ 1 refers to the uniform length of the lids. The procedure returns value true if all vital points in C can be covered with the collection of k lids. Otherwise the returned value is f alse. We now show how to efficiently compute the optimal (minimal) size of the lid. We will need the following lemma. Lemma 4.2 If L is the optimal (minimal) size of lids, there must be some integer

1 ≤ l ≤ k, s.t, L = e j -b i l , for some 1 ≤ i ≤ j ≤ n.
We now present the algorithm that computes the optimal size of lids. Using Lemma 4.2, one can observe that we need to test at most O(kn 2 ) values in search for the optimal size of lids. We can sort these values in time O(kn 2 log n) and later use binary search to find the optimal value. The number of tests during the binary search is O(log n) and the cost of each test is O(min{n, k log n}), see Lemma 4.1. Thus the total complexity is dominated by sorting performed in time O(kn 2 log n).

Observation 4.3

The optimal size of lids can be computed in time O(kn 2 log n).

The complexity of this algorithm can be further improved if we use an implicit representation of O(kn 2 ) candidates based on values e j -b i l , for 1 ≤ i ≤ j ≤ n and 1 ≤ l ≤ k, and perform search for the optimal size of lids in a more sophisticated fashion. We perform search among values based on each l separately.

Let M l i represent implicitly the list of values ( e i -b i l , e i+1 -b i l , . . . , en-b i l ), for 1 ≤ i ≤ n. Each list M l i contains at most n values. Any value from this list can be calculated on the basis of the sequence e i , . . . , e n , where values e 1 through e n are stored in an array of length n. In particular, using this representation one can calculate the value of any requested element in M l i in constant time. The search algorithm operates in rounds, processing all M l i s, with 1 ≤ i ≤ n and 1 ≤ l ≤ k, simultaneously. At the beginning all entries in M l i are potential candidates for being the optimal length of the lids. During each round the list of candidates in half of M l i s is reduced by half but the remaining candidates in M l i always form a sublist of consecutive elements in M l i . The reduction process in each round is performed as follows.

Procedure FastLidSearch (C): {true, f alse}; repeat in consecutive rounds 1. Find the medians m l i among the remaining candidates in each non-empty list M l i .

2. Find the median m * among all m l i , ranging over indices

1 ≤ i ≤ n, 1 ≤ l ≤ k corresponding to non-empty M l i s.
3. Use procedure T estLidSize to test whether m * is long enough.

4. And if yes, reduce by half the content of lists M l i with m l i > m * .

Otherwise, reduce by half the content of lists

M l i with m l i < m * .
until only one candidate value is left.

Note that the cost of each round, in which there are a ≤ kn non-empty lists M l i , can be bounded by O(a + min{n, k log n}). We will now compute the bound on the total number of rounds. At the start we associate with each list M l i a potential of log n. This means that the combined potential of all lists is kn log n. During each round the potential of half of the lists is reduced by 1. Eventually some lists M l i become empty which is reflected in the null potential. Note that until at least kn 2 lists are non-empty the combined potential is reduced by kn 4 during each round. Thus the number of rounds with at least kn 2 non-empty lists is limited by (kn log n)/( kn 4 ) = 4 log n, and the total duration of these rounds is O(log n • (kn + min{n, k log n})). Furthermore, we reduce the number of non-empty lists from kn 2 to nk 4 also in at most ( kn 2 log n)/( kn 8 ) = 4 log n rounds, and the total duration of these rounds is O(log n • ( kn 2 + min{n, k log n})). Thus, if we continue this process until only one element in one list is left, the total time of execution can be bounded as:

O log(kn) j=0 log n • ( kn 2 j + min{n, k log n}) = O(kn log n+log n(log n+log k) min{n, k log n}) = = O(kn log n + k log 3 n + n log k log n) = O(kn log n).

Corollary 4.4

The optimal size of lids can be computed in time O(kn log n).

This approach is also applicable to the combined strategy on the cycle, since, in fact, the optimal lid size only needs to be computed in the case when the cycle contains some neutral region N i of length at least 1/(2k). Then, the problem on the cycle C reduces to that on the closed segment C \ N i . We have the following:

Theorem 4.5 Consider k robots patrolling a boundary cycle (resp., segment) with n vital regions. The robot trajectories which result in minimal idleness can be described using the combined strategy (resp., the partition strategy). Such a description can be computed using an O(kn log n) algorithm.

to the claim of (2'), such that for any other terrain (V , N ) which violates clause (2') it holds that V V . (Such an inclusion-wise minimal counterexample always exists, since the set of vital points is by assumption a closed set.) By the minimality of V , the set of its vital points must be discrete, say, V = {u 0 , . . . , u n-1 }. Suppose that for some 0 ≤ i ≤ n, we have dist(u i , u (i+2) mod (n) ) ≤ 1/(2k). The terrain (V \ {u i+1 }, N ∪ {u i+1 }) has no neutral intervals of length greater than 1/(2k), and thus is a smaller counterexample to our claim, a contradiction. It follows that min 0≤i<n dist(u i , u (i+2) mod (n) ) > 1/(2k). Since for all 0 ≤ i < n, dist(u i , u (i+1) mod (n) ) < 1/(2k), we must have n ≥ 2k + 1. So, choosing points {v 0 , . . . , v 2k } as v i = u i , for all 0 ≤ i ≤ 2k, we find in V the subset of vital points satisfying clause (2'). So, V cannot be a counter-example to the claim.

Proof of Lemma 3.5

Proof. Let (v 0 , v 1 , . . . , v k ) be k + 1 vital points chosen so that dist(v i , v (i+1) ) ≥ s, for all 0 ≤ i ≤ k.
Throughout the proof, indices of points and robots are understood modulo k + 1, i.e. v i ≡ v i mod (k+1) and r j ≡ r j mod (k+1) . We will show that the claim holds even if {v 0 , v 1 , . . . , v k } are the only vital points of the cycle.

Fix > 0. Consider a strategy A such that I(A) < 2s -2 . To prove the lemma, we will show that there exists a point v i , 0 ≤ i ≤ k, such that the time between some two consecutive visits of a robot to point v i is greater than τ = 1 k -. Without loss of generality, by modifying the trajectories of the robots, we can convert a strategy A into another strategy A so that the following properties are satisfied by A :

(i) if a robot following A leaves some vital point v i , then it does not reenter this vital point before reaching some other vital point first (namely, v i-1 or v i+1 ), (ii) no two robots following A ever meet, (iii) if a vital point is visited by a robot following strategy A at time t, then it is visited by a robot following strategy A within the interval [t -4 , t + 4 ].

For completeness, we outline the technical steps which are required to perform the above conversion. First, property (i) is achieved by modifying the trajectories of the robots in neutral regions, only. Next, properties (ii) and (iii) can be ensured by first converting the strategy to one which preserves the ordering of the robots as in Lemma .6, and then delaying the movements of some of the robots to avoid meetings, without changing the time intervals during which a vital point is occupied by more than 4 . By property (iii), if a point is unvisited by A in time interval [t 1 , t 2 ], then it is unvisited by A in the time interval [t 1 + 4 , t 2 -4 ]. It now suffices to show that the time between some two consecutive visits of a robot following strategy A to point v i is greater than τ + 2 = 1 k -2 . Moreover, I(A ) ≤ I(A)+ 2 < 2s. From now on we consider robots following A , only.

Since no two robots following A ever meet by (ii), we can denote an arbitrarily chosen robots by r 1 , and the other robots by r 2 , . . . , r k in clockwise order; this order never changes throughout the traversal.

Suppose that at some time t, some robot r j leaves point v i on the arc towards point v i+1 . By (i), the next vital point it reaches has to be point v i+1 . Therefore, robot r j cannot reenter point v i before time t + 2dist(v i , v i+1 ) ≥ t + 2s > t + I(A ). So, some other robot must visit point v i in between the two visits by robot r j . Since the robots never meet, it follows that within the time interval [t, t + I(A )], robot r j-1 entered node v i . Before this visit, the previous vital point visited by r j-1 must have been v i-1 . It follows that to each traversal of the arc (v i , v i+1 ) by robot r j that starts at some time t, we can assign a distinct traversal of the arc (v i-1 , v i ) by robot r j-1 that ends within the time interval [t, t + I(A )]. Fix two values of time T 1 and T 2 , 0 ≤ T 1 < T 2 . From now on, we will apply certain counting arguments within the time interval [T 1 , T 2 ]. Let us denote by C j (i, i + 1) the number of traversals of arc (v i , v i+1 ) by robot r j starting in the time interval [T 1 , T 2 ]. Since only the first and last traversals of (v i , v i+1 ) by robot r j within this time interval may be unmatched by corresponding traversals of (v i-1 , v i ) by robot r j-1 within the same time interval, we have:

C j (i, i + 1) -C j-1 (i -1, i) ≤ 2.
Let C(i, i + 1) = k j=1 C j (i, i + 1) be the total number of traversals of the arc (v i , v i+1 ) by all robots starting within the time interval [T 1 , T 2 ]. Summing the above inequalities, we have:

C(i, i + 1) -C(i -1, i) ≤ 2k.
An analogous analysis can be performed for the counter-clockwise direction, i.e., considering values of the form C(i + 1, i), corresponding to traversal of the arc from v i+1 to v i . We obtain:

C(i, i -1) -C(i + 1, i) ≤ 2k.
In general, by iterating the above around the cycle, for any two vital points v i 1 and v i 2 we obtain:

C(i 1 , i 1 + 1) -C(i 2 , i 2 + 1) ≤ 2k 2 .
Denoting by C cw = min 0≤i≤k C(i, i + 1), we have for any i:

C(i, i + 1) ≤ C cw + 2k 2 .
An analogous analysis can be performed for the counter-clockwise direction, i.e., considering values of the form C(i + 1, i), corresponding to traversal of the arc from v i+1 to v i . Consequently, denoting C cc = min 0≤i≤k C(i + 1, i), we have for any i:

C(i + 1, i) ≤ C cc + 2k 2 .
Now, denote by W j (i) ≥ 0 the total time spent by robot r j at point v i within the time interval [T 1 , T 2 ], and let W (i) = k j=1 W j (i). Without loss of generality, let v 0 be a vital point with the minimal total waiting time, i.e., W (0) = min 0≤i≤k W (i).

With respect to point v 0 , the trajectory of each robot r j within the time interval [T 1 , T 2 ] can be described by an ordered sequence of time moments (e 1 j , l 1 j , e 2 j , l 2 j , . . . , l n j j ), where e p j is the time at which robot r j enters point v 0 for the p-th time, whereas l p j is the time at which robot r j leaves point v 0 for the p-th time. We assume that T 1 ≤ e 1 j ≤ l 1 j < e 2 j ≤ l 2 j < . . . < e n j j ≤ l n j j ≤ T 2 , where we put e 1 j = T 1 if robot r j was located at node v 0 at time T 1 , and l n j j = T 2 if robot r j was located at node v 0 at time T 2 . For the sake of notation, let l 0 j = T 1 and e n j +1 j = T 2 . During the time interval [T 1 , T 2 ], point v 0 is covered by a robot during the set of moments X given as:

X = k j=1 n j p=1 [e p j , l p j ],
such that |X| = W (0). During the remaining time, i.e. X = [T 1 , T 2 ] \ X, no robot is located at v 0 . We observe that X is a union of at most 1 + k j=1 n j intervals. Hence, there exists some time interval of length τ :

τ ≥ |X| 1 + k j=1 n j = (T 2 -T 1 ) -|X| 1 + k j=1 n j = (T 2 -T 1 ) -W (0) 1 + k j=1 n j (4)
during which v 0 remains unvisited.

Notice that each robot r j leaves point v 0 at least n j -1 times in the time interval [T 1 , T 2 ], going towards either point v 1 or point v k . Thus, we have:

C(0, 1) + C(0, k) ≥ k j=1 (n j -1) = k j=1 n j -k.
Taking into account that C(0, 1) ≤ C cw + 2k 2 and C(0, k) ≤ C cc + 2k 2 , we have:

k j=1 n j ≤ C cw + C cc + 4k 2 + k. (5)
Moreover, since each arc of the cycle is traversed in either direction a total of at least C cw + C cc times, the total distance covered by all the robots is at least C cw + C cc . Thus, the total time of movement of all k robots within the time interval [T 1 , T 2 ] is at least C cw + C cc , and we have the following inequality:

C cw + C cc + k i=0 W (i) ≤ k(T 2 -T 1 ) C cw + C cc ≤ k(T 2 -T 1 ) -(k + 1)W (0). (6)
Combining inequalities ( 4), ( 5), and ( 6), we obtain:

τ ≥ (T 2 -T 1 ) -W (0) k(T 2 -T 1 ) -(k + 1)W (0) + 4k 2 + k + 1 ≥ 1 k + 4k 2 +k+1-W (0) (T 2 -T 1 )-W (0) ≥ ≥ 1 k + 4k 2 +k+1 (T 2 -T 1 )-(4k 2 +k+1) > 1 k - 4k 2 + k + 1 (T 2 -T 1 ) -(4k 2 + k + 1)
.

In the above, we assumed that (T 2 -T 1 ) -W (0) > 0, i.e., there cannot be a robot covering v 0 throughout the time interval [T 1 , T 2 ]. This is true, since otherwise, taking into account that W (i) ≥ W (0) for all 1 ≤ i ≤ k, all k + 1 points would have to be covered by a robot throughout [T 1 , T 2 ], and there are only k robots, a contradiction. Now, suppose that T 2 is chosen to be sufficiently large so that 4k 2 +k+1 (T 2 -T 1 )-(4k 2 +k+1) < 2 . We then have τ ≥ 1 k -2 , and so there exists a vital point on the cycle such that the time between some two successive visits of robots following A to this point is greater than 1 k -2 . This completes the proof of Lemma 3.5.

Proof of Lemma 3.6

Proof. Let (v 0 , v 1 , . . . , v 2k ) be 2k + 1 vital points chosen in accordance with the assumptions of the lemma. For the proof of the lower bound, we introduce the concept of a shadow robot, which can be seen as an auxiliary robot which temporarily appears in the system and assists robots in their patrolling task. More precisely, given a strategy A, consider the trajectory of a robot r j . Suppose that the robot leaves a vital point v i at some time t a , moves to an adjacent vital point v i 1 ∈ {v i-1 , v i+1 } and then returns to point v i at time t b , without encountering any other vital points within the interval [t a , t b ]. We say that a shadow robot r i * j is created at time t a at point v i , waits at v i protecting it until time t b , and then disappears. The addition of such a shadow robot, obviously, cannot increase the idleness of the strategy.

Observe that one robot can create at most two shadow robots at a time: when r j is located anywhere within a closed arc [v i , v i+1 ], then it may only have the shadow robots r i * j and r (i+1) * j

. Robot r j and its shadow robots can wait at not more than two vital points simultaneously.

Will show that the claim holds even if {v 0 , v 1 , . . . , v 2k } are the only vital points of the cycle. The rest of the proof proceeds analogously to the proof of Lemma 3.5, subject to the inclusion of shadow robots in the team of robots patrolling the terrain. Once again, for a fixed > 0, we modify the trajectories of the robots, converting any strategy A into another strategy A fulfilling the following properties:

(i) if a robot following A leaves some vital point v i , then it does not reenter this vital point before reaching some other vital point first (namely, v i-1 or v i+1 ), (ii) no two robots following A ever meet each other or the shadow robots of other robots, (iii) if a point P is visited by a robot following strategy A at time t, then it is visited by a robot or shadow robot following strategy A within the interval [t -4 , t + 4 ].

From now on we consider robots (r 1 , r 2 , . . . , r k ) and their shadow robots following A , only, and proceed to perform a modification of the proof of Lemma 3.5 which takes shadow robots into account.

Suppose that I(A ) < 1/k -. We will call a traversal of the directed arc (v i , v i+1 ) by robot r j shadowless if after arriving at v i+1 , the next vital point visited by robot r j is v i+2 (not v i ). Equivalently, a traversal of arc (v i , v i+1 ) is shadowless if r j does not leave its shadow robot r i * j at v i during this traversal. Fix a time interval [T 1 , T 2 ]. For all 0 ≤ i ≤ 2k, we will denote by C j (i, i + 2) the number of shadowless traversals of the directed arc (v i , v i+1 ) by robot r j starting in this time interval. Suppose that robot r j initiates a shadowless traversal at some time t. Since dist(v i , v i+2 ) > 1 2k by assumption, we have that the next visit of this robot to v i takes place after time t + 1/k > t + I(A ). Since v i is not occupied by a shadow robot, the robot r j-1 must arrive at point v i at some time t ∈ (t, t + 1/k). The previous vital point occupied by robot r j-1 before t must have been v i-1 . Before that, the robot cannot have occupied vital point v i , since then, during its traversal from v i to v i-1 and back to v i , the shadow robot r i * j-1 would have existed at v i . This shadow robot must have met robot r i at point v i at time t, which contradicts the assumption that robots and shadow robots do not meet. It follows that before arriving at v i-1 robot r j-1 must have been located at v i-2 . Thus, robot r j-1 was performing a shadowless traversal of (v i-2 , v i-1 ). This traversal counts towards C j-1 (i -2, i) if robot r j left v i-2 within the interval [T 1 , T 2 ]. Following the reasoning from Lemma 3.5, we obtain the following bound:

C j (i, i + 2) -C j-1 (i -2, i) ≤ 2.
Summing the above inequalities over all robots, and performing the analysis for the counter-clockwise direction we have:

C(i, i + 2) -C(i -2, i) ≤ 2k.

C(i, i -2) -C(i + 2, i) ≤ 2k.

Since the number of points 2k + 1 is odd, by iterating the above around the cycle at most 2k times in one direction, for any two vital points v i 1 and v i 2 we obtain:

C(i 1 , i 1 + 2) -C(i 2 , i 2 + 2) ≤ 2k 2 . C(i 1 , i 1 -2) -C(i 2 , i 2 -2) ≤ 2k 2 .
Denoting C cw = min 0≤i≤2k C(i, i + 2) and C cc = min 0≤i≤2k C(i + 2, i), we have for any i:

C(i, i + 2) ≤ C cw + 2k 2 . C(i + 2, i) ≤ C cc + 2k 2 .
Now, denote by W j (i) ≥ 0 the total time spent by robot r j at point v i and by its shadow r i * j within the time interval [T 1 , T 2 ], and let W (i) = k j=1 W j (i). Without loss of generality, let v 0 be a vital point with the minimal total waiting time, i.e., W (0) = min 0≤i≤2k W (i).

With respect to point v 0 , the trajectory of each robot r j within the time interval [T 1 , T 2 ] can be described by an ordered sequence of time moments (e 1 j , l 1 j , e 2 j , l 2 j , . . . , l n j j ), where e p j is the time at which robot r j enters point v 0 for the p-th time after a shadowless traversal (of arc (v 2k-1 , v 2 k) or (v 2 , v 1 )), whereas l p j is the time at which robot r j leaves point v 0 starting its p-th shadowless traversal (of arc (v 0 , v 1 ) or (v 0 , v 2k )). We assume that T 1 ≤ e 1 j ≤ l 1 j < e 2 j ≤ l 2 j < . . . < e n j j ≤ l n j j ≤ T 2 , and make the same boundary assumptions as in the proof of Lemma 3.5.

During the time interval [T 1 , T 2 ], point v 0 is covered by some robot or some shadow robot during the set of moments X given as:

X = k j=1 n j p=1
[e p j , l p j ],

such that |X| = W (0). During the remaining time, i.e. X = [T 1 , T 2 ] \ X, no robot and no shadow robot is located at v 0 . We observe that X is a union of at most 1 + k j=1 n j intervals. Hence, there exists some time interval of length τ during which point v 0 remains unvisited, lower-bounded by an inequality of the same form as (1):

τ ≥ |X| 1 + k j=1 n j = (T 2 -T 1 ) -|X| 1 + k j=1 n j = (T 2 -T 1 ) -W (0) 1 + k j=1 n j (7)
Notice that each robot r j leaves point v 0 at least n j -1 times in the time interval [T 1 , T 2 ], embarking on a shadowless traversal of the arc either to point v 1 (and then to v 2 ) or to point v 2k (and then to v 2k-1 ). Thus, we have:

C(0, 2) + C(0, 2k -1) ≥ k j=1 (n j -1) = k j=1 n j -k.
Taking into account that C(0, 2) ≤ C cw + 2k 2 and C(0, 2k -1) ≤ C cc + 2k 2 , we have:

k j=1 n j ≤ C cw + C cc + 4k 2 + k. (8)
For any robot r j , we trace its trajectory within the time interval [T 1 , T 2 ], looking at the number of shadow robots in time. At any time, r j and its shadow robots may be waiting at at most two vital points in total. Moreover, suppose that r j embarks on a shadowless traversal of some arc (v i , v i+1 ), leaving v i at some moment of time t, arriving at v i+1 not earlier than at time t + dist(v i , v i+1 ). Then, throughout the time interval [t, t + dist(v i , v i+1 )], robot r j can have at most one shadow located at v i+1 . Suppose this shadow robot r (i+1) * j exists. Then, the last traversal of r j preceding time t must have been one of the arc (v i+1 , v i ), and not shadowless. Tracing back in time the zig-zags of robot r j between points v i , v i+1 , during which it had shadows at both v i and v i+1 , we come back to the earliest traversal of arc (v i , v i+1 ) (or possibly arc (v i+1 , v i ), directly after the robot's arrival from v i-1 (respectively, from v i+2 ). During this traversal, of duration at least dist(v i , v i+1 ), robot r j had precisely one shadow located at v i (respectively, at v i+1 ). In summary, we have shown that during every shadowless traversal of arc (v i , v i+1 ), robot r j either has no shadow, or it has exactly 1 shadow and we can associate with this traversal another time period of length dist(v i , v i+1 ) during which it has exactly 1 shadow (with no overlap of time periods). The same argument applies for the counter-clockwise direction. Thus, we obtain a bound on the total waiting time of robot r j and its shadows:

2k i=0 W j (i) ≤ 2(T 2 -T 1 ) -2 2k i=0 (C j (i, i + 2) + C j (i + 1, i -1) -2)dist(v i , v i+1 ),

Cyclic strategy. Observation 3 . 2

 32 The idleness of the combined strategy on the cycle is I = min{1/k, 2L}, where L is the minimum possible lid size of a (L, k)-lid cover of the cycle.

Theorem 3 . 3

 33 The idleness I(A) of any traversal strategy A in a cycle with neutral regions satisfies I ≥ min{1/k, 2L}, where L is the minimum possible lid size of a (L, k)-lid cover of the cycle.

Lemma 3 . 4 (

 34 Critical point lemma) Let C = (V, N ) be a cycle with set of vital regions V . Let L be the minimum size of the lid cover of the vital regions of C with k lids, and let B = sup{dist(e, b) : b, e ∈ [0, 1], [b, e] ⊆ N }. Then:

Lemma 3 . 6 (

 36 2k + 1 point lemma) Let (v 0 , v 1 , . . . , v 2k ) be a set of 2k + 1 points chosen from vital regions of the terrain, arranged in clockwise order along the cycle, s.t. dist(v i , v (i+2) mod (2k+1) ) > 1 2k . The idleness I(A) of any traversal strategy A for k mobile robots in this terrain satisfies I(A) ≥ 1 k .

Lemma 4 . 1

 41 Procedure TestLidSize(k, d, p): {true,false}; 1. Use the next available lid to cover segment [p, p + d]; 2. if (p + d) ≥ e n then return(true); /* all vital points are covered */ 3. p * = inf{p ∈ V : p > p + d}; /* p * exists since p + d < e n . */ 4. if (k > 1) then return(T estLidSize(k -1, d, p * )) else return(f alse); For any positive integer k, d > 0, and p ∈ C = (V, N ), such that p is vital, procedure T estLidSize(k, d, p) verifies in time O(min{n, k log n}) whether all vital points in [p, e n ] can be covered by k lids of length d.

  ii) no two robots following A ever meet, (iii) if a vital point is visited by a robot following strategy A at time t, then it is visited by a robot following strategy A within the interval [t -4 , t + 4 ].

By property (iii), if a point is unvisited by

A in time interval [t 1 , t 2 ], then it is unvisited by A in the time interval [t 1 + 4 , t 2 -4 ]

. So, it now suffices to show that the time between some two consecutive visits of a robot following strategy A to point v i is greater than τ + 2 = 1 k -2 . Moreover, I(A ) ≤ I(A) + 2 < 2s. From now on we consider robots following A , only.

APPENDIX Proof of Theorem 2.1

To prove the theorem, we start by showing a property of a greedy cover of the segment with lids.

Lemma .6 Suppose that L is the minimum value such that a given terrain C admits a (L, k)-lid cover, and let L < L. Then, the region C \ [0, L ] does not admit a (L , k -1)-lid cover.

Proof. Indeed, if the region C \ [0, L ] admitted a (L , k -1)-lid cover, then one could obtain a (L , k)-lid cover of C simply by adding lid [0, L ] to the lid cover obtained for the region C \ [0, L ]. This contradicts the minimality of L.

Lemma .7 Any patrolling strategy may be converted to a strategy, achieving the same idleness, for which the relative order of the mobile robots on the segment is maintained throughout the traversal.

Proof. The proof is based on the simple observation that when two mobile robots meet while moving in opposite directions they can "exchange" roles, so that the coverage of the points on the segment by one robot is the same as coverage by the other. Since after this change of roles the set of visited nodes at any time remains the same, this does not affect the idleness of visited nodes.

The proof of the claim I ≥ 2L now proceeds by induction on the number of robots. It is clearly true for k = 1, since the idleness of the strategy cannot be smaller than twice the distance between the extremal vital points C, which corresponds precisely to the size of the smallest lid cover.

Suppose, by contradiction, that there exists a value of k and some terrain C such that the idleness of some patrolling strategy A is I = 2L < 2L. By Lemma .7, w.l.o.g. we can assume that the robots never change places along the segment. Consider the trajectory of the leftmost robot r 1 following strategy A. Let c be the supremum of all points along the segment reached by robot r 1 . If point c is reached by robot r 1 at some time t, its last visit to point 0 must have been no later than at time t -c, and the next visit to point 0 will take place at time not earlier than t + c. From Lemma .7, we have that point 0 is never visited by any robot when it is not visited by r 1 . Consequently, we must have 2c ≤ 2L , and so c ≤ L . It follows that the region C \ [0, L ] must be patrolled solely by the set of k -1 robots, without the help of r 1 , with idleness at most 2L . From the inductive assumption, we have that C \ [0, L ] admits a L -lid cover. This is a contradiction, by Lemma .6. This completes the proof of Theorem 2.1.

Proof of Lemma 3.4

Proof. To prove clause (1), let v 0 be the first vital point located at the clockwise endpoint of a neutral region of length B. Fix > 0 and consider the set of points chosen iteratively as follows: let v i+1 be the first vital point located at arc distance not less than Lfrom v i , moving in the clockwise direction. We claim that point v k is reached before completing one full rotation around the cycle, starting from v 0 . Indeed, if this were not the case, then there would exist a set of k lids:

covering the whole of V , a contradiction with the minimality of lid cover size L. Finally, note that the distance between points v 0 and v k is at least B ≥ 1/(2k). Parametrizing each of the points v i as v i ( ), it follows that for any > 0, we can find a set of k + 1 points (v 0 ( ), v 1 ( ), . . . , v k ( )) such that min 0≤i≤k dist(v i ( ), v (i+1) mod (k+1) ( )) ≥ min{1/(2k), L} -. By taking into account that the set of vital points V is a closed set and v i ( ) is non-decreasing and bounded (w.r.t. shifts in the clockwise direction) for any sequence 0, we converge to a sequence of vital points (v 0 (0), . . . , v k (0)) satisfying clause [START_REF] Ponce | The Art Gallery Theorem and Algorithm[END_REF].

To prove clause (2), we will show a slightly stronger version "(2')" of this clause in which we replace the assumption "B < 1/(2k)" by "B ≤ 1/(2k)". Suppose that terrain (V, N ) is a counterexample where the constant is subtracted from C j to account for boundary conditions around times T 1 and T 2 . Summing over all k robots we obtain:

Taking into account that the circumference of the cycle is 1 and that W (0) is the minimum of all W (i), we have:

and finally:

(compare inequality (3)). Combining inequalities ( 7), [START_REF] Chin | Shortest watchman routes in simple polygons[END_REF], and ( 9), we obtain:

In the above, we assumed that (T 2 -T 1 ) -W (0) > 0, i.e., there cannot be a robot covering v 0 throughout the time interval [T 1 , T 2 ]. This is true, since otherwise, taking into account that W (i) ≥ W (0) for all 1 ≤ i ≤ k, all 2k + 1 points would have to be covered by a robot or its shadow robot throughout

and there are at most 2k robots and shadow robots in total at any time, a contradiction. Now, suppose that T 2 is chosen to be sufficiently large so that

(T 2 -T 1 )-2(4k 2 +k+3) < 2 . We then have τ ≥ 1 k -2 , and so there exists a vital point on the cycle such that the time between some two successive visits of robots following A to this point is greater than 1 k -2 . This completes the proof of the lemma.

Proof of Lemma 4.1

Proof. We first show that our recursive procedure performs verification correctly. In the proof we use induction on k. More precisely, we assume inductively that for any 1 ≤ l < k and q ∈ C the call T estLidSize(l, d, q) verifies whether one can cover all valid points in the interval [q, e n ] using l lids of length d.

Proof of Lemma 4.2

Proof. Consider any cover based on lids with the minimal size. In such a cover one can arrange the lids so that they touch but do not overlap with each other. If such an arrangement is not possible, one could decrease the length of the lids, contradicting the minimality of their length. Thus, we can assume that in the cover all the lids are partitioned into maximal sequences, such that in each sequence the lids are placed tightly one after another, but different sequences do not share their endpoints. Consider any such sequence based on m lids. The left endpoint of the leftmost lid in this sequence must coincide with some b i . Otherwise, this would not be the leftmost lid in the sequence. If the right endpoint of the rightmost (m-th) lid in this sequence coincides with some e j , the claim of the lemma follows. Assume, to the contrary, that this is not the case for any maximal sequence of lids. This means that the last lid in each maximal sequence overlaps with some neutral region, and consequently, that the length of the lids could be decreased.


Amélie Rochet-Capellan
email: amelie.rochet-capellan@gipsa-lab.grenoble-inp.fr

Susanne Fuchs
email: fuchs@zas.gwz-berlin.de

The interplay of linguistic structure and breathing in German spontaneous speech

Keywords: spontaneous speech, breathing kinematics, breath group, inhalation pauses, syntactic clause, hesitation

This paper investigates the relation between the linguistic structure of the breath group and breathing kinematics in spontaneous speech. 26 female speakers of German were recorded by means of an Inductance Plethysmograph. The breath group was defined as the interval of speech produced on a single exhalation. For each group several linguistic parameters (number and type of clauses, number of syllables, hesitations) were measured and the associated inhalation was characterized. The average duration of the breath group was ~3.5 s. Most of the breath groups consisted of 1-3 clauses; ~53% started with a matrix clause; ~24% with an embedded clause and ~23% with an incomplete clause (continuation, repetition, hesitation). The inhalation depth and duration varied as a function of the first clause type and with respect to the breath group length, showing some interplay between speech-planning and breathing control. Vocalized hesitations were speaker-specific and came with deeper inhalation. These results are informative for a better understanding of the interplay of speech-planning and breathing control in spontaneous speech. The findings are also relevant for applications in speech therapies and technologies.

Introduction

On a time-scale of several seconds, speech production is a sequence of short inhalations pauses followed by long exhalations with phonation. The interval of speech produced on a single exhalation is commonly defined as the breath group. It relies on linguistic, communicative and physiological constraints. The breath group is also an important unit for prosody and speech perception [START_REF] Lieberman | Intonation, Perception and Language[END_REF]. The present paper analyses the breath group in German spontaneous speech with respect to two main questions: [START_REF] Lieberman | Intonation, Perception and Language[END_REF] What is the linguistic structure of the breath group? (2) Is this structure anticipated during inhalation?

The relation of the inhalation depth and duration to the linguistic structure of the upcoming breath group reflects the interplay of speech-planning with ventilation [START_REF] Henderson | Temporal patterns of cognitive activity and breath control in speech[END_REF][START_REF] Grosjean | Breathing, pausing and reading[END_REF][START_REF] Conrad | Speech and respiration[END_REF][START_REF] Conrad | Speech respiration as an indicator of integrative contextual processing[END_REF][START_REF] Winkworth | Variability and consistency in speech breathing during reading: lung volumes, speech intensity, and linguistic factors[END_REF][START_REF] Winkworth | Breathing patterns during spontaneous speech[END_REF][START_REF] Mitchell | Cognitive-linguistic demands and speech breathing[END_REF]. These relations have been investigated in both read and spontaneous speech. These studies involved different speech tasks (e.g. sentences and texts reading, spontaneous speech with different cognitive load) and estimated breathing parameters with different methods (detection of breath noises, e.g. [START_REF] Henderson | Temporal patterns of cognitive activity and breath control in speech[END_REF][START_REF] Bailly | Pauses and respiratory markers of the structure of book reading[END_REF]; measurement of the air flow from the mouth and nose, e.g. [START_REF] Teston | L' aérodynamique du souffle phonatoire utilisé dans la lecture d'un texte en français[END_REF]; monitoring of the kinematics of the chest wall, e.g. [START_REF] Grosjean | Breathing, pausing and reading[END_REF][START_REF] Conrad | Speech and respiration[END_REF][START_REF] Conrad | Speech respiration as an indicator of integrative contextual processing[END_REF][START_REF] Winkworth | Variability and consistency in speech breathing during reading: lung volumes, speech intensity, and linguistic factors[END_REF][START_REF] Winkworth | Breathing patterns during spontaneous speech[END_REF][START_REF] Mitchell | Cognitive-linguistic demands and speech breathing[END_REF][START_REF] Sperry | Speech breathing in senescent and younger women during oral reading[END_REF][START_REF] Whalen | Exploring the relationship of inspiration duration to utterance duration[END_REF][START_REF] Fuchs | Acoustic and respiratory evidence for utterance planning in German[END_REF][START_REF] Mcfarland | Effects of vocal task and respiratory phase on prephonatory chest wall movements[END_REF][START_REF] Wang | Breath group analysis for reading and spontaneous speech in healthy adults[END_REF][START_REF] Huber | Effects of utterance length and vocal loudness on speech breathing in older adults}[END_REF], see also [START_REF] Wang | Accuracy of perceptual and acoustic methods for the detection of inspiratory loci in spontaneous speech[END_REF] for a comparison between acoustic and kinematic methods).

Several studies show an anticipation of the breath group length during the preceding inhalation for sentence and text reading. The inhalation depth and duration increase with the sentence length [START_REF] Winkworth | Variability and consistency in speech breathing during reading: lung volumes, speech intensity, and linguistic factors[END_REF][START_REF] Sperry | Speech breathing in senescent and younger women during oral reading[END_REF][START_REF] Whalen | Exploring the relationship of inspiration duration to utterance duration[END_REF][START_REF] Fuchs | Acoustic and respiratory evidence for utterance planning in German[END_REF][START_REF] Mcfarland | Effects of vocal task and respiratory phase on prephonatory chest wall movements[END_REF][START_REF] Huber | Effects of utterance length and vocal loudness on speech breathing in older adults}[END_REF]. Furthermore, inhalations in sentence reading are not clearly related to the syntactic complexity (number of clauses) of the upcoming breath group [START_REF] Whalen | Exploring the relationship of inspiration duration to utterance duration[END_REF][START_REF] Fuchs | Acoustic and respiratory evidence for utterance planning in German[END_REF]. In text reading, almost 100 % of the inhalation pauses occurs at syntactic boundaries, indicated by punctuation marks or conjunctions (e.g. and). These results show that the breath groups are syntactically structured [2-6, 8-10, 15]. In text reading, the inhalation depth and duration also differed with respect to syntactic marks (e.g. paragraph > period > comma) [START_REF] Conrad | Speech respiration as an indicator of integrative contextual processing[END_REF][START_REF] Winkworth | Variability and consistency in speech breathing during reading: lung volumes, speech intensity, and linguistic factors[END_REF].

In spontaneous speech, the breathing pauses are not only governed by syntax but also by the cognitive processing required to generate the linguistics content [START_REF] Henderson | Temporal patterns of cognitive activity and breath control in speech[END_REF][START_REF] Conrad | Speech and respiration[END_REF][START_REF] Winkworth | Breathing patterns during spontaneous speech[END_REF][START_REF] Mitchell | Cognitive-linguistic demands and speech breathing[END_REF][START_REF] Wang | Breath group analysis for reading and spontaneous speech in healthy adults[END_REF]. This process introduces disfluencies in the speech flow. In spontaneous speech about 80% of the breathing pauses occur at syntactic constituents; the average amplitude and duration of inhalation are similar to text reading and are reflecting the length of the upcoming breath group. The average duration of breath groups is also longer than in text reading [see: [START_REF] Conrad | Speech and respiration[END_REF][START_REF] Winkworth | Breathing patterns during spontaneous speech[END_REF][START_REF] Wang | Breath group analysis for reading and spontaneous speech in healthy adults[END_REF][START_REF] Mcfarland | Respiratory markers of conversational interaction}[END_REF][START_REF] Huber | Effect of cues to increase sound pressure level on respiratory kinematic patterns during connected speech}[END_REF]. The ranges of variability of these parameters are larger in spontaneous speech as compared to text reading. Spontaneous speech is also characterized by the production of vocalized hesitations (uh, um) that have been assumed to have different functions and have been related to breathing [START_REF] Ferreira | Disfluencies and human language comprehension[END_REF][START_REF] Schonle | Hesitation vowels: a motor speech respiration hypothesis[END_REF]. This paper evaluates the relationship between the kinematics of breathing and the linguistic structure of the breath group in German spontaneous speech. As in previous studies we consider the syntactic structure (number of clauses) and the number of syllables in the breath group. We also analyzed the type of clauses (matrix, embedded clause) and disfluencies (hesitationsuh, um, repetition, repairs...) in the breath group. The type of the first clause (matrix clause or embedded clause) in the breath group is an indicator of the location of inhalation relative to the linguistic structure. The association of breathing to disfluencies, and especially vocalized hesitations, is informative about the cognitive process involved in speech planning.

Experiment

Subjects

The participants were 26 female, native speakers of German (age: 25 years (mean) ±3.1 (standard deviation), body mass index 21.5 ±2.1). All participants had no known history of speech, language or hearing disorders.

Experimental settings and procedure

Participants were standing up in front of a directional microphone and two loudspeakers (Figure 1.A). The spontaneous speech task was part of larger experimental protocol. After a short recording of breathing at rest and short reading, participants were instructed to listen attentively to the audio recordings of ten brief texts (151±22.1 syllables), read by a male or a female native speaker of German. The tracks were played back through the loudspeakers. After listening to each text, participants briefly summarized the story. In order to limit the movements that could interfere with the monitoring of breathing kinematics, participants were instructed to keep their hands along their trunk. Vital capacity (VC) maneuvers were run at the end of the procedure to estimate the displacement of the rib cage and the abdomen induced by VC. To do so, subjects exhaled as much air as they could and then inhaled as much air as they could.

Data acquisition, processing and labeling

The rib cage and the abdominal kinematics were recorded by means of an Inductance Plethysmograph (Respitrace TM ). One band was positioned at the level of the axilla (rib cage) and the other band at the level of the umbilicus (abdomen, see Figure 1.A). The acoustic and the breathing signals were recorded synchronously by means of a six channels voltage data acquisition system. The gains were the same for the thorax and the abdomen and for all the participants. All signals were sampled at 11030 Hz, After the recording, the breathing data were sub-sampled at 200 Hz and pass-band filtered . The contribution of the rib cage and the abdomen to speech breathing varied according to the speaker. For some speakers, breathing cycles were not clear for the abdomen. For these reasons, we analyzed the sum of the rib cage and the abdomen displacements. As Respitrace TM was not calibrated, our measures could over-or sub-estimate the contribution of the thorax relative to the contribution of the abdomen to lung volume and should not be considered as a direct estimation of lung volume [START_REF] Konno | Measurement of the separate volume changes of rib cage and abdomen during breathing[END_REF][START_REF] Banzett | A simple and reliable method to calibrate respiratory magnetometers and Respitrace[END_REF]. To allow comparison between speakers and conditions, displacements were expressed for each subject in %MD (Maximal Displacement). MD was the displacement corresponding to the excursion of the rib cage and the abdomen during the VC maneuver. The onset and offset of inhalations were automatically detected on the breathing signal using the velocity profiles and zero crossing. The detection was then visualized and corrected when required. The breathing cycle was divided into an inhalation and an exhalation phase (Figure 1.B).

Speech productions were labeled in Praat [START_REF] Boersma | Praat, a System for doing Phonetics by Computer, version 3.4[END_REF] by detecting the onset and offset of vocalizations and by transcribing the spoken text for each breath group. The vocalized hesitations (e.g. uh, um) and the non-breathing pauses were distinguished (see Figure 1.C). On the basis of this transcription, the number of syllables was derived automatically from the output of the BALLOON toolkit [START_REF] Reichel | PermA and Balloon: Tools for string alignment and text processing[END_REF]. The syntactic labeling of the breath groups was done by a trained phonetician. The clauses were marked by distinguishing between matrix and embedded clauses. German is a language where the position of the auxiliary verb (verb second or verb final) defines the type of clause. Mainly, the clauses with a verb in a second position were considered as matrix (also called main) clauses and those with a verb final position were considered as embedded clauses. For instance, m-e1-e2 characterized a breath group that included one matrix clause followed by two embedded clauses, with the first one (e1) referring to the matrix clause (m), and the second one (e2) referring to the first embedded clause (e1), see Figure 1.C. The third category, uncompleted clauses (u), included words or groups of words corresponding to hesitations, repetitions or repairs.

Data selection

Our data set included 1467 breath groups. We discarded 45 groups that were perturbed by laugh, cough or body movements. The number of clauses ranged from 1 to 7 (2.11 (mean) ±1.13 (standard error)). The dataset was restricted to groups with 1-3 clauses. They represented 88% of the observations and were produced by all subjects. Only groups starting with m, e1, e2 or u were considered in this study (99% of the groups with 1-3 clauses).

Measures and analyses

We estimated: (1) the duration of the breath group (dur_g), as the time interval from speech onset to speech offset; (2) the amplitude (amp_I) and duration (dur_I) of inhalation; (3) the relationship between amp_I and the amplitude of exhalation (amp_IE, amp_I divided by the amplitude of exhalation). This last measure evaluates if speakers exhale more air (amp_IE < 1), less air (amp_IE > 1) or the same amount of air (amp_IE = 1) than they have just inhaled to produce the breath group. This measure could not be taken as an indicator of the reserve volume consumption, as displacements values were not expressed relative to a zero volume.

We considered four main factors: (1) the number of clauses in the breath group (n_clauses, 1, 2, 3); (2) the number of syllables n_syll (continuous factor); (3) the type of first clause f_clause (m, e1, e2, u); (4) the type of hesitation: t_hesi (levels: none, at least one at onset: onset, at least one not at onset: elsewhere).

The effects of n_syll, n_clauses and f_clause on the different parameters were tested as fixed factors effects using Linear Mixed Models (LMM), with subject as a random factor. The interactions between factors were not significant and therefore, additive models were calculated. For dur_I and amp_IE the log values were used to satisfy normality. An analysis of hesitation was introduced in a second step with subject as random factor and n_syll and t_hesi as fixed factors. All the effects reported significant were satisfying the criteria pMCMC <.01.

Results

Linguistic structure of the breath group

The average characteristics of the breath groups and their repartition according to the first clause and to the number of clauses are displayed in Table 1. Speakers produced from 13 to 99 breath groups (47.4 (mean) ±4.5 (sterr), Figure 2). Half of the breath groups (53%) started with a matrix clause (m), a quarter (24%) with and embedded clause and the last quarter (23%) with an uncompleted clause (u). On average, the breath group included ~15.9 syllables (range: 1 to 50), and lasted ~3.5 s (range: .17 to 12.1). The number of syllables and the duration of the groups significantly increased with the number of clauses (~+7.5 syllables and +1.5 s per supplementary clause), but were similar for groups starting with a matrix as compared to an embedded clause. Groups starting with an uncompleted clause were ~6 syllables and 1.1 s shorter than the other groups. The percentage of breath groups with vocalized hesitations ranged form 0 to more than 50% according to the subject (average 40%, see Figure 2). Among the breath groups with at least one hesitation (n=482), 40% started with a hesitation. Note that the groups with at least one hesitation not at the onset of the group were longer than the groups starting with a hesitation (~+3syllables and ~+749 ms) and than the groups without hesitation (~+3syllables and ~+1246 ms). The effect of hesitation type (t_hesi) on the number of syllables and the duration of the group were significant but didn't interact with the effect of the first clause.

Breathing kinematics

On average, the duration of inhalation was 676 ms (±8.5) and the amplitude was 17.6 %MD (± 0.2). The amplitude and the duration of inhalation depended both on the length of the breath group and on the type of the first clause. These values were also positively correlated with the number of syllables (r = ~.20 for all values and r = ~.60 for average correlations, see Figure 3, first two columns). LMM showed a significant effect of n_syll on both amp_I and dur_I. The duration of inhalation (Figure 4.A) significantly increased from 1 to 2 (+26 ms) and 2 to 3 (+36 ms) clauses. Dur_I was also longer for groups starting with a matrix clause as compared to other types of clauses (+197 ms). Inhalation (Figure 4.B) was significantly deeper when the first clause of the upcoming group was a matrix clause (+3.5 %MD) than any other clauses. Yet, amp_I did not significantly depend on the number of clauses.

The analysis of the inhalation displacement relative to the exhalation displacement (amp_IE, Figure 3 and4) shows: (1) that amp_IE was close to 1 for groups with 2 clauses and groups with 15-18 syllables; (2) a significant linear correlation between the logarithm of amp_IE with the number of syllables (-.48 for all values, -.83 for average, significant effect of n_syll); (3) an effect of the number of clauses (1 > 2 > 3); (4) no significant effect of the type of the first clause. Hence, on average, the inhalation displacement was similar to the exhalation displacement for groups with 2 clauses or 15-18 syllables, larger for shorter groups and smaller for longer groups.

Inhalations were deeper (+2.54 %MD) and longer (+41 ms) for the breath groups with at least one hesitation as compare with no hesitation (Figure 4). The effect of t_hesi on amp_IE was not significant when the number of syllables was taken into account.

Discussion

The present study investigated the linguistic structure of the breath group in German spontaneous speech and evaluated if this structure is reflected in breathing kinematics. The important findings are:

(1) Inhalations occur at syntactic boundaries (before a matrix or an embedded clause) or before a disfluency (uncompleted clause, repetition, hesitation, repair);

(2) Inhalation depth and duration reflect: (2.1) the length of the breath group (number of syllables); (2.2) the type of the first clause, with deeper and longer inhalation for groups starting with a matrix clause as compared to the other groups; (2.3) vocalized hesitations, with deeper and longer inhalations for groups that include at least one vocalized hesitation as compared to none;

(3) Syntactic complexity (number of clauses) is reflected only in the duration but not in the amplitude of inhalation;

(4) On average the amplitude of exhalation is similar to the amplitude of inhalation for groups with 2 clauses or 15-18 syllables.

The observation that most of the inhalation pauses respect the syntactic organization of speech is consistent with previous work on English spontaneous speech [START_REF] Winkworth | Breathing patterns during spontaneous speech[END_REF][START_REF] Wang | Breath group analysis for reading and spontaneous speech in healthy adults[END_REF]. The average duration (3.5 s), the number of syllables in the breath group (16 syllables) and the duration of inhalation (~.7 s) are also similar to values reported in the literature on English language ( [START_REF] Winkworth | Breathing patterns during spontaneous speech[END_REF][START_REF] Mitchell | Cognitive-linguistic demands and speech breathing[END_REF][START_REF] Wang | Breath group analysis for reading and spontaneous speech in healthy adults[END_REF]).

As described in the introduction, previous studies found deeper and longer inhalations for longer utterances. Our dataset also show these relations. However, we also found that inhalations were deeper and longer for the breath groups starting with a matrix clause and for the groups including hesitations as compared to the other groups. To our knowledge, the relationship between the type of the first clause and hesitation to inhalation parameters have not been investigated so far for spontaneous speech. This relation is important with respect to the understanding of speech planning. It suggests that speaker inhale more air: (1) when they are starting a matrix clause that may come with other related clauses; (2) when they produce hesitations and do not know exactly what they are going to say. In this case, they can use vocalized hesitations as fillers during the exhalation phase, which help to preserve ventilation and speech at the same time [START_REF] Schonle | Hesitation vowels: a motor speech respiration hypothesis[END_REF]. The fact that the breath groups with a hesitation at the onset were shorter than groups with a later hesitation shows that when hesitation came at the onset of the group, speaker probably inhaled again soon after it.

We also found that groups with an average number of syllables [START_REF] Wang | Breath group analysis for reading and spontaneous speech in healthy adults[END_REF][START_REF] Huber | Effects of utterance length and vocal loudness on speech breathing in older adults}[END_REF][START_REF] Wang | Accuracy of perceptual and acoustic methods for the detection of inspiratory loci in spontaneous speech[END_REF][START_REF] Mcfarland | Respiratory markers of conversational interaction}[END_REF] show similar exhalation and inhalation amplitudes. These breath groups correspond to 2 clauses and could be a "favored" association between linguistic structure and breathing. This hypothesis should be tested by considering inter-speaker variability and speaker-specific lung volume capacities.

The speech task used in the present study required speakers to summarize the story they have just heard. This task is cognitively demanding and could have influenced the production of hesitations and the breathing profiles. This is in line with inter-speakers variability we found with respect to the number of breath groups and hesitations produced in the current task. To our knowledge only [START_REF] Mitchell | Cognitive-linguistic demands and speech breathing[END_REF] have investigated the possible effect of cognitive load on breathing kinematics during spontaneous speech. We think it is important to distinguish between speakerspecific behaviors according to the task (e.g. variation in disfluency, hesitations).

Limits and perspectives

This study is a first analysis of a larger corpus of breathing kinematics in German spontaneous speech that now includes more than 50 speakers. Our global aim is to understand the interplay of speech planning and breathing in unconstrained speech. From the current study some first issues appear: (1) it is difficult to distinguish between the effect of the number of syllables and the effect of the number of clauses. Note that the quartile of the average number of syllables (10-15-21) were close to the average number of syllables in 1, 2, and 3 clauses, respectively (10-17-25 syllables); (2) Uncompleted clauses should be analyzed in more detail by splitting between hesitations, repairs and repetitions, that could have specific effect on breathing; (3) the amplitude of inhalation anticipates the upcoming breath group, but may also rely on what happened before [START_REF] Bailly | Pauses and respiratory markers of the structure of book reading[END_REF]. This may be especially true for groups starting with an embedded clause. The next step is also to characterize the breath group in spontaneous speech not only as an individual unit but as a temporal sequence that depends on the preceding and following speech.

Speaker-specific behavior and context effects should also be considered. Previous studies on read and spontaneous speech, found that the properties of the breath group and their relations to inhalation parameters are speaker-specific [START_REF] Teston | L' aérodynamique du souffle phonatoire utilisé dans la lecture d'un texte en français[END_REF][START_REF] Fuchs | Acoustic and respiratory evidence for utterance planning in German[END_REF], varied with age [START_REF] Sperry | Speech breathing in senescent and younger women during oral reading[END_REF], cognitive load [START_REF] Mitchell | Cognitive-linguistic demands and speech breathing[END_REF], speech rate [START_REF] Grosjean | Breathing, pausing and reading[END_REF] and loudness [START_REF] Huber | Effects of utterance length and vocal loudness on speech breathing in older adults}[END_REF][START_REF] Huber | Effect of cues to increase sound pressure level on respiratory kinematic patterns during connected speech}[END_REF].

A large variability has also been observed for a same subject across repetitions and according to her emotional state [START_REF] Winkworth | Variability and consistency in speech breathing during reading: lung volumes, speech intensity, and linguistic factors[END_REF][START_REF] Winkworth | Breathing patterns during spontaneous speech[END_REF][START_REF] Teston | L' aérodynamique du souffle phonatoire utilisé dans la lecture d'un texte en français[END_REF]. The sensitivity of speakers' breathing regarding these multiple influences is important to understand the interplay between linguistics and respiration and may provide a fundamental tool for pathological diagnostics and speech therapy. Furthermore, implementing breathing in speech synthesis may improve the naturalness of speech synthesizers.

Figure 1 :

 1 Figure 1: (A) Experimental set-up; (B) Sample breathing kinematics with inhalation (I) and exhalation phase (E). (C) Labeling of the breath groups, with number of syllables and clauses. H indicates the vocalized hesitations parts, see text for details.

  ) 1.53 (±.07) 2.26 (±.09) 7 (±.36) 18.2 (±.56) 18.3 (±.91) 13.8 (±.54) 17.1 (±.27) dur_g 3.95 (±.08) 3.90 (±.15) 3.88 (±.35) 3.27 (±.15) 3.82 (±.07) 4 (±.47) 26.3 (±1.12) 22.1(±1.74) 21.0 (±.84) 25.3 (±.40) dur_g 5.61 (±.12) 5.30 (±.18) 4.50 (±.45) 4.68 (±.22) 5.35 (±.09) 9 (±.31) 17.0 (±.56) 15.5 (±.77) 10.8 (±.42) 15.9 (±.24) dur_g 3.94 (±.07) 3.62 (±.12) 3.35 (±.19) 2.53 (±.10) 3.52 (±.05)

Figure 2 .

 2 Figure 2. Number of breath groups for each speaker with repartition of groups in: no hesitation (none), at least one hesitation at onset or elsewhere

Figure 3 .

 3 Figure 3. Correlations between n_syll in the breath group with: dur_I and amp_I and amp_IE, all values (top), average (bottom). Correlations values for amp_IE are indicated for log(amp_IE), see text for details.

Figure 4 .

 4 Figure 4. Average and standard errors of dur_I, amp_I and amp_IE according to n_clauses and f_clause (white panels) and to the type of hesitation in the breath group (gray panel)

Table I .

 I Description of the breath groups according to the number of clauses and to the type of the first clause. NB: Number of breath groups;

					F_clause
			m	e1	e2	u	All
		NB.	218	84	40	160	502
	1	n_syll 11.7 (±.35) 11.3 (±.59) 11.2 (±.66) 6.2 (±.32) 9.9 (±.24)
	N_clauses	dur_g 2.61 (±.08) 2.57 (±.16) 2.57 (±.17

n_syll: Average number of syllables; dur_g: average duration (± one standard error).

Acknowledgements

This work was funded by a grant from the BMBF (01UG0711) and the French-German University to the PILIOS project. The authors want to thanks Jörg Dreyer, Anna Sopronova and Uwe Reichel for their help with data collection and labeling.