💻 computer science

Autonomous Navigation of Quadrupeds Using Coverage Path Planning with Morphological Skeleton Map

This paper presents a novel autonomous coverage path planning method for quadrupeds that utilizes morphological skeleton maps to generate and order points of interest for scanning unstructured environments, achieving 86.5% waypoint reachability in indoor tests despite challenges with map drift.

Original authors: Alexander James Becoy, Kseniia Khomenko, Luka Peternel, Raj Thilak Rajan

Published 2026-02-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Alexander James Becoy, Kseniia Khomenko, Luka Peternel, Raj Thilak Rajan

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 have a very smart, four-legged robot dog (like a high-tech version of a pet) that needs to clean a messy, unfamiliar room. But here's the catch: the room is full of weird shapes, dead ends, and no one has drawn a map for the robot yet. The robot needs to make sure it checks every single corner of the room without getting lost or wasting time.

This paper describes a new "brain" for that robot dog that solves this problem. Here is how it works, broken down into simple steps:

1. The Problem: The "Blindfolded" Explorer

Usually, robots are great at walking in straight lines, but they struggle in messy, unstructured places (like a disaster zone or a construction site). If you tell a robot to "go everywhere," it might get confused, walk in circles, or miss spots.

2. The Solution: The "Skeleton Key"

The researchers came up with a clever trick. Instead of looking at the whole room as a giant, confusing blob, they turn the map of the room into a skeleton.

The Analogy: Imagine you have a drawing of a complex maze. If you shrink the walls down until they are just thin, one-pixel-wide lines, you get the "skeleton" of the maze. It looks like a stick-figure version of the room.
How the Robot Uses It: The robot looks at this "skeleton map." It realizes that to cover the whole room, it doesn't need to walk every single inch of the floor. It just needs to walk along the "spine" or the "branches" of this skeleton. It's like a gardener pruning a bush; they follow the main branches to trim every leaf efficiently.

3. The Three-Step Process

Step A: Reading the Map (The "Skeletonizer")
The robot takes a 2D map of the room (created by its laser scanner) and runs it through a filter.

It smooths out the noise (like dust on a camera lens).
It turns the room into a black-and-white picture.
It shrinks the walkable areas down to a thin line (the skeleton).
Result: A list of "Checkpoints" (Points of Interest) that look like the branches of a tree.

Step B: Planning the Route (The "Tour Guide")
Now the robot has a list of checkpoints. It needs to visit them all in the most efficient order.

The Analogy: Think of this like the Traveling Salesman Problem. If you have to visit 10 friends' houses, what is the fastest route to do it without backtracking?
The robot's brain calculates the shortest path to hit every "branch tip" (dead end) of the skeleton first, then works its way back. It creates a perfect, non-repeating loop.

Step C: The "Traffic Cop" (The State Machine)
This is the robot's manager. It switches between two modes:

Drive Mode: "Okay, go to the next checkpoint!" (It uses standard navigation software to get there).
Scan Mode: "Stop! Look around and scan this spot."

If the robot gets stuck or confused, the "Traffic Cop" can pause the mission and ask a human for help, or send the robot home.

4. The Results: How Well Did It Work?

The team tested this on a Unitree Go2 robot (a real, commercial robot dog) in a large, empty indoor room.

Speed: The robot's brain is incredibly fast. It can process a map and plan the route in less than the blink of an eye (about 2-4 milliseconds).
Success Rate: In five different tries, the robot successfully reached 86.5% of all the checkpoints it was supposed to visit.
The Glitch: The few times it failed, it wasn't because the plan was bad. It was because the robot's internal map "drifted" (like a GPS signal getting slightly off over time). The robot thought a wall was in a different spot than it actually was, so it couldn't reach the final checkpoints.

5. Why This Matters

For Disaster Zones: Imagine a robot dog entering a collapsed building after an earthquake. It needs to scan every room to find survivors. This method ensures it doesn't miss a corner and doesn't waste battery walking in circles.
For Industry: It's cheaper and more efficient than previous methods because it uses a simple "image processing" trick (the skeleton) instead of complex, slow math.
Open Source: The best part? The code is free for anyone to use and improve!

The Bottom Line

This paper teaches a robot dog how to clean a messy room by first turning the room into a simple "stick-figure map," finding the most efficient path to walk along those sticks, and then checking every corner. It's a smart, fast, and open-source way to make robots better at exploring the unknown.

1. Problem Statement

The paper addresses the challenge of enabling quadruped robots to autonomously scan and map unstructured environments (e.g., disaster zones, mines, nuclear facilities) using Coverage Path Planning (CPP).

The Gap: While legged robots are versatile in rough terrain, existing CPP methods often rely on time-constrained planning (unsuitable for variable execution times) or complex, non-modular map generation algorithms.
Specific Challenge: There is a lack of modular, computationally efficient frameworks that allow quadrupeds (specifically the Unitree Go2 Edu) to generate optimal scanning paths from a prior 2D map without being strictly bound by predefined mission times.
Hardware Context: The study focuses on the Unitree Robotics Go2 Edu, chosen for its balance of cost, ROS 2 integration, and battery life compared to expensive commercial alternatives like Boston Dynamics' Spot.

