Perancangan Laluan Robot menggunakan Fungsi Harmonik melalui Kaedah Lelaran Sapuan Suku
Robot Path Planning using Harmonic Functions via Quarter Sweep Iterative Method
DOI:
https://doi.org/10.37134/jsml.vol5.1.2017Keywords:
Perancangan laluan robot, fungsi-fungsi Harmonik, kaedah lelaran, sapuan separuh, sapuan suku, persamaan LaplaceAbstract
Kertas kajian ini mengemukakan aplikasi fungsi harmonik dalam menyelesaikan masalah perancangan laluan robot. Fungsi harmonik diperolehi dengan menyelesaikan persamaan Laplace. Dalam kajian ini, fungsi-fungsi harmonik bertindak sebagai nilai-nilai potensi pada setiap titik dalam persekitaran robot. Nilai-nilai potensi ini kemudiannya digunakan untuk mencari laluan dari titik mula sehinggalah ke titik destinasi yang telah ditetapkan. Bagi mendapatkan fungsi-fungsi harmonik ini, pendekatan yang paling biasa digunakan adalah kaedah beza terhingga iaitu lelaran Jacobi, Gauss-Seidel dan Successive Over-relaxation (SOR). Namun, kaedah-kaedah lelaran yang lazim ini terlalu perlahan, terutamanya apabila melibatkan persekitaran yang luas. Oleh itu, kajian ini mencadangkan kaedah yang lebih pantas menggunakan gabungan teknik lelaran sapuan suku dengan lelaran SOR. Keputusan ujikaji menunjukkan kaedah-kaedah yang dicadangkan ini telah berjaya mengurangkan masa pengiraan fungsi-fungsi harmonik secara drastik. Ini secara langsung telah meningkatkan prestasi keseluruhan algoritma perancangan laluan, terutamanya aspek masa perlaksanaan.
-------------------------------------------------------------------------------------------
This paper presents the application of harmonic functions in solving the robot path planning problem. The harmonic function is obtained by solving the Laplace’s equation. In this study, the harmonic functions act as potential values at each point in the robot environment. These potential values are then used to find path from the starting point to the specified target point. In order to obtain these harmonic functions, the most commonly used approaches are the finite difference methods of Jacobi, Gauss-Seidel and Successive Over-relaxation (SOR). However, these standard iterative methods are too slow, especially when it involves large environments. Therefore, this study proposes faster methods that employ the combination of quarter sweep techniques with SOR iteration. The results of experiments show that these proposed methods have successfully reduced the time of computation of harmonic functions drastically. This has directly improved the overall performance of the path planning algorithm, particularly in terms of execution time.
Keywords: Robot path planning, Harmonic functions, iterative method, half sweep, quarter sweep, Laplace’s equation
Downloads
References
Akhir, M. K. M., Othman, M., Suleiman, M., and Sulaiman, J. 2012. A new Octo-sweep iterative method for solving two-dimensional elliptic equations. International Journal of Applied Mathematics and Statistics, 30(6): 60-71.
Akishita, S., Kawamura, S., and Hayashi, K. 1990. Laplace potential for moving obstacle avoidance and approach of a mobile robot. In Japan-USA Symposium on Flexible Automation, A Pacific Rim Conference, July 9-13, 1990, Kyoto, Japan, pp. 139-142.
Connolly, C. I., & Grupen, R. A. (1993). The applications of harmonic functions to robotics. Journal of Field Robotics, 10(7), 931-946.
Connolly, C. I., Burns, J. B., & Weiss, R. (1990, May). Path planning using Laplace’s equation. In Robotics and Automation, 1990. Proceedings., 1990 IEEE International Conference on (pp. 2102-2106). IEEE.
Connolly, C. I., Burns, J., and Weiss, R. 1990. Path planning using Laplace’s equation. In Proceedings of the IEEE International Conference on Robotics and Automation, May 13-18, 1990, Cincinnati, USA, pp. 2102-2106.
Dahlquist, G. and Bjorck, A. 1974. Numerical Methods. New Jersey: Prentice Hall.
Daily, R., & Bevly, D. M. (2008, June). Harmonic potential field path planning for high speed vehicles. In American Control Conference, 2008 (pp. 4609-4614). IEEE.
Evans, D. J. (1985). Group explicit iterative methods for solving large linear systems. International Journal of Computer Mathematics, 17(1), 81-108.
Faires, J. and Burden, R. 2012. Numerical Methods, 4th Edition. Boston: Cengage Learning.
Garrido, S., Moreno, L., Blanco, D., & Monar, F. M. (2010). Robotic motion using harmonic functions and finite elements. Journal of Intelligent and Robotic Systems, 59(1), 57-73.
Karnik, M., Dasgupta, B., & Eswaran, V. (2002). A comparative study of Dirichlet and Neumann conditions for path planning through harmonic functions. Computational Science—ICCS 2002, 442-451. 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, pp. 442-451. Berlin Heidelberg: Springer-Verlag.
Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The international journal of robotics research, 5(1), 90-98.
Khatib, O. 1985. Real-time obstacle avoidance for manipulators and mobile robots. In Proceedings of the IEEE International Conference on Robotics and Automation, Mar 25-28, 1985, St. Louis, USA, vol. 2, pp. 500-505.
Kress, R. 1998. Numerical Analysis. New York: Springer-Verlag.
LaValle, S. M. 2011. Motion planning. IEEE Robotics and Automation Magazine, 18(1): 79-89.
LeVeque, R. J. (2007). Finite difference methods for ordinary and partial differential equations: steady-state and time-dependent problems. Society for Industrial and Applied Mathematics.
Othman, M., & Abdullah, A. R. (2000). An efficient four points modified explicit group poisson solver. International Journal of Computer Mathematics, 76(2), 203-217.
Saad, Y., & Van Der Vorst, H. A. (2000). Iterative solution of linear systems in the 20th century. Journal of Computational and Applied Mathematics, 123(1), 1-33.
Sasaki, S. (1998, September). A practical computational technique for mobile robot navigation. In Control Applications, 1998. Proceedings of the 1998 IEEE International Conference on (Vol. 2, pp. 1323-1327). IEEE.
Sasaki, S. 1998. A practical computational technique for mobile robot navigation. In Proceedings of the IEEE International Conference on Control Applications, Sep 4, 1998, Trieste, Italy, vol. 2, pp. 1323-1327.
Saudi, A., & Sulaiman, J. (2016). Path Planning Simulation using Harmonic Potential Fields through Four Point-EDGSOR Method via 9-Point Laplacian. Jurnal Teknologi, 78(8-2), 12-24.
Sulaiman, J., Othman, M., & Hasan, M. K. (2007, August). Red-black EDGSOR iterative method using triangle element approximation for 2D Poisson equations. In International Conference on Computational Science and Its Applications (pp. 298-308). Springer, Berlin, Heidelberg.
Sulaiman, J., Othman, M., and Hasan, M. K. 2007. Red-Black EDGSOR iterative method using triangle element approximation for 2D Poisson equations. In O. Gervasi and M. L. Gavrilova. (eds.). Lecture Notes in Computer Science 4707: Computational Science and Its Applications - ICCSA 2007, pp. 298-308. Berlin Heidelberg: Springer-Verlag.
Tran, N., Nguyen, D.-T., Vu, D.-L., and Truong, N.-V. 2013. University of Information Technology, Vietnam National University-Ho Chi Minh City, Vietnam. In Proceedings of the IEEE International Conference on Control, Automation and Information Sciences, Nov 25-28, 2013, Ho Chi Minh, Vietnam, pp. 317-321.
Young, D. (1954). Iterative methods for solving partial difference equations of elliptic type. Transactions of the American Mathematical Society, 76(1), 92-111.
Young, D. M. 1950. Iterative Methods for Solving Partial Difference Equations of Elliptic Type. PhD Thesis. Harvard University.
Yousif, W. S., & Evans, D. J. (1986). Explicit group over-relaxation methods for solving elliptic partial differential equations. Mathematics and Computers in Simulation, 28 (6), 453-466.
