# Pathfinding for Mobile Robot Navigation by Exerting the Quarter-Sweep Modified Accelerated Overrelaxation (QSMAOR) Iterative Approach via the Laplacian Operator

Authors: A’qilah A. Dahalan; Azali Saudi; Jumat Sulaiman
Journal: Modelling and Simulation in Engineering
 (2022)

---

## Abstract

Mobile robots are often in a situation where they need to find a bump-free path or navigation in their environment from any starting to a specific target point. Within this study, improving the navigation problem of a mobile robot iteratively by using a numerical method based on the potential field method is one of the main aims. This potential field will lean on the use of Laplace’s equation to restrain the formation of a potential function across regions within the mobile robot configuration area. The present paper proposed a Quarter-Sweep Modified Accelerated Overrelaxation (QSMAOR) approach to improve the pathfinding of mobile robots in a given environment. The experiment shows that, by using a finite difference method, it is capable of producing an optimal path and creating a smooth path between the starting and target point. The results of the simulation also show that this numerical approach works more rapidly and provides a smoother/clearer direction than the previous study.


---

## Body

## 1. Introduction

The problem of pathfinding or navigation plays a vitally important role in autonomous mobile robots to ensure accuracy, safety, and efficiency. The basic idea to construct a genuinely autonomous mobile robot is that it must be able to design a route effectively and efficiently from the initial to the final configuration, without interfering with any static obstacles or other agents present between them. Competent algorithms to solve these kinds of problems have substantial practices in fields like computer animation [1, 2], industrial robotics [3–5], automated surveillance [6], or drug design [7]. It is therefore not shocking that studies conducted in this area have gradually increased over the last few years.In their groundbreaking work, Connolly and Gruppen [8] have shown that harmonic functions possess many useful properties in robotic applications. Meanwhile, Khatib [9] used potential functions for robot pathfinding, in which each obstacle generates repellent force while the targets exert an enticing force. However, the major shortcoming of potential fields was suffering from the cause of local minima. In the meantime, Connolly et al. [10] and Akishita et al. [11] individually industrialized a global approach through Laplace’s path planning equations towards the construction of a smooth collision-free path. These two studies show that the harmonic functions provide a swift method of generating paths for a robot configuration region and prevent the unprompted formation of local minima. Sasaki [12] indicated the use of computational methods to address the issue of path planning. It says that by simulating complicated problems on the maze, the current computational approach to motion planning worked very successfully. Dijkstra’s algorithm was implemented by Karonava et al. [13] using labyrinth-based image processing for mobile robot track planning. The algorithm determines the shortest path to the destination and demonstrates that an object can be moved through a large-scale labyrinth for the least amount of time, whereas Hachour’s analysis [14] employed the autonomous mobile technique of navigation in the form of a grid map of an unidentified region using an intelligent/smart hybrid with motionless anonymous obstacles. The crucial aspect of this is the use of the best approach to perform biological genetic theory in conjunction with networks in the role of fuzzy reasoning and inference through the use of human intelligence to take the finest avoidance course in obtaining excellent protection against obstacle risk.This paper seeks to simulate a point-robot pathfinding in the configuration space, using numerical potential functions based on the thermal transmission theory. This heat conduction model generates an environment that is not only free from local minima but also advantageous for the robot navigation control. Laplace’s equation is used to model the problem as a heat conduction process. The aim is to obtain Laplace’s equation solutions, also known as harmonic functions, to be used in simulating the temperature distribution in the configuration space for path generation purposes. Different approaches have been used to gain the harmonic functions, but, due to the obtainability of fast processing machines and their elegance and competence in problem solving, the most commonly used method is numerical approaches. In this study, several experiments were carried out to investigate the efficiency of the accelerated iterative method used to generate a mobile robot path for multisize environments. In essence, the overall process of the pathfinding construction phase in this study consists of the following steps are shown in Algorithm1.Algorithm 1
BeginStep 1: Mapping the configuration spaces (known grid space containing the goalposition, obstacles, and walls, which are based upon [15]).Step 2: Formulation and modelling the finite difference method of proposed iterativeschemes.Step 3: Algorithm of the proposed iterative schemes.Step 4: Numerical solution.Step 5: Evaluation and analysis.End


## 2. Materials and Methods

