Collision-free Random Paths between Two Points

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.