Path planning and smoothing of mobile robot based on improved artificial fish swarm algorithm

Li Fei-Fei, Yun Du, Kejin JiaScientific 2022 · DOI

TL;DR

Researchers have developed an enhanced "Artificial Fish Swarm Algorithm" (AFSA) that helps mobile robots navigate complex environments more efficiently. By combining bio-inspired swarm intelligence with Dijkstra’s algorithm and third-order Bézier curves, the new method produces paths that are not only shorter and more accurate but also smooth enough to satisfy a robot's physical steering constraints.

What Problem Does This Paper Address?

Path planning is a fundamental challenge in robotics: how do you get from Point A to Point B without hitting anything? While many algorithms exist—ranging from the classic A* to Ant Colony Optimization—they often struggle with a "jaggedness" problem. Traditional swarm algorithms frequently produce paths with sharp, unrealistic turns (inflection points) that a physical robot cannot execute smoothly.

Furthermore, the standard Artificial Fish Swarm Algorithm (AFSA) often suffers from low accuracy and slow convergence. In grid-based environments, "fish" (the digital agents) might only move in 4 or 8 directions, leading to inefficient routes. They can also suffer from "premature convergence," where the swarm gets stuck in a local dead-end rather than finding the globally shortest path.

Methods

The authors propose an improved version of AFSA, dubbed IDAFSA-S16, integrated with a path-smoothing component. Key technical innovations include:

  • Expanded Search Space: Instead of the standard 8-direction movement, the authors implemented a 16-direction search with 24 neighborhoods, allowing for much finer control and shorter paths.
  • Dijkstra Integration: To prevent agents from "teleporting" through obstacles when taking large steps, the algorithm uses Dijkstra’s algorithm to validate the feasibility of a move.
  • Dynamic Feedback & Adaptive Steps: The "field of vision" (how far an agent looks) and the "step size" are no longer static. They start large to explore the map quickly and shrink as the robot approaches the goal to fine-tune the final path.
  • Sharing Mechanism: To save on computational costs, agents at the same grid point share obstacle information, reducing redundant calculations.
  • Bézier Curve Smoothing: Once a path is found, the algorithm applies third-order Bézier curves. This ensures $C^1$ and $C^2$ continuity, meaning the path has a continuous orientation and curvature—essential for the kinematics of real-world wheeled robots.

Datasets

The study does not use external real-world datasets. Instead, the authors evaluated their algorithm using simulated grid map environments of varying complexity:

  • A simple $10 \times 10$ grid.
  • A more complex $20 \times 20$ grid.
  • A high-density $40 \times 40$ grid for testing path smoothing.

These benchmarks are standard for evaluating the geometric efficiency and computational speed of path-planning algorithms.

Key Insights and Ideas

  • The "Fish-Eye" Strategy: The most clever part of the improvement is the dynamic field of vision. By mimicking how a searcher might look at a broad map from a distance and then zoom in as they get closer to their destination, the algorithm avoids the "oscillation" that usually plagues swarm algorithms in the final stages of a search.
  • Safety via Dijkstra: Swarm algorithms are often criticized for being "blind" to obstacles between steps. By using a classical graph-search algorithm (Dijkstra) as a safety check for the bio-inspired swarm, the authors created a hybrid that is both creative and robust.
  • Collinear Optimization: Before smoothing the path, the algorithm identifies and removes redundant points on straight lines. This "cleaning" phase makes the subsequent Bézier curve fitting much more effective, preventing unnecessary wobbles in the final trajectory.

Key Results

The proposed IDAFSA-S16 outperformed traditional AFSA variants across several metrics:

  • Accuracy: Achieved a 100% planning success rate in tested environments.
  • Path Length: In a $10 \times 10$ environment, the average path length was reduced by approximately 27.4% compared to the basic 4-direction AFSA.
  • Efficiency: The number of iterations required to find the target was significantly lower, with the IDAFSA-S16 converging much faster than its predecessors.
  • Smoothness: Qualitative results show that the Bézier-smoothed paths eliminate sharp turns, making them ready for deployment on hardware with specific minimum turning radii.

Limitations and Future Work

While the results are promising, the paper notes a few areas for growth:

  • Static Environments: The algorithm was tested in static raster (grid) maps. It remains to be seen how it handles dynamic obstacles (like moving people or other robots) in real-time.
  • Computational Overhead: While the sharing mechanism helps, the introduction of Dijkstra’s algorithm increases the computational load per step.
  • Real-World Testing: The study is entirely simulation-based. The authors plan to move into real-world experimental debugging and explore multi-robot collaborative path planning in future iterations.

Summary updated

Abstract

An algorithm that integrates the improved artificial fish swarm algorithm with continuous segmented Bézier curves is proposed, aiming at the path planning and smoothing of mobile robots. On the one hand, to overcome the low accuracy problems, more inflection points and relatively long planning paths in the traditional artificial fish swarm algorithm for path planning, feasible solutions and a range of step sizes are introduced based on Dijkstra's algorithm. To solve the problems of poor convergence and degradation that hinder the algorithm's ability to find the best in the later stage, a dynamic feedback horizon and an adaptive step size are introduced. On the other hand, to ensure that the planned paths are continuous in both orientation and curvature, the Bessel curve theory is introduced to smooth the planned paths. This is demonstrated through a simulation that shows the improved artificial fish swarm algorithm achieving 100% planning accuracy, while ensuring the shortest average path in the same grid environment. Additionally, the smoothed path is continuous in both orientation and curvature, which satisfies the kinematic characteristics of the mobile robot.
BibTeX
@inproceedings{feifei2022path,
  author = {Li Fei-Fei and Yun Du and Kejin Jia},
  title = {{Path planning and smoothing of mobile robot based on improved artificial fish swarm algorithm}},
  booktitle = {Scientific},
  year = {2022},
  doi = {10.1038/s41598-021-04506-y},
}
Figure