Instead of using the actual robot vehicle, we simulate the idea of moving the robot vehicle using a point that moves in a recognized space. The robot’s pathfinding problem can be designated as a problem of steady-state heat conduction. In the analogy of heat conduction, the target is to be viewed as a sink heat-tugging in. Physical boundaries and obstacles are known as heat initiators that are set at constant temperatures. The temperature distribution evolves through the thermal conductivity process, and the thermal fluxes streaming into the sink fill the configuration space. This can be perceived as a means of communication between the target, robots, and obstacles. The field temperature distribution can then be used as a reference point for a mobile robot to travel from the departure point to the target point by monitoring the thermal flux from high-temperature sources to the lowest temperature point in the region. The temperature dispersal of the configuration region is figured by engaging the harmonic function to model the setup of the environment.Mathematically, a harmonic function on a domainΩ⊂ℝn is a function that contains Laplace’s equation, wherein xi is the i-th Cartesian coordinates and n is the dimension. For the construction of the robot path, the domain Ω comprises the inner and outer boundary walls and altogether obstacles in the configuration space, starting points, and target point.
(1)∇2ϕ=∑i=1n∂2ϕ∂xi2=0.The min–max principle holds for harmonic functions, implying that no local minima can arise spontaneously within the solution domain [8]. The Gauss Integral Theorem [16] states that there is a balance between inward and outward flow on the boundary of any volume within the solution domain (excluding obstacles/goals). As a result, there is always an escape path at any point or location. The gradient vector field of a harmonic function has zero curl, and the function itself follows the min–max principle. As a result, saddle points are the only critical points that can occur. A search in the area surrounding such a critical point can lead to the escape. Furthermore, any disruption of a path caused by such points produces a smooth path everywhere. The equation of Laplace can be efficiently solved with a numerical method. Jacobi and Gauss-Seidel are standard solutions to the problem, while in this paper, equation (1) has been solved using an accelerated iterative method for rapid computation.The robot is defined in this model by a point in the configuration area. The design area is in the grid pattern. The value of the function for each node is then calculated by the numerical approach to fulfil equation (1) iteratively. The uppermost temperature is allocated to the starting point; however, the lowest is allocated to the target point. Various initial temperature values are given to the obstacles and wall boundaries. There is no requirement to allocate initial temperature values to the starting points. With the boundary conditions of Dirichlet, ϕ∂Ω=c, in which c is the constant, the solutions for Laplace’s equation were examined. As soon as the potential values of the configuration area are gained, the smooth path is able to be created by outlining the temperature distribution via the steepest descent approach, where the algorithm trails the negative gradient from the beginning to the successive points with a lower temperature until/up to the lowest temperature target point.


### 2.1. Concept of Finite Difference Approximation

Consider the equation of 2-dimensional Laplace’s as set out in equation (1) as
(2)∂2U∂x2+∂2U∂y2=0.The approximation of equation (2) can be streamlined over the five-point second-order standard finite difference method (FDM) as stated commonly as
(3)Ui−1,j+Ui+1,j+Ui,j−1+Ui,j+1−4Ui,j=0.Equation (3) is basically representing the full-sweep iteration, where the computation will consider all nodes in the mesh points. The x−y axis can also be rotated clockwise to 45° to provide another form of approximation based on the cross-orientation operator, also known as half-sweep iteration [17]. The end result will have a rotated (skewed) approximation and only half of the total nodes are taken into account. The approximation of half-sweep concept can be written as
(4)Ui+1,j+1+Ui−1,j−1+Ui+1,j−1+Ui−1,j+1−4Ui,j=0.In addition, the following approximation can be obtained by considering the distance between two points and only one quarter of the total nodes, better known as quarter-sweep iteration [18], is considered:
(5)Ui−2,j+Ui+2,j+Ui,j−2+Ui,j+2−4Ui,j=0.To understand the concept of finite difference scheme, the computational molecules for the corresponding five-point approximation of full-, half-, and quarter-sweep iterations [18] are shown in Figure 1.Figure 1
Computational molecules of five-point approximation.
(a)
Standard/full-sweep(b)
Half-sweep(c)
Quarter-sweep iterationsThe illustration of the portion of the computational grid for these five-point approximations about point for all three concepts is detailed in Figure2.Figure 2
Computational nodes of the configuration space for (a) standard or full-sweep, (b) half-sweep, and (c) quarter-sweep iteration, respectively.
(a)(b)(c)


### 2.2. Modified Point Iterative Method

The basic concept of the red-black ordering technique is computing the iteration layer by layer. Thus, the formulation of full-, half-, and quarter-sweep cases will first be considered with the red nodes, followed by the computation of the black nodes in the mesh points of the configuration spaces. The computational grid for the modified variants, which involves the red-black ordering technique for full-, half-, and quarter-sweep, is presented in Figure3.Figure 3
Computational nodes of the configuration space for (a) standard or full-sweep, (b) half-sweep, and (c) quarter-sweep iteration, respectively.
(a)(b)(c)


### 2.3. Formulation of the Proposed Method

In the robotics literature, the iterative method of standard Gauss-Seidel (GS) [11] and Successive Overrelaxation (SOR) [19] was practiced to solve equation (1). The solution of Laplace’s equation in this analysis is computed using an improved and faster numerical solver, namely, Accelerated Overrelaxation (AOR) iterative method and its variant, Modified Accelerated Overrelaxation (MAOR) iterative method.


### 2.4. Standard Accelerated Overrelaxation Iterative Method

