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 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 ( $1+1$ ) 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 ( $1+1$ ) EA with the improved mutation can find the shortest path in runtime $O(n^{5})$ , while the ( $1+1$ ) 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.