Exploration methods have been implemented using neural networks and landmarks [13][4] as well as other techniques. In our approach, grid locations are classified into 3 basic types: blocked, clear and unknown. We would like to reduce all unknown regions until all reachable areas are either clear or blocked. We achieve this by assigning an attractive potential field to all unknown areas, while maintaining the obstacle repulsion fields.
This was implemented by re-using our path planning algorithm, with the unknown grid locations all being assigned as destinations with d = 0. The breadth-first search is begun simultaneously at all these locations. By following the path with the minimum cost, the robot is guided to the nearest accessible unknown region. With periodic reevaluation and re-planning, the robot will explore from unknown region to unknown region until no more unknown regions are reachable.
Figure 11 shows an example of exploration in progress. The dark line indicates the path that Spinoza has taken. Figure 12 shows the exploration completed, with no unknown destinations remaining.
Figure 11: Exploration in progress
