Performance Analysis of the (1+1) EA on Mobile Robot Path Planning
Path planning is a fundamental function of mobile robots that have been nowadays used in a variety of areas. Evolutionary algorithms (EAs) have been experimentally showed to be efficient for the problem of mobile robot path planning, an NP-problem. However, there is no theoretical work about EAs on...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10735204/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850199871192039424 |
|---|---|
| author | Xinsheng Lai Yulin Feng |
| author_facet | Xinsheng Lai Yulin Feng |
| author_sort | Xinsheng Lai |
| collection | DOAJ |
| description | Path planning is a fundamental function of mobile robots that have been nowadays used in a variety of areas. Evolutionary algorithms (EAs) have been experimentally showed to be efficient for the problem of mobile robot path planning, an NP-problem. However, there is no theoretical work about EAs on the problem. In this paper, to understand more about why EAs are efficient and to give some advice on how to design more efficient EAs for this problem, we perform the first theoretical analysis of the expected runtime of a simple EA called (<inline-formula> <tex-math notation="LaTeX">$1+1$ </tex-math></inline-formula>) EA with three different mutations for the mobile robot path planning problem in two constructed environments. In addition, a new method of producing a path from an uncomplete path is proposed, in which a new Insert process is proposed. Meanwhile, an obvious disadvantage of one of these three mutations is discovered during the expected runtime analysis in the first environment. Based on this discovery, an improved version of this mutation is proposed. In the second constructed environment, the improved mutation is proved to be superior to the others. In detail, the (<inline-formula> <tex-math notation="LaTeX">$1+1$ </tex-math></inline-formula>) EA with the improved mutation can find the shortest path in runtime <inline-formula> <tex-math notation="LaTeX">$O(n^{5})$ </tex-math></inline-formula>, while the (<inline-formula> <tex-math notation="LaTeX">$1+1$ </tex-math></inline-formula>) EA with any one of the other mutations may be trapped in local optima. Experiments have been performed on the two constructed environments and six randomly generated environments with different sizes and varying obstacle densities. |
| format | Article |
| id | doaj-art-0553ce53aae442a8a60aef9dfd51509f |
| institution | OA Journals |
| issn | 2169-3536 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-0553ce53aae442a8a60aef9dfd51509f2025-08-20T02:12:30ZengIEEEIEEE Access2169-35362024-01-011215992015993410.1109/ACCESS.2024.348653210735204Performance Analysis of the (1+1) EA on Mobile Robot Path PlanningXinsheng Lai0https://orcid.org/0000-0002-2849-4298Yulin Feng1https://orcid.org/0009-0002-0845-8334Department of Computer Science and Engineering, Shaoxing University, Shaoxing, Zhejiang, ChinaDepartment of Computer Science and Engineering, Shaoxing University, Shaoxing, Zhejiang, ChinaPath planning is a fundamental function of mobile robots that have been nowadays used in a variety of areas. Evolutionary algorithms (EAs) have been experimentally showed to be efficient for the problem of mobile robot path planning, an NP-problem. However, there is no theoretical work about EAs on the problem. In this paper, to understand more about why EAs are efficient and to give some advice on how to design more efficient EAs for this problem, we perform the first theoretical analysis of the expected runtime of a simple EA called (<inline-formula> <tex-math notation="LaTeX">$1+1$ </tex-math></inline-formula>) EA with three different mutations for the mobile robot path planning problem in two constructed environments. In addition, a new method of producing a path from an uncomplete path is proposed, in which a new Insert process is proposed. Meanwhile, an obvious disadvantage of one of these three mutations is discovered during the expected runtime analysis in the first environment. Based on this discovery, an improved version of this mutation is proposed. In the second constructed environment, the improved mutation is proved to be superior to the others. In detail, the (<inline-formula> <tex-math notation="LaTeX">$1+1$ </tex-math></inline-formula>) EA with the improved mutation can find the shortest path in runtime <inline-formula> <tex-math notation="LaTeX">$O(n^{5})$ </tex-math></inline-formula>, while the (<inline-formula> <tex-math notation="LaTeX">$1+1$ </tex-math></inline-formula>) EA with any one of the other mutations may be trapped in local optima. Experiments have been performed on the two constructed environments and six randomly generated environments with different sizes and varying obstacle densities.https://ieeexplore.ieee.org/document/10735204/Mobile robotpath planningevolutionary algorithmsperformance analysisNP-hard problem |
| spellingShingle | Xinsheng Lai Yulin Feng Performance Analysis of the (1+1) EA on Mobile Robot Path Planning IEEE Access Mobile robot path planning evolutionary algorithms performance analysis NP-hard problem |
| title | Performance Analysis of the (1+1) EA on Mobile Robot Path Planning |
| title_full | Performance Analysis of the (1+1) EA on Mobile Robot Path Planning |
| title_fullStr | Performance Analysis of the (1+1) EA on Mobile Robot Path Planning |
| title_full_unstemmed | Performance Analysis of the (1+1) EA on Mobile Robot Path Planning |
| title_short | Performance Analysis of the (1+1) EA on Mobile Robot Path Planning |
| title_sort | performance analysis of the 1 1 ea on mobile robot path planning |
| topic | Mobile robot path planning evolutionary algorithms performance analysis NP-hard problem |
| url | https://ieeexplore.ieee.org/document/10735204/ |
| work_keys_str_mv | AT xinshenglai performanceanalysisofthe11eaonmobilerobotpathplanning AT yulinfeng performanceanalysisofthe11eaonmobilerobotpathplanning |