Complete and Near-Optimal Robotic Crack Coverage and Filling in Civil Infrastructure

This paper presents a simultaneous sensor-based inspection and footprint coverage (SIFC) planning and control framework that enables autonomous robots to efficiently map and fill cracks in civil infrastructure by minimizing travel distance while guaranteeing complete sensing and near-optimal filling coverage, even when target information is initially unknown.

The Gist

Imagine you are a homeowner with a very specific, annoying problem: your driveway is covered in tiny, invisible cracks. If you don't fix them now, they will grow into huge potholes later. But you don't know exactly where the cracks are, and you can't see them with the naked eye.

Now, imagine you have a magical, self-driving robot vacuum cleaner. But instead of sucking up dust, this robot has two superpowers:

1. Super Eyes: It has a giant, wide-angle camera that can spot cracks from far away.
2. Magic Paintbrush: It has a small, precise nozzle right under its belly that can fill in the cracks it touches with sealant.

The challenge? The robot needs to do two things at once:

• Scan: Look everywhere to find the cracks (like a detective).
• Clean: Drive over every single crack it finds to fix it (like a painter).

The problem is that the robot's "eyes" see a huge area, but its "paintbrush" only covers a tiny circle directly underneath it. If the robot just drives back and forth like a normal vacuum, it wastes a lot of time and energy. If it just tries to find cracks randomly, it might miss some or drive over the same spot twice.

This paper introduces a new "brain" (an algorithm) for this robot that solves this puzzle perfectly. Here is how it works, broken down into simple concepts:

1. The "Mowing the Lawn" vs. "Finding the Lost Keys" Problem

Usually, robots have to do one of two things:

• The Lawn Mower: Go back and forth over a whole field to cut the grass (covering everything).
• The Key Finder: Walk around a room looking for a specific lost object (finding targets).

This robot has to do both at the same time. It has to map the whole room (the lawn) while simultaneously finding and fixing the cracks (the keys). The authors call this SIFC (Simultaneous Inspection and Footprint Coverage).

2. The "Online" vs. "Offline" Brain

The paper presents two versions of the robot's brain:

• The "Offline" Brain (SCC): Imagine you have a perfect map of the driveway before the robot even starts. It knows exactly where every crack is. The brain calculates the absolute shortest, most efficient route to visit every crack and scan the whole area. It's like planning a road trip with a GPS that knows every traffic jam in advance.
• The "Online" Brain (oSCC): This is the real magic. Imagine the robot starts with no map. It doesn't know where the cracks are. As it drives, its eyes spot a crack.
  • Step 1: It drives in a smart pattern to scan the empty space.
  • Step 2: The moment it spots a crack, it instantly switches modes. It stops scanning the empty space and starts driving specifically to fill that crack.
  • Step 3: Once the crack is fixed, it goes back to scanning the rest of the room, but it "remembers" the area it just fixed so it doesn't waste time going back there.

This "Online" brain is like a smart delivery driver who is driving around a city delivering packages. They don't know where the customers are. As they drive, they see a house with a "Deliver Here" sign. They immediately pull over, drop the package, and then continue driving, updating their mental map so they don't drive past that house again.

3. The "Nozzle Dance" (Coordinated Control)

Here is a tricky part: The robot moves slowly, but the cracks might be everywhere under its belly. If the robot drives forward, how does the paint nozzle know which crack to fill?

Think of the robot as a bus and the nozzle as a passenger with a paintbrush.

• The bus (robot) drives along a main road (the planned path).
• The passenger (nozzle) can move left, right, forward, and backward inside the bus very quickly.
• The "brain" tells the passenger: "Hey, the bus is passing over Crack A. Move the brush to Crack A and paint it! Now the bus is moving to Crack B; jump over and paint that one!"

The paper uses a sophisticated math system (Model Predictive Control) to make sure the passenger (nozzle) and the bus (robot) move in perfect harmony so no crack is missed and no paint is wasted.

4. Why is this a Big Deal?

The researchers tested this on a real robot in a lab. They compared their "Smart Brain" against older, dumber methods:

• The "ZigZag" Method: Just driving back and forth like a lawnmower. This covers everything but is slow and wastes a lot of paint because it drives over empty space.
• The "Greedy" Method: Just driving until it sees a crack, fixing it, then looking for the next one. This often leads to the robot getting stuck in loops or missing spots.

The Result: Their new "Smart Brain" (oSCC) was the winner. It:

• Drove the shortest distance (saving battery and time).
• Found every single crack (100% coverage).
• Filled them accurately without missing spots.
• Did all this without needing a map beforehand.

The Bottom Line

This paper teaches robots how to be efficient multitaskers. Instead of just blindly sweeping a floor or just randomly looking for problems, the robot learns to "scan and fix" simultaneously. It's like having a mechanic who can drive your car, look for engine trouble, and fix the problem all in one smooth, continuous motion, saving you time, money, and effort.

This technology could soon be used to automatically repair roads, bridges, and airport runways, keeping our infrastructure safe without needing armies of human workers to do the dangerous and tedious job.

Technical Summary

1. Problem Statement

The paper addresses the Simultaneous Sensor-based Inspection and Footprint Coverage (SIFC) problem, specifically applied to autonomous robotic crack mapping and filling in civil infrastructure (e.g., roads, bridges).

• Core Challenge: The robot must perform two coupled tasks simultaneously:
  1. Complete Sensing Coverage: Detect all unknown targets (cracks) within the workspace using an onboard sensor (e.g., camera) with a sensing radius $S$.
  2. Complete Footprint Coverage: Physically cover and repair all detected targets using a filling actuator (nozzle) with a footprint radius $a$.
