💻 computer science

Fast Motion Planning for Non-Holonomic Mobile Robots via a Rectangular Corridor Representation of Structured Environments

This paper proposes an efficient motion planning framework for non-holonomic robots that uses a deterministic decomposition of structured environments into a compact graph of rectangular corridors to enable fast, kinematically-feasible, and scalable navigation.

Original authors: Alejandro Gonzalez-Garcia, Sebastiaan Wyns, Sonia De Santis, Jan Swevers, Wilm Decré

Published 2026-02-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Alejandro Gonzalez-Garcia, Sebastiaan Wyns, Sonia De Santis, Jan Swevers, Wilm Decré

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to navigate a massive, sprawling IKEA warehouse. You have two ways to find your way to the meatballs:

The "Microscopic" Way: You look at a map that shows every single tiny scratch on the floor and every individual tile. If you try to plan your route by looking at every single tile, your brain will freeze because there are millions of them. This is how traditional robot planners work—they get boggedos with too much detail.
The "Blueprint" Way: Instead of looking at tiles, you look at a simplified map that just shows the long hallways and the big rectangular rooms. You realize, "Okay, I just need to go down Hallway A, turn left into Room B, and then head to Hallway C."

This paper introduces a way for robots to use the "Blueprint Way."

The Problem: The "Too Much Information" Trap

Most robots navigate using "occupancy grids"—essentially a giant digital grid of tiny squares. The robot asks, "Is this specific square empty? How about this one?"

If the warehouse is huge, the robot spends all its "brainpower" (computation) just checking squares. Even worse, most robots are "non-holonomic," which is a fancy way of saying they can’t move sideways like a crab; they have to steer like a car. Planning a smooth, car-like path through millions of tiny squares is incredibly slow and difficult.

The Solution: The "Corridor" Shortcut

The researchers created a system that performs a "magic trick" on the map. Before the robot even starts moving, the system looks at the complex map and simplifies it into a collection of overlapping rectangular corridors.

Think of it like turning a messy, detailed drawing of a house into a simple set of LEGO instructions. Instead of a million points, the robot now sees a small, neat graph of connected rectangles.

This does two amazing things:

Extreme Compression: They achieved a "compression ratio" of 10,000:1. Imagine taking a massive, heavy encyclopedia and shrinking it down until it fits on a single postage stamp, without losing the information about where the rooms are.
Speed: Because the robot is only looking at a few dozen "corridors" instead of millions of "squares," it can make decisions incredibly fast.

How the Robot Moves: The "Analytical" Driver

Once the robot knows which corridors to follow (e.g., "Corridor 1 $\rightarrow$ Corridor 5 $\rightarrow$ Corridor 2"), it doesn't need to do heavy math to figure out how to steer.

Instead of "thinking" about every inch of the turn, it uses a set of pre-set "driving moves"—like a professional driver who knows exactly how much to turn the wheel to make a smooth arc. This is called Analytical Planning. It’s like having a cheat sheet for the perfect turn, so the robot doesn't have to reinvent the wheel every time it hits a corner.

The Results: Fast and Smooth

The researchers tested this on simulations and a real-world robot. The results were impressive:

It’s a Speed Demon: It is significantly faster than the standard "smart" planners used in most robots today.
It’s Reliable: It doesn't just find a path; it finds a smooth path that the robot can actually follow without wobbling or crashing.
It Scales: Whether the building is a small room or a giant factory, the robot doesn't get overwhelmed because it only cares about the structure (the hallways), not the resolution (the tiny details).

In Short...

Instead of a robot staring at every grain of sand on a path, this paper teaches the robot to see the hallways and rooms. By simplifying the world into a "connect-the-dots" game of rectangles, the robot can navigate massive, complex buildings with lightning speed and smooth, car-like movements.

Technical Summary: Fast Motion Planning for Non-Holonomic Mobile Robots via a Rectangular Corridor Representation

1. Problem Statement

Autonomous Mobile Robots (AMRs) operating in large-scale, structured environments (like warehouses or factories) face a fundamental trade-off in motion planning:

