Show description

Each robot is equipped with a holonomic (uniform in all orientations) sensor that records a line of sight perception of the environment within a maximum sensing radius r. We assume that two robots can reliably communicate if they are within line of sight of each other and if the distance between their positions is less than or equal to 2r. The position of a robot is constrained to be within some free region Q, which is a closed compact subset of R2 . The obstacle region B makes up the rest of the world, and is defined as the complement of Q.

The ingoing frontier can always be aligned, without admitting recontamination, such that its anchor points correspond to the tangent points τ1 , τθ(j) on the two boundary walls that it subtends. By Lemma 1, a junction of degree θ(j) will have tangent points on θ(j) distinct boundary walls. Thereafter the ingoing frontier can always be extruded toward each of the other θ(j) − 2 tangent points in turn, likewise without admitting recontamination. Thus for a junction j with tangent points τ1 , τ2 , .

Volkov et al. 2, for junction nodes the representation is as follows. For each junction entry node u ∈ V let Eu ⊂ E be the set of edges {e1 , e2 , . . , eγ(u) } connecting u to its associated set of junction exit nodes {v1 , v2 , . . , vγ(u) }. For each junction, we define a traversal function δ : Eu → N, where i δ(ei ) is the number of robots required to traverse the junction. This corresponds to the minimum number of robots required to form a split frontier at the junction, given by its ceiling length Fs .