From equations (3), (4), and (5), by adding the weighted parameter ω through SOR [20], the iterative scheme/formula for Full-Sweep SOR (FSSOR), Half-Sweep SOR (HSSOR), and Quarter-Sweep SOR (QSSOR), respectively, can be written as follows:
(6)Ui,jk+1=ω4Ui−1,jk+1+Ui+1,jk+Ui,j−1k+1+Ui,j+1k+1−ωUi,jk,(7)Ui,jk+1=ω4Ui−1,j−1k+1+Ui+1,j−1k+1+Ui−1,j+1k+Ui+1,j+1k+1−ωUi,jk,(8)Ui,jk+1=ω4Ui−2,jk+1+Ui+2,jk+Ui,j−2k+1+Ui,j+2k+1−ωUi,jk.In order to increase the convergence speed, the AOR iterative scheme is implemented by dividing the weighted parameterω from equation (6), (7), and (8) and adding another optimal relaxation parameter called r. The iterative scheme for the Full-Sweep AOR (FSAOR), Half-Sweep AOR (HSAOR), and Quarter-Sweep AOR (QSAOR) iterative method, respectively, is shown as follows:
(9)Ui,jk+1=r4Ui−1,jk+1−Ui−1,jk+Ui,j−1k+1−Ui,j−1k+ω4Ui−1,jk+Ui+1,jk+Ui,j−1k+Ui,j+1k+1−ωUi,jk,(10)Ui,jk+1=r4Ui−1,j−1k+1−Ui−1,j−1k+Ui+1,j−1k+1−Ui+1,j−1k+ω4Ui−1,j−1k+Ui+1,j−1k+Ui−1,j+1k+Ui+1,j+1k+1−ωUi,jk,(11)Ui,jk+1=r4Ui−2,jk+1−Ui−2,jk+Ui,j−2k+1−Ui,j−2k+ω4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ωUi,jk.


### 2.5. Modified Accelerated Overrelaxation Iterative Method

An approach involving the application of the red-black ordering scheme strategy towards FSSOR, HSSOR, and QSSOR, namely, the Full-Sweep Modified SOR (FSMSOR), the Half-Sweep Modified SOR (HSMSOR), and the Quarter-Sweep Modified SOR (QSMSOR) methods, respectively, can eventually enhance the convergence speed. The formulation of FSMSOR can be expressed as(12a)Ui,jk+1=ω4Ui−1,jk+Ui+1,jk+Ui,j−1k+Ui,j+1k+1−ωUi,jk,in red nodes, whereas in black nodes, it can be expressed as
(12b)Ui,jk+1=ω′4Ui−1,jk+1+Ui+1,jk+1+Ui,j−1k+1+Ui,j+1k+1+1−ω′Ui,jk.Next, the formulation of HSMOR can be written in red nodes as(13a)Ui,jk+1=ω4Ui−1,j−1k+Ui+1,j−1k+Ui−1,j+1k+Ui+1,j+1k+1−ωUi,jk,while in black nodes, it can be written as
(13b)Ui,jk+1=ω′4Ui−1,j−1k+1+Ui+1,j−1k+1+Ui−1,j+1k+1+Ui+1,j+1k+1+1−ω′Ui,jk.The formulation of the QSMSOR method can be written as(14a)Ui,jk+1=ω4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ωUi,jk,in red nodes, whereas in black nodes, it can be written as
(14b)Ui,jk+1=ω′4Ui−2,jk+1+Ui+2,jk+1+Ui,j−2k+1+Ui,j+2k+1+1−ω′Ui,jk.In the meantime, the formulation of AOR variants, from now on known as FSMAOR, HSMAOR, and QSMAOR methods, which are generalized from equations (9), (10), and (11), respectively, can be specified as follows:
(15a)Ui,jk+1=ω4Ui−1,jk+Ui+1,jk+Ui,j−1k+Ui,j+1k+1−ωUi,jk,in red nodes, and in black nodes, it can be specified as
(15b)Ui,jk+1=r4Ui−1,jk+1−Ui−1,jk+Ui,j−1k+1−Ui,j−1k+r4Ui+1,jk+1−Ui+1,jk+Ui,j+1k+1−Ui,j+1k+ω′4Ui−1,jk+Ui+1,jk+Ui,j−1k+Ui,j+1k+1−ω′Ui,jk,for FSMAOR. The formulation of the HSMAOR method is given as
(16a)Ui,jk+1=ω4Ui−1,j−1k+Ui+1,j−1k+Ui−1,j+1k+Ui+1,j+1k+1−ωUi,jk,in red nodes, and in black nodes, it is given as
(16b)Ui,jk+1=r4Ui−1,j+1k+1−Ui−1,j+1k+Ui−1,j−1k+1−Ui−1,j−1k+r4Ui+1,j+1k+1−Ui+1,j+1k+Ui+1,j−1k+1−Ui+1,j−1k+ω′4Ui−1,j−1k+Ui+1,j−1k+Ui−1,j+1k+Ui+1,j+1k+1−ω′Ui,jk.Finally, the formulation of the QSMAOR method can be stated as(17a)Ui,jk+1=ω4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ωUi,jk,in red nodes, and in black nodes, it can be stated as
(17b)Ui,jk+1=r4Ui−2,jk+1−Ui−2,jk+Ui,j−2k+1−Ui,j−2k+r4Ui+2,jk+1−Ui+2,jk+Ui,j+2k+1−Ui,j+2k+ω′4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ω′Ui,jk.For all formulations of AOR variants, ther, ω, and ω′ are indicated as the optimum relaxation parameters. The uncertain optimum values of r, ω, and ω′ did not limit the minimum number of iterations. Hadjidimos [21] defined that the value of r and ω′ is typically selected to be close to the value ω of the corresponding SOR, where 1≤ω<2.In this study, all these weighted parameters are determined by the process of sensitivity analysis, otherwise called parameter tuning, by means of trial and error. In order to find the optimal value, the weighted parameter values are different for each of the half- and quarter-sweep cases, as some values do not converge in certain cases. Moreover, the effect of complexity on finding parameter value to overall computation does not alter since the value of each parameter is set before the execution/computation. It will indeed change if the ranges of parameter values are set in the algorithm computation. Table1 shows some of the preliminary results (for environment size 300×300) with optimal values used throughout the experiments.Table 1
Preliminary results of weighted parameters.
Weighted parametersMethodsIteration numberExecution time (in second)ω=1.86FSSOR17288.13HSSOR8372.39QSSOR3510.39ω=1.86FSAOR15918.61r=1.87HSAOR7591.72QSAOR3480.56ω=1.86FSMSOR15836.72ω′=1.88HSMSOR7472.13QSMSOR3740.34ω=1.86FSMAOR15247.44r=1.87HSMAOR7082.19ω′=1.85QSMAOR2640.39Thus, the implementation of the QSMAOR scheme based on equations (17a) and (17b) for solving 2-dimensional Laplace’s problem as expressed in equation (2) can be stated in Algorithm 2.Algorithm 2: QSMAOR method.
1 Setup the configuration space with specified start and goal position.2 Initialising starting pointU, ε⟵10−15, iteration⟵0.3 For all non-occupied red node points using Equation (17a), calculateUi,jk+1⟵ω/4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ωUi,jk.4 For all non-occupied black node points using Equation (17b), calculateUi,jk+1⟵r/4Ui−2,jk+1−Ui−2,jk+Ui,j−2k+1−Ui,j−2k+r/4Ui+2,jk+1−Ui+2,jk+Ui,j+2k+1−Ui,j+2k+ω′/4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ω′Ui,jk.5 Compute the remaining non-occupied node points of type□ via direct method by using equationUi,jk+1⟵1/4Ui−1,j−1k+1+Ui+1,j−1k+Ui−1,j+1k+1+Ui+1,j+1k,and node points of type○ using equation.Ui,jk+1⟵1/4Ui−1,jk+1+Ui+1,jk+Ui,j−1k+1+Ui,j+1k.6 Check the convergence test forε⟵10−15. If yes, go to next step. Else back to step (3).7 Execute GDS to generate path from start to target position.


