On sampling inside obstacles for boosted sampling of narrow corridors. (22nd March 2019) - Kala, Rahul
Abstract: Narrow corridors are a cause of intense problems in sampling‐based approaches due to the small probability of generation of samples inside the narrow corridor. The obstacle‐based sampling and bridge test sampling techniques rely on generating fresh samples at every iteration. Memory of the forbidden configuration space can lead to the discovery of new narrow corridors or generating additional key samples inside the same narrow corridor. Hence, in this paper, it is proposed to additionally solve the problem of generating a roadmap in the forbidden configuration space, called as the dual roadmap. The dual roadmap, so generated, has vertices that are collision‐prone and stores the structure of the forbidden configuration space. To reduce memory and computation time, only the boundary of the forbidden configuration space is stored, which is more informative. The dual roadmap, so constructed, is used to generate valid samples inside the middle of the narrow corridors. The construction of the additional roadmap takes a very small time and memory and is largely the biproduct of obstacle‐based sampling that is normally thrown away. Experimental results show that the proposed sampling method is very effective for finding narrow corridors as compared to popular sampling methodologies existing in the literature.