ROUTE PLANNING FOR A MOBILE ROBOT IN 3D SPACE BASED ON AN ALGORITHM PROBABILISTIC ROADMAP

ALGORITHM PROBABILISTIC ROADMAP

Vladyslav Yevsieiev1,

Svitlana Maksymova1,

Amer Abu-Jassar2

1Department of Computer-Integrated Technologies, Automation and Robotics,

Kharkiv National University of Radio Electronics, Ukraine

2Faculty of Information Technology, Department of Computer Science, Ajloun

National University, Ajloun, Jordan

ABSTRACT

This article discusses route planning for a mobile robot in three-dimensional space using the Probabilistic Roadmap (PRM) algorithm. The mathematical apparatus of PRM allows you to build a state graph for the robot’s movement space, taking into account obstacles and environmental features. The developed Python program includes an implementation of the PRM algorithm to find the optimal path in 3D space. Experiments on route generation in various environments were conducted to demonstrate the effectiveness and accuracy of the proposed approach. The results obtained confirm the applicability of the PRM algorithm for route planning of mobile robots in complex 3D environments.

Key words: Industry 5.0, Сomputer Vision Systems, Mobile Robots, Work zone, Manufacturing Innovation, Industrial Innovation

INTRODUCTION

In the modern world, autonomous mobile robots are playing an increasingly important role in various fields, including manufacturing, logistics, medicine, and more [1]-[17]. For such robots to function effectively, it is necessary to have effective route planning algorithms [18]-[23], especially in three-dimensional space, which takes into account not only the plane of motion, but also vertical obstacles and environmental conditions. Various methods, approaches, and ideas can be used here [24]-[33]. One of the promising methods for planning routes for mobile robots in 3D space is the Probabilistic Roadmap (PRM) algorithm, which allows you to generate routes taking into account complex 3D obstacles and environmental features.

However, to effectively implement a PRM algorithm, it is important to consider a number of features and challenges. First, it is necessary to correctly select the algorithm parameters, such as the number of generated points and the radius of the search for nearest neighbors, to ensure optimality and speed of route construction. Secondly, computational complexity must be taken into account, especially when working with large amounts of data in 3D space.

Thus, the implementation of route planning for a mobile robot in 3D space based on the PRM algorithm is an urgent task, ensuring efficient and accurate movement of robots in complex three-dimensional conditions. Research in this area will allow the development of new methods and technologies to improve the navigation of autonomous systems and their application in various fields of industry and science.

Related works

Modern trends in path finding for a mobile robot involve the use of various algorithms. Among them we can highlight Probabilistic Roadmap (PRM) algorithm. It is considered for path planning by plenty of scientists in their researches. Let us look at some recent works on this topic.

Let us begin from the fact, that path planning and navigation is a very important problem in robotics, especially for mobile robots operating in complex environments [34]. An improved sampling-based path planning method for mobile robot navigation is proposed in [34]. The proposed method uses a layered hybrid Probabilistic Roadmap and the Artificial Potential Field (APF) method for global planning.

Paper [35] presents a new path planning algorithm based on the probabilistic roadmaps method, in order to effectively solve the autonomous path planning of mobile robots in complex environments with multiple narrow channels. The improved PRM algorithm mainly improves the density and distribution of sampling points in the narrow channel, through a combination of the learning process of the PRM algorithm and the APF algorithm.

Authors in [36] try to develop a new path planning algorithm that can guarantee the optimal path solution. Their method hybridizes the Probabilistic Road Map (PRM) algorithm with the Information Search Algorithm.

Probabilistic Roadmap algorithm is also used for cable harness route planning. A novel multi-branch cable harness layout design method is presented in [37], which unites the probabilistic roadmap method and the genetic algorithm.

Researchers in [38] present Temporal-PRM, a novel sampling-based pathplanning algorithm that performs obstacle avoidance in dynamic environments. They show that their algorithm can run onboard a flying robot, performing obstacle avoidance in real time.