### 2.6. Computational Complexity

This section discusses the computational complexity analysis of all iterative techniques considered in this study. Each arithmetic operation (addition and multiplication) is expected to take one unit of computational time. The path tracing procedure of the GDS-DT algorithm and the arithmetic operations used in the convergence test are excluded. Tables2 and 3 show the total number of arithmetic operations required by each of the approaches examined. Additional arithmetic operations are performed for the HS and QS algorithms to determine the remaining points after convergence using direct methods, as shown in Table 4.Table 2
Number of arithmetic operations per iteration for SOR and its modified variants, MSOR methods.
MethodsADD/SUBMUL/DIVFSSOR/FSMSOR4N−122N−12HSSOR/HSMSOR4N/22+N/2−122N/22+N/2−12QSSOR/QSMSOR4N/2−122N/2−12Table 3
Number of arithmetic operations per iteration for AOR and its modified variants, MAOR methods.
MethodsADD/SUBMUL/DIVFSAOR/FSMAOR8N−123N−12HSAOR/HSMAOR8N/22+N/2−123N/22+N/2−12QSAOR/QSMAOR8N/2−123N/2−12Table 4
Number of additional arithmetic operations for the remaining points by using direct methods for all proposed iterative methods.
MethodsADD/SUBMUL/DIVHalf-sweep cases3N2/2−NN2/2−NQuarter-sweep cases33N2/4−N3N2/4−NTheoretically, as the computational complexity of the algorithm drops, the number of iterations decreases, reducing CPU time. Despite having more arithmetic operations than SOR method families, AOR method families converge faster because of additional accelerated parameter [22]. Meanwhile, the remaining points will be ignored from the total computation of computational complexity because they will have no significant impact because the computation of the remaining points is calculated in one iteration only.


## 2.1. Concept of Finite Difference Approximation

Consider the equation of 2-dimensional Laplace’s as set out in equation (1) as
(2)∂2U∂x2+∂2U∂y2=0.The approximation of equation (2) can be streamlined over the five-point second-order standard finite difference method (FDM) as stated commonly as
(3)Ui−1,j+Ui+1,j+Ui,j−1+Ui,j+1−4Ui,j=0.Equation (3) is basically representing the full-sweep iteration, where the computation will consider all nodes in the mesh points. The x−y axis can also be rotated clockwise to 45° to provide another form of approximation based on the cross-orientation operator, also known as half-sweep iteration [17]. The end result will have a rotated (skewed) approximation and only half of the total nodes are taken into account. The approximation of half-sweep concept can be written as
(4)Ui+1,j+1+Ui−1,j−1+Ui+1,j−1+Ui−1,j+1−4Ui,j=0.In addition, the following approximation can be obtained by considering the distance between two points and only one quarter of the total nodes, better known as quarter-sweep iteration [18], is considered:
(5)Ui−2,j+Ui+2,j+Ui,j−2+Ui,j+2−4Ui,j=0.To understand the concept of finite difference scheme, the computational molecules for the corresponding five-point approximation of full-, half-, and quarter-sweep iterations [18] are shown in Figure 1.Figure 1
Computational molecules of five-point approximation.
(a)
Standard/full-sweep(b)
Half-sweep(c)
Quarter-sweep iterationsThe illustration of the portion of the computational grid for these five-point approximations about point for all three concepts is detailed in Figure2.Figure 2
Computational nodes of the configuration space for (a) standard or full-sweep, (b) half-sweep, and (c) quarter-sweep iteration, respectively.
(a)(b)(c)


