Bidirectional Jump Point Search Path-Planning Algorithm Based on Electricity-Guided Navigation Behavior of Electric Eels and Map Preprocessing
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 el...
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-08-01
|
| Series: | Biomimetics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2313-7673/8/5/387 |
| _version_ | 1797581085610082304 |
|---|---|
| author | Hao Gong Xiangquan Tan Qingwen Wu Jiaxin Li Yongzhi Chu Aimin Jiang Hasiaoqier Han Kai Zhang |
| author_facet | Hao Gong Xiangquan Tan Qingwen Wu Jiaxin Li Yongzhi Chu Aimin Jiang Hasiaoqier Han Kai Zhang |
| author_sort | Hao Gong |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T23:00:08Z |
| format | Article |
| id | doaj.art-48602523ccfa489692781332893c440a |
| institution | Directory Open Access Journal |
| issn | 2313-7673 |
| language | English |
| last_indexed | 2024-03-10T23:00:08Z |
| publishDate | 2023-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Biomimetics |
| spelling | doaj.art-48602523ccfa489692781332893c440a2023-11-19T09:43:47ZengMDPI AGBiomimetics2313-76732023-08-018538710.3390/biomimetics8050387Bidirectional Jump Point Search Path-Planning Algorithm Based on Electricity-Guided Navigation Behavior of Electric Eels and Map PreprocessingHao Gong0Xiangquan Tan1Qingwen Wu2Jiaxin Li3Yongzhi Chu4Aimin Jiang5Hasiaoqier Han6Kai Zhang7Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, ChinaChangchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, ChinaChangchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, ChinaChangchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, ChinaChangchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, ChinaChangchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, ChinaChangchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, ChinaChangchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences, Changchun 130033, ChinaThe 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.https://www.mdpi.com/2313-7673/8/5/387electricity guidedgrid mapinflection pointsmap preprocessingpath planningrewiring |
| spellingShingle | Hao Gong Xiangquan Tan Qingwen Wu Jiaxin Li Yongzhi Chu Aimin Jiang Hasiaoqier Han Kai Zhang Bidirectional Jump Point Search Path-Planning Algorithm Based on Electricity-Guided Navigation Behavior of Electric Eels and Map Preprocessing Biomimetics electricity guided grid map inflection points map preprocessing path planning rewiring |
| title | Bidirectional Jump Point Search Path-Planning Algorithm Based on Electricity-Guided Navigation Behavior of Electric Eels and Map Preprocessing |
| title_full | Bidirectional Jump Point Search Path-Planning Algorithm Based on Electricity-Guided Navigation Behavior of Electric Eels and Map Preprocessing |
| title_fullStr | Bidirectional Jump Point Search Path-Planning Algorithm Based on Electricity-Guided Navigation Behavior of Electric Eels and Map Preprocessing |
| title_full_unstemmed | Bidirectional Jump Point Search Path-Planning Algorithm Based on Electricity-Guided Navigation Behavior of Electric Eels and Map Preprocessing |
| title_short | Bidirectional Jump Point Search Path-Planning Algorithm Based on Electricity-Guided Navigation Behavior of Electric Eels and Map Preprocessing |
| title_sort | bidirectional jump point search path planning algorithm based on electricity guided navigation behavior of electric eels and map preprocessing |
| topic | electricity guided grid map inflection points map preprocessing path planning rewiring |
| url | https://www.mdpi.com/2313-7673/8/5/387 |
| work_keys_str_mv | AT haogong bidirectionaljumppointsearchpathplanningalgorithmbasedonelectricityguidednavigationbehaviorofelectriceelsandmappreprocessing AT xiangquantan bidirectionaljumppointsearchpathplanningalgorithmbasedonelectricityguidednavigationbehaviorofelectriceelsandmappreprocessing AT qingwenwu bidirectionaljumppointsearchpathplanningalgorithmbasedonelectricityguidednavigationbehaviorofelectriceelsandmappreprocessing AT jiaxinli bidirectionaljumppointsearchpathplanningalgorithmbasedonelectricityguidednavigationbehaviorofelectriceelsandmappreprocessing AT yongzhichu bidirectionaljumppointsearchpathplanningalgorithmbasedonelectricityguidednavigationbehaviorofelectriceelsandmappreprocessing AT aiminjiang bidirectionaljumppointsearchpathplanningalgorithmbasedonelectricityguidednavigationbehaviorofelectriceelsandmappreprocessing AT hasiaoqierhan bidirectionaljumppointsearchpathplanningalgorithmbasedonelectricityguidednavigationbehaviorofelectriceelsandmappreprocessing AT kaizhang bidirectionaljumppointsearchpathplanningalgorithmbasedonelectricityguidednavigationbehaviorofelectriceelsandmappreprocessing |