International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 12, No. 3, 8 Jun. 2020
Cover page and Table of Contents: PDF (size: 692KB)
Collision-free Random Paths between Two Points
Full Text (PDF, 692KB), PP.27-34
Views: 0 Downloads: 0
Author(s)
Index Terms
Random Paths, Obstacles, Mobile Robots, Ontology, Graph Theory
Abstract
This paper proposes a collision-free path planning algorithm based on the generation of random paths between two points. The proposed work applies to many fields such as education, economics, computer science and AI, military, and other fields of applied sciences. Our work has spanned several phases, where in the first phase a novel computer algorithm to generate random paths between two points in space has been developed. The aim was to be able to generate paths between two points in real-time that cannot be predicted in advance. In the second phase, we have developed an ontology that describes the domain of discourse. The aim was two folds; firstly, to provide an optimized generation of best points that are closer to the target point. Secondly, to provide sharable, reusable ontological objects that can be deployed to other projects. We reinforced our solution by the initiation of several case studies that have been designed using and extending our work. One problem that we have faced in some cases is the existence of some obstacles between the starting and the ending point. For example, in our work towards the automation of a navigation system for drones, we faced some obstacles like trees, no flying zones, and buildings. This problem is also applicable to mobile robots and other unmanned vehicles, where fee-collision mobility is necessary. In this phase, we have reworked the algorithm to generate random paths between two points P0(x0, y0), Pn(xn, yn) with obstacles. Our generated random paths are placed within circles that are centered in Pn: c1, c2, …, cn-1, which passes thru the points P1, P2, …, Pn-1 respectively. Point Pi may approach Pn if it takes any position within circle c centered in Pn with radius PiPn and satisfies some constraints, discussed in detail in the paper, which insure that the selected paths do not fall within obstacles and reach the target point. we also classified the generated paths based on given properties such as the longest path, shortest path, and paths with some given costs. The resulted algorithms were very encouraging and leading to the applicability of real-life cases.
Cite This Paper
Mohammad Ali H. Eljinini, Ahmad Tayyar, "Collision-free Random Paths between Two Points", International Journal of Intelligent Systems and Applications(IJISA), Vol.12, No.3, pp.27-34, 2020. DOI:10.5815/ijisa.2020.03.04
Reference
[1]A. Tayyar, “Generating Random Paths between Two Points in Space: Proposed Algorithm”. Proceedings of the International Conference on Computer Science, Computer Engineering, and Social Media, Thessaloniki, Greece, 2014.
[2]A. Tayyar, M.A. Eljinini, “Ontology-Based Generation of Random Paths between Two Points”. Journal of Applied and Theoretical Information Technology, vol. 96, no. 15, pp. 4984-4905, 2018.
[3]P. Raja, S. Pugazhenthi, “Optimal Path Planning of Mobile Robots: A Review”. International Journal of Physical Sciences, vol. 7, no. 9, pp. 1314-1320, 2012.
[4]D. Payton, J. Rosenblatt, D. Keirsey, “Grid-based mapping for autonomous mobile robot”. Journal of Robotics and Autonomous Systems, vol. 11, no. 1, pp. 13-21, 1993.
[5]O. Hachour, “Path planning of autonomous mobile robot”. International Journal of Systems Applications, Engineering and Development, vol. 4, no. 2, pp. 178-190, 2008.
[6]P. Frana, “An Interview with Edsger W. Dijkstra”. Communications of the ACM, vol. 53, no. 8, pp. 41–47, 2010.
[7]W. Huijuan, Y. Yuan, Q. Yuan. “Application of Dijkstra Algorithm in robot path planning”. Proceedings of the Second International Conference on Mechanical Automation and Control Engineering, pp. 1067-1069, 2011.
[8]I. Al-Taharwa, A. Sheta, M. Al-Weshah, “A mobile robot path planning using genetic algorithm in static environment”. Journal of Computer Science, vol. 4, no. 4, pp. 341-344, 2008.
[9]M. Garcia, O. Montiel, O. Castillo, R. Sepulveda, P. Melin, “Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost evaluation”. Journal of Applied Soft Computing, vol. 9, pp. 1102-1110, 2009.
[10]Q. Zhang, G. Gu, “Path planning based on improved binary particle swarm optimization algorithm”. Proceedings of the IEEE International Conference on Robotics, Automation and Mechatronics, China, pp. 462-466, 2008.
[11]Y. Zhu, T. Zhang, J. Song, X. Li, “A new hybrid navigation algorithm for mobile robots in environments with incomplete knowledge”. The Journal of Knowledge–Based Systems, vol. 27, pp. 302–313, 2012.
[12]T. Krajn´ık, V. Vonasek, D. Fi´ser, J. Faigl. “AR-drone as a platform for robotic research and education”. Proc. Research and Education in Robotics: EUROBOT, 2011.
[13]L. Kleinrock, Queueing Systems. John Wiley & Sons, 1975.
[14]L. Allen, G. Jackson, J. Ross, S. White, “What counts is how the game is scored: One way to increase achievement in learning mathematics”. Simulation & Games, vol. 9, pp. 371-389, 1978.
[15]EA. Codling, MJ. Plank, s. Benhamou, “Random walk models in biology”. Journal of the Royal Society Interface, vol 5, no. 25, pp. 813–834, 2008.
[16]PM. Kareiva, N. Shigesada, “Analyzing insect movement as a correlated random walk”. Oecologia. vol. 56, pp. 234–238, 1983.
[17]A. Okubo, S. Levin, Diffusion and Ecological Problems: Modern Perspectives. Springer Science & Business Media, New York, 2nd Ed., 2013.
[18]D. Floreano, R.J. Wood, “Science, technology and the future of small autonomous drones”. Nature, vol. 521, pp. 460–466, 2015.
[19]M. Hassanalian, A. Abdelkefi, “Classifications, applications, and design challenges of drones: A review”. Progress in Aerospace Sciences, vol. 91, pp. 99-131, 2017.
[20]M. Funk, “Human-drone interaction: let's get ready for flying user interfaces. Interactions”. Interactions, ACM, New York, vol. 25, no. 3, pp. 78-81, 2018.