Connectivity-preserving scattering of mobile robots with limited visibility

摘要: The scattering problem is a fundamental task for mobile robots, which requires that no two robots share the same position. We investigate in limited-visibility model. In particular, we focus on connectivity-preservation property. That is, must be achieved so disconnection of visibility graph never occurs (in are nodes and edges their relationship). algorithm propose assumes ATOM (i.e. semi-synchronous) these settings our guarantees connectivity-preserving property, reaches scattered configuration within O(min{n, D2 + log n}) asynchronous rounds expectation, where D diameter initial graph. Note complexity analysis adaptive since it depends D. This implies quickly scatters all crowded small-diameter also provide lower bound Ω(n) scattering. It follows optimal sense non-adaptive analysis.