 Open Access
 Total Downloads : 478
 Authors : Azali Saudi, Jumat Sulaiman
 Paper ID : IJERTV1IS7251
 Volume & Issue : Volume 01, Issue 07 (September 2012)
 Published (First Online): 25092012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Indoor Path Planning for Mobile Robot using HalfSweep GaussSeidel via NinePoint Laplacian (HSGS9L)
Azali Saudi1 and Jumat Sulaiman2
1School of Engineering and Information Technology
2School of Science and Technology University of Malaysia Sabah Kota Kinabalu, MALAYSIA
Abstract
This paper proposed a numerical computation for solving path planning problem for a mobile robot operating in indoor environment grid model. It is based on the use of Laplaces Equation to constraint the distribution of potential values in the configuration space of a mobile robot. Consequently, the solution of Laplaces Equation is computed by employing HalfSweep GaussSeidel via NinePoint Laplacian (HSGS9L) iterative method. The simulation results show that this halfsweep iteration performs much faster than the previous methods in generating smooth path for mobile robot to move from start to goal position.

Introduction
In industrial automation, the robot is often required to have the capability of moving quickly from a given initial point to a specified goal point. During its exploration, the robot must be able to avoid from colliding with any obstacles in its environment model. Thus, path planning problem is considered one of the most important issue in constructing a truly autonomous vehicle. This study attempts to provide the solution to the path planning problem for a mobile robot operating in indoor environment model by using a global numerical approach. It is inspired by the theory of heat transfer analogy. Based on this heat transfer model, the configuration space is modeled with Laplaces equation. Consequently, the solutions of Laplace's equation also called harmonic functions that represent temperature values distribution in the configuration space will be used to simulate the generation of path for mobile robot motion. In the past, various approaches had been used to obtain harmonic functions, but the most common method is
via numerical techniques due to the availability of fast processing machine and their elegant and efficiency in solving the problem. In this work, we investigate the performance of GaussSeidel with halfsweep iteration method based on 9point formula, better known as HalfSweep Gauss via NinePoint Laplacian (HSGS9L) iterative method to obtain the harmonic functions for generating mobile robot path in varying sizes of environment model.

Literature Review
Pioneer work by Connolly and Gruppen [1] shows that harmonic functions have a number of properties useful in robotic applications. Khatib [2] utilized the use of potential functions for robot path planning, in which every obstacle produces a repelling force and the goal exerts an attractive force. In contrast, the work by Koditschek [3] concluded that geometrically at least in certain types of domains, the potential functions can be used to guide the effector from almost any point to a given point. All of these potential field methods, however, suffer from the generation of local minima. Connolly et al.
[4] and Akishita et al. [5], both of them developed independently a global method that generates smooth path by using solutions to Laplaces equations, where the potential fields were computed in a global manner over the entire region. Meanwhile, Waydo & Murray [6] studied the use of stream functions for vehicle motion. More recently, Szulczyski et al. [7] employed harmonic functions for realtime obstacle avoidance.Various approaches had been used to obtain harmonic functions in the past. The standard are Jacobi and GaussSeidel [8] point iterative methods. Daily and Bevly [9] employed analytical solution for arbitrarily shaped obstacles. Garrido et al. [10] computed the harmonic functions with finite elements for robotic motion. Then, Abdullah [11]
introduced halfsweep iteration for his works on Explicit Decoupled Group (EDG) iterative method for solving 2D Poisson equations. This halfsweep iterative method was also applied in solving partial differential equations in Ibrahim & Abdullah [12], Yousif & Evans [13], and Abdullah & Ali [14]. A modified version of this method was also investigated by Sulaiman et al. for solving diffusion equation [15].

Configuration Space Model
Mobile robot path planning problem can be modeled as a wellknown steadystate heat transfer problem, where heat sources come from the boundaries and the heat sink will pull the heat in. This heat conduction process produces a temperature distribution and the heat flux lines that are flowing to the sink fill the workspace. In a mobile robot environment setup, the goal point is treated as a heat sink whilst the boundary walls and obstacles are considered as heat sources that are fixed with constant temperate values. Once the temperature distribution in the field is obtained, it will be used as a guide to generate path for mobile robot to move from the start point to the goal point. The idea is to follow the heat flux that will flow from high temperature sources to the lowest temperature point in the environment. The temperature distribution of the configuration space is computed by employing harmonic function to model the environment setup.
Mathematically, a harmonic function on a domain Rn is a function which satisfies Laplaces equation, in which xi is the ith Cartesian coordinate, and n is the dimension. In the case of robot path construction, the domain consists of the outer boundary walls, all obstacles in the workspace, start points and the goal point.
2 n 2
The solutions to the Laplaces Equation are examined with Dirichlet boundary conditions.