## 2.2. Modified Point Iterative Method

The basic concept of the red-black ordering technique is computing the iteration layer by layer. Thus, the formulation of full-, half-, and quarter-sweep cases will first be considered with the red nodes, followed by the computation of the black nodes in the mesh points of the configuration spaces. The computational grid for the modified variants, which involves the red-black ordering technique for full-, half-, and quarter-sweep, is presented in Figure3.Figure 3
Computational nodes of the configuration space for (a) standard or full-sweep, (b) half-sweep, and (c) quarter-sweep iteration, respectively.
(a)(b)(c)


## 2.3. Formulation of the Proposed Method

In the robotics literature, the iterative method of standard Gauss-Seidel (GS) [11] and Successive Overrelaxation (SOR) [19] was practiced to solve equation (1). The solution of Laplace’s equation in this analysis is computed using an improved and faster numerical solver, namely, Accelerated Overrelaxation (AOR) iterative method and its variant, Modified Accelerated Overrelaxation (MAOR) iterative method.


## 2.4. Standard Accelerated Overrelaxation Iterative Method

From equations (3), (4), and (5), by adding the weighted parameter ω through SOR [20], the iterative scheme/formula for Full-Sweep SOR (FSSOR), Half-Sweep SOR (HSSOR), and Quarter-Sweep SOR (QSSOR), respectively, can be written as follows:
(6)Ui,jk+1=ω4Ui−1,jk+1+Ui+1,jk+Ui,j−1k+1+Ui,j+1k+1−ωUi,jk,(7)Ui,jk+1=ω4Ui−1,j−1k+1+Ui+1,j−1k+1+Ui−1,j+1k+Ui+1,j+1k+1−ωUi,jk,(8)Ui,jk+1=ω4Ui−2,jk+1+Ui+2,jk+Ui,j−2k+1+Ui,j+2k+1−ωUi,jk.In order to increase the convergence speed, the AOR iterative scheme is implemented by dividing the weighted parameterω from equation (6), (7), and (8) and adding another optimal relaxation parameter called r. The iterative scheme for the Full-Sweep AOR (FSAOR), Half-Sweep AOR (HSAOR), and Quarter-Sweep AOR (QSAOR) iterative method, respectively, is shown as follows:
(9)Ui,jk+1=r4Ui−1,jk+1−Ui−1,jk+Ui,j−1k+1−Ui,j−1k+ω4Ui−1,jk+Ui+1,jk+Ui,j−1k+Ui,j+1k+1−ωUi,jk,(10)Ui,jk+1=r4Ui−1,j−1k+1−Ui−1,j−1k+Ui+1,j−1k+1−Ui+1,j−1k+ω4Ui−1,j−1k+Ui+1,j−1k+Ui−1,j+1k+Ui+1,j+1k+1−ωUi,jk,(11)Ui,jk+1=r4Ui−2,jk+1−Ui−2,jk+Ui,j−2k+1−Ui,j−2k+ω4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ωUi,jk.


## 2.5. Modified Accelerated Overrelaxation Iterative Method