The study [39] proposes an improved probabilistic roadmap planning method for safe indoor flights based on the assumption of a quadrotor model UAV. The results showed that our method ensures safe indoor UAV flights while significantly improving computational efficiency.

Scientists in [40] developed a novel probabilistic roadmap algorithm, or node reduction-based search algorithm. They try to reduce the shortcomings of conventional algorithms in mobile robot path planning, such as long paths, random sampling and high collision risk.

Thus, we see that this algorithm is widely used to create various paths in a wide variety of areas. Next, we will consider the use of this algorithm to select the path of a mobile robot

Mathematical description of the Probabilistic Roadmap algorithm for

planning the route for a mobile robot

The PRM (Probabilistic Roadmap) algorithm is a powerful method for planning routes for mobile robots in 3D space. Its main advantage is that it allows paths to be built in complex and dynamic environments, taking into account various constraints and obstacles. The way the algorithm works is that it creates a graph where the vertices represent valid positions for the robot, and the edges represent valid paths between these positions.

One of the key stages of the algorithm is the generation of random points in space, which can be used as potential vertices of the graph. Then, for each point, its connection to other points is checked through an obstacle collision check. If two points can be connected, then an edge is added to the graph between them.

One of the disadvantages of the PRM algorithm is that it can require a large number of points to construct the graph in complex environments. This can lead to high computational complexity and memory requirements. Additionally, PRM does not guarantee finding the optimal path because it operates on random samples and may miss better paths.

However, the PRM algorithm remains a popular choice for route planning in 3D space due to its efficiency and ability to work in a variety of environments. It can take into account complex obstacle shapes and dynamically changing conditions, making it applicable to a wide range of motion planning problems for mobile robots.

LetV be a set of graph vertices, where each vertex represents a point in space,E

