1
|
Wang S, Cao L, Chen Y, Chen C, Yue Y, Zhu W. Gorilla optimization algorithm combining sine cosine and cauchy variations and its engineering applications. Sci Rep 2024; 14:7578. [PMID: 38555275 PMCID: PMC10981701 DOI: 10.1038/s41598-024-58431-x] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/08/2024] [Accepted: 03/29/2024] [Indexed: 04/02/2024] Open
Abstract
To address the issues of lacking ability, loss of population diversity, and tendency to fall into the local extreme value in the later stage of optimization searching, resulting in slow convergence and lack of exploration ability of the artificial gorilla troops optimizer algorithm (AGTO), this paper proposes a gorilla search algorithm that integrates the positive cosine and Cauchy's variance (SCAGTO). Firstly, the population is initialized using the refractive reverse learning mechanism to increase species diversity. A positive cosine strategy and nonlinearly decreasing search and weight factors are introduced into the finder position update to coordinate the global and local optimization ability of the algorithm. The follower position is updated by introducing Cauchy variation to perturb the optimal solution, thereby improving the algorithm's ability to obtain the global optimal solution. The SCAGTO algorithm is evaluated using 30 classical test functions of Test Functions 2018 in terms of convergence speed, convergence accuracy, average absolute error, and other indexes, and two engineering design optimization problems, namely, the pressure vessel optimization design problem and the welded beam design problem, are introduced for verification. The experimental results demonstrate that the improved gorilla search algorithm significantly enhances convergence speed and optimization accuracy, and exhibits good robustness. The SCAGTO algorithm demonstrates certain solution advantages in optimizing the pressure vessel design problem and welded beam design problem, verifying the superior optimization ability and engineering practicality of the SCAGTO algorithm.
Collapse
Affiliation(s)
- Shuxin Wang
- School of Intelligent Manufacturing, Shanghai Zhongqiao Vocational and Technical University, Shanghai, 201514, China
| | - Li Cao
- School of Intelligent Manufacturing and Electronic Engineering, Wenzhou University of Technology, Wenzhou, 325035, China
| | - Yaodan Chen
- School of Intelligent Manufacturing and Electronic Engineering, Wenzhou University of Technology, Wenzhou, 325035, China
| | - Changzu Chen
- School of Intelligent Manufacturing and Electronic Engineering, Wenzhou University of Technology, Wenzhou, 325035, China
| | - Yinggao Yue
- School of Intelligent Manufacturing and Electronic Engineering, Wenzhou University of Technology, Wenzhou, 325035, China.
- Wenzhou Key Laboratory of New Energy Materials and Devices, Wenzhou University of Technology, Wenzhou, 325035, China.
| | - Wenwei Zhu
- School of Intelligent Manufacturing and Electronic Engineering, Wenzhou University of Technology, Wenzhou, 325035, China
| |
Collapse
|
2
|
Liu N, Ma C, Hu Z, Guo P, Ge Y, Tian M. Workshop AGV path planning based on improved A* algorithm. MATHEMATICAL BIOSCIENCES AND ENGINEERING : MBE 2024; 21:2137-2162. [PMID: 38454677 DOI: 10.3934/mbe.2024094] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 03/09/2024]
Abstract
This article proposes an improved A* algorithm aimed at improving the logistics path quality of automated guided vehicles (AGVs) in digital production workshops, solving the problems of excessive path turns and long transportation time. The traditional A* algorithm is improved internally and externally. In the internal improvement process, we propose an improved node search method within the A* algorithm to avoid generating invalid paths; offer a heuristic function which uses diagonal distance instead of traditional heuristic functions to reduce the number of turns in the path; and add turning weights in the A* algorithm formula, further reducing the number of turns in the path and reducing the number of node searches. In the process of external improvement, the output path of the internally improved A* algorithm is further optimized externally by the improved forward search optimization algorithm and the Bessel curve method, which reduces path length and turns and creates a path with fewer turns and a shorter distance. The experimental results demonstrate that the internally modified A* algorithm suggested in this research performs better when compared to six conventional path planning methods. Based on the internally improved A* algorithm path, the full improved A* algorithm reduces the turning angle by approximately 69% and shortens the path by approximately 10%; based on the simulation results, the improved A* algorithm in this paper can reduce the running time of AGV and improve the logistics efficiency in the workshop. Specifically, the walking time of AGV on the improved A* algorithm path is reduced by 12s compared to the traditional A* algorithm.
Collapse
Affiliation(s)
- Na Liu
- College of Mechanical and Electrical Engineering, Shihezi University, Shihezi 832003, China
| | - Chiyue Ma
- College of Mechanical and Electrical Engineering, Shihezi University, Shihezi 832003, China
| | - Zihang Hu
- College of Mechanical and Electrical Engineering, Shihezi University, Shihezi 832003, China
| | - Pengfei Guo
- College of Mechanical and Electrical Engineering, Shihezi University, Shihezi 832003, China
| | - Yun Ge
- College of Mechanical and Electrical Engineering, Shihezi University, Shihezi 832003, China
| | - Min Tian
- College of Mechanical and Electrical Engineering, Shihezi University, Shihezi 832003, China
| |
Collapse
|
3
|
Muñoz P, Bellutta P, R-Moreno MD. Proposing new path-planning metrics for operating rovers on Mars. Sci Rep 2023; 13:22256. [PMID: 38097724 PMCID: PMC10721909 DOI: 10.1038/s41598-023-49144-8] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/04/2023] [Accepted: 12/05/2023] [Indexed: 12/17/2023] Open
Abstract
The on-ground operation of Mars rovers is a complex task that requires comprehensive planning in which path planning plays a fundamental role. The selection of paths has to be carefully chosen considering the scientific objectives, terrain, energy, and safety. In this regard, operators are assisted by path-planning algorithms that generate candidate paths based on cost functions. Distance traveled has always been considered one of the primary criteria when comparing paths. Other metrics such as the run-time to generate the solution or the number of expanded nodes are common measures considered in the literature. However, we want to analyze if those metrics provide useful information in challenging and partially known terrain. In this paper, we will review those metrics using two-path planning algorithms on real Mars maps. Based on our experience operating Mars rovers, we propose new metrics for assessing paths in real-world applications.
Collapse
Affiliation(s)
- Pablo Muñoz
- Universidad de Alcalá. EPS. ISG Group, 28871, Alcalá de Henares, Madrid, Spain
| | | | - Maria D R-Moreno
- Universidad de Alcalá. EPS. ISG Group, 28871, Alcalá de Henares, Madrid, Spain.
- TNO, IAS, The Hague, The Netherlands.
| |
Collapse
|
4
|
Gong H, Tan X, Wu Q, Li J, Chu Y, Jiang A, Han H, Zhang K. Bidirectional Jump Point Search Path-Planning Algorithm Based on Electricity-Guided Navigation Behavior of Electric Eels and Map Preprocessing. Biomimetics (Basel) 2023; 8:387. [PMID: 37754138 PMCID: PMC10526936 DOI: 10.3390/biomimetics8050387] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/04/2023] [Revised: 08/18/2023] [Accepted: 08/21/2023] [Indexed: 09/28/2023] Open
Abstract
The electric eel has an organ made up of hundreds of electrocytes, which is called the electric organ. This organ is used to sense and detect weak electric field signals. By sensing electric field signals, the electric eel can identify changes in their surroundings, detect potential prey or other electric eels, and use it for navigation and orientation. Path-finding algorithms are currently facing optimality challenges such as the shortest path, shortest time, and minimum memory overhead. In order to improve the search performance of a traditional A* algorithm, this paper proposes a bidirectional jump point search algorithm (BJPS+) based on the electricity-guided navigation behavior of electric eels and map preprocessing. Firstly, a heuristic strategy based on the electrically induced navigation behavior of electric eels is proposed to speed up the node search. Secondly, an improved jump point search strategy is proposed to reduce the complexity of jump point screening. Then, a new map preprocessing strategy is proposed to construct the relationship between map nodes. Finally, path planning is performed based on the processed map information. In addition, a rewiring strategy is proposed to reduce the number of path inflection points and path length. The simulation results show that the proposed BJPS+ algorithm can generate optimal paths quickly and with less search time when the map is known.
Collapse
Affiliation(s)
- Hao Gong
- Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, China
- Research Center for Materials and Optoelectronics, University of Chinese Academy of Sciences, Beijing 100049, China
| | - Xiangquan Tan
- Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, China
- Research Center for Materials and Optoelectronics, University of Chinese Academy of Sciences, Beijing 100049, China
- CAS Key Laboratory of On-Orbit Manufacturing and Integration for Space Optics System, Chinese Academy of Sciences, Changchun 130033, China
| | - Qingwen Wu
- Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, China
- Research Center for Materials and Optoelectronics, University of Chinese Academy of Sciences, Beijing 100049, China
- CAS Key Laboratory of On-Orbit Manufacturing and Integration for Space Optics System, Chinese Academy of Sciences, Changchun 130033, China
| | - Jiaxin Li
- Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, China
- CAS Key Laboratory of On-Orbit Manufacturing and Integration for Space Optics System, Chinese Academy of Sciences, Changchun 130033, China
| | - Yongzhi Chu
- Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, China
- Research Center for Materials and Optoelectronics, University of Chinese Academy of Sciences, Beijing 100049, China
- CAS Key Laboratory of On-Orbit Manufacturing and Integration for Space Optics System, Chinese Academy of Sciences, Changchun 130033, China
| | - Aimin Jiang
- Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, China
- Research Center for Materials and Optoelectronics, University of Chinese Academy of Sciences, Beijing 100049, China
- CAS Key Laboratory of On-Orbit Manufacturing and Integration for Space Optics System, Chinese Academy of Sciences, Changchun 130033, China
| | - Hasiaoqier Han
- Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, China
- Research Center for Materials and Optoelectronics, University of Chinese Academy of Sciences, Beijing 100049, China
- CAS Key Laboratory of On-Orbit Manufacturing and Integration for Space Optics System, Chinese Academy of Sciences, Changchun 130033, China
| | - Kai Zhang
- Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, China
- CAS Key Laboratory of On-Orbit Manufacturing and Integration for Space Optics System, Chinese Academy of Sciences, Changchun 130033, China
| |
Collapse
|
5
|
Wang L, Yang X, Chen Z, Wang B. Application of the Improved Rapidly Exploring Random Tree Algorithm to an Insect-like Mobile Robot in a Narrow Environment. Biomimetics (Basel) 2023; 8:374. [PMID: 37622979 PMCID: PMC10452469 DOI: 10.3390/biomimetics8040374] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/04/2023] [Revised: 08/05/2023] [Accepted: 08/15/2023] [Indexed: 08/26/2023] Open
Abstract
When intelligent mobile robots perform global path planning in complex and narrow environments, several issues often arise, including low search efficiency, node redundancy, non-smooth paths, and high costs. This paper proposes an improved path planning algorithm based on the rapidly exploring random tree (RRT) approach. Firstly, the target bias sampling method is employed to screen and eliminate redundant sampling points. Secondly, the adaptive step size strategy is introduced to address the limitations of the traditional RRT algorithm. The mobile robot is then modeled and analyzed to ensure that the path adheres to angle and collision constraints during movement. Finally, the initial path is pruned, and the path is smoothed using a cubic B-spline curve, resulting in a smoother path with reduced costs. The evaluation metrics employed include search time, path length, and the number of sampling nodes. To evaluate the effectiveness of the proposed algorithm, simulations of the RRT algorithm, RRT-connect algorithm, RRT* algorithm, and the improved RRT algorithm are conducted in various environments. The results demonstrate that the improved RRT algorithm reduces the generated path length by 25.32% compared to the RRT algorithm, 26.42% compared to the RRT-connect algorithm, and 4.99% compared to the RRT* algorithm. Moreover, the improved RRT algorithm significantly improves the demand for reducing path costs. The planning time of the improved RRT algorithm is reduced by 64.96% compared to that of the RRT algorithm, 40.83% compared to that of the RRT-connect algorithm, and 27.34% compared to that of the RRT* algorithm, leading to improved speed. These findings indicate that the proposed method exhibits a notable improvement in the three crucial evaluation metrics: sampling time, number of nodes, and path length. Additionally, the algorithm performed well after undergoing physical verification with an insect-like mobile robot in a real environment featuring narrow elevator entrances.
Collapse
Affiliation(s)
- Lina Wang
- College of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, China
- Key Laboratory of Intelligent Manufacturing Quality Big Data Tracing and Analysis of Zhejiang Province, China Jiliang University, Hangzhou 310018, China
| | - Xin Yang
- College of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, China
| | - Zeling Chen
- College of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, China
| | - Binrui Wang
- College of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, China
| |
Collapse
|
6
|
Qiao L, Luo X, Luo Q. An Optimized Probabilistic Roadmap Algorithm for Path Planning of Mobile Robots in Complex Environments with Narrow Channels. SENSORS (BASEL, SWITZERLAND) 2022; 22:8983. [PMID: 36433584 PMCID: PMC9699578 DOI: 10.3390/s22228983] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 10/25/2022] [Revised: 11/12/2022] [Accepted: 11/16/2022] [Indexed: 06/16/2023]
Abstract
In this paper, we propose a new path planning algorithm based on the probabilistic roadmaps method (PRM), in order to effectively solve the autonomous path planning of mobile robots in complex environments with multiple narrow channels. The improved PRM algorithm mainly improves the density and distribution of sampling points in the narrow channel, through a combination of the learning process of the PRM algorithm and the APF algorithm. We also shortened the required time and path length by optimizing the query process. The first key technology to improve the PRM algorithm involves optimizing the number and distribution of free points and collision-free lines in the free workspace. To ensure full visibility of the narrow channel, we extend the obstacles through the diagonal distance of the mobile robot while ignoring the safety distance. Considering the safety distance during movement, we re-classify the all sampling points obtained by the quasi-random sampling principle into three categories: free points, obstacle points, and adjacent points. Next, we transform obstacle points into the free points of the narrow channel by combining the APF algorithm and the characteristics of the narrow channel, increasing the density of sampling points in the narrow space. Then, we include potential energy judgment into the construction process of collision-free lines shortening the required time and reduce collisions with obstacles. Optimizing the query process of the PRM algorithm is the second key technology. To reduce the required time in the query process, we adapt the bidirectional A* algorithm to query these local paths and obtain an effective path to the target point. We also combine the path pruning technology with the potential energy function to obtain a short path without collisions. Finally, the experimental results demonstrate that the new PRM path planning technology can improve the density of free points in narrow spaces and achieve an optimized, collision-free path in complex environments with multiple narrow channels.
Collapse
Affiliation(s)
- Lijun Qiao
- School of Mechatronical Engineering, Beijing Institute of Technology, Beijing 100081, China
| | - Xiao Luo
- School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
| | - Qingsheng Luo
- School of Mechatronical Engineering, Beijing Institute of Technology, Beijing 100081, China
| |
Collapse
|
7
|
Improved On-Demand Travel Route Planning Model with Interest Fields. COMPUTATIONAL INTELLIGENCE AND NEUROSCIENCE 2022; 2022:6442441. [PMID: 35983138 PMCID: PMC9381231 DOI: 10.1155/2022/6442441] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 05/26/2022] [Accepted: 07/09/2022] [Indexed: 11/17/2022]
Abstract
Intelligent tourism route planning is an important element of smart tourism, and the current tourism route planning has problems such as strong subjectivity and low personalization considering tourists' interests. To solve the problems of current tourism route planning, an improved interest field travel route planning model is proposed. Firstly, an intelligent interest field extraction model is established. Secondly, an improved greedy algorithm is designed to reduce the risk of missing the optimal solution, strengthen the local search capability, and improve the solution accuracy of the algorithm. The extracted routes of interest sites are planned, and a motivated iterative value output model is established. The experimental results demonstrate that the selected routes are shorter and less expensive than the traditional model. By iterating the actual data to obtain the iterative values of different tourist route motivations and the sequential guide map of attractions based on tourist interests, the optimal and suboptimal routes that satisfy the tourist motivation interests are analyzed. This model has strong feasibility and practical significance for smart tourism route planning.
Collapse
|
8
|
Xiang D, Lin H, Ouyang J, Huang D. Combined improved A* and greedy algorithm for path planning of multi-objective mobile robot. Sci Rep 2022; 12:13273. [PMID: 35918508 PMCID: PMC9345932 DOI: 10.1038/s41598-022-17684-0] [Citation(s) in RCA: 7] [Impact Index Per Article: 3.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/20/2022] [Accepted: 07/29/2022] [Indexed: 11/09/2022] Open
Abstract
With the development of artificial intelligence, path planning of Autonomous Mobile Robot (AMR) has been a research hotspot in recent years. This paper proposes the improved A* algorithm combined with the greedy algorithm for a multi-objective path planning strategy. Firstly, the evaluation function is improved to make the convergence of A* algorithm faster. Secondly, the unnecessary nodes of the A* algorithm are removed, meanwhile only the necessary inflection points are retained for path planning. Thirdly, the improved A* algorithm combined with the greedy algorithm is applied to multi-objective point planning. Finally, path planning is performed for five target nodes in a warehouse environment to compare path lengths, turn angles and other parameters. The simulation results show that the proposed algorithm is smoother and the path length is reduced by about 5%. The results show that the proposed method can reduce a certain path length.
Collapse
Affiliation(s)
- Dan Xiang
- School of Automation, Guangdong Polytechnic Normal University, Guangzhou, 510665, Guangdong, China.,School of Computer Science and Information Engineering, Guangzhou Maritime University, Guangzhou, 510725, Guangdong, China
| | - Hanxi Lin
- School of Automation, Guangdong Polytechnic Normal University, Guangzhou, 510665, Guangdong, China
| | - Jian Ouyang
- Industrial Training Center, Guangdong Polytechnic Normal University, Guangzhou, 510665, Guangdong, China.
| | - Dan Huang
- The School of Mechanical and Automotive Engineering, South China University of Technology, Guangzhou, 510641, Guangdong, China
| |
Collapse
|