An approach involving the application of the red-black ordering scheme strategy towards FSSOR, HSSOR, and QSSOR, namely, the Full-Sweep Modified SOR (FSMSOR), the Half-Sweep Modified SOR (HSMSOR), and the Quarter-Sweep Modified SOR (QSMSOR) methods, respectively, can eventually enhance the convergence speed. The formulation of FSMSOR can be expressed as(12a)Ui,jk+1=ω4Ui−1,jk+Ui+1,jk+Ui,j−1k+Ui,j+1k+1−ωUi,jk,in red nodes, whereas in black nodes, it can be expressed as
(12b)Ui,jk+1=ω′4Ui−1,jk+1+Ui+1,jk+1+Ui,j−1k+1+Ui,j+1k+1+1−ω′Ui,jk.Next, the formulation of HSMOR can be written in red nodes as(13a)Ui,jk+1=ω4Ui−1,j−1k+Ui+1,j−1k+Ui−1,j+1k+Ui+1,j+1k+1−ωUi,jk,while in black nodes, it can be written as
(13b)Ui,jk+1=ω′4Ui−1,j−1k+1+Ui+1,j−1k+1+Ui−1,j+1k+1+Ui+1,j+1k+1+1−ω′Ui,jk.The formulation of the QSMSOR method can be written as(14a)Ui,jk+1=ω4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ωUi,jk,in red nodes, whereas in black nodes, it can be written as
(14b)Ui,jk+1=ω′4Ui−2,jk+1+Ui+2,jk+1+Ui,j−2k+1+Ui,j+2k+1+1−ω′Ui,jk.In the meantime, the formulation of AOR variants, from now on known as FSMAOR, HSMAOR, and QSMAOR methods, which are generalized from equations (9), (10), and (11), respectively, can be specified as follows:
(15a)Ui,jk+1=ω4Ui−1,jk+Ui+1,jk+Ui,j−1k+Ui,j+1k+1−ωUi,jk,in red nodes, and in black nodes, it can be specified as
(15b)Ui,jk+1=r4Ui−1,jk+1−Ui−1,jk+Ui,j−1k+1−Ui,j−1k+r4Ui+1,jk+1−Ui+1,jk+Ui,j+1k+1−Ui,j+1k+ω′4Ui−1,jk+Ui+1,jk+Ui,j−1k+Ui,j+1k+1−ω′Ui,jk,for FSMAOR. The formulation of the HSMAOR method is given as
(16a)Ui,jk+1=ω4Ui−1,j−1k+Ui+1,j−1k+Ui−1,j+1k+Ui+1,j+1k+1−ωUi,jk,in red nodes, and in black nodes, it is given as
(16b)Ui,jk+1=r4Ui−1,j+1k+1−Ui−1,j+1k+Ui−1,j−1k+1−Ui−1,j−1k+r4Ui+1,j+1k+1−Ui+1,j+1k+Ui+1,j−1k+1−Ui+1,j−1k+ω′4Ui−1,j−1k+Ui+1,j−1k+Ui−1,j+1k+Ui+1,j+1k+1−ω′Ui,jk.Finally, the formulation of the QSMAOR method can be stated as(17a)Ui,jk+1=ω4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ωUi,jk,in red nodes, and in black nodes, it can be stated as
(17b)Ui,jk+1=r4Ui−2,jk+1−Ui−2,jk+Ui,j−2k+1−Ui,j−2k+r4Ui+2,jk+1−Ui+2,jk+Ui,j+2k+1−Ui,j+2k+ω′4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ω′Ui,jk.For all formulations of AOR variants, ther, ω, and ω′ are indicated as the optimum relaxation parameters. The uncertain optimum values of r, ω, and ω′ did not limit the minimum number of iterations. Hadjidimos [21] defined that the value of r and ω′ is typically selected to be close to the value ω of the corresponding SOR, where 1≤ω<2.In this study, all these weighted parameters are determined by the process of sensitivity analysis, otherwise called parameter tuning, by means of trial and error. In order to find the optimal value, the weighted parameter values are different for each of the half- and quarter-sweep cases, as some values do not converge in certain cases. Moreover, the effect of complexity on finding parameter value to overall computation does not alter since the value of each parameter is set before the execution/computation. It will indeed change if the ranges of parameter values are set in the algorithm computation. Table1 shows some of the preliminary results (for environment size 300×300) with optimal values used throughout the experiments.Table 1
Preliminary results of weighted parameters.
Weighted parametersMethodsIteration numberExecution time (in second)ω=1.86FSSOR17288.13HSSOR8372.39QSSOR3510.39ω=1.86FSAOR15918.61r=1.87HSAOR7591.72QSAOR3480.56ω=1.86FSMSOR15836.72ω′=1.88HSMSOR7472.13QSMSOR3740.34ω=1.86FSMAOR15247.44r=1.87HSMAOR7082.19ω′=1.85QSMAOR2640.39Thus, the implementation of the QSMAOR scheme based on equations (17a) and (17b) for solving 2-dimensional Laplace’s problem as expressed in equation (2) can be stated in Algorithm 2.Algorithm 2: QSMAOR method.
1 Setup the configuration space with specified start and goal position.2 Initialising starting pointU, ε⟵10−15, iteration⟵0.3 For all non-occupied red node points using Equation (17a), calculateUi,jk+1⟵ω/4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ωUi,jk.4 For all non-occupied black node points using Equation (17b), calculateUi,jk+1⟵r/4Ui−2,jk+1−Ui−2,jk+Ui,j−2k+1−Ui,j−2k+r/4Ui+2,jk+1−Ui+2,jk+Ui,j+2k+1−Ui,j+2k+ω′/4Ui−2,jk+Ui+2,jk+Ui,j−2k+Ui,j+2k+1−ω′Ui,jk.5 Compute the remaining non-occupied node points of type□ via direct method by using equationUi,jk+1⟵1/4Ui−1,j−1k+1+Ui+1,j−1k+Ui−1,j+1k+1+Ui+1,j+1k,and node points of type○ using equation.Ui,jk+1⟵1/4Ui−1,jk+1+Ui+1,jk+Ui,j−1k+1+Ui,j+1k.6 Check the convergence test forε⟵10−15. If yes, go to next step. Else back to step (3).7 Execute GDS to generate path from start to target position.


## 2.6. Computational Complexity

This section discusses the computational complexity analysis of all iterative techniques considered in this study. Each arithmetic operation (addition and multiplication) is expected to take one unit of computational time. The path tracing procedure of the GDS-DT algorithm and the arithmetic operations used in the convergence test are excluded. Tables2 and 3 show the total number of arithmetic operations required by each of the approaches examined. Additional arithmetic operations are performed for the HS and QS algorithms to determine the remaining points after convergence using direct methods, as shown in Table 4.Table 2
Number of arithmetic operations per iteration for SOR and its modified variants, MSOR methods.
MethodsADD/SUBMUL/DIVFSSOR/FSMSOR4N−122N−12HSSOR/HSMSOR4N/22+N/2−122N/22+N/2−12QSSOR/QSMSOR4N/2−122N/2−12Table 3
Number of arithmetic operations per iteration for AOR and its modified variants, MAOR methods.
MethodsADD/SUBMUL/DIVFSAOR/FSMAOR8N−123N−12HSAOR/HSMAOR8N/22+N/2−123N/22+N/2−12QSAOR/QSMAOR8N/2−123N/2−12Table 4
Number of additional arithmetic operations for the remaining points by using direct methods for all proposed iterative methods.
MethodsADD/SUBMUL/DIVHalf-sweep cases3N2/2−NN2/2−NQuarter-sweep cases33N2/4−N3N2/4−NTheoretically, as the computational complexity of the algorithm drops, the number of iterations decreases, reducing CPU time. Despite having more arithmetic operations than SOR method families, AOR method families converge faster because of additional accelerated parameter [22]. Meanwhile, the remaining points will be ignored from the total computation of computational complexity because they will have no significant impact because the computation of the remaining points is calculated in one iteration only.


