Time Optimal Trajectory Planing Based on Improved Sparrow Search Algorithm

Xiaofeng Zhang, Fan Xiao, Xiliang Tong, Juntong Yun, Ying Liu, Ying Sun, Bo Tao, Jianyi Kong, Manman Xu, Baojia ChenFrontiers in Bioengineering and Biotechnology 2022 · DOI

TL;DR

This paper introduces a high-efficiency framework for time-optimal robot trajectory planning by combining a "unique domain" approach to inverse kinematics (IK) with an enhanced Sparrow Search Algorithm (SSA). By partitioning the joint space to streamline IK and using chaotic mapping with adaptive step factors for optimization, the researchers achieved a 40% reduction in IK computation time and significantly smoother, faster robot motions.

What Problem Does This Paper Address?

In industrial robotics, "time-optimal trajectory planning" is the holy grail of efficiency—moving a robot arm from point A to point B as quickly as possible without exceeding the physical limits of its motors (velocity, acceleration, and jerk).

However, two major bottlenecks exist:

  1. The IK Bottleneck: Calculating how joints must move to reach a specific point in space (Inverse Kinematics) is computationally heavy. Most robots have multiple ways to reach the same point (multiple solutions), and filtering these solutions in real-time wastes precious processing power.
  2. The Optimization Trap: Finding the absolute fastest trajectory is a complex, non-linear problem. Standard optimization algorithms often get stuck in "local optima" (good solutions that aren't the best) or converge too slowly for real-time applications.

Methods

The authors propose a two-part solution implemented on a UR5 collaborative robot:

1. Joint Space Partitioning (Unique Domain Theory)

Instead of calculating all eight possible IK solutions for the UR5 and then filtering them, the authors used "unique domain theory." By partitioning the joint space based on the robot's Jacobian matrix, they ensure that each domain corresponds to a single, unique analytic solution. This eliminates the need for redundant calculations and filtering logic.

2. Improved Sparrow Search Algorithm (TADF-SSA)

The Sparrow Search Algorithm (SSA) is a relatively new metaheuristic inspired by the foraging and anti-predatory behavior of sparrows. The authors improved it in two ways:

  • Tent Chaotic Mapping: Standard algorithms start with a random population. Using Tent mapping ensures a more uniform distribution of "sparrows" across the search space, increasing population diversity and preventing early convergence on a mediocre solution.
  • Adaptive Step Factor (ADF): They introduced a cosine annealing-based step factor. This allows the algorithm to take large "leaps" early on to explore the global space and smaller, precise "steps" later to fine-tune the optimal trajectory.

Datasets

As is common in robotics research, the "dataset" consists of a specific task trajectory used for benchmarking. The authors used a spiral line trajectory in a Cartesian coordinate system with:

  • A center at (-200, 100) mm.
  • A radius of 60 mm and a pitch of 10 mm.
  • 20 discrete sampling points.

The performance was evaluated against standard SSA, T-SSA (Tent mapping only), and ADF-SSA (Adaptive factor only).

Key Insights and Ideas

  • IK as a Geometry Problem, Not Just Math: By treating the joint space as a set of partitioned "unique domains," the authors turned a selection problem into a direct calculation. This is a significant shift from the "calculate-then-filter" status quo.
  • Smoothness via Cubic Splines: The use of cubic splines ensures that while the robot is moving at its limit, the acceleration remains continuous. This prevents the "jerky" movements that cause mechanical wear and tear.
  • Balancing Exploration and Exploitation: The TADF-SSA demonstrates that combining chaotic initialization with adaptive movement logic significantly outperforms the base algorithm in both speed and accuracy.

Key Results

  • IK Speedup: The joint space division method saved 39.76% of the time required for inverse kinematics calculations compared to traditional filtering methods.
  • Trajectory Optimization: The movement time of the optimized trajectory was 8.66 seconds, which is 82.68% shorter than the initial unoptimized guess (50 seconds).
  • Convergence Efficiency: The improved TADF-SSA reached its optimal fitness value in just 18.2 iterations on average, compared to 47.8 iterations for the standard SSA.
  • Smoothness: Experimental results confirmed that the trajectories stayed within the maximum velocity, acceleration, and jerk constraints of the UR5, ensuring motor protection.

Limitations and Future Work

The primary limitation acknowledged by the authors is generalizability. The current method for calculating the unique IK domains relies heavily on the specific mechanical structure and DH parameters of the UR5 robot.

While the optimization algorithm (TADF-SSA) can be applied to any robot, the high-speed IK partitioning currently requires manual derivation for different robot configurations. The authors suggest that future work should focus on generalizing this joint space partitioning to a wider variety of tandem robots.

Summary updated

Abstract

Complete trajectory planning includes path planning, inverse solution solving and trajectory optimization. In this paper, a highly smooth and time-saving approach to trajectory planning is obtained by improving the kinematic and optimization algorithms for the time-optimal trajectory planning problem. By partitioning the joint space, the paper obtains an inverse solution calculation based on the partitioning of the joint space, saving 40% of the inverse kinematics solution time. This means that a large number of computational resources can be saved in trajectory planning. In addition, an improved sparrow search algorithm (SSA) is proposed to complete the solution of the time-optimal trajectory. A Tent chaotic mapping was used to optimize the way of generating initial populations. The algorithm was further improved by combining it with an adaptive step factor. The experiments demonstrated the performance of the improved SSA. The robot's trajectory is further optimized in time by an improved sparrow search algorithm. Experimental results show that the method can improve convergence speed and global search capability and ensure smooth trajectories.
BibTeX
@inproceedings{zhang2022time,
  author = {Xiaofeng Zhang and Fan Xiao and Xiliang Tong and Juntong Yun and Ying Liu and Ying Sun and Bo Tao and Jianyi Kong and Manman Xu and Baojia Chen},
  title = {{Time Optimal Trajectory Planing Based on Improved Sparrow Search Algorithm}},
  booktitle = {Frontiers in Bioengineering and Biotechnology},
  year = {2022},
  doi = {10.3389/fbioe.2022.852408},
}
Figure