be a set of graph edges, where each edge connects two vertices, if these vertices can be connected without intersecting with obstacles, then:),( EVG 

(1)G

– routes graph;V

– graph vertices set;E

– graph edges set.

Let us denote bystart

P andend

P – start and end points respectively.

Then the main steps of the PRM algorithm can be represented as follows:

– points generation:},...,,...,,,,{ 21 niendstart PPPPPPV 

(2)start

P

– start point;end

P

– end point;i

P

– randomly generated points;

– edge search:}),(|),{( FalsePPCPPE jiji 

(3)C

– function for checking collisions between two points or their surroundings and obstacles;ji PP,

– randomly generated points and

– pathfinding (you can use standard pathfinding algorithms such as Dijkstra's algorithm or A* to find the optimal path between the starting and ending points).

This can be represented as follows: letcur

P be the current point on the path, be)( cur

PN

the set of all neighbors of the poincur

P t,),( nextcur PPC be a function that determines the cost of moving from pointcur

P to pointnext

P , let),( endstart PSD be the length of the path from pointstart

P to pointend

P . Then the path search can be described as follows:

– initialization:}{},{, startstartstartcur PVisitedPPathPP 

(4)

Under the condition that whileendcur PP  then:

1. Selecting)( curnext PNP  , such thatVisitedPnext  andmin),( nextcut PPC

2. Addingnext

P toPath andVisited

3.nextcur PP  andPath is returned

Software implementation and experiments

To check the correctness of the reasoning, we will develop a program in Python in the development environment PyCharm 2022.2.3 (Professional Edition). Let us give an example of software implementation of the above described mathematical expressions.

# Generate PRM path

num_samples = 50

num_neighbors = 1

prm_path = generate_prm_path(start, end, obstacles, num_samples, num_neighbors, radius)

This code uses the previously defined start point, end point, obstacles list, and the num_samples, num_neighbors, and radius parameters to generate a path using the generate_prm_path function.

The num_samples parameter determines the number of random points that will be generated to construct the PRM graph, num_neighbors is the number of nearest neighbors taken into account when constructing the graph, and radius is the collision radius to check the intersection of points with obstacles.

After executing this code, the prm_path variable will contain the generated path from the start to the end point using the PRM algorithm.

# Rendering space with obstacles

for obstacle in obstacles:

ax.plot([obstacle.x], [obstacle.y], [obstacle.z], color='black', marker='s')

This code is used to draw obstacles in 3D space on a graph. For each obstacle in the obstacles list, it calls the plot method of the ax object, indicating the obstacle's X, Y, and Z coordinates. The obstacles are displayed as black cubes (marker 's'). This code should be placed after the space is created and before the graph is displayed so that obstacles are added to the graph

# Draw start and end points

ax.scatter(start.x, start.y, start.z, color='g', marker='o')

ax.scatter(end.x, end.y, end.z, color='b', marker='o')

This code is used to draw the start and end points on the graph. It calls the scatter method of the ax object (coordinate axes) to display points with the coordinates of the starting point start and the end point end. The start point is shown with green color (color='g') and a circle marker (marker='o'), and the end point is shown with blue color (color='b') and a circle marker (marker='o'). This code should be placed after the obstacles are drawn and before the graph is displayed so that the points are added to the graph.

The following hardware was used for research: CPU Intel(R) Core(TM) i5- 9300H CPU @ 2.40GHz, RAM 16 Gb, GPU NVideo GeForce GTX 1660Ti (Ram 8Gb), Web-camera HD WebCam, OS Windows 10 Pro ( Version 22H2). A program for implementing route construction in 3-dimensional space based on the PRM algorithm was developed in the PyCharm 2022.2.3 (Professional Edition) environment in Python. The results of the program are presented in Figure 1.

a) (num_samples = 10; num_neighbors=5)

b) (num_samples = 50; num_neighbors=1)

Figure 1: Results of the program for constructing a route in 3D space based on the PRM algorithm

However, the PRM algorithm also has some disadvantages. It can require a lot of computational resources and time to build a route graph in complex environments. In addition, PRM does not guarantee that the optimal path will be found, since it is based on random samples of points and may miss more efficient routes.

To successfully implement the PRM algorithm, it is recommended to conduct a thorough analysis of the environment and its features to determine the optimal parameters for generating points and checking collisions. It is also important to take into account the limitations of the robot and the features of its movement when building a route.

CONCLUSION

The PRM (Probabilistic Roadmap) algorithm is an efficient approach to route planning for mobile robots in 3D space. It is widely used due to its ability to operate in complex environments with obstacles and dynamically changing conditions. The advantage of the algorithm is its probabilistic nature, which allows it to take into account random factors and uncertainty in the environment.

One of the key benefits of PRM is the ability to build a path that takes into account the shape of obstacles and optimal use of available space. This makes it suitable for tasks where it is necessary to avoid collisions with obstacles and find the optimal route given various constraints.

To successfully implement the PRM algorithm, it is recommended to conduct a thorough analysis of the environment and its features to determine the optimal parameters for generating points and checking collisions. It is also important to take into account the limitations of the robot and the features of its movement when building a route.

Overall, the PRM algorithm is a powerful tool for planning routes for mobile robots in 3D space, which can take into account complex environmental conditions and ensure safe and efficient robot movement.

REFERENCES

1. Shcherbyna, V., & et al. (2023). Mobile Robot for Fires Detection Development. Journal of Universal Science Research, 1(11), 17-27.

2. Nevliudov, I., & et al. (2023). Development of a Mobile Robot Prototype with an Interactive Control System. Системи управління, навігації та зв’язку. Збірник наукових праць, 3(73), 128-133.

3. Matarneh, R., & et al. (2018). Voice Control for Flexible Medicine Robot. International Journal of Computer Trends and Technology, 56(1), 1-5.

4. Al-Sharo Y., & et al. (2023). A Robo-hand prototype design gripping device within the framework of sustainable development. Indian Journal of Engineering, 2023, 20, e37ije1673.

5. Nevliudov, I., & et al. (2023). A Small-Sized Robot Prototype Development Using 3D Printing. In XXXI International Conference CAD In Machinery Design Implementation and Educational Issues,12.

6. Attar, H., Abu-Jassar, A. T., Yevsieiev, V., Lyashenko, V., Nevliudov, I., & Luhach, A. K. (2022). Zoomorphic Mobile Robot Development for Vertical Movement Based on the Geometrical Family Caterpillar. Computational intelligence and neuroscience, 2022, 3046116.

7. Abu-Jassar, A. T., Al-Sharo, Y. M., Lyashenko, V., & Sotnik, S. (2021). Some Features of Classifiers Implementation for Object Recognition in Specialized Computer systems. TEM Journal, 10(4), 1645.

8. Baker, J. H., Laariedh, F., Ahmad, M. A., Lyashenko, V., Sotnik, S., & Mustafa, S. K. (2021). Some interesting features of semantic model in Robotic Science. SSRG International Journal of Engineering Trends and Technology, 69(7), 38-44.

9. Matarneh, R., Maksymova, S., Deineko, Z., & Lyashenko, V. (2017). Building robot voice control training methodology using artificial neural net. International Journal of Civil Engineering and Technology, 8(10), 523-532.

10. Al-Sharo, Y. M., Abu-Jassar, A. T., Sotnik, S., & Lyashenko, V. (2021). Neural networks as a tool for pattern recognition of fasteners. International Journal of Engineering Trends and Technology, 69(10), 151-160.

11. Sotnik, S., Mustafa, S. K., Ahmad, M. A., Lyashenko, V., & Zeleniy, O. (2020). Some features of route planning as the basis in a mobile robot. International Journal of Emerging Trends in Engineering Research, 8(5), 2074-2079.

12. Sotnik, S., & Lyashenko, V. (2022). Prospects for Introduction of Robotics in Service. Prospects, 6(5), 4-9.

13. Ahmad, M. A., Sinelnikova, T., Lyashenko, V., & Mustafa, S. K. (2020). Features of the construction and control of the navigation system of a mobile robot. International Journal of Emerging Trends in Engineering Research, 8(4), 1445-1449.

14. Lyashenko, V., & Sotnik, S. (2022). Overview of Innovative Walking Robots. International Journal of Academic Engineering Research (IJAER), 6(4), 3-7.

15. Lyashenko, V., & Sotnik, S. (2020). Analysis of Basic Principles for Sensor System Design Process Mobile Robots. Journal La Multiapp, 1(4), 1-6.

16. Abu-Jassar, A. T., Attar, H., Lyashenko, V., Amer, A., Sotnik, S., & Solyman, A. (2023). Access control to robotic systems based on biometric: the generalized model and its practical implementation. International Journal of Intelligent Engineering and Systems, 16(5), 313-328.

17. Al-Sharo, Y. M., Abu-Jassar, A. T., Sotnik, S., & Lyashenko, V. (2023). Generalized Procedure for Determining the Collision-Free Trajectory for a Robotic Arm. Tikrit Journal of Engineering Sciences, 30(2), 142-151.

18. Yevsieiev, V., & et al. (2024). Using Contouring Algorithms to Select Objects in the Robots’ Workspace. Technical Science Research In Uzbekistan, 2(2), 32-42.

19. Basiuk, V., & et al. (2023). Mobile Robot Position Determining Using Odometry Method. Multidisciplinary Journal of Science and Technology, 3(3), 227- 234.

20. Yevsieiev, V., & et al. (2024). Active Contours Method Implementation for Objects Selection in the Mobile Robot’s Workspace. Journal of Universal Science Research, 2(2), 135-145.

21. Nevliudov, I., & et al. (2023). Mobile Robot Navigation System Based on Ultrasonic Sensors. In 2023 IEEE XXVIII International Seminar/Workshop on Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED), IEEE, 1, 247-251.

