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:
- Perception: Interpreting sparse, ambiguous geometry.
- Planning: Finding feasible paths through tight spaces quickly.
- 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.
- 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.
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