# The Path Planning of Mobile Robots Based on an Improved Genetic Algorithm
## 3 Improved Genetic Algorithm
### Population Initialization
#### 3.1.2 The Multi-Step Method  
Traditional path planning algorithms typically use the grid center points as a standard, where the path travels from the starting point through several center points to the destination. This method is simple and effective, but it has significant drawbacks: the path is constrained by the grid centers, often resulting in a stair-step or polyline shape, lacking smoothness and a natural feel. Additionally, in complex obstacle environments, excessive reliance on grid centers may prevent the discovery of an effective path, resulting in a lack of flexibility and robustness.  
Since the Bresenham algorithm does not require floating-point operations, it conserves hardware resources, as its integer arithmetic avoids the high cost and inefficiency associated with complex floating-point calculations. Therefore, an improved multi-step method based on the Bresenham algorithm is proposed, which eliminates the constraint of grid centers. This method directly detects the linear connectivity between two points. If the two points are directly connected, a straight-line path is generated; if obstructed by an obstacle, intermediate nodes are dynamically inserted, prioritizing the midpoint or nearby free grid cells for adjustment, to ensure the connectivity and feasibility of the path. As shown in Figure 2, the green dashed line represents the determination of whether the straight line passes through an obstacle based on the Bresenham algorithm; the black solid line represents the feasible path segment; P1, P2, and P3 are insertion points; and the red circles indicate locations where the straight line intersects obstacles.  
However, the traditional Bresenham algorithm can only directly identify the dark-blue grid cells shown in Figure 3, while the light-colored grid cells will be missed. To address this issue, this paper improves the Bresenham algorithm by adding a detection mechanism for light-colored grid cells, enabling it to identify all the grid cells that the line passes through. Method for detecting light-colored grid cells: taking the line with slope k = \(\frac{y_{2}-y_{1}}{2-x_{1}}\in[0,1]\) and the grid cells A \((x_{A},y_{A})\) and B \((x_{B},y_{B})\) from Figure 3 as an example, when the Bresenham algorithm computes the change in the y-coordinate of grid cell B, compare \((x_{A}+0.5)\)k with \(y_{A}=y_{1}\). If \((x_{A}+0.5)\)k \(>y_{1}\), the line passes through the cell above A; if \((x_{A}+0.5)\)k \(=y_{1}\), the line passes through only both grid cells A and B; if \((x_{A}+0.5)\)k \(<y_{1}\), the line passes through the cell below B. This is shown in Figure 3.  
The specific steps of the improved Bresenham algorithm for detecting the grid cells a straight line passes through are as follows:  
Step 1: Input the coordinates of the two endpoints, \((x_{1}\),\(y_{1})\) and \((x_{2}\),\(y_{2})\), and initialize an empty array [X, Y].  
Step 2: Calculate dx = \(\mid x_{1}-x_{2}\mid\) and \(\mid y_{1}-y_{2}\mid\). If dx \(<\) dy, swap the x and y coordinates to ensure stepping along the y-axis. If \(x_{1}>x_{2}\), swap the start and end coordinates to ensure traversal from left to right.  
Step 3: Traverse the x coordinates from left to right. Each time x moves one step forward, accumulate the error. If the error exceeds the threshold, update the y coordinate and add the updated coordinates (x, y) to the [X, Y] set (if dx \(<\) dy, swap the coordinates before adding to [X, Y]). Each time the y coordinate is updated, check for any missing grid cells. If there are any, they should be supplemented promptly, and the supplemented grid cells should also be added to [X, Y] (similarly, when dx \(<\) dy, swap the coordinates before adding to [X, Y]).  
Step 4: Return the array [X, Y], which contains the coordinates of all grid cells on the path.  
The improved Bresenham algorithm is shown in Algorithm 1.  
Figure 3: The improved Bresenham algorithm detects all the grid cells a straight line passes through.  
Figure 2: Multi-step principle diagram. (a) step1; (b) step2; (c) step3.