22. Yevsieiev, V., & et al. (2024). Object Recognition and Tracking Method in the Mobile Robot’s Workspace in Real Time. Technical Science Research In Uzbekistan, 2(2), 115-124.

23. Yevsieiev, V., & et al. (2024). The Canny Algorithm Implementation For Obtaining the Object Contour in a Mobile Robot’s Workspace in Real Time. Journal of Universal Science Research, 2(3), 7-19.

24. Uchqun o‘g‘li, B. S., Valentin, L., & Vyacheslav, L. (2023). Image Processing Techniques as a Tool for the Analysis of Liver Diseases. Journal of Universal Science Research, 1(8), 223-233.

25. Babker, A., Sotnik, S., & Lyashenko, V. (2018). Polymeric Materials in Medicine. Sch. J. Appl. Med Sci, 6, 148-153.

26. Ahmad, M. A., Kots, G. P., & Lyashenko, V. V. (2015). Bank Lending Efficiency in the Real Sector of the Economy of Ukraine within the Period of 2011 to 2014 Years. Modern Economy, 6(12), 1209-1218.

27. Ahmad, M. A., Kots, G. P., & Lyashenko, V. V. (2016). Statistical Study of Bank Lending Efficiency in the Real Sector of the Economy of Ukraine within the Period of Years 2009 to 2012. Asian Academic Research Journal of Multidisciplinary, 3(2), pp. 104-120.