## 3. Results

The experiments were carried out on the AMD A10 machine that was equipped with 8 GB memory running at 2.50 GHz. The iteration process to evaluate the temperature values numerically at all points continues up until the stopping criterion is encountered. If the temperature values are no longer showing changes, the loop would be terminated where the difference in the measurement values was extremely small, i.e.,10−15. This high precision was needed in the solution to prevent the creation of a flat area, otherwise known as saddle points, from failing the generation of paths.Tables5 and 6 depict the number of iterations and the time of execution in seconds, respectively, required for all numerical techniques compared in the experiment to measure all temperature values in the region.Table 5
Performance of the methods considered in terms of the number of iterations.
NMethods300600900120015001800Case 1FSSOR1728811717831313464771469063FSAOR1591752916594289844429264349FSMSOR1583755716697291324480063671FSMAOR1524731116069281884339661685HSSOR83741089086158922428634630HSAOR75938038420147682256932089HSMSOR74738128484148452290932583HSMAOR70836718190143132216331409QSSOR3512078463281131248317701QSAOR3481913428075081156716436QSMSOR2541910430875711172616650QSMAOR2641836416173121130316084Case 2FSSOR2228877619254335585162173346FSAOR2006797317538305733759540082FSMSOR2097832318307319314913169822FSMAOR1872754216617289823535137356HSSOR107144389813171492641737562HSAOR94440238924156141921620483HSMSOR98841989314162932511635744HSMAOR85537878435147821802319014QSSOR4522229501487711354819254QSAOR430200745427976982710433QSMSOR3632097474783261287418304QSMAOR34918764285753791899634Case 3FSSOR362414644330045748488366125567FSAOR323613165296805173879540112979FSMSOR340213814311945436383604131946FSMAOR302312395280374889075154106841HSSOR1780744516856294184526464339HSAOR1568668115149264564071057897HSMSOR1659700615912278024280160851HSMAOR1448627114284249703845654714QSSOR82837698624150612321132999QSAOR69833667740135452088629680QSMSOR75435358122142162193331203QSMAOR60531427272127571969728031Case 4FSSOR2507986821654377625805482524FSAOR2288902519840346015319975634FSMSOR2395941120667360375542878781FSMAOR2169862318949330565086472308HSSOR1212500011036192882968342245HSAOR1097455510098176702720238693HSMSOR1155476910526184122834340319HSMAOR102843519643168772600737012QSSOR5552502563898731520821647QSAOR4672287514890301394419850QSMSOR4962391536494141452620666QSMAOR3882174490186191331118950Table 6
Performance of the methods considered in terms of the time of execution (in seconds).
NMethods300600900120015001800Case 1FSSOR8.13227.951134.253728.928686.0817147.79FSAOR8.61230.171148.873692.748660.1516968.09FSMSOR6.72240.991227.394082.359588.9019327.49FSMAOR7.44247.991295.654330.5610208.1319265.66HSSOR2.3981.24404.151375.273255.636624.13HSAOR1.7273.76369.911247.652990.336046.26HSMSOR2.1373.03373.181295.143113.406234.52HSMAOR2.1981.73431.961471.833580.866892.12QSSOR0.3914.9981.55293.92718.551445.17QSAOR0.5615.8384.47292.46709.111463.86QSMSOR0.2716.6190.51326.84787.371571.21QSMAOR0.3918.1896.43349.09848.991669.26Case 2FSSOR10.69251.721270.234077.228871.9016374.18FSAOR10.27248.241226.663976.336346.319640.11FSMSOR9.36269.681355.344329.638601.3418314.85FSMAOR9.30267.181360.644342.876977.8211888.25HSSOR2.9586.77445.701423.273356.366214.61HSAOR2.7576.79403.251263.632200.893323.99HSMSOR2.6480.20414.861338.132799.646024.91HSMAOR2.3486.67450.831409.042397.263937.09QSSOR0.6416.6990.03313.44738.741404.43QSAOR0.5616.6889.98314.14547.43829.91QSMSOR0.5018.9099.75341.75751.321556.51QSMAOR0.4218.21101.92343.47597.57897.37Case 3FSSOR16.22427.272190.457432.6814928.5134024.02FSAOR18.66418.452073.257254.0214726.6334297.24FSMSOR14.40462.032361.087957.7016036.7441566.73FSMAOR15.35450.602420.887800.2516291.2838068.00HSSOR5.16154.79783.722634.525571.9312912.67HSAOR4.80137.18721.942300.845044.6011679.58HSMSOR4.08140.88739.142443.075239.6312545.53HSMAOR4.66151.04803.102573.745642.2812799.79QSSOR0.9230.04166.12567.281275.102803.43QSAOR1.0829.24161.76570.331255.652785.10QSMSOR0.9234.09184.67629.301367.243134.97QSMAOR0.8133.22188.82608.371369.753095.58Case 4FSSOR11.02281.851441.474853.5710789.6521088.78FSAOR12.52281.781423.544743.219182.1220942.50FSMSOR9.78309.741576.445150.0711768.1023502.56FSMAOR9.83309.981581.295163.2410231.8023211.15HSSOR3.58102.16510.221686.653969.008030.14HSAOR3.0892.44471.171511.933173.827095.03HSMSOR3.2894.51482.171578.803765.847712.18HSMAOR3.27100.31533.661686.723559.837980.54QSSOR0.7519.85106.87369.38883.071736.46QSAOR0.7319.97108.78364.51790.141714.40QSMSOR0.6221.99116.25406.91860.321925.26QSMAOR0.4522.54123.71402.04876.541939.07The graphs in Figures4 (the number of iterations) and 5 (the execution time) indicate the output of the proposed methods based on Tables 5 and 6. It can be deduced from both figures that the higher the number of iterations, the longer each execution takes. By referring to both graphs, it can be seen that the QSMAOR and QSAOR have outperformed their corresponding suggested methods, in terms of either an iteration count or CPU time. This idea can also be clearly seen in Tables 5 and 6. As we can see from the table of results, the graphs for the number of iterations as well as execution time gave the same pattern. Apparently, the QSMAOR iterative scheme provides high efficiency in terms of iteration number compared to other proposed approaches, although the time required for modified families varied slightly from that for conventional methods, depending on the environments.Figure 4
Number of iterations in varying environments.
(a)
Standard technique(b)
Modified techniqueFigure 5
Performance (in seconds) in varying environments.
(a)
Standard technique(b)
Modified technique


