sw/
← projects
Universitat de Girona·2017

Autonomous frontier exploration with OctoMap

A TurtleBot dropped into an unknown building explores it on its own: frontier detection and A* to map as much as it can in a time budget, then RRT* on the OctoMap to drive home. ROS and Gazebo, VIBOT MSc.

Problem

Put a robot in a building it has never seen and give it a fixed amount of time. It has to map as much as it can on its own, then find its way back to where it started. This was the Autonomous Robots project of the VIBOT MSc at the Universitat de Girona, run on a TurtleBot (Kobuki base, Kinect) in Gazebo’s Willow Garage map.

What I did

With Anirudh Puligandla, Hassan Saeed and Dousai Nayee Muddin Khan, supervised by Prof. Marc Carreras, I worked on a two-stage, high-level controller in ROS.

Explore. gmapping builds a 2D occupancy grid from the Kinect’s laser scan, with laser scan matching for odometry. Each cell is empty, unexplored or obstacle, and frontier points are the explored cells that border unexplored ones. We keep a candidate only if its 3×3 neighbourhood has enough explored and unexplored cells and no obstacles, cluster the candidates by connected components, and send the robot to the nearest accessible, unvisited cluster centre with an A* search. On arrival it spins for a 360° sweep, updates the map and picks the next frontier; frontiers it cannot reach in time are marked inaccessible. Meanwhile OctoMap integrates the point cloud into a 3D occupancy map.

Return. The start pose is saved from odometry before exploration begins. When the time budget runs out, two ROS services take over: one asks OMPL’s RRT* planner for an optimal, collision-free path on the OctoMap back to the start, and the other lets the low-level TurtleBot controller drive it while avoiding obstacles.

Result

In simulation the robot explored the Willow Garage environment and returned to its starting position, as the video shows. The main limitation was that it could stay in one room until it was fully mapped, leaving gaps elsewhere. Next steps we identified: room segmentation to avoid revisiting partly explored areas, and recomputing frontier targets that become explored while the robot is on its way.

diagrams

scroll sideways on small screens

Frontier exploration pipelineStage 1: from the start position the TurtleBot maps with GMapping and OctoMap and navigates with move_base towards the nearest frontier found by clustering and A*, sweeping 360 degrees at each goal. Stage 2: when time is up, OMPL's RRT* plans a path home over the explored OctoMap and the robot follows it back to the start.Stage 1 · explore, until time runs outStage 2 · return to startStartGMapping2D SLAMOctoMap3D occupancymove_basenavigationFrontier searchcluster · A* to nearestExplored mapOctoMapRRT* (OMPL)path homeFollow pathTurtleBot controlStarttime upnext frontier goal · 360° sweep on arrival
diagramTwo stages: explore towards the nearest frontier while mapping, then plan home with RRT* over the map built so far.Source: the 2017 project report
Frontier target placed on an obstacleThe robot looks past an obstacle. The obstacle's shadow forms a triangular cluster of frontier points, and the cluster centre, the frontier target, lands on the obstacle itself, so it cannot be reached.FrontiertargetObstacleFrontier pointsNavigationpathRobotgoalsensor view
figureA failure case the strategy has to handle: an obstacle's shadow forms a triangular frontier cluster whose centre, the frontier target, lands on the obstacle itself, so the goal is unreachable. The robot marks it inaccessible, sweeps its sensors and moves to the closest remaining frontier.Source: Puligandla, Wagh, Saeed, Khan, 2017

figures

click to enlarge

fig. 01Homing: candidate RRT* paths back to the start (blue) and the optimised smooth path the robot follows (green).Puligandla, Wagh, Saeed, Khan, 2017
fig. 02Limitation: the robot can stay in one room until it is fully mapped, leaving gaps elsewhere in the OctoMap.Puligandla, Wagh, Saeed, Khan, 2017
esc