Cooperative terrain model acquisition by two point-robots in planar polygonal terrains

摘要

We address the model acquisition problem for an unknown terrain by a team of two robots. The terrain may be cluttered by a finite number of polygonal obstacles with unknown shapes and positions. The robots are point-sized and equipped with visual sensors which acquire all visible parts of the terrain by scanning from their locations. The robots communicate with each other via wireless connection. The performance is measured by the number of the sensor (scan) operations which are assumed to be the most time-consuming/expensive of all the robot operations. We employ the restricted visibility graph methods in a hierarchiacal setup. For terrains with convex obstacles, the sensing time can be halved compared to a single robot implementation. For terrains with concave corners, the performance of the algorithm depends on the number of concave regions and their depths. A hierarchical decomposition of the restricted visibility graph into 2-connected components and trees is considered. Performance for the 2-robot team is expressed in terms of sizes of 2-connected components, and the sizes and diameters of the trees. The proposed algorithm and analysis can be applied to the methods based on Voronoi diagram and trapezoidal decomposition.