Frontier-Based Exploration




Once frontiers have been detected within a particular evidence grid, the robot attempts to navigate to the nearest accessible, unvisited frontier. The path planner uses a depth-first search on the grid, starting at the robot's current cell and attempting to take the shortest obstacle-free path to the cell containing the goal location.


The image above shows the path planned by the robot through a cluttered office, around a desk, and past a chair. The blue line represent the path, while the blue dots represent cells that are checked to guarantee that the space around the path is free of obstacles. The red crosshairs mark the robot's destination. The red circles indicate obstacles around which the planner had to detour the path.

 While the robot moves toward its destination, reactive obstacle avoidance behaviors prevent collisions with any obstacles not present while the evidence grid was constructed. In a dynamic environment, this is necessary to avoid collisions with, for example, people who are walking about. These behaviors also allow the robot to steer around these obstacles and, as long as the world has not changed too drastically, return to follow its path to the destination.

 When the robot reaches its destination, that location is added to the list of previously visited frontiers. The robot performs a 360 degree sensor sweep using laser-limited sonar and adds the new information to the evidence grid. Then the robot detects frontiers present in the updated grid and attempts to navigate to the nearest accessible, unvisited frontier.

 If the robot is unable to make progress toward its destination, then after a certain amount of time, the robot will determine that the destination is inaccessible, and its location will be added to the list of inaccessible frontiers. Then the robot conducts a sensor sweep, updates the evidence grid, and attempts to navigate to the closest remaining accessible, unvisited frontier.

Frontier-Based Exploration