2. Methodology

The authors propose a novel, modular software framework built on ROS 2 consisting of three primary modules:

A. Map Reader (Morphological Skeletonization)

Instead of using complex topological methods like Voronoi diagrams, the system treats the 2D navigation map as an image to extract a morphological skeleton.

Preprocessing: The 2D map (generated via SLAM) is converted to an 8-bit array. Unknown regions are treated as occupied to define boundaries.
Filtering: A Gaussian filter removes noise, followed by binarization to distinguish free vs. occupied space.
Contouring & Erosion: The largest contour is filled to ensure connectivity. The free space is then eroded using a morphological kernel to create a safe navigation corridor, removing narrow passages the robot cannot traverse.
Skeletonization: The remaining free space is reduced to a 1-pixel-wide topological skeleton.
Waypoint Generation: The skeleton pixels are converted into real-world coordinates to form an unordered set of Points of Interest (POIs/Waypoints).

B. Path Planning (Graph Traversal)

The unordered waypoints are converted into a connected acyclic graph $G$ .

Algorithm: The problem is framed as a variation of the Travelling Salesman Problem (TSP).
Strategy: The system identifies "leaf vertices" (dead-ends) in the skeleton graph. It starts from the leaf closest to the robot's current position and iteratively finds the nearest unvisited leaf.
Optimization: Shortest paths between leaves are calculated using Dijkstra's algorithm. The path is then downsampled (by a factor $D/R$ ) to ensure the robot scans at intervals matching its sensor range rather than every single pixel, optimizing time efficiency.

C. Control Architecture (Finite State Machine)

A Finite State Machine (FSM) orchestrates the high-level operation, switching between:

Load Map: Generates waypoints and plans the route.
Check Waypoints: Iterates through the ordered list.
Check Destination: Verifies if the robot has reached the target pose within tolerance.
Move: Commands the robot (via Nav2) to navigate to the target.
Scan: Executes local environment scanning (using LiDAR) upon arrival.
Manual Control: Allows human intervention if the robot gets stuck or terrain is too difficult.
Home: Returns the robot to the start position.

3. Key Contributions

Novel Framework: Development of a control framework specifically for the Unitree Go2 Edu that switches autonomously between navigation and scanning modes.
Morphological Efficiency: Introduction of a morphological skeleton technique for path planning that is computationally more efficient than wave propagation or Voronoi-based methods, allowing for rapid processing of large maps.
Modularity: The system decouples the path planner from the map generation algorithm, allowing it to work with various SLAM outputs.
ROS 2 Integration: An extended interface enabling the Go2 Edu to work seamlessly with the Nav2 framework and SLAM Toolbox.
Open Source: The entire application is released as open-source software.

4. Experimental Results

The system was validated in a leveled, indoor, non-convex environment over five trials.

Computational Efficiency:
- Map Reader: Processes maps (approx. 200x200 pixels) in 2.52 ms on average. Computation time scales linearly at 22.0 ns/pixel.
- Path Planner: Generates paths in 1.7 ms on average. Computation time scales at 8.17 µs/waypoint.
- Implication: The system can handle maps up to ~45 million pixels within a 1-second lead time.
Navigation Performance:
- Reachability: The robot successfully reached 86.5% of all planned waypoints across the five trials.
- Time Efficiency: The median time per waypoint was 5.38 seconds.
Limitations Observed:
- Map Drift: In Trials 3 and 5, significant SLAM drift occurred over time (due to reliance on relative sensors like IMU and LiDAR). This caused the 2D map to misalign with reality, placing future waypoints inside "walls" (occupied space), rendering them unreachable.
- Local Path Failures: In some instances, the Nav2 local planner failed to converge within tolerance, causing the robot to stall and requiring human intervention.

5. Significance and Future Work

Significance: This work demonstrates a highly efficient, modular approach to autonomous coverage for quadrupeds. By using morphological skeletonization, it achieves faster computation times compared to state-of-the-art time-constrained methods, making it suitable for environments where mission duration is variable.
Future Directions:
- Drift Mitigation: Integrating absolute sensors (GPS, UWB anchors) to correct SLAM drift.
- Dynamic Obstacles: Extending the method to handle moving obstacles and 3D terrain variations.
- 3D Exploration: Moving from 2D coverage to real-time autonomous exploration in unknown 3D environments.
- Parameter Tuning: Systematic investigation of key parameters (e.g., erosion kernel size, waypoint spacing) to optimize performance across diverse environments.

In conclusion, the paper presents a robust, open-source solution for quadruped navigation that balances computational speed with effective coverage, while clearly identifying the need for better localization stability in long-duration autonomous missions.