Figure 1. Flowchart of the proposed energy-aware CPP framework. The process begins with map generation and ACO-based path planning. Redundant nodes are then inserted to account for energy constraints, and a GA refines the solution by scheduling proactive recharging stops to minimize total mission time.
This repository provides supplementary materials and visualizations for our study:
"Proactive Mission-Time-Efficient Coverage Path Planning Using Hierarchical Heuristics"
(Under Review, 2025)
The proposed framework integrates:
- Ant Colony Optimization (ACO) for initial coverage path construction
- Genetic Algorithm (GA) for proactive recharging optimization
By embedding charging decisions into the planning stage, the method achieves up to 24.66% mission-time reduction, particularly in sparse charging environments.
- Proactive Charging Strategy: Incorporates recharge stops before the battery reaches critical levels.
- Hierarchical Heuristic Framework: ACO ensures effective path ordering; GA optimizes the recharging schedule.
- Robust Efficiency Gains: Validated across synthetic layouts, real-world-acquired environments, and an Antarctica-based case study.
This paper addresses the challenge of energy-aware multi-robot coverage path planning. Traditional reactive methods only trigger recharging when the battery level drops critically low, which often leads to inefficient routes or mission failure in sparse charging environments. The proposed Globally Extended Routing (GER) method proactively integrates recharging decisions into the path generation process. By embedding charging stops within the coverage sequence, GER minimizes the overall mission time while ensuring that energy constraints are satisfied.
The following Figure illustrates the difference: Black circles (N): coverage nodes, Green circles (C): charging stations, Dotted circles (Rs): sensing ranges,
Reactive planning recharges late, whereas GER proactively plans recharging actions during route construction.
Evaluation of four methods in a synthetic coverage environment:
- NCPP: No charging consideration, fails due to depletion.
- ER: Reactive charging when nearly empty, causing detours.
- EVTSP: Improves travel efficiency but still reactive in charging.
- GER (Proposed): Proactive charging integration, avoiding unnecessary detours and reducing mission time.
GER sustains safer energy margins by scheduling earlier recharges, avoiding critical depletion and reducing mission delays.
Total mission time (T(Q*)) of NCPP, ER, EVTSP, and GER in real-world-acquired environments.
GER consistently achieves the lowest mission times across charging station densities.
In the demonstration video, the coverage mission time is accelerated by approximately 24× so that the mission completes within about one minute for visual clarity. In contrast, our paper reports the normalized mission times obtained from simulation. Especially, in the sparse charging-station case, our proposed GER achieves 1164.42 s, compared to 1431.33 s for ER and 1331.86 s for EVTSP, as described in Table 4.
▶ Watch here: YouTube Link
@unpublished{Lee2025,
author = {{Junghwan Gong, Moses O. Oluma, and Seunghwan Lee},
title = {Proactive Mission-Time-Efficient Coverage Path Planning Using Hierarchical Heuristics},
note = {Manuscript under review, 2025}
}