## 4. Discussion

In this analysis, the environment setup involves four different sizes:300×300, 600×600, 900×900, and 1200×1200. From Figure 6, the target point was addressed at the fixed and lowest temperature values, while no particular temperature values are assigned to all three starting points. Various numbers of obstacles with different shapes have been placed in the environment. The Dirichlet boundary condition was implemented in the initial setting, in which the obstacles and walls were installed at high temperature values. In the region, every point was fixed to zero temperature value and then again for the target point at the lowest temperature values.Figure 6
Creation of paths from different starting points (square/green point) and target positions (round/red point) for different environments.
(a)
Case 1(b)
Case 2(c)
Case 3(d)
Case 4The trail was created by performing the steepest descent search from the start to the target point, once the temperature values have been obtained. The path generation process was very fast, in which the algorithm straightforwardly picks the lowest temperature value of its adjacent points from the current point. The cycle continues until the target point is reached. Figure6 shows that in an obstacle environment, the paths were positively created on the basis of the temperature distribution outline gained by numerical computation. Each starting point (square/green point) has been successfully completed at the specified target point (round/red point), escaping the many obstacles set in place. The flow diagram of the pathfinding technique of this study is shown in Figure 7.Figure 7
Flow diagram of the pathfinding technique.


## 5. Conclusions

The experiments show that the solution to the robot pathfinding problem can be solved using numerical approaches due to the availability of advanced algorithms and fast machines today. The QSMAOR iterative method has been shown to be very capable in obtaining the solution faster than standard SOR and AOR methods as shown in the results. In terms of actual computational time, the QSMSOR and QSMAOR methods provide the best performance. An increase in the number of obstacles in the environment does not affect the performance of the proposed algorithms, as the computing actually gets faster as the areas occupied by the obstacles are ignored during the calculation. The proposed algorithms provide a safe and smooth path from the start to the target regardless of obstacle shape and position since the generated path tends to move away from the obstacles. In the future work, the approach can be extended by employing a more advanced numerical technique that utilizes block iteration [23, 24], further speeding up the convergence rate of the iteration process.Furthermore, this outcome has the potential to be utilized in real-world applications. For example, Amer et al. [25] discussed the development of an adaptive path tracking controller with a knowledge-based supervisory algorithm for an autonomous heavy vehicle. They presented an adaptive algorithm that would determine the best controller parameter automatically based on the manoeuvring and vehicle conditions. The proposed adaptive controller worked effectively in guiding the vehicle along all trajectories, while Oskar et al. [26] developed a simulation model that allows researchers to investigate in-pipe machine features in terms of dependence on body size, bristle geometry, actuator, pipe deviations, etc. The experimental model was used to validate the simulation model, which yielded promising results. Following that, Virgala et al. [27] examined a snake robot motion in narrow spaces (i.e., a pipe) and developed a unique experimental snake robot with one revolute and one linear joint on each module and the capacity to execute in planar motion. The study presents a novel method for anchoring snake robot modules in a pipe using symmetrical curves during locomotion. Moreover, it is of high importance from a practical standpoint that the proposed new methods be able to cope with dynamic environments. Therefore, the findings of this study can also be extended/investigated in the future to include performing in a dynamic environment with moving obstacles. For example, consider [28], in which electrostatic potential field theory is applied to solve a robot’s path planning problem. To make the decision, all obstacles’ features are integrated into a scalar potential field. Practicing a scalar potential field simplifies mathematical computations and is thus realistically feasible to be applied in both static and dynamic contexts. It can be seen that the concept of potential field utilized for path planning in [28] has some similar key concepts with the current work.



---

*Source: 9388146-2022-03-12.xml*