Numerical simulation of robot navigation algorithms using families of block modified two-parameter over relaxation iterative methods

A truly autonomous robot must have the capability to find path from its starting to a specified goal position efficiently. This study proposed a robot path finding technique that relies on the use of Laplace's equation to constrain the generation of Laplacian potential values. Previously, it was found that by applying numerical techniques, the computation of Laplacian potentials becomes more efficient as it produces more encouraging results. The numerical implementations of these previous works, however, were too slow when handling computation in a large environment. In an attempt to improve the robustness of robot path finding, this study initiates the application of Two-Parameter Over-Relaxation (TOR) and its modified variants, Modified Two-Parameter Over-Relaxation (MTOR) iterative methods for computing the Laplacian potentials to solve the path finding problem. The proposed methods would be implemented using family of Point and Block iteration techniques based on the 5-Point Laplacian finite difference discretisation schemes. Within the family of Point methods, the simulation results show that the application of half- and quarter-sweep concepts has reduced the computational complexities of the algorithms by approximately 50% and 75% respectively. Significantly, simulations with the family of Block methods have provided even faster computation. In terms of iterations count, the Block iterative methods have shown lesser number of iterations than that of Point methods. Likewise, in terms of CPU time, the speed difference between Point and Block iterative methods also varied significantly especially for large environment. These both terms improved by approximately 25% to 35%. Once the Laplacian potentials are obtained, the combination of Gradient Descent Search (GDS) and Distance Transform (DT), known as GDS-DT, technique is performed for path tracing to the goal position. In conclusion, the main contribution of this study is the designation of the family of Point and Block TOR and MTOR iterative methods to obtain the Laplacian potentials. These faster MTOR variants method overcome the slow performance of the existing methods, particularly when handling computation in large environment. Finally, a new robust path searching GDS-DT technique with combination of the proposed method offers the capability of successfully handling navigations even in complex environment.