Enhanced Rime Optimization Algorithm for Robot Path Planning in Complex Environments

0
0
0

Enhanced Rime Optimization Algorithm for Robot Path Planning in Complex Environments

Introduction

With the rapid development of automation technology, robots have become a prominent product of artificial intelligence and automation, widely applied across various fields. In healthcare, researchers have developed robots capable of performing complex microinjections for genetic studies, significantly enhancing the efficiency of large-scale genetic experiments. In the energy sector, inspection robots are employed to monitor power tunnels, ensuring the safe and reliable operation of electrical circuits and equipment. In manufacturing, robots are utilized for welding high-strength steel, reducing labor intensity and improving production efficiency. As robots become increasingly prevalent, path planning has emerged as a critical challenge in robotics. Path planning involves finding an optimal path for a robot in a given environment while satisfying specific constraints. An efficient path planning algorithm can effectively address complex robotic path planning problems.

Traditional path planning algorithms include artificial potential field methods, rapidly exploring random tree (RRT) algorithms, probabilistic roadmap (PRM) algorithms, and A* algorithms. However, as problem dimensionality and complexity increase, traditional methods struggle to handle high-dimensional nonlinear problems. Consequently, researchers have turned to heuristic algorithms for path planning.

Heuristic algorithms encompass traditional methods such as genetic algorithms (GA), particle swarm optimization (PSO), simulated annealing (SA), and ant colony optimization (ACO), as well as newer algorithms like the gradient-based optimizer (GBO), differentiated creative search (DCS), attraction-repulsion optimization algorithm (AROA), and exponential distribution optimizer (EDO). Compared to traditional methods, heuristic algorithms combine the global exploration capabilities of Monte Carlo methods with the strong local exploitation abilities of heuristic techniques.

The rime optimization algorithm (RIME) is a physics-inspired metaheuristic algorithm proposed in 2023, simulating the growth process of rime ice. It incorporates soft rime search strategies and hard rime penetration mechanisms to solve global optimization problems. While RIME demonstrates strong performance in convergence speed and solution accuracy, it faces challenges such as susceptibility to local optima and slow convergence in complex environments. To address these limitations, this paper proposes an enhanced rime optimization algorithm (ERIME) for mobile robot path planning in complex environments.

Methodology

  1. Environment Modeling

Constructing an environmental map model is fundamental to robot path planning. Common modeling methods include grid maps, topological maps, semi-parametric maps, probabilistic maps, and free-space methods. This study adopts a grid-based approach due to its simplicity, effectiveness, and ease of implementation. In this model, black grids represent obstacles, while white grids denote traversable areas. The robot can move in eight directions, and paths intersecting obstacles are deemed infeasible.

  1. Overview of the RIME Algorithm

RIME is inspired by the growth mechanisms of rime ice, which consists of soft rime and hard rime. The algorithm employs two main strategies:

• Soft Rime Search Strategy: Simulates the random growth of soft rime particles under windy conditions. The position update rule is influenced by the best solution from the previous iteration, random factors, and environmental parameters.

• Hard Rime Penetration Mechanism: Mimics the direct and structured growth of hard rime particles under strong winds. When conditions are met, particles directly adopt the position of the best solution.

Despite its strengths, RIME suffers from slow convergence and a tendency to get trapped in local optima.

  1. Enhanced RIME Algorithm (ERIME)

To improve RIME’s performance, three enhancement strategies are introduced:

3.1 Lens Imaging Population Selection Strategy Based on Sine Chaos Mapping

Random initialization in the original RIME may lead to suboptimal starting points, increasing the search space and slowing convergence. To address this, a sine chaos mapping method is employed to generate a more diverse initial population. The sine mapping ensures uniform distribution of particles across the search space, enhancing exploration. Additionally, a dynamic lens imaging strategy is incorporated to focus on promising regions, accelerating convergence.

3.2 Stochastic Factor-Controlled Optimal Search Strategy

