PATH PLANNING SIMULATION USING HARMONIC POTENTIAL FIELDS THROUGH FOUR POINT-EDGSOR METHOD VIA 9-POINT LAPLACIAN
DOI:
https://doi.org/10.11113/jt.v78.9537Keywords:
Path planning simulation, Explicit Decoupled Group SOR, iterative methodAbstract
This paper presents our study on a simulation of path planning for indoor robot that relies on the use of Laplace’s equation to constrain the generation of Harmonic Potential Fields (HPF). The computation of HPF requires immense amount of computing resources, particularly when the size of environment is large. In the past, fast iterative methods that apply the use of half-sweep iteration and block technique are suggested. In this study, faster iterative method known as Four Point-Explicit Decoupled Group Successive Over relaxation via 9-Point Laplacian (4-EDGSOR-9L) is introduced. Essentially, the 4-EDGSOR-9L is actually a variant of block SOR iterative method based on four points that employs half-sweep iteration and utilizes 9-Point Laplacian discretization scheme. Once the HPF is obtained, the standard Gradient Descent Search (GDS) technique is performed for path tracing to the goal point.References
Connolly, C. I., Burns, J., and Weiss, R. 1990. Path planning using Laplace's equation. Proceedings of the IEEE International Conference on Robotics and Automation, May 13-18, 1990, Cincinnati, USA. 2102-2106.
Akishita, S., Kawamura, S., and Hayashi, K. 1990. Laplace Potential For Moving Obstacleavoidance And Approach Of A Mobile Robot. Japan-USA Symposium on FlexibleAutomation, July 9-13, 1990, Kyoto, Japan. 139-142.
Barraqu and, J., Langlois, B., and Latombe, J. C. 1992. Numerical Potential Field Techniques For Robot Path
Planning. IEEE Transactions on Systems, Man and Cybernetics. 22(2): 224-241.
Sasaki, S. 1998. A Practical Computational Technique For Mobile Robot Navigation. Proceedings of the IEEE International Conference on Control Applications, Sep 4, 1998, Trieste, Italy. 2: 1323-1327.
Saudi, A. and Sulaiman, J. 2009. Efficient Weighted Block Iterative Method for Robot Path Planning Using Harmonic Functions. Proceedings of the 2nd International Conference on Control, Instrumentation and Mechatronic Engineering (CIM09), Malacca, Malaysia. June 2-3, 2009.
Saudi, A. and Sulaiman, J. 2009. Path Planning for Mobile Robot with Half-Sweep Successive Over-Relaxation (HSSOR) Iterative Method. Proc. of the Symposium on Progress in Information & Communication Technology, Kuala Lumpur (SPICT’09). 57-62.
Saudi, A. and Sulaiman, J. 2010. Robot Path Planning based on Four Point-EGSOR Iterative Method. Proc. of the 2010 IEEE Conference on Robotics Automation and Mechatronics (RAM). 476 – 481. ISBN: 978-1-4244-6503-3.
Saudi, A. and Sulaiman, J. 2012. Robot Path Planning via EGSOR Iterative Method Using Nine-Point Laplacian. Proc. of the 3rd Int. Conf. on Intelligent Systems, Modeling and Simulation (ISMS2012), Kota Kinabalu, Malaysia, 8-10 Feb 2012. 61 – 66. ISBN: 978-1-4673-0886-1.
Saudi, A. & Sulaiman, J. 2012. Path Planning for Mobile Robot using 4EGSOR via Nine-Point Laplacian (4EGSOR9L) Iterative Method. International Journal of Computer Applications. 53(16): 38-42. ISBN: 973-93-80870-44-0.
Saudi, A. & Sulaiman, J. 2012. Path Planning for Indoor Mobile Robot using Half-Sweep SOR via Nine-Point Laplacian (HSSOR9L). IOSR Journal of Mathematics (IOSR-JM), ISSN: 2278-5728. 3(2) Sep-Oct. 2012: 1-7. ISSN: 2278-5728.
Connolly, C. I. and Grupen, R. A. 1993. The Applications Of Harmonic Functions To Robotics. Journal of Robotic Systems. 10(7): 931-946.
Zelek, J. S. and Levine, M. D. 2000. Local-Global Concurrent Path Planning And Execution. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans. 30(6): 865-870.
Khatib, O. 1985. Real-Time Obstacle Avoidance For Manipulators And Mobile Robots. Proceedings of the IEEE International Conference on Robotics and Automation, Mar 25-28, 1985, St. Louis, USA. 2: 500-505.
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, March 31 - April 3, 1987, Raleigh, USA. 4: 1-6.
Rimon, E. and Koditschek, D. E. 1992. Exact Robot Navigation Using Artificial Potential Functions. IEEE Transactions on Robotics and Automation. 8(5): 501-518.
Kim, J. O. and Khosla, P. K. 1992. Real-Time Obstacle Avoidance Using Harmonic Potential Functions. IEEE Transactions on Robotics and Automation. 8(3): 338-349.
Waydo, S. and Murray, R. M. 2003. Vehicle Motion Planning Using Stream Functions. Proceedings of the IEEE International Conference on Robotics and Automation, Sep 14-19, 2003, Taipei, Taiwan. 2: 2484-2491.
Rosell, J. and Iniguez, P. 2005. Path Planning Using Harmonic Functions And Probabilistic Cell Decomposition. Proceedings of the IEEE International Conference on Robotics and Automation, April 18-22, 2005, Barcelona, Spain. 1803-1808.
Daily, R. and Bevly, D. M. 2008. Harmonic Potential Field Path Planning For High Speed Vehicles. Proceedings of the IEEE American Control Conference, June 11-13, 2008, Seattle, USA. 4609-4614.
Garrido, S., Moreno, L., Blanco, D., and Martin Monar, F. 2010. Robotic Motion Using Harmonic Functions And Finite Elements. Journal of Intelligent and Robotic Systems. 59(1): 57-73.
Szulczynski, P., Pazderski, D., and Kozlowski, K. 2011. Real-Time Obstacle Avoidance Using Harmonic Potential Functions. Journal of Automation Mobile Robotics and Intelligent Systems. 5: 59-66.
Yang, F. and Ariyur, K. B. 2011. Laplacian Path Planning: Implementation And Generalizations. Proceedings of the Infotech@Aerospace 2011 Conference, March 29-31, 2011, St. Louis, MO, USA. 1-9.
Pedersen, M. D. and Fossen, T. I. 2012. Marine Vessel Path Planning And Guidance Using Potential Flow. Proceedings of the 9th IFAC Conference on Manoeuvring and Control of Marine Craft, Sep 19-21, 2012, Arenzano, Italy. 188-193.
Liang, X., Wang, H., Li, D., and Liu, C. 2014. Three-Dimensional Path Planning For Unmanned Aerial Vehicles Based On Fluid Flow. Proceedings of the IEEE Aerospace Conference, March 1-8, 2014, Big Sky, USA. 1-13.
Kress, R. 1998. Numerical Analysis. New York: Springer-Verlag.
Saad, Y. and Van Der Vorst, H. A. 2000. Iterative Solution Of Linear Systems In The 20th Century. Journal of Computational and Applied Mathematics. 123(1-2): 1-33.
Abdullah, A. R. 1991. The Four Point Explicit Decoupled Group (EDG) Method: A Fast Poisson Solver. International Journal of Computer Mathematics. 38(1-2): 61-70.
Evans, D. J. 1985. Group Explicit Iterative Methods For Solving Large Linear Systems. International Journal of Computer Mathematics. 17(1): 81-108.
Yousif, W. S. and Evans, D. J. 1995. Explicit De-coupled Group Iterative Methods And Their Parallel Implementations. Parallel Algorithms and Applications. 7(1-2): 53-71.
Sulaiman, J., Othman, M., and Hasan, M. K. 2009. Nine Point-EDGSOR Iterativemethodfor The Finite Element Solution Of 2D Poisson Equations. O. Gervasi, D. Taniar,B. Murgante, A. Lagana, Y. Mun, and M. L. Gavrilova. (eds.). Lecture Notes in Computer Science 5592: Computational Science and Its Applications - ICCSA 2009. 764-774. Berlin Heidelberg: Springer-Verlag.
Akhir, M. K. M., Othman, M., Abdul Majid, Z., Suleiman, M., and Sulaiman, J. 2012. Four Point Explicit Decoupled Group Iterative Method Applied To Two-Dimensional Helmholtz Equation. International Journal of Mathematical Analysis. 6(20): 963-974.
Akhir, M. K. M., Othman, M., Sulaiman, J., Abdul Majid, Z., and Suleiman, M. 2011. Half-Sweep Modified Successive Overrelaxation For Solving Two-Dimensional Helmholtz Equations. Australian Journal of Basic and Applied Sciences. 5(12): 3033-3039.
Fauzi, N. I. M. and Sulaiman, J. 2012. Half-sweep Modified Successive Overrelaxtion Method For Solving Second Order Two-Point Boundary Value Problems Using Cubic Spline. International Journal of Contemporary Mathematical Sciences. 7(32): 1579-1589.
Muthuvalu, M. S. and Sulaiman, J. 2012. Half-Sweep Geometric Mean Iterative Method For The Repeated Simpson Solution Of Second Kind Linear Fredholm Integral Equations. Proyecciones. 31(1): 65-79.
Sulaiman, J., Hasan, M. K., Othman, M., and Karim, S. A. A. 2014. Implicit Finite Difference Solutions Of One-Dimensional Burgers' Equation Using Newton-HSSOR Method. A. Kilicman, W. J. Leong, and Z. Eshkuvatov. (eds.). International
Conference on Mathematical Sciences and Statistics 2013. 285-295. Singapore: Springer-Verlag.
Karnik, M., Dasgupta, B., and Eswaran, V. 2002. A Comparative Study Of Dirichlet And Neumann Conditions For Path Planning Through Harmonic Functions. In P. M. A. Sloot, A. G. Hoekstra, C. J. K. Tan, and J. J. Dongarra. (eds.). Lecture Notes in Computer Science 2330: Computational Science - ICCS 2002. 442-451. Berlin Heidelberg: Springer-Verlag.
Le Veque, R. J. 2007. Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-state and Time-dependent Problems. Philadelphia: Society for Industrial Applied Mathematics.
Zachmanoglou, E. C. and Thoe, D. W. 2012. Introduction to Partial Differential Equations with Applications. New York: Dover Publications.
Souccar, K., Coelho, J., Connolly, C., and Grupen, R. 1998. Harmonic Functions For Path Planning And Control. Practical Motion Planning In Robotics: Current Approaches And Future Directions. 277-302. Chichester: John Wiley.
Michel, O. 2004. WebotsTM: Professional Mobile Robot Simulation. International Journal of Advanced Robotics Systems. 1(1): 39-42.
Fletcher, C. A. J. 1984. Computational Galerkin Methods. Springer Series in Computational Physics. New York: Springer-Verlag.
Sulaiman, J., Othman, M., and Hasan, M. K. 2007. Red-Black Half-Sweep Iterative Method Using Triangle Finite Element Approximation For 2D Poisson Equations. Y. Shi, G. D. van Albada, J. Dongarra, and P. M. A. Sloot. (eds.). Lecture Notes in Computer Science 4487: Computational Science - ICCS 2007. 326-333. Berlin Heidelberg: Springer-Verlag.
Young, D. M. 1950. Iterative Methods for Solving Partial Difference Equations of Elliptic Type. PhD Thesis. Harvard University.
Ali, N. H. M. and Abdullah, A. R. 1998. New Parallel Nine-Point Poisson Solver. Journal of Information Technology. 2(10): 1-9.
Ling, S. T. and Ali, N. H. M. 2013. New High Order Group Iterative Schemes In The Solution Of Poisson Equation. International Journal of Mathematical, Computational, Physical and Quantum Engineering. 7(12): 1170-1175.
Ali, N. H. M. 2002. Reka Bentuk Algoritma Blok Baru Stensil 9-Titik Dalam Masalah Nilai Sempadan. Matematika. 18(1): 45-62.
Fauzi, N. I. M. and Sulaiman, J. 2013. Quarter-Sweep Gauss-Seidel Method With Quadratic Spline Scheme Applied To Fourth Order Two-Point Boundary Value Problems. Proceedings of the 20th National Symposium on Mathematical Sciences: Research in Mathematical Sciences: A Catalyst for Creativity and Innovation, Dec 18-20, 2013, Putrajaya, Malaysia. 1522: 735-743.
Sulaiman, J., Othman, M., and Hasan, M. K. 2010. MEGSOR Iterative Scheme For The Solution Of 2D Elliptic PDE's. World Academy of Science, Engineering and Technology. 38: 418-424.
Downloads
Published
Issue
Section
License
Copyright of articles that appear in Jurnal Teknologi belongs exclusively to Penerbit Universiti Teknologi Malaysia (Penerbit UTM Press). This copyright covers the rights to reproduce the article, including reprints, electronic reproductions, or any other reproductions of similar nature.