Formulation of HalfSweep Gauss Seidel via NinePoint Laplacian
Our previous works that employed a block iterative method using 9point formula (also known as 9point Laplacian) [19, 20] performed much faster than the iteration using standard 5point formula [16, 17], except for halfsweep iteration [18] which is essentially computed only half of the total nodes in the configuration space. In this study, we propose an improved version of [18] by employing 9point formula into the equation. The proposed method is now known as HalfSweep GaussSeidel via Nine Point Laplacian (HSGS9L) would iterate only half of the node points in the configuration space but include 8 neighbouring points in its formulation. By adding more points in the formulation, the accuracy of each node point calculation get higher, thus leads to faster convergence rate. With HSGS9L iterative method, the computation involves node of black points only, thus in contrast to fullsweep iteration as shown in Figure 1 (a), the halfsweep iteration of HSGS9L as shown in Figure 1 (b) involves only half of the whole node points.
Essentially, the standard fullsweep iteration uses 5point stencil shown in Figure 2 (a), whereas half sweep iteration is actually based on the fivepoint 45degree rotated finite difference approximation as shown in Figure 2 (b). The main characteristic of halfsweep iteration is the reduction of computational complexity by considering only half of the total node points.
In the case of 9point formulation, fullsweep iteration uses stencils shown in Figure 3 (a), whereas in the implementation of halfsweep iteration with
HSGS9L the stencil shown in Figure 3 (b) is used.
x2 0
(1)
Figure 4 (a) shows the five black points involve in
i1 i
The equation of Eq. (1) can be solved efficiently using numerical method. Standard methods are point Jacobi and GaussSeidel iterative method. In this study, th robot model is represented by a point in the configuration space. The configuration space is
each calculation of standard 5point halfsweep iteration, whereas Figure 4 (b) shows the nine black points to be considered in each calculation of HSGS9L iterative method. Now, let us consider the twodimensional Laplaces equation in Eq. (1) defined as
2U 2U
designed in grid form. The function values associated with each node are then computed iteratively via numerical technique to satisfy
2 x
0
2 y
(2)
equation in Eq. (1). The highest temperature is assigned to the start point whereas the goal point is assigned the lowest, meanwhile different initial temperature values are assigned to the outer wall boundaries and obstacles. Initial temperature values are not required to be assigned to the start points.
Then, the discretization of Eq. (2) based on the
NinePoint Laplacian can be defined as below
4(Ui1, j1 Ui1, j1 Ui1, j1 Ui1, j1 ) Ui2, j Ui, j2 Ui2, j Ui, j2 20Ui, j 0
(3)
The 9point finite difference approximation equation in Eq. (3) is then used to generate linear
system. To solve the generated linear system, the iterative process is run until the maximum error falls into a specified tolerance error, in which the iteration stops. It is important that tolerance error is set to a very small value since high precision is essential in order to avoid (or at least minimize) the occurrence of flat area in the final solution. Once the temperature values of all black points are obtained, approximate values of the remaining white points will be obtained directly by standard direct method computation in single iteration.

Experiments and Results
The experiment was carried out with varying sizes of static environment model, i.e. 128×128, 256×256 and 512×512, that consists of a goal point, three starting points and varying setup of inner walls and outer boundary walls. Initially, the inner and outer walls were fixed with high temperature values, whereas the goal point was set to very low temperature, and all other free spaces were set to zero temperature value. The experiments run on Intel Core 2 Duo CPU running at 3 GHz speed with 1GB of RAM. The software code, now known as RobotPath Simulator, was written in Delphi for very fast computation, see Figure 5. In the previous works [16 – 19], the code was written in MatLab. The computation speed increased 5 folds with Delphi implementation.
The iteration process terminated when the computation converges to a specified very small value, i.e. 1.010, where there were no more significant changes in temperature values. The number of iterations, maximum error and elapsed time for various numerical techniques are shown in Table 1. It was clearly shown in Figure 6 that HSGS9L iteration performed faster than the various previous methods. Note that the speed of computation gets faster as the number of obstacles increases, since nodes occupied by obstacles were ignored during computation, see Table 2.
Once the temperature distributions were obtained, the path was generated by performing steepest descent search from the start points to the goal point. The process of generating the paths was very fast. From the current point, the algorithm simply picked the lowest temperature value from its eight neighbouring points. This process continues, until the generated path reached the goal point. As shown in Figure 7(a) – (d), all three paths are successfully generated for all four scenarios of obstacles setup.