Grid-based planners (e.g., A, Dijkstra):* Scalability issues; as map resolution or size increases, the computational cost grows exponentially. They also typically produce geometric paths that ignore the robot's non-holonomic (kinematic) constraints.
Lattice-based/Kinematic planners: They enforce kinematic feasibility but suffer from high search-space complexity, making them slow for large environments.
Sampling-based planners (e.g., RRT, PRM): They lack deterministic guarantees and struggle to navigate "narrow passages," which are common in structured environments.
Convex Cover methods: Often rely on expensive online optimization or are designed for holonomic systems (like quadrotors) rather than constrained mobile robots.

The core challenge is to achieve real-time, kinematically feasible, and near-time-optimal trajectory generation that scales with the structural complexity of an environment rather than its pixel resolution.

2. Methodology

The authors propose a two-phase framework that decouples environmental representation from trajectory generation.

A. Offline Phase: Automatic Corridor Generation (ACG)
Instead of a dense occupancy grid, the environment is decomposed into a compact graph of overlapping rectangular corridors. The pipeline includes:

Line Detection & Straightening: Detecting wall segments and aligning them to canonical or mean angles.
Snap Point Extraction: Using a "union-find" approach to cluster endpoints into "full" (convex) or "half" (concave/hanging) snap points.
Face Identification & Corner Resolution: Classifying cycles as interiors or obstacles and converting obtuse corners into "double snap points" to ensure all corridors can be represented by axis-aligned rectangles.
Rectangle Generation & Obstacle Carving: Creating maximal rectangles and splitting them if they overlap with obstacles to ensure safety.
Connectivity Graph Construction: Using the Separating Axis Theorem (SAT) to find overlapping rectangles and building a graph $G$ where edges represent navigable transitions.

B. Online Phase: Motion Planning

Transition Graph ( $G_T$ ): A precomputed graph where nodes are transition points (corridor centers and intersection centroids/corners).
Corridor Sequence Planning: Using Dijkstra’s algorithm to find the shortest path through the transition graph, augmented with the robot's current start and goal poses.
Analytical Motion Planning (AP): Instead of using expensive optimization (like Mixed-Integer Programming), the framework uses an analytical planner. It concatenates specific motion primitives—on-the-spot rotations ( $T$ ), circular arcs ( $C$ ), and straight lines ( $S$ )—to create a smooth, kinematically feasible trajectory. Heuristic rules are applied to handle complex cases like door-like narrow passages or consecutive corridors with the same direction.

3. Key Contributions

Deterministic Structural Compression: A novel algorithm that reduces massive occupancy grids into a compact graph of rectangles, achieving compression ratios exceeding 10,000:1.
Optimization-Free Planning: A framework that generates near-time-optimal trajectories using analytical methods rather than online numerical optimization, enabling real-time performance.
Kinematic Feasibility: Unlike pure geometric planners, the output is a complete trajectory (geometry + timing) that respects the unicycle model constraints.
Open-Source Implementation: A modular ROS 2 implementation designed for reproducibility.

4. Results

Scalability: The ACG algorithm's complexity scales with the number of structural features (walls/corners) rather than the number of pixels. A 7.3M-pixel map was reduced to a <10KB graph.
Computational Efficiency:
- The proposed framework achieved planning times of 20–40ms.
- On long paths (>25m), it was 2.3× faster than A* and an order of magnitude faster than state-of-the-art kinematic planners like Smac Hybrid-A* and Smac State Lattice Planner (SLP).
Experimental Validation: The framework was successfully tested on a physical Husarion ROSbot 3 in a laboratory setting with projected virtual environments, demonstrating real-time replanning and navigation.

5. Significance

This work provides a highly efficient solution for industrial AMRs. By shifting the heavy computational burden of "understanding" the map to an offline preprocessing stage, the robot can perform complex, high-speed navigation in massive environments using relatively low-power onboard hardware. It bridges the gap between simple geometric pathfinding and computationally heavy optimal control, offering a practical middle ground for real-world autonomous systems.