To improve convergence speed, a stochastic factor-controlled search strategy is introduced. This strategy narrows the search range by utilizing the maximum and minimum positions of particles, allowing solutions to oscillate near optimal values and expediting the search process. Random factors enhance the algorithm’s ability to escape local optima.

3.3 Centroid-Guided Development Mechanism

In the later stages of iteration, particles in RIME tend to converge rapidly around the current best solution, risking premature convergence to local optima. To mitigate this, a centroid-guided mechanism is proposed. By calculating the centroid of the current population, the algorithm encourages exploration of broader regions, promoting diversity and improving the likelihood of finding global optima.

  1. Algorithm Workflow

The ERIME algorithm integrates the three enhancement strategies into the original RIME framework:

  1. Initialization: The population is initialized using sine chaos mapping and lens imaging.

  2. Soft Rime Search: Particles update their positions based on the best solution and stochastic factors.

  3. Hard Rime Penetration: Particles adopt the best solution if conditions are met.

  4. Centroid Guidance: The centroid mechanism ensures diversity and prevents premature convergence.

  5. Time Complexity Analysis

The time complexity of ERIME is analyzed to ensure efficiency. The soft rime search and hard rime penetration stages each have a complexity of O(n²), while fitness evaluation is O(n log n). Thus, the overall complexity remains O((n + log n) × n), consistent with the original RIME.

Convergence Analysis

  1. Markov Chain Model

To validate ERIME’s convergence, a Markov chain model is constructed. The algorithm’s state transitions are modeled as a Markov process, where future states depend only on the current state. Key definitions include:
• Particle State: Represents a particle’s position in the search space.

• Population State: The collective state of all particles.

• State Transition Probability: The probability of transitioning between states, governed by the soft rime search and hard rime penetration mechanisms.

The model confirms that ERIME’s state sequence forms a finite homogeneous Markov chain.

  1. Global Convergence

Using the global convergence theorem, ERIME is proven to converge to the global optimum with probability 1. The algorithm satisfies two conditions:

  1. Elitism: The best solution is preserved in each iteration.
  2. Exploration: The probability of not finding the global optimum approaches zero over infinite iterations.

Thus, ERIME is guaranteed to converge to the global optimum.

Experimental Validation

  1. Numerical Optimization

ERIME is tested on the CEC2017 benchmark functions and compared with seven metaheuristic algorithms (PSO, GWO, GTO, CSA, DMO, GBO, and RIME). Key findings include:
• Exploration-Exploitation Balance: ERIME exhibits a balanced trade-off, with high exploration in early iterations and increased exploitation later.

• Convergence Speed and Accuracy: ERIME outperforms competitors in both convergence speed and solution accuracy across single-modal and multi-modal functions.

• Statistical Significance: Wilcoxon rank-sum tests confirm ERIME’s superiority with p-values < 0.05 in most cases.

  1. Robot Path Planning

ERIME is applied to grid-based path planning in four environments (20×20, 40×40, 60×60, and 80×80). Results demonstrate:
• Path Quality: ERIME generates shorter, smoother paths with fewer turns compared to other algorithms.

• Robustness: In randomized environments, ERIME consistently finds feasible paths, showcasing its adaptability.

Conclusion

This paper presents an enhanced rime optimization algorithm (ERIME) for mobile robot path planning in complex environments. By incorporating sine chaos mapping, stochastic factor-controlled search, and centroid-guided mechanisms, ERIME addresses the limitations of the original RIME, achieving faster convergence and better avoidance of local optima.

Theoretical analysis proves ERIME’s global convergence, while extensive experiments validate its superiority over existing algorithms. Applications in grid-based path planning further demonstrate ERIME’s effectiveness and versatility. Future work will explore ERIME’s potential in other optimization problems, such as cloud resource scheduling, neural network feature selection, and drone trajectory planning.

doi.org/10.19734/j.issn.1001-3695.2024.07.0202

Was this helpful?

0 / 0