Conclusions
This study shows that solving robot path planning problem using numerical techniques are indeed very attractive and feasible due to the recent advanced and
new found techniques as well as the availability of fast machine nowadays. The proposed HSGS9L iterative method performs significantly faster than the previous methods as described in our earlier works [16 – 19]. In the future work, we would include an accelerator through Successive Over Relaxation (SOR) into the proposed method to further speed up the computation, similar to the application of NinePoint Laplacian in [20],[21].

References

Connolly, C.I. & Gruppen, R. 1993. On the applications of harmonic functions to robotics. Journal of Robotic Systems, 10(7): 931946.

Khatib, O. 1985. Real time obstacle avoidance for manipulators and mobile robots. IEEE Transactions on Robotics and Automation 1:500505.

Koditschek, D.E. 1987. Exact robot navigation by means of potential functions: Some topological considerations. Proceedings of the IEEE International Conference on Robotics and Automation: 16.

Connolly, C. I., Burns, J.B. & Weiss, R. 1990. Path planning using Laplaces equation. Proceedings of the IEEE International Conference on Robotics and Automation: 21022106.

Akishita, S., Kawamura, S. & Hayashi, K. 1990. Laplace potential for moving obstacle avoidance and approach of a mobile robot. JapanUSA Symposium on flexible automation, A Pacific rim conf.: 139 142.

Waydo, S. & Murray, R.M. 2003. Vehicle motion planning using stream functions. In Proc. of the Int. Conf. on Robotics and Automation (ICRA), 2003, pp.24842491.

Szulczyski, P., Pazderski, D. & Kozowski, K. 2011. RealTime Obstacle Avoidance Using Harmonic Potential Functions. Journal of Automation, Mobile Robotics & Intelligent Systems. Volume 5, No 3, 2011.

Sasaki, S. 1998. A Practical Computational Technique for Mobile Robot Navigation. Proceedings of the IEEE International Conference on Control Applications: 13231327.

Daily, R. & Bevly, D.M. 2008. Harmonic Potential Field Path Planning for High Speed Vehicles. In the proceeding of American Control Conference, Seattle, June 1113, 46094614.

Garrido, S., Moreno, L., Blanco, D. & Monar, F.M. 2010. Robotic Motion Using Harmonic Functions and Finite Elements. Journal of Intelligent and Robotic Systems archive. Volume 59, Issue 1, July 2010. Pages 57 73.

Abdullah, A.R. 1991. The Four Point Explicit Decoupled Group (EDG) Method: A Fast Poisson Solver. International Journal of Computer Mathematics 38, 6170 (1991).

