Post

Frontier-Based Exploration in ROS, From Scratch

Frontier-based autonomous exploration in ROS (C++) from scratch: OctoMap, simulated LiDAR, frontier clustering, A* planning and fallback behaviours.

Frontier-Based Exploration in ROS, From Scratch

A pre-research exercise at the SJTU RAP Lab: build a complete autonomous exploration system in ROS (C++) without relying on the navigation stack. The robot is dropped into an unknown map and must keep choosing where to go next until nothing is left to explore. The method follows Yamauchi’s frontier-based exploration (CIRA 1997).

Demo video: youtube.com/watch?v=MhtYzAHmc9I Code: github.com/dunyanong/exploration-preresearch

System

flowchart LR
  P[World point cloud] --> M[Map builder<br/>OctoMap → 2D grid + simulated LiDAR]
  M --> G[Occupancy grid<br/>what the robot has seen]
  G --> E[Explorer<br/>frontiers → clusters → goal]
  E --> A[A* path finder<br/>on an inflated costmap]
  A --> L[Local planner]
  L --> O[Odometry manager<br/>ground robot or UAV]
  O --> M
  • Map builder. Loads the world point cloud into an OctoMap once, and turns it into 2D ground-truth grids by checking occupancy at two heights (0.5 m and 1.5 m), so the ground robot and the UAV see different obstacles. A simulated LiDAR then marches 120 rays across that grid from the robot’s pose, and the map builder publishes only the cells the robot has actually seen.
  • Explorer. Marks free cells next to unknown cells as frontier cells, clusters neighbouring ones, discards clusters below a minimum size, and picks the nearest accessible cluster as the next goal.
    • Goals the robot fails to reach are blacklisted, so it doesn’t keep retrying them.
    • If no frontier is reachable, it falls back to retreating or a random walk instead of stopping.
  • Path finder. Runs A* on a costmap inflated around obstacles.
  • Local planner. Follows the A* path.
  • Odometry manager. Supports both a ground vehicle and a UAV model.

Exploration ends when no frontier clusters remain.

Why it mattered

This is one robot exploring an unknown map. VADER, my research on decentralized multi-robot navigation in unknown environments, asks the same question for a team: each robot maps and plans on its own, and robots merge what they have seen when they meet.

This post is licensed under CC BY 4.0 by the author.