28. Ahmad, M. A., Kuzemin, O., Lyashenko, V., & Ahmad, N. A. (2015). Microsituations as part of the formalization of avalanche climate to avalanche-riskiness and avalanche-safety classes in the emergency situations separation. International Journal, 3(4), 684-691.

29. Lyashenko, V. V., Matarneh, R., Baranova, V., & Deineko, Z. V. (2016). Hurst Exponent as a part of wavelet decomposition coefficients to measure long-term memory time series based on multiresolution analysis. American Journal of Systems and Software, 4(2), 51-56.

30. Lyashenko, V., Ahmad, M. A., Sotnik, S., Deineko, Z., & Khan, A. (2018). Defects of communication pipes from plastic in modern civil engineering. International Journal of Mechanical and Production Engineering Research and Development, 8(1), 253-262.

31. Babker, A. M., Altoum, A. E. A., Tvoroshenko, I., & Lyashenko, V. (2019). Information technologies of the processing of the spaces of the states of a complex biophysical object in the intellectual medical system health. International Journal of Advanced Trends in Computer Science and Engineering, 8(6), 3221-3227.

32. Lyubchenko, V., Matarneh, R., Kobylin, O., & Lyashenko, V. (2016). Digital image processing techniques for detection and diagnosis of fish diseases. International Journal of Advanced Research in Computer Science and Software Engineering, 6(7), 79-83.

33. Vasiurenko, O., Lyashenko, V., Baranova, V., & Deineko, Z. (2020). Spatial-Temporal Analysis the Dynamics of Changes on the Foreign Exchange Market: an Empirical Estimates from Ukraine. Journal of Asian Multicultural Research for Economy and Management Study, 1(2), 1-6.

34. Ravankar, A. A., & et al. (2020). HPPRM: hybrid potential based probabilistic roadmap algorithm for improved dynamic path planning of mobile robots. Ieee Access, 8, 221743-221766.

35. Qiao, L., & et al. (2022). An Optimized Probabilistic Roadmap Algorithm for Path Planning of Mobile Robots in Complex Environments with Narrow Channels. sensors, 22(22), 8983.

36. Aria, M. (2021). Optimal path planning using informed probabilistic road map algorithm. Journal of Engineering Research.

37. Zhao, Y., & et al. (2021). Multi-branch cable harness layout design based on genetic algorithm with probabilistic roadmap method. Chinese Journal of Mechanical Engineering, 34, 1-11.

38. Hüppi, M., & et al. (2022). T-prm: Temporal probabilistic roadmap for path planning in dynamic environments. In 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE, 10320-10327.

39. Jin, Q., & et al. (2023). An improved probabilistic roadmap planning method for safe indoor flights of unmanned aerial vehicles. Drones, 7(2), 92.

40. Kumar, S., & Sikander, A. (2023). A modified probabilistic roadmap algorithm for efficient mobile robot path planning. Engineering Optimization, 55(9), 1616-1634.