Ibrahim, A. & Abdullah, A.R. 1995. Solving the twodimensional diffusion equation by the four point
explicit decoupled group (EDG) iterative method.
International Journal Computer Mathematics, 58
June 15 17, 2010, Kuala Lumpur, Malaysia.
Page(s): 831 836. ISBN: 9781424467150.
(1995) 253256.
[18] Saudi, A. & Sulaiman, J. 2009. HalfSweep Gauss
[13] Yousif, W. S. & Evans, D.J. 2001. Explicit De
Seidel (HSGS) Iterative Method for Robot Path
coupled Group iterative methods and their
Planning. Proceedings of the 3rd International
[14] implementations. Parallel Algorithms and Applications, 7 (2001) 5371.
Abdullah, A.R. & Ali, N.H.M. 1996. A Comparative
Conference on Informatics and Technology 2009 (Informatics 2009), Kuala Lumpur, Malaysia, Oct 27
– 28, 2009.
Study of Parallel Strategies for the Solution of
[19] Saudi, A. & Sulaiman, J. 2010. Block Iterative
Elliptic PDEs. Parallel Algorithms and Applications, 10 (1996) 93103.
Method using NinePoint Laplacian for Robot Path Planning. European Journal of Scientific Research.
[15] Sulaiman, J., Hasan, M.K. & Othman, M. 2004. The
ISSN 1450216X Vol.43 No.2, pp.204211.
HalfSweep Iterative Alternating Decomposition
[20] Saudi, A. & Sulaiman, J. 2012. Robot Path Planning
Explicit (HSIADE) Method for Diffusion Equation.
Using Four PointExplicit Group Via NinePoint
CIS 2004, LNCS 3314, pp. 5763, 2004. Springer
Laplacian (4EG9L) Iterative Method. International
Verlag Berlin Heidelberg.
Journal Procedia Engineering Volume 41, 2012,
[16] Saudi, A. & Sulaiman, J. 2009. Block Iterative Method for Robot Path Planning. The 2nd Seminar
on Engineering and IT 2009 (SEIT09), Kota Kinabalu, July 7 8, 2009.
Pages 182188. International Symposium on Robotics and Intelligent Sensors 2012 (IRIS 2012), Sep 4 6, 2012, Kuching, Malaysia. ISSN: 1877
7058.
[17] Saudi, A. & Sulaiman, J. 2010. Numerical Technique for Robot Path Planning using Four PointEG Iterative Method. In proc. of the 2010 Int.
Symposium on Information Technology (ITSim),
[21] Adams, L.M., Leveque, R.J. & Young, D.M. 1988. Analysis of the SOR Iteration for the 9Point Laplacian. SIAM Journal of Numerical Analysis 25 (5): 11561180.

(b)

Figure 1: (a) All nodes will be considered in fullsweep iteration. (b) Only black points will be considered in halfsweep iteration.
(a) (b)
Figure 2: Stencils of 5point formula for (a) fullsweep and (b) halfsweep iteration, respectively.
(a) (b)
Figure 3: Stencils of 9point formula for (a) fullsweep and (b) halfsweep iteration, respectively.
(a) (b)
Figure 4: (a) Fives black points for each calculation of 5point formula implementation. (b) For 9point formula computation, nine black points are used.
Figure 5: RoboPath Simulator was written in Delphi for very fast computation.
Figure 6: Graph performance of the three iterative methods. Number of iterations against sizes of environment model in 1 obstacle setup.
(a) (b)
(c) (d)
Figure 7: The paths generated with HalfSweep GaussSeidel via NinePoint Laplacian iterative method. (a) One obstacle; (b) Two obstacles; (c) Three obstacles; (d) Four obstacles.
Table 1. Performance comparison of GS vs HSGS vs HSGS9L in 1 obstacles setup.
Iterative 
Sizes of environment 

methods 
128×128 
256×256 
512×512 

Number of iteration 
GS 
21552 
78522 
281220 
HSGS 
11280 
41344 
149130 

HSGS9L 
9537 
34984 
126352 

Maximum error 
GS 
0.999910 
0.999910 
0.999910 
HSGS 
0.999010 
0.999910 
0.999910 

HSGS9L 
0.998810 
0.999810 
0.999910 

Elapsed time (m:s:ms) 
GS 
0:15:517 
3:52:336 
61:00:070 
HSGS 
0:03:485 
0:43:845 
10:20:754 

HSGS9L 
0:03:750 
0:48:643 
11:39:741 
GS: GaussSeidel; HSGS: HalfSweep GaussSeidel; HSGS9L: HSGS via NinePoint Laplacian.
Table 2. Performance of HSGS9L with varying number of obstacles.
Number of Size of environment
obstacles 
128×128 
256×256 
512×512 
Number of 1 
9537 
34984 
126352 
iterations 2 
9268 
34080 
123362 
3 
9073 
33451 
121337 
4 
8132 
30327 
111041 
Maximum 1 
0.998810 
0.999810 
0.999910 
error 2 
0.999710 
0.999910 
0.999910 
3 
0.998710 
0.999810 
0.999910 
4 
0.998610 
0.999710 
0.999910 
Elapsed time 1 
0m3s844ms 
0m48s643ms 
11m39s741ms 
(m:s:ms) 2 
0m3s750ms 
0m48s2ms 
11m30s632ms 
3 
0m3s672ms 
0m46s907ms 
11m10s506ms 
4 
0m3s282ms 
0m42s626ms 
10m25s630ms 