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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2169-3536 |