## 3 Methods
### A* with Map Processing  
In the modified method, the main assumption was to reduce the size of the map, which reduces the number of operations necessary to perform by the A* algorithm. In order to compensate for the loss of data about obstacles resulting from the interpolation of the values of each pixel, image processing methods based on mathematical morphology were used. As a result, the obstacle was artificially enlarged so that, after rescaling, a collision-free path was achieved with an insignificant change in the path length. The general workflow of the improved A* algorithm is shown in Figure 4.  
Figure 3: Workflow of the basic A* algorithm. In the first step, depending on the entered value of the scaling factor, the map size was reduced using the bicubic interpolation method according to the following formula [36;39]:  
\[I(x,y)=\sum_{i=-1}^{2}\sum_{j=-1}^{2}p(i,j)\times w(x-i)\times w(y-j) \tag{4}\]  
where  
\(I(x,y)\)--the interpolated pixel value at the point (\(x,y\));  
\(p(I_{j})\)--the pixel value in the neighbourhood of the point (\(x,y\)) before scaling;  
\(w(d)\)--the weighting function (bicubic interpolation kernel) that defines the influence of neighbouring pixels on the value of \(I(x,y)\), calculated as follows:  
\[\mathrm{w}(d)= \begin{cases}1.5|d|^{3}-2.5|d|^{2}+1&\text{for }|d|\leq 1,\\ -0.5|d|^{3}+2.5|d|^{2}+4|d|-2&\text{for }1<|d|\leq 2,\\ 0&\text{for }|d|>2.\end{cases}  \tag{5}\]  
In the analysed case shown in Figure 5, the scaling factor was set to 0.2, which means a five-fold reduction in the map resolution. No significant differences can be observed between the two images. Figure 4: Workflow of the modified A* algorithm. Figure 5: Grayscale image used as a map for comparison of methods: (**a**) at original resolution; (**b**) after rescaling. Then, morphological operations such as dilation and closing were performed with a square-shaped structural element with dimensions of 4 \(\times\) 4 pixels (Figure 6). The value of the structural element was selected empirically to ensure a safe collision-free path. Dilation involves adding pixels to the boundaries of obstacles in an image. For grayscale images, it can be described by the following formula:  
\[(\text{A}\ \oplus\text{B})(x,y)=\text{max}(i,j)\in\text{B}\ [\text{A}(x-i,y-i)] \tag{6}\]  
where  
A--dilated image;  
B--structuring element which defines the neighbourhood of the pixel (x,y) being processed;  
(x,y)--coordinates of the pixel of a dilated image;  
(i,j)--the coordinates of the pixels within the structuring element. The above operation expanded the obstacle to prevent the calculation of route coordinates, which, after being scaled to the original size, was performed through the area occupied by the obstacle. Then, a closing operation was performed consisting of dilation followed by morphological erosion, expressed by the following formula:  
\[(\text{A}\ \cdot\text{B})(\text{x,y})=(\text{A}\ \oplus\text{B})\ \ominus\text{B} \tag{7}\]  
The morphological erosion operation is expressed by the following formula:  
\[(\text{I}\ominus\text{B})(\text{x,y})=\text{min}(\text{i,j})\in\text{B}\ [ \text{I}(\text{x}+\text{i},\text{y}+\text{j})] \tag{8}\]  
The closing operation is useful for filling small holes in an image and removing image noise such as single high-intensity pixels while preserving the shape and size of large gaps and obstacles in the image. A comparison of the original grayscale image with the image obtained after image processing using mathematical morphology operations is shown in Figure 7. After performing the above processing, the image was segmented with a threshold of 75/255 to obtain an occupancy grid. The type of morphological operation, size, and shape of the structural element significantly impact the result of map processing. Reducing the map causes the effect known as the \"blurring\" of pixels, which, after applying threshold segmentation, may increase the loss of information about obstacles in the occupancy grid.