Robot path planning using family of SOR iterative methods with laplacian behaviour-based control

A truly autonomous robot must have the capability to find path from its start point to a specified goal point. This study proposed a robot path planning technique that relies on the use of Laplace's equation to constrain the generation of potential values. It is based on the theory of heat tran...

Full description

Saved in:

Bibliographic Details
Main Author:	Azali Saudi
Format:	Thesis
Language:	English English
Published:	2015
Subjects:	TJ210.2-211.47 Mechanical devices and figures Automata Ingenious mechanisms Robots (General)
Online Access:	https://eprints.ums.edu.my/id/eprint/37449/1/24%20PAGES.pdf https://eprints.ums.edu.my/id/eprint/37449/2/FULLTEXT.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-ums-ep.37449
record_format	uketd_dc
spelling	my-ums-ep.374492023-10-02T07:21:22Z Robot path planning using family of SOR iterative methods with laplacian behaviour-based control 2015 Azali Saudi TJ210.2-211.47 Mechanical devices and figures. Automata. Ingenious mechanisms. Robots (General) A truly autonomous robot must have the capability to find path from its start point to a specified goal point. This study proposed a robot path planning technique that relies on the use of Laplace's equation to constrain the generation of potential values. It is based on the theory of heat transfer, when there exist a temperature gradient within a surface, heat energy will flow from the region of high temperature at heat source to the region of low temperature at heat sink. In this model, high Laplacian potentials are assigned to outer boundary, inner walls and obstacles. Whilst, the goal point is assigned the lowest and no Laplacian potentials are assigned to all other free spaces. The Laplacian potentials for nodes on free spaces are then computed iteratively using numerical techniques. In the literature, computing these Laplacian potentials using numerical techniques produced encouraging results. The numerical implementations of these previous works, however, were only based on family of point iterative methods i.e. Jacobi, Gauss-Seidel and Successive Overrelaxation (SOR). These standard methods are too slow when handling large environment. Therefore, this study introduces the concepts of half-sweep and quarter-sweep iterations, and initiates the first application of using family of Point SOR and family of Four Point-Block SOR iterative methods for computing the Laplacian potentials to solve the path planning problem. The implementations employ two finite difference discretization schemes that are based on 5-Point and 9-Point Laplacian. Within the family of Point SOR iterative methods, the simulation results shows that the application of half-sweep and quarter-sweep concepts reduced the computational complexities of the algorithms by approximately 50% and 75%, respectively. Significantly, simulations with family of Four Point-Block SOR iterative methods provide even faster computation. In terms of iterations count, the iterative methods based on the 9-Point Laplacian give the less number of iterations than the 5-Point Laplacian. Whilst, in terms of execution time, the speed difference between iterative methods based on 5-Point and 9-Point Laplacian is very minimal. Once the Laplacian potentials are obtained, the standard Gradient Descent Search (GDS) technique is performed for path tracing to the goal point. The existing GDS, however, suffers from the occurrence of flat region in a more difficult environment which causing the path generation to fail. Thus, this study proposes a new control known as Laplacian Behaviour-Based Control (LBBC) to overcome such problem. Due to its robustness, the LBBC successfully generated smooth path even in a more complex configuration space. Therefore in conclusion, the significant contribution of this study is in introducing for the first time the fast half-sweep and quarter-sweep iterative methods using families of Point SOR and Four Point-Block SOR methods via 5-Point and 9-Point Laplacian. These faster iterative methods overcome the slow performances of the existing standard methods, particularly when handling large environment. In addition, the newly proposed LBBC overcomes the drawback of the existing GDS that face difficulty when handling complex environment. Finally, the path planning problem is solved by combining the fast iterative method with the robust path searching LBBC technique, so that the path planning algorithm is capable of handling large and complex environment. 2015 Thesis https://eprints.ums.edu.my/id/eprint/37449/ https://eprints.ums.edu.my/id/eprint/37449/1/24%20PAGES.pdf text en public https://eprints.ums.edu.my/id/eprint/37449/2/FULLTEXT.pdf text en validuser dphil doctoral Universiti Malaysia Sabah Faculty of Science and Natural Resources
institution	Universiti Malaysia Sabah
collection	UMS Institutional Repository
language	English English
topic	TJ210.2-211.47 Mechanical devices and figures Automata Ingenious mechanisms Robots (General)
spellingShingle	TJ210.2-211.47 Mechanical devices and figures Automata Ingenious mechanisms Robots (General) Azali Saudi Robot path planning using family of SOR iterative methods with laplacian behaviour-based control
description	A truly autonomous robot must have the capability to find path from its start point to a specified goal point. This study proposed a robot path planning technique that relies on the use of Laplace's equation to constrain the generation of potential values. It is based on the theory of heat transfer, when there exist a temperature gradient within a surface, heat energy will flow from the region of high temperature at heat source to the region of low temperature at heat sink. In this model, high Laplacian potentials are assigned to outer boundary, inner walls and obstacles. Whilst, the goal point is assigned the lowest and no Laplacian potentials are assigned to all other free spaces. The Laplacian potentials for nodes on free spaces are then computed iteratively using numerical techniques. In the literature, computing these Laplacian potentials using numerical techniques produced encouraging results. The numerical implementations of these previous works, however, were only based on family of point iterative methods i.e. Jacobi, Gauss-Seidel and Successive Overrelaxation (SOR). These standard methods are too slow when handling large environment. Therefore, this study introduces the concepts of half-sweep and quarter-sweep iterations, and initiates the first application of using family of Point SOR and family of Four Point-Block SOR iterative methods for computing the Laplacian potentials to solve the path planning problem. The implementations employ two finite difference discretization schemes that are based on 5-Point and 9-Point Laplacian. Within the family of Point SOR iterative methods, the simulation results shows that the application of half-sweep and quarter-sweep concepts reduced the computational complexities of the algorithms by approximately 50% and 75%, respectively. Significantly, simulations with family of Four Point-Block SOR iterative methods provide even faster computation. In terms of iterations count, the iterative methods based on the 9-Point Laplacian give the less number of iterations than the 5-Point Laplacian. Whilst, in terms of execution time, the speed difference between iterative methods based on 5-Point and 9-Point Laplacian is very minimal. Once the Laplacian potentials are obtained, the standard Gradient Descent Search (GDS) technique is performed for path tracing to the goal point. The existing GDS, however, suffers from the occurrence of flat region in a more difficult environment which causing the path generation to fail. Thus, this study proposes a new control known as Laplacian Behaviour-Based Control (LBBC) to overcome such problem. Due to its robustness, the LBBC successfully generated smooth path even in a more complex configuration space. Therefore in conclusion, the significant contribution of this study is in introducing for the first time the fast half-sweep and quarter-sweep iterative methods using families of Point SOR and Four Point-Block SOR methods via 5-Point and 9-Point Laplacian. These faster iterative methods overcome the slow performances of the existing standard methods, particularly when handling large environment. In addition, the newly proposed LBBC overcomes the drawback of the existing GDS that face difficulty when handling complex environment. Finally, the path planning problem is solved by combining the fast iterative method with the robust path searching LBBC technique, so that the path planning algorithm is capable of handling large and complex environment.
format	Thesis
qualification_name	Doctor of Philosophy (PhD.)
qualification_level	Doctorate
author	Azali Saudi
author_facet	Azali Saudi
author_sort	Azali Saudi
title	Robot path planning using family of SOR iterative methods with laplacian behaviour-based control
title_short	Robot path planning using family of SOR iterative methods with laplacian behaviour-based control
title_full	Robot path planning using family of SOR iterative methods with laplacian behaviour-based control
title_fullStr	Robot path planning using family of SOR iterative methods with laplacian behaviour-based control
title_full_unstemmed	Robot path planning using family of SOR iterative methods with laplacian behaviour-based control
title_sort	robot path planning using family of sor iterative methods with laplacian behaviour-based control
granting_institution	Universiti Malaysia Sabah
granting_department	Faculty of Science and Natural Resources
publishDate	2015
url	https://eprints.ums.edu.my/id/eprint/37449/1/24%20PAGES.pdf https://eprints.ums.edu.my/id/eprint/37449/2/FULLTEXT.pdf
_version_	1783727539280150528

Robot path planning using family of SOR iterative methods with laplacian behaviour-based control

Similar Items