Conclusions

We have developed a search strategy that can be used for an actual autonomous robot. Obviously, a number of problems remain. Just like [9] provided a crucial step towards the solution for exploring general simple polygons described in [7], one of the most interesting challenges is to extend our results to more general settings with a larger number of obstacles, or the exploration of a complete region. See Figure 8 for a typical realistic scenario. It should be noted that scan cost (and hence positive step length without vision) can cause theoretical problems in the presence of tiny bottlenecks; even without scan cost, this is the basis of the class of examples in [1] for polygons with holes. However, in a practical setting, lower bounds on the feature size are given by robot size and scanner resolution. Thus, there may be some hope.

Figure 8: A typical scenario faced by Kurt3D. Top left: Extracted points at height 75 cm (corresponding to figure 1, bottom middle). Top right: Line detection using Hough transform. Bottom: Automatically generated map with occlusion lines [17].