• Constraints & Complexity:
  • The sensing range $S$ is typically larger than the footprint radius $a$ ($S \ge a$).
  • The targets (cracks) are initially unknown; the robot must discover them online while moving.
  • The goal is to minimize the total traveling distance of the robot while guaranteeing 100% detection of cracks and 100% repair of detected cracks.
  • The problem is NP-hard, involving variations of the Covering Salesman Problem, Art Gallery Problem, and Chinese Postman Problem.

2. Methodology

The authors propose a hierarchical approach involving three main algorithms and a coordinated motion control system.

A. Graph-Based Coverage (GCC)

• Context: Assumes a known target map (crack map).
• Process:
  1. Target Graph Construction ($G_c$): Extracts crack skeletons, dilates them by the footprint radius $a$ (Minkowski sum) to create a "footprint region" ($M_f$). Nodes are defined by endpoints and intersection points of cracks; edges represent the shortest paths within $M_f$.
  2. Path Planning: Formulates the problem as a Rural Postman Problem (RPP). It identifies odd-degree vertices in the graph and pairs them to minimize the total added edge cost (using Minimum Spanning Trees and Linear Programming).
  3. Output: Generates an Euler tour (or near-optimal path) that traverses every crack edge exactly once with minimal revisits.

B. Sensor-Based Complete Coverage (SCC)

• Context: Assumes known target maps but requires scanning the entire workspace (including empty space) to ensure no cracks are missed.
• Process:
  1. Morse-based Cellular Decomposition (MCD): Decomposes the free workspace into cells based on critical points (where slice connectivity changes).
  2. Reeb Graph ($G_w$): Constructs a graph representing the connectivity of these cells.
  3. Integration: Combines the Reeb graph ($G_w$) with the target graph ($G_c$).
  4. Euler Tour: Generates a least-cost Euler tour that covers all cells (for sensing) and all target edges (for filling).
• Result: Guarantees complete sensing of the workspace and complete footprint coverage of known targets with near-optimal path length.

C. Online Sensor-based Complete Coverage (oSCC)

• Context: The general solution for unknown target information (the primary contribution).
• Process:
  1. Online Construction: The robot starts with no target map. It treats the workspace as a Reeb graph ($G_w$) and plans a path to scan the environment.
  2. Incremental Discovery: As the robot moves, it detects cracks. When a crack node is found, it constructs a local target graph ($G_c$) using the GCC algorithm.
  3. Dynamic Re-planning: The robot switches to the local GCC path to fill the discovered cracks. Once the local task is done, it updates the global map (removing covered areas) and re-plans the global Reeb graph path for the remaining uncovered space.
  4. Optimality: The algorithm guarantees complete coverage of the free space and all targets. It achieves near-optimality in polynomial time by minimizing redundant connections between cells.

D. Coordinated Motion Control

• Robot Kinematics: Uses a 4-wheel omnidirectional robot.
• Nozzle Coordination: The filling nozzle moves on an XY-table relative to the robot body.
• Control Strategy: A Nonlinear Model Predictive Control (MPC) framework is used.
  • Objective: Minimize position errors and control inputs while satisfying constraints (nozzle speed > robot speed during filling, nozzle stays within footprint).
  • Logic: The nozzle switches between multiple cracks within the footprint based on a threshold distance $L$, ensuring efficient filling while the robot moves.

3. Key Contributions

1. Novel oSCC Algorithm: A complete, online motion planning algorithm that solves the SIFC problem for unknown targets. It guarantees complete sensing of the workspace and complete footprint coverage of targets in polynomial time.
2. Near-Optimal Efficiency: The algorithm minimizes total travel distance. Theoretical analysis and experiments show it performs significantly better than heuristic benchmarks (Greedy, ZigZag) and approaches the theoretical lower bound (GCC).
3. Coordinated Control Design: A unified control framework that synchronizes the mobile robot's trajectory with the nozzle's filling motion, handling the dynamic constraints of both systems.
4. Comprehensive Validation: Extensive real-world experiments and simulations on various crack distributions (Uniform and Gaussian) and densities.

4. Experimental Results

The authors tested the system on a custom-built omnidirectional robot in a 5.79m x 6.10m indoor arena using simulated cracks (blue paint) and filling (red paint).

• Performance Metrics:
  • Path Length: oSCC reduced robot path length by up to 24% compared to the Greedy algorithm and significantly outperformed ZigZag.
  • Sensor Coverage: Achieved 100% workspace coverage with minimal overlap (up to 62% less overlap than Greedy).
  • Time Efficiency: Reduced total filling and travel time compared to benchmarks.
  • Accuracy: Filling accuracy was consistently near 98-99% across all planners.
• Comparison:
  • oSCC vs. SCC: Performance was nearly identical, confirming that the online nature of oSCC does not sacrifice optimality.
  • oSCC vs. Benchmarks: oSCC and SCC were superior to Greedy and ZigZag in all metrics (time, distance, coverage).
• Computational Complexity: oSCC computation time scales linearly with crack density. It is computationally efficient enough for online execution.

5. Significance

• Infrastructure Maintenance: Provides a viable, cost-effective, and safe solution for automating the labor-intensive task of crack repair in civil infrastructure.
• Generalizability: While focused on cracks, the SIFC framework is applicable to other dual-task robotic problems, such as sensing and cleaning dirty surfaces, or finding and collecting mines.
• Theoretical Advancement: Bridges the gap between offline optimal coverage (known maps) and online exploration (unknown maps), offering a provably complete and near-optimal solution for coupled sensing and actuation tasks.
• Practical Implementation: Demonstrates that complex motion planning and coordinated control can be successfully deployed on physical hardware with real-time constraints.

In conclusion, this work presents a robust, mathematically grounded, and experimentally validated framework for autonomous robotic maintenance, solving the complex coupling of inspection and repair in unknown environments.