The advancement of robotics and automation has ushered in an era where intelligent robots are increasingly tasked with complex duties such as environmental cleaning, surveillance, agricultural harvesting, and industrial inspection. A fundamental capability for these autonomous agents is Full Coverage Path Planning (FCPP). The objective is to ensure the robot’s trajectory passes over every accessible point within a defined workspace, while simultaneously minimizing path overlap and total travel distance. This is particularly critical for applications like floor cleaning or lawn mowing, where missing spots (low coverage) or repeated passes (high repetition rate) directly impact performance and efficiency. Traditional methods often struggle with complex, obstacle-dense environments, leading to inefficiencies and incomplete coverage. This article presents a novel FCPP method for intelligent robots based on an enhanced Artificial Fish Swarm Algorithm (AFSA). The proposed approach models dead-zone escape mechanisms, establishes a coverage completion criterion, and designs an iterative planning algorithm to achieve high coverage, low repetition, and efficient path generation in both simple and complex settings.
1. Introduction and Background
The operational efficacy of an intelligent robot in tasks requiring exhaustive area coverage hinges on the sophistication of its path planning algorithm. The core challenge lies in generating a continuous path that guides the robot to visit all free cells in a discretized map representation, typically a grid, while navigating around obstacles. Key performance indicators for evaluating such algorithms include:
Coverage Rate (CR): The percentage of the total accessible area successfully traversed by the robot.
Repetition Rate (RR): The percentage of the total path length that covers already-visited areas.
Total Path Length (PL): The cumulative distance traveled to achieve full coverage.
An ideal algorithm for an intelligent robot maximizes CR to 100%, while minimizing both RR and PL. Existing approaches, such as biologically inspired neural networks or template-based methods, often face limitations in complex environments, including susceptibility to local minima (trapping in “dead zones”), high computational load, and suboptimal path redundancy. The Artificial Fish Swarm Algorithm (AFSA), inspired by the collective behaviors of fish such as foraging, swarming, and following, offers a robust optimization framework. Its advantages include simplicity, strong robustness, insensitivity to initial parameters, and the ability to find global optima through population-based search. This work leverages these properties to develop a dedicated FCPP framework for intelligent robots, integrating a dead-zone model and a coverage-completion criterion directly into the fish swarm optimization process.
2. The Artificial Fish Swarm Algorithm (AFSA) Primer
The AFSA is a population-based metaheuristic optimization algorithm. In our context, each artificial fish (AF) represents a potential state or position of the intelligent robot within the search space (the grid map). The “food concentration” at a point is analogous to the desirability for the robot to move there, often defined by an objective function related to coverage gain and path cost. The core behaviors simulated are:
Foraging Behavior: An AF randomly selects a new state within its visual range. If the objective function value is better there, it moves a step toward it; otherwise, it selects another state randomly.
Swarming Behavior: An AF examines the number of companions ($n_f$) within its visual range and the central position ($X_c$) of that group. If the central position offers a significantly better objective value and the area is not overly crowded ($n_f / N < \delta$, where $N$ is total population and $\delta$ is a crowd factor), the AF moves toward $X_c$.
Following Behavior: An AF identifies the companion ($X_{max}$) with the best objective value within its visual range. If $X_{max}$ is significantly better and its vicinity is not too crowded, the AF moves toward $X_{max}$.
These behaviors are executed iteratively. The position of each AF is updated using formulas that incorporate its current state, perceived best local/global states, and random factors. For an AF $i$ with position $X_i(t)$ at iteration $t$, its movement can be modeled as a vector influenced by its previous velocity, its own best position ($P_i$), and the global best position ($G$) found by the swarm:
$$ \vec{v}_i(t+1) = \omega \vec{v}_i(t) + \phi_1 r_1 (\vec{P}_i – \vec{X}_i(t)) + \phi_2 r_2 (\vec{G} – \vec{X}_i(t)) $$
$$ \vec{X}_i(t+1) = \vec{X}_i(t) + \vec{v}_i(t+1) $$
where $\omega$ is an inertia weight, $\phi_1$ and $\phi_2$ are acceleration coefficients, and $r_1, r_2$ are random numbers in [0,1]. This framework provides the foundation for our path planning strategy, where the state $X_i$ encodes the robot’s position and possibly its heading.
3. Dead-Zone Modeling for Intelligent Robot Escape
A critical failure mode in FCPP for an intelligent robot is entrapment in a “dead zone” – a region from which there are no adjacent unvisited cells reachable without backtracking over visited ones. To mitigate this, we first establish a grid map model. The workspace is divided into $N_k$ square cells:
$$ N_k = \frac{L_h}{s_d} \times \frac{W_h}{s_d} $$
where $L_h$ and $W_h$ are the length and width of the map, and $s_d$ is the side length of a single grid cell. Each cell has an associated activity value $p(x,y)$ which reflects its state and attractiveness to the robot:
$$
p(x,y) =
\begin{cases}
100, & \text{if } k_m = 1 \text{ (covered)} \cup f_d = 0 \text{ (not a dead-end)} \\
50, & \text{if } k_m = 1 \cup f_d = 1 \\
0, & \text{if } k_m = 0 \text{ (uncovered)} \cup f_d = 0 \\
-50, & \text{if } k_m = 0 \cup f_d = 1
\end{cases}
$$
Here, $f_d$ is a flag indicating if a cell is a potential dead-end candidate. The activity value guides the robot’s local movement. However, to actively escape a confirmed dead zone, we define a state function $E_{ij}$ for the robot’s current cell $(i, j)$:
$$ E_{ij} = \frac{W_{sta} \cdot u_{ij}}{N_k \cdot \theta} $$
$W_{sta}$ is the number of unvisited cells in the immediate neighborhood (within a defined adjacency, e.g., 4-connectivity or 8-connectivity). $u_{ij}$ is the count of such unvisited neighbors (typically $u_{ij} \in \{0,1,2,3,4\}$). $\theta$ is a normalization constant related to the robot’s orientation. When $u_{ij} = 0$, the robot is in a dead zone. The escape direction (angle adjustment $\Delta \beta_{dead}$) is then calculated based on the gradient of $E_{ij}$ or a pre-computed vector pointing toward the nearest cell with $u_{ij} > 0$:
$$ \Delta \beta_{dead} = \arctan \left( \frac{\nabla E_{ij}^y}{\nabla E_{ij}^x} \right) \quad \text{or} \quad \Delta \beta_{dead} = \frac{E_{ij} \cdot \bar{\beta}}{\pi} $$
where $\bar{\beta}$ is a base guidance angle derived from global information. This model ensures the intelligent robot can proactively identify and navigate out of traps, reducing unnecessary repetition.
4. Full Path Coverage Criterion Based on AFSA
To guarantee the intelligent robot completes its mission, a termination criterion based on full coverage is essential. We integrate this criterion into the AFSA evaluation. The robot’s state within the AFSA is represented as an element vector in a coordinate system that includes its 2D position and a time or sequence parameter:
$$ G_t = [x_i, y_i, t_i]^T $$
The objective is to find a sequence of states (a path) that minimizes a total cost function $g_{total}$ while ensuring all free cells are visited. For path planning between target points, we define a cost function $g(x,y)$ for moving from the current state to a candidate state $(x,y)$:
$$ g(x,y) = k(x,y) + d(x,y) + \alpha \cdot \Delta \beta_{penalty} $$
where $k(x,y)$ is the actual traversal cost (often proportional to distance), $d(x,y)$ is a heuristic estimate (e.g., Euclidean distance to the goal), and $\alpha \cdot \Delta \beta_{penalty}$ penalizes sharp turns ($\Delta \beta$ being the turning angle) to encourage smooth paths. The heuristic $d(x,y)$ is crucial and is linked to coverage. We define it as the distance to the nearest unvisited cell. Within the AFSA framework, the “food concentration” or fitness value for an artificial fish (representing a candidate next position for the intelligent robot) is inversely related to this cost.
The coverage completion is checked by evaluating the minimum distance $D_{mn}$ from the robot’s prospective position to any unvisited cell. A threshold-based rule is applied:
$$
\text{If } \min(d(x,y)) > D_{threshold} \text{ for all } (x,y) \text{ in candidate set, then assume coverage complete.}
$$
In practice, a more robust method is to maintain a visited grid map. The AFSA’s global best solution $G$ is evaluated not only on path cost but also on the percentage of cells its associated path covers. The algorithm iterates until a path with $100\%$ coverage is found and no further cost reduction is possible.
5. Integrated Path Planning Algorithm for Intelligent Robots
Combining the dead-zone model and the coverage criterion, we design the complete AFSA-based FCPP algorithm for the intelligent robot. The algorithm operates on a grid map where cells are marked as free, obstacle, visited, or unvisited.
Step 1: Initialization. Initialize the fish population. Each AF’s state $X_i(0)$ is assigned a random free cell on the grid. Set personal best $P_i = X_i(0)$ and initialize the global best $G$. Mark the start cell as visited.
Step 2: Behavior Selection and Execution. For each AF $i$ (representing a potential path extension point):
- Evaluate State: Check if the current cell $(X_i)$ is a dead zone ($u_{ij}==0$). If true, invoke the dead-zone escape model to compute a temporary target direction $\Delta \beta_{dead}$.
- Foraging: Generate a random candidate cell $X_{rand}$ within the visual range. Calculate its fitness $F_{rand}$ based on $g(x,y)$ and coverage gain (prioritizing moves to unvisited cells).
- Swarming: Find the central cell $X_c$ of AFs within visual range. Calculate its fitness $F_c$.
- Following: Find the AF $X_{max}$ with the best fitness within visual range.
- Decision: Move AF $i$ to the candidate ($X_{rand}$, $X_c$, or $X_{max}$) that yields the highest fitness, adhering to the crowding factor rule. If dead-zone escape is active, bias the movement toward $\Delta \beta_{dead}$.
- Update Maps: Mark the new cell as visited. Update the path sequence.
Step 3: Update Best Positions. Update each AF’s personal best $P_i$ and the swarm’s global best $G$ if a better fitness (higher coverage rate and/or lower path cost) is found.
Step 4: Check Termination. Evaluate the global best path $G$. If it achieves $100\%$ coverage and the algorithm has converged (no improvement for consecutive iterations), proceed to Step 5. Otherwise, return to Step 2.
Step 5: Path Output. Output the global best path $G$ as the planned trajectory for the intelligent robot.
The flow of this integrated algorithm ensures that the intelligent robot systematically covers the area, escapes local traps, and minimizes repeated coverage.
6. Experimental Simulation and Analysis
To validate the proposed method, simulation experiments were conducted in MATLAB R2022a. The simulated intelligent robot had a linear speed of 0.2 m/s and an angular speed of 0.3 rad/s. Two distinct grid map environments were created: a Simple Environment with regular obstacles and a Complex Environment
6.1 Performance in Simple Environment
The simple environment featured rectangular obstacles forming regular corridors. The planned paths for all methods were visualized. The quantitative results are summarized below:
| Method | Coverage Rate (CR) | Repetition Rate (RR) | Path Length (PL in meters) |
|---|---|---|---|
| Proposed AFSA Method | 100% | 5.23% | 15.36 |
| BINN Method [Ref] | 98.5% | 6.99% | 16.98 |
| Convex Division Method [Ref] | 97.8% | 8.01% | 16.24 |
| TDWA Method [Ref] | 99.1% | 8.91% | 17.49 |
The proposed method successfully achieved complete (100%) coverage, while the others showed minor omissions. Furthermore, it demonstrated the lowest repetition rate and the shortest overall path length, indicating superior efficiency.
6.2 Performance in Complex Environment
The complex environment tested the algorithm’s robustness with cluttered, non-convex obstacles creating numerous potential dead zones. The paths were noticeably more tortuous. The performance metrics are shown in the following table:
| Method | Coverage Rate (CR) | Repetition Rate (RR) | Path Length (PL in meters) |
|---|---|---|---|
| Proposed AFSA Method | 100% | 10.24% | 20.34 |
| BINN Method [Ref] | 94.2% | 15.01% | 21.49 |
| Convex Division Method [Ref] | 91.5% | 22.05% | 22.36 |
| TDWA Method [Ref] | 95.7% | 18.27% | 21.07 |
In this challenging scenario, the proposed method maintained its 100% coverage, significantly outperforming the others which failed to cover all areas. Although the repetition rate and path length naturally increased compared to the simple case, they remained substantially lower than those of the对比 methods. This underscores the effectiveness of the integrated dead-zone escape model and the AFSA’s global optimization capability in preventing the intelligent robot from becoming trapped and in efficiently exploring the entire space.
6.3 Discussion of Results
The experimental results conclusively demonstrate the advantages of the AFSA-based FCPP method for intelligent robots. The consistent achievement of 100% coverage in both environments highlights the reliability of the full-coverage termination criterion. The lower repetition rates are directly attributable to the dead-zone model, which provides a principled escape mechanism instead of random backtracking. The shorter path lengths result from the AFSA’s ability to optimize the sequence of visited cells, effectively balancing exploration (visiting new cells) and exploitation (moving efficiently between them). The contrast in performance between simple and complex environments also validates the algorithm’s adaptability and robustness, which are essential qualities for a real-world intelligent robot operating in unpredictable settings.
7. Conclusion and Future Work
This article has presented a comprehensive and effective solution for the Full Coverage Path Planning problem faced by intelligent robots. By innovatively integrating a dead-zone escape model and a coverage-completion criterion into an Artificial Fish Swarm Algorithm optimization framework, the proposed method addresses key shortcomings of existing approaches. The simulation experiments confirm that the algorithm enables an intelligent robot to achieve complete area coverage (100%) with minimized path repetition and reduced total travel distance, outperforming several contemporary methods in both simple and complex obstacle environments. The success of this approach lies in its emulation of efficient collective biological behavior, translated into a robust computational strategy for autonomous navigation.
Future work will focus on several enhancements to increase the practicality and scope of the method. First, the computational efficiency and real-time performance of the algorithm will be investigated, potentially through code optimization or parallelization techniques suitable for embedded systems on intelligent robots. Second, the method will be extended and tested with different types of robotic platforms, such as differential-drive and aerial drones, to evaluate its generalizability. Third, incorporating dynamic obstacles and real-time sensor uncertainty into the model will be a critical step toward deployment in more realistic, unstructured environments. Finally, exploring hybrid approaches that combine AFSA with other local planners could further refine path smoothness and energy efficiency. The ongoing development of such advanced planning algorithms is vital for unlocking the full potential of intelligent robots across a wide spectrum of service and industrial applications.