Maze Runner: Autonomous Maze Navigation with Line-Based Localization and Control Barrier Functions

Alvaro J. Gaona, Lucas Gómez-Velayos, Peter Pasuy-QuevedoarXiv 2026 · arXiv

TL;DR

Maze Runner is an open-source C++/ROS 2 autonomy stack designed for high-precision navigation in structured, sparse environments like mazes. It achieves centimeter-level localization accuracy by using line-based features and ensures collision-free movement through a "safety shield" comprised of Nonlinear Model Predictive Control (NMPC) and Control Barrier Functions (CBFs).

What Problem Does This Paper Address?

Navigating a maze is a classic but deceptively difficult robotics challenge. Standard grid-based mapping often struggles with the thin, repetitive geometry of maze walls. Furthermore, narrow corridors leave almost zero margin for error; a localization drift of just a few centimeters can cause a robot to strike a wall or believe it is trapped inside one.

The authors identify three interconnected hurdles:

  1. Perception: Interpreting sparse, ambiguous geometry.
  2. Planning: Finding feasible paths through tight spaces quickly.
  3. Control: Maintaining safety even when the robot's internal map is slightly wrong or an unmapped obstacle appears.

Methods

The authors built a modular stack where the core algorithms reside in a ROS-free C++ library for maximum performance and portability.

The system architecture consists of perception, localization, planning, and control layers.
  • Line-Based Perception: Instead of processing raw 2D LiDAR point clouds, the system uses RANSAC and Total Least Squares to extract wall lines. This provides a compact, geometrically meaningful representation of the environment.
  • Dual-Mode Localization: An Extended Kalman Filter (EKF) uses these lines to localize the robot. It can operate against a known map (extracted from the simulation mesh) or in SLAM mode, building the line map on the fly.
  • Efficient Planning: The authors compared several planners, ultimately favoring A* with line-of-sight shortcutting. This approach finds a path on a grid and then "smooths" it into straight segments, proving much faster than more complex alternatives like Hybrid A*.
  • Safety-Critical Control: The "secret sauce" is the combination of NMPC and discrete-time Control Barrier Functions (CBFs). While the NMPC tries to follow the global plan, the CBF layer acts as a mathematical safety bubble. It looks at real-time LiDAR returns and forces the controller to steer away from obstacles, even if they aren't in the robot's map.

Datasets

The system was evaluated in a high-fidelity simulation using Gazebo and ROS 2.

  • Platform: A simulated Husarion ROSbot XL equipped with a 2D LiDAR (Slamtec RPLIDAR S3).
  • Environment: A complex 135-meter maze route designed to test both long-distance navigation and tight maneuvering.

Key Insights and Ideas

  • Lines over Points: In environments dominated by flat surfaces, lines are far more robust landmarks than individual points or occupancy grids. They handle repetitive geometry better and provide clear orientation cues.
  • The Safety Shield: By embedding CBFs directly into the NMPC optimization, safety becomes a hard constraint. The robot doesn't just "try" to avoid obstacles; the math ensures it stays at a safe distance.
  • Simplicity Wins in Planning: While Hybrid A is popular for car-like robots, the authors found that simple A with a shortcutting post-process was 40 times faster while producing paths of nearly identical quality for this specific task.

Key Results

The system demonstrated impressive real-time performance on an Apple M5 Pro laptop:

  • Localization Accuracy: Achieved a 1.0 cm RMSE (Root Mean Square Error) when localizing against a known map. In SLAM mode (without loop closure), the error was 24 cm over a 135m run.
  • Speed: The planner returns a path in just 6 ms, and the NMPC controller solves its optimization problem in an average of 11.7 ms, well within its 80 ms real-time budget.
  • Robustness: In a "stress test," the authors placed an unmapped pillar in the robot's path. The CBF-constrained controller successfully steered the robot around the pillar with 0.57 m of clearance, despite the obstacle being invisible to the global planner.
The robot successfully follows a 135m route, with the EKF estimate (blue) closely matching the ground truth.

Limitations and Future Work

  • Simulation Only: While the results are promising, the stack has yet to be tested on physical hardware, where sensor noise and wheel slip are less predictable.
  • SLAM Drift: The current SLAM implementation lacks "loop closure" (the ability to recognize a previously visited location to correct accumulated error), leading to drift over very long distances.
  • Planner "Blindness": While the controller avoids unmapped obstacles, the planner doesn't know they exist. If an obstacle completely blocks a corridor, the robot will stop safely but won't know to look for an alternative route. Integrating LiDAR data back into the occupancy grid is a suggested next step.

Summary updated

Abstract

Maze navigation requires localization from sparse, repetitive geometry, planning through narrow corridors, and control that stays safe when the estimate or the map is wrong. We present Maze Runner, an open autonomy stack in C++ and ROS 2 that addresses these needs end to end on a simulated Husarion ROSbot XL with a 2D LiDAR in Gazebo. Perception extracts wall lines from each scan with RANSAC and total least squares, with per-line uncertainty. The same line front end feeds two estimators: an Extended Kalman Filter (EKF) that localizes against a line map built from the maze mesh, and an EKF SLAM variant that builds the line map online. Planning runs online on an inflated occupancy grid with A* plus line-of-sight shortcutting, or with a forward-only Hybrid A*. A nonlinear Model Predictive Controller (NMPC) tracks the plan while discrete-time Control Barrier Functions (CBFs) on world-frame LiDAR points keep the robot clear of walls and unmapped obstacles. The algorithms live in a ROS-free, unit-tested core library, and the whole stack builds and runs from a single reproducible environment. In simulation, the robot drives a 135 m route through the maze with 1.0 cm localization RMSE against the known map and 24 cm in SLAM mode, the planner returns a path in 6 ms, and the NMPC solves in 11.7 ms on average, never exceeding its 80 ms budget.
BibTeX
@misc{gaona2026maze,
  author = {Alvaro J. Gaona and Lucas Gómez-Velayos and Peter Pasuy-Quevedo},
  title = {{Maze Runner: Autonomous Maze Navigation with Line-Based Localization and Control Barrier Functions}},
  year = {2026},
  eprint = {2611.12949},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.12949},
}
Figure