Ibrahim A. Hassan | Issa A. Abed
| Walid A. Al-Hussaibi
© 2023 IIETA. This article is published by IIETA and is licensed under the CC BY 4.0 license (http://creativecommons.org/licenses/by/4.0/).
OPEN ACCESS
Autonomous mobile robots grapple with the complexities of navigating their operational environment and exercising independent decision-making. A principal challenge in robotics lies in path planning, i.e., identifying the optimal route from an origin to a destination. Various approaches to surmount this challenge have been probed by researchers, taking into account parameters such as the environment, the type of robot, and application prerequisites. A proficient path-planning algorithm stands as a linchpin for secure mobile robot navigation and the triumphant execution of robotics applications. Typically, the primary objective of the navigation process is to minimize the distance traversed, given its implications on other metrics such as processing time and energy consumption. This research aims to shed light on the pivotal components of mobile robot environment representation, navigation, and offers an analysis of certain path-planning techniques. When the development of navigation algorithms initially kicked off, classical techniques such as Artificial Potential Field (APF), Cell Decomposition, and Roadmap gained popularity. However, compared to their predecessors, heuristic path planning techniques like Genetic Algorithms (GA), Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO) have recently witnessed a surge in exploration. This research presents a balanced examination of the merits and demerits of these methods.
autonomous mobile robots, environments of mobile robots, navigation, path planning
In recent years, mobile robots have become increasingly popular [1]. Today, autonomous mobile robots are essential elements in many applications in real life [2]. Robots are used in industry, the military, agriculture, transportation, medicine, automotive, hazardous environments, science, and technology [3, 4]. Robots are too often used in services as assistants in houses; they can perform any operation, such as serving food, cleaning rooms, and others [5, 6]. Unmanned Aerial Vehicles (UAVs) and Unmanned Underwater Vehicles (UUVs) are also applications of robots [7]. Nowadays, autonomous mobile robots demonstrate remarkable efficiency, precision, and safety as they undertake various tasks [8]. This robot can navigate and work freely without continuous human guidance [9].
In robotics, an important factor is navigation [10], where the motion of a mobile robot from its initial position toward its target position in an environment without collision with obstacles is referred to as navigation [11]. Perception, localization, cognition, and path planning are four parts of the navigation problem [12]. The mobile robot understands the surrounding environment and has the ability to acquire knowledge about itself and the external environment; this is called perception. Perception is essential for a robot to perform autonomously, and it is achieved with the help of high-resolution sensors and algorithms that extract information from them. Processing information from sensors, data representation (environmental modeling), and artificial intelligence algorithms are the essential elements of perception [6]. Localization is defined as a robot’s ability to determine its present location with respect to its position inside a map [10]. Localization gives a mobile robot an assessment of its position and orientation in the environment. Absolute localization and relative localization are two categories among the many technologies utilized in mobile robot localization. Internal sensors such as an encoder, inertial sensors, and a digital compass are used in relative (local) localization to estimate the pose of the robot [6]. By utilizing external sensors, absolute (global) localization enables a robot to locate itself from within its domain. [9]. The strategy and goal are identified by the cognition function; the main goal is to make robots' cognitive processes more similar to those of humans in terms of recognition, interaction, learning, recollection, and memory [6, 13]. Path planning is one of the most important applications in robotics today; it allows the robot to study and calculate the path that it must take to reach the goal [14]. A robot's path planning entails determining the best sequence of translation and rotation from a starting point to a terminal point while avoiding obstacles in its working environment [15, 16]. Four important factors should be focused on for the design of a path. The first factor is the destination, where you discover a good path in a static or dynamic environment. The robot should avoid collisions with obstacles, which is part of the second factor, safety. Optimization is the third factor on which attention should be focused. Its functions include obtaining the best path while minimizing time, shortest distance, and energy consumption. Fourth-factor constraints include acceleration, the ability to rotate, the use of energy, and others. These are some dynamic and environmental constraints [17].
This paper is organized as follows: Three subsections make up Section 2, which explains path planning. The categories of path planning are covered in 2.1 along with environmental representation. 2.2 describes the stages that make up any proposed algorithm as well as the path planning algorithms. The next section describes some of the techniques used in this area and explains the path planning methodologies, which include both classical and heuristic approaches.
A robot must be able to find a path from its current location to its destination position to navigate successfully. Additionally, it must be able to avoid both static and moving obstacles. In order to save time and energy, it may also be assumed that the robot will be able to optimize its path by finding the fastest and safest way to reach its destination [1].
2.1 Environment representation
Figure 1. Categories of path planning [18]
The importance of path planning has been a continuous research subject; therefore, many researchers have focused a lot of attention on path planning [12, 17]. The first step for path planning that is very important is an environment or map representation; topologic, polygon, and digital maps are the three main types of maps that are typically used to help us understand the environment in our daily lives and the path planning input [17]. Environments can be divided into two categories: static and dynamic [18]. Based on the environment and target nature [19], path planning is divided into global and local paths [1, 18, 19]. Partially known and unknown environments deal with local path-planning strategies, while known environments deal with global path-planning strategies [18]. Categories of path planning are shown in Figure 1 [18]. A mobile robot needs to have prior knowledge of the environment for global navigation, while for local navigation; the robot does not need prior knowledge of the environment, obstacle position, or target position [20]. In local navigation, a mobile robot obtains the environment’s information during movement from local sensors [21]. The mobile robot's sensors will help with obstacle Detection and Environment mapping as it moves toward the desired destination; the navigation system's accuracy depends on the working environment and the sensors [9]. In general, navigating in a known environment is easier than navigating in an unknown environment, where an unknown environment can contain static or dynamic obstacles or both [22]. In various conditions of the environment, many algorithms in path planning are researched to get the optimal path for mobile robots [23]. However, methods for tracking the path are just as vital as path planning when it comes to the development of autonomous robots [24].
2.2 Path planning algorithms
Paper Many researchers have been focusing greatly on path planning for mobile robots in a practical and complex environment; many various approaches have been proposed [17]. Path-planning algorithms have become a vital and hot research area. Algorithms can obtain the optimal path for various environments. To select the optimal path for the mobile robot to travel smoothly like a human in the real-world environment, various path-planning algorithms were investigated and proposed [23]. There are three stages to the proposed algorithm: The first stage is intended to be a process for classifying objects in the robot environment (target, robot, and obstacles). For safe and efficient path planning, the localization information and position of these objects have been estimated in the second stage by template matching methods, and a new kinematic control structure has been used to design the third stage as a position controller [25]. Path planning algorithms should be designed with these criteria in mind: shorter path distance, faster response, reasonability, optimality, meeting constraints, less time consumption, and completeness [23]. To obtain the best trajectory along a route, the algorithms should be further optimized to adapt and reduce the noise. The algorithm is more efficient when producing productive results, like less time consumption and a shorter length of path [22]. Many developed algorithms find the optimal solution for many problems, such as multiple regions and narrow passages [8]. Effective point-to-point and safe navigation will be ensured by selecting a suitable path-planning algorithm. The robot geometry and computing constraints are factors that the optimal algorithm in path planning depends on and necessitate a thorough knowledge of current solutions [21].
2.3 Path-planning methodologies
Figure 2. Path planning methods [26]
In general, classical and heuristic approaches are two groups that are classified as path-planning methods [26]. Frequently used classical path-planning approaches include the Artificial Potential Field (APF), mathematical programming, cell decomposition, and the roadmap approach method. On the other hand, heuristic approaches like Bacterial Foraging Optimization (BFO), Genetic Algorithms (GA), Artificial Neural Networks (ANN), Particle Swarm Optimization (PSO), Fuzzy Logic (FL), Artificial Bee Colonies (ABC), and Ant Colony Optimization (ACO) are getting popular among researchers in the field [24, 26, 27]. Figure 2 explains various methods for path planning [26].
2.3.1 Classical approaches
The major disadvantages of classical approaches are their large computational and memory costs and their failure to adapt to the environment's uncertainty; therefore, for implementation in real-time, they are less desirable [8, 20]. For mobile robot path planning, simplicity and computational efficiency are advantages that are very important. Some of the classical approaches are discussed in the following:
(1) Artificial Potential Field (APF): The APF presented in 1986 by Khatib for the navigation of mobile robots. [20, 28]. This technique's main goal is to direct the robot to the objective by creating attractive and repulsive forces in its workspace. Targets are assigned attractive forces, and obstacles are given repulsive forces [12]. Figure 3 shows the attractive and repulsive forces.
Figure 3. Model of artificial potential [28]
(a) Visibility graph
(b) Voronoi diagram
Figure 4. Visibility graph and Voronoi diagram [20]
(2) Cell Decomposition (CD) Method: In this method, the robot’s workspace is divided into many sample regions, each of which is called a cell [20, 29]. The objective of this method is to present a series of stages from the initial point to the goal without any obstacles. Using cells with no obstacles would provide such a sequence of steps. First, the cell with obstacles is divided into other new cells, and then these pure cells (without obstacles) are added to the series [12]. There are three types of CD approaches: exact, adaptive, and approximate [20].
(3) Roadmap (RA) Method: The shortest path between the robot's starting position and its goal position can be determined by using the RA. The roadmap has been developed using the visibility graph and the Voronoi diagram. Figure 4 (a) shows the start and goal positions on the map are connected with nodes by using the visibility graph. For path planning, another roadmap method used is the Voronoi diagram. In this method, the region is divided into sub-regions, as shown in Figure 4 (b) [20].
2.3.2 Heuristic approaches
Compared to the previous approaches, heuristic path planning methods have seen a lot of activity recently. The fundamental distinction is that a heuristic-based approach has the capability of learning from behavior similar to that of humans [1]. Some of the most popular approaches are discussed in the following:
(1) Genetic Algorithm: John Holland developed the Genetic Algorithm in 1960 [30], a general-purpose searching and optimizing algorithm based on the principles of Darwin's theory of evolution [30, 31]. GA is an optimization algorithm that is widely used to create answers for problems involving both optimization and search. GA followed the principles of natural selection and genetic. The main GA applications have been in the area of computer science. However, the field of robot navigation also includes the use of GA-based algorithms. The GA does not start with any knowledge of the best solution and relies entirely on how the environment and evolutionary operators respond to find the best solution. By avoiding the obstacles, GA is used in the search for the target [26]. One optimization technique, GA, allows searching inside very large, complex areas [32]. GA is a method of randomized search [33]. This algorithm effectively adapts to the environment (both known and unknown); it is used in the 2D path planning of a humanoid robot and the 3D path planning problem for aerial and underwater vehicles [20]. GA have the benefit of covering a broad search field while utilizing little memory and CPU resources [21]. Many scholars have created a hybrid strategy by applying GA in addition to other intelligent algorithms, like GA-NN, GA-PSO, and GA-FL.
(2) Particle Swarm Optimization (PSO): is a swarm intelligence-inspired meta-heuristic algorithm [10]. It is based on how fish in a pool or a flock of birds behave when looking for food [27]. PSO has been used for a variety of purposes, particularly in mobile robotics [34]. It is frequently employed in mobile robot navigation [20]. This approach describes population members as particles that represent potential solutions to a given problem, and it uses processes like generation, evaluation, and updating to help these particles converge on the best solution [10]. Most researchers were motivated to adapt this technique for use by mobile robots navigating in dynamic environments because of PSO's excellent efficiency in terms of memory needs and speed. When creating the path planner, this method takes into account any obstacles and the shape of the robot. The fitness function in this method is defined with a simple coding scheme [26]. In the early stages of the search, the algorithm's convergence speed is fast, but in the late stages of the search, it is slow [35]. Although the method is fast and effective, it is simple to approach a local optimum [29]. The local optimal solution is the best one, based on PSO [35]. The advantages of this algorithm for solving path planning in robotics include fast convergence, easy implementation, and high precision [29].
(3) Ant Colony Optimization (ACO): In 1996, Italian researcher Marco Dorigo introduced Ant Colony Optimization, a method for traveling agents and solving distributed optimization problems based on the foraging behavior of ants [36]. The combinatorial optimization problem is resolved using ACO [26]. The fundamental idea behind the ACO is that each ant will secrete a substance to serve as a reference for its next steps and to detect other ants' secretions while in search of food. Usually, this secretion is referred to as a pheromone. The pheromone is a parameter in this algorithm; the ant colony can communicate with one another and make decisions due to pheromones. When one path has more pheromones than the other ones, the ant colony will travel on this path, causing more secretions to be released so that the pheromone concentration rises to draw in the later ants, creating a positive feedback process. After some time, the pheromone concentration on the shorter path increases, and the number of ants choosing it gradually rises. The pheromones on other routes drop progressively until they disappear. The overall ant colony is finally condensed along the optimal route. The path planning of robots is similar to that of an ant colony [29]. Several Numerous sectors of science and engineering have already used the ACO algorithm, including vehicle routing, quadratic assignment issues, traveling salesman problems, graph coloring, and many others. The ACO is being employed to solve the problem of mobile robot navigation for effective path planning and obstacle avoidance [20, 26].
It An important topic of research in mobile robots that has attracted the interest of many researchers is the path planning problem. A description of the various path planning methods applied to mobile robot navigation, environment representation, the categories of global and local path planning, and both classical and heuristic approaches are discussed in this research. In addition, discuss the benefits and drawbacks of each approach. RA, APF, and CD are some of the classical approaches discussed. Due to their demanding computing needs and inability to operate in dynamic environments, they might not be dependable in practical applications. GA, PSO, and ACO are only some of the heuristic-based approaches that are discussed. Some of the most popular techniques for mobile robot navigation are these ones. These algorithms, in contrast to the classical approaches, do not absolutely guarantee finding a solution, but when they do, they will do so with less time and computation. As a result, heuristic techniques are much better suited to practical applications, particularly in dynamic environments. However, the efficiency of these methods, in general, depends largely on how exact and reliable the information is given. Therefore, based on the methods that have been reviewed, it is expected that the trend of path planning research will continue, and the field is likely heading toward heuristic techniques. Future work includes designing and implementing a mobile robot capable of working in both static and dynamic situations in real-time and employing one of the path planning methods to evaluate the performance and behavior of these methods.
[1] Campbell, S., O'Mahony, N., Carvalho, A., Krpalkova, L., Riordan, D., Walsh, J. (2020). Path planning techniques for mobile robots a review. In 2020 6th International Conference on Mechatronics and Robotics Engineering (ICMRE), IEEE, Barcelona, Spain, pp. 12-16. https://doi.org/10.1109/ICMRE49073.2020.9065187
[2] Nasrinahar, A., Chuah, J.H. (2018). Intelligent motion planning of a mobile robot with dynamic obstacle avoidance. Journal on Vehicle Routing Algorithms, 1: 89-104. https://doi.org/10.1007/s41604-018-0007-4
[3] Alshorman, A.M., Alshorman, O., Irfan, M., Glowacz, A., Muhammad, F., Caesarendra, W. (2020). Fuzzy-based fault-tolerant control for omnidirectional mobile robot. Machines, 8(3): 55. https://doi.org/10.3390/machines8030055
[4] Lee, C.T., Su, B.R., Chang, C.H., Hsu, T.Y., Lee, W.D. (2018). Applications of Taguchi method to PID control for path tracking of a wheeled mobile robot. In 2018 IEEE International Conference on Applied System Invention (ICASI), IEEE, Chiba, Japan, pp. 453-456. https://doi.org/10.1109/ICASI.2018.8394283
[5] Denysyuk, P., Teslyuk, V., Chorna, I. (2018). Development of mobile robot using LIDAR technology based on Arduino controller. In 2018 XIV-th International Conference on Perspective Technologies and Methods in MEMS Design (MEMSTECH), IEEE, Lviv, Ukraine, pp. 240-244. https://doi.org/10.1109/MEMSTECH.2018.8365742
[6] Niloy, M.A., Shama, A., Chakrabortty, R.K., Ryan, M.J., Badal, F.R., Tasneem, Z., Ahamed, M.H., Moyeen, S.I., Das, S.K., Ali, M.F., Islam, M.R., Saha, D.K. (2021). Critical design and control issues of indoor autonomous mobile robots: A review. IEEE Access, 9: 35338-35370. https://doi.org/10.1109/ACCESS.2021.3062557
[7] Drake, D., Koziol, S., Chabot, E. (2018). Mobile robot path planning with a moving goal. IEEE Access, 6: 12800-12814. https://doi.org/10.1109/ACCESS.2018.2797070
[8] Pol, R.S., Murugan, M. (2015). A review on indoor human aware autonomous mobile robot navigation through a dynamic environment survey of different path planning algorithm and methods. In 2015 International Conference on Industrial Instrumentation and Control (ICIC), IEEE, Pune, India, pp. 1339-1344. https://doi.org/10.1109/IIC.2015.7150956
[9] Esan, O., Du, S., Lodewyk, B. (2020). Review on autonomous indoor wheel mobile robot navigation systems. In 2020 International Conference on Artificial Intelligence, Big Data, Computing and Data Communication Systems (icABCD), IEEE, Durban, South Africa, pp. 1-6. https://doi.org/10.1109/icABCD49160.2020.9183838
[10] Ab Wahab, M.N., Nefti-Meziani, S., Atyabi, A. (2020). A comparative review on mobile robot path planning: Classical or meta-heuristic methods? Annual Reviews in Control, 50: 233-252. https://doi.org/10.1016/j.arcontrol.2020.10.001
[11] Wang, D., Hu, Y., Ma, T. (2020). Mobile robot navigation with the combination of supervised learning in cerebellum and reward-based learning in basal ganglia. Cognitive Systems Research, 59: 1-14. https://doi.org/10.1016/j.cogsys.2019.09.006
[12] Injarapu, A.S.H.H.V., Gawre, S.K. (2017). A survey of autonomous mobile robot path planning approaches. In 2017 International Conference on Recent Innovations in Signal Processing and Embedded Systems (RISE), IEEE, Bhopal, India, pp. 624-628. https://doi.org/10.1109/RISE.2017.8378228
[13] Aarthi, R., Amudha, J. (2020). Study on computational visual attention system and its contribution to robotic cognition system. In 2020 4th International Conference on Trends in Electronics and Informatics (ICOEI)(48184), IEEE, Tirunelveli, India, pp. 278-283. https://doi.org/10.1109/ICOEI48184.2020.9142955
[14] Choueiry, S., Owayjan, M., Diab, H., Achkar, R. (2019). Mobile robot path planning using genetic algorithm in a static environment. In 2019 Fourth International Conference on Advances in Computational Tools for Engineering Applications (ACTEA), IEEE, Beirut, Lebanon, pp. 1-6. https://doi.org/10.1109/ACTEA.2019.8851100
[15] Santos, L.C., Santos, F.N., Pires, E.S., Valente, A., Costa, P., Magalhães, S. (2020). Path planning for ground robots in agriculture: A short review. In 2020 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC), IEEE, Ponta Delgada, Portugal, pp. 61-66. https://doi.org/10.1109/ICARSC49921.2020.9096177
[16] Zhi, L., Xuesong, M. (2018). Navigation and control system of mobile robot based on ROS. In 2018 IEEE 3rd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), IEEE, Chongqing, China, pp. 368-372. https://doi.org/10.1109/IAEAC.2018.8577901
[17] Ou, L., Liu, W., Yan, X., Chen, Y., Liang, J. (2018). A review of representation, model, algorithm and constraints for mobile robot path planning. In 2018 IEEE 4th Information Technology and Mechatronics Engineering Conference (ITOEC), IEEE, Chongqing, China, pp. 563-569. https://doi.org/10.1109/ITOEC.2018.8740620
[18] Alatise, M.B., Hancke, G.P. (2020). A review on challenges of autonomous mobile robot and sensor fusion methods. IEEE Access, 8: 39830-39846. https://doi.org/10.1109/ACCESS.2020.2975643
[19] Zhong, X., Tian, J., Hu, H., Peng, X. (2020). Hybrid path planning based on safe A* algorithm and adaptive window approach for mobile robot in large-scale dynamic environment. Journal of Intelligent & Robotic Systems, 99: 65-77. https://doi.org/10.1007/s10846-019-01112-z
[20] Patle, B.K., Pandey, A., Parhi, D.R.K., Jagadeesh, A.J.D.T. (2019). A review: On path planning strategies for navigation of mobile robot. Defence Technology, 15(4): 582-606. https://doi.org/10.1016/j.dt.2019.04.011
[21] Karur, K., Sharma, N., Dharmatti, C., Siegel, J.E. (2021). A survey of path planning algorithms for mobile robots. Vehicles, 3(3): 448-468. https://doi.org/10.3390/vehicles3030027
[22] Khaksar, W., Vivekananthen, S., Saharia, K.S.M., Yousefi, M., Ismail, F.B. (2015). A review on mobile robots motion path planning in unknown environments. In 2015 IEEE International Symposium on Robotics and Intelligent Sensors (IRIS), IEEE, Langkawi, Malaysia, pp. 295-300. https://doi.org/10.1109/IRIS.2015.7451628
[23] Yan, Y., Li, Y. (2016). Mobile robot autonomous path planning based on fuzzy logic and filter smoothing in dynamic environment. In 2016 12th World Congress on Intelligent Control and Automation (WCICA), IEEE, pp. 1479-1484. https://doi.org/10.1109/WCICA.2016.7578767
[24] Hernández, B., Giraldo, E. (2018). A review of path planning and control for autonomous robots. In 2018 IEEE 2nd Colombian Conference on Robotics and Automation (CCRA), IEEE, Guilin, China, pp. 1-6. https://doi.org/10.1109/CCRA.2018.8588152
[25] Dirik, M., Kocamaz, A.F., Castillo, O. (2020). Global path planning and path-following for wheeled mobile robot using a novel control structure based on a vision sensor. International Journal of Fuzzy Systems, 22: 1880-1891. https://doi.org/10.1007/s40815-020-00888-9
[26] Hewawasam, H.S., Ibrahim, M.Y., Appuhamillage, G.K. (2022). Past, present and future of path-planning algorithms for mobile robot navigation in dynamic environments. IEEE Open Journal of the Industrial Electronics Society, 3: 353-365. https://doi.org/10.1109/OJIES.2022.3179617
[27] Zafar, M.N., Mohanta, J.C. (2018). Methodology for path planning and optimization of mobile robots: A review. Procedia Computer Science, 133: 141-152. https://doi.org/10.1016/j.procs.2018.07.018
[28] Rostami, S.M.H., Sangaiah, A.K., Wang, J., Liu, X. (2019). Obstacle avoidance of mobile robots using modified artificial potential field algorithm. EURASIP Journal on Wireless Communications and Networking, 2019(1): 1-19. https://doi.org/10.1186/s13638-019-1396-2
[29] Zhang, H.Y., Lin, W.M., Chen, A.X. (2018). Path planning for the mobile robot: A review. Symmetry, 10(10): 450. https://doi.org/10.3390/sym10100450
[30] Lamini, C., Benhlima, S., Elbekri, A. (2018). Genetic algorithm based approach for autonomous mobile robot path planning. Procedia Computer Science, 127: 180-189. https://doi.org/10.1016/j.procs.2018.01.113
[31] Cheng, K.P., Mohan, R.E., Nhan, N.H.K., Le, A.V. (2020). Multi-objective genetic algorithm-based autonomous path planning for hinged-tetro reconfigurable tiling robot. IEEE Access, 8: 121267-121284. https://doi.org/10.1109/ACCESS.2020.3006579
[32] Abed, I.A., Koh, S.P., Sahari, K.S.M., Tiong, S.K., Tan, N.M. (2013). Optimization of task scheduling for single-robot manipulator using pendulum-like with attraction-repulsion mechanism algorithm and genetic algorithm. Australian Journal of Basic and Applied Sciences, 7: 426-445.
[33] Hussin, K.N., Naha, A.K., Khleaf, H.K. (2022). A hybrid bat-genetic algorithm for improving the visual quality of medical images. Indonesian Journal of Electrical Engineering and Computer Science, 28(1): 220-226. https//doi.org/10.11591/ijeecs.v28.i1.pp220-226
[34] Zhang, J.H., Zhang, Y., Zhou, Y. (2018). Path planning of mobile robot based on hybrid multi-objective bare bones particle swarm optimization with differential evolution. IEEE Access, 6: 44542-44555. https://doi.org/10.1109/ACCESS.2018.2864188
[35] Li, D., Wang, P., Du, L. (2018). Path planning technologies for autonomous underwater vehicles-A review. IEEE Access, 7: 9745-9768. https://doi.org/10.1109/ACCESS.2018.2888617
[36] Zhang, D., You, X., Liu, S., Pan, H. (2020). Dynamic multi-role adaptive collaborative ant colony optimization for robot path planning. IEEE Access, 8: 129958-129974. https://doi.org/10.1109/ACCESS.2020.3009399
