1. Introduction

Mobile robots are widely used in automated industrial environments such as military, security environments, agriculture, mining and in warehouses [1]. The ultimate goal in designing the path planning for a mobile robot is for the mobile robot to move successfully and able to execute task in the environment. In order to achieve this, a path planning algorithms need to be design first. Such algorithm is meant to provide the free collision path from the starting point to its destination with respect to certain criteria such as distance, time taken, safety level of the path and path smoothness. Thus, determining an optimal path in an environment containing obstacles is one of the challenge in designing path planning algorithm. This problem is categorized as NP-complete or NP-hard, depending on the complexity of the environment [2]. Path planning not only save a lot of time but also reduce the wear and capital investment of mobile robot.

Robot navigation can be further divided into three parts which are global navigation, local navigation and personal navigation. In global navigation, the mobile robot knows the location of obstacles, type of environment and its target point. Local navigation is more challenging where the location of the obstacles is dynamic. The mobile robot deals with unknown or partially known environment since certain objects might be stationery or moving.  In this kind of navigation, the mobile robot need to be able to interact with objects or even carrying out task.  Personal navigation is for monitoring of the individual robot and anything in contact with it.

Figure 1: Few Popular Classical and Heuristics Approaches for Mobile Robot Path Planning

Path search algorithm for global navigation is based on classical approaches such as cell decomposition, roadmap algorithm and AFP. Local navigational approaches are more intelligence since they need to interact with the dynamic environment and execute plan autonomously. These methods are classified as in Figure 1.

      The rest of this paper presents the overview of the latest works done in mobile robot path planning field and is organized as follows. Section 2 discussed the optimization criteria for path planning. Section 3 and 4 presents the latest works of most common used classical and heuristics method respectively. Finally, Section 5 concludes the paper.

2. Optimization Criteria

There are few optimization criteria need to be considered in providing an optimal path whether in global or local navigation category. The criteria include distance, cost, time taken, smoothness and energy level. Not just that the characteristics of the mobile robot and environment also need to be taken into account such as turning radius of the robot, velocity, acceleration, shapes of the obstacles and the occurrence of dynamic environment. Three commonly used optimization objective is as follows:

2.1.  Path Length

        Through this criteria, the main goal is to have the shortest path as possible. In order to obtain the total path length, all sub length from the source point to destination point will be total up. This calculation is presented as the following formula [3].

In (1),  represent the number of nodes from the source point to its target.

2.2.  Smoothness

        Smoothness objective tries to have a straight path as possible. This objective will help to reduce energy level as the mobile robot will navigate through the path with minimal turns in a straight way compared to a curvy path that’s uses a lot more energy. Path smoothness can be measured through the following equation [4].

In (2),  are number of angles formed from starting position to target destination and  is value of angle for  Figure 2 illustrates the graphical explanation of this objective with

Figure 2: Graphical Explanation to Measure Smoothness Degree of a Path

2.3.  Safety Degree

Safety degree of a path is definitely vital to provide free collision paths especially in the environment where robot and human needs to interact to each other. A safe path planning is a must especially for a high degree of freedoms (DOFs) mobile robots in dynamic environment where the obstacles are not necessary stationery or in a crowded environment. The safety degree which is also can represent the collision probability is presented in [3]. It can be defined as

In (3)  is the shortest distance between the -th segment and its nearest obstacles, and  is the threshold of the safety degree. Path with a small value of safety degree reflects the small collision probability and will be chosen.

3. Classical Approach

  Initially, classical approaches are commonly used in mobile robot path planning before the development of artificial intelligence methods. The major drawback of these methods are high computational cost and unable to make decision prior to dynamic environment and execute new planning [5]. Cell decomposition approach (CD), roadmap approach (RA) and artificial potential field (AFP) are few classical approaches that are being reviewed in this paper.

3.1.  Cell decomposition approach (CD)

The idea of this method is to divide the environment into a number of connected regions. The shape of the region or cell can be vertical strip cells, array of rectangular grid, or unequal size rectangular grid. Each cells are connected to each other and not overlapping. If the cell contains any obstacles, it will be considered as ‘corrupted cell’ and will be decompose further to get free cell. All cell is given its number representation. This idea is illustrated in Figure 3.

Figure 3: Environment is Decomposing into Few Numbered Free Cells

In this decomposition, any two cells are adjacent if they shared the same boundary. This decomposition can be later on convert into graph as in Figure 4 where cell 1 is the starting position of the mobile robot and cell 14 is the destination.

Figure 4: Decomposition is Converted into Graph

This method has been presented in [6] for real-time operation of mobile robot path planning, in [7] to handle multiple activities in three dimensional environments by using greedy depth-first search and GA based method and in [8] to compare the trajectories of various cell decomposition and graph weights.

3.2.  Roadmap approach (RA)

        Roadmap approach or highway approach uses visibility graphs to develop the roadmap of the environment and further help in finding the shortest path from starting position to the target. In developing visibility graph, all obstacles will first be represented as a polygon. Each of this polygonal obstacles will have nodes correspond to its vertices.

All the nodes will be connected if:

1. they form an edge of the obstacles.
2. the line segment joining them forming a visible connection.

The advantage of this method is if the path found in this roadmap will be the shortest path. However, the performance of this method will be greatly reduced in a complex environment or in higher dimensional-space. The application of roadmap approach using visibility graphs is as presented in [9].

3.3.  Artificial potential field (AFP)

Artificial potential field is first developed by Khatib [10] for mobile robot navigation. This method assumes an artificial force field consists of attractive and repulsive force in the environment. The goal will produce attractive force that attract the mobile robot to move towards it. While, the obstacles generate a repulsive force and is pointing out from the obstacles. These imaginary forces attract the robot towards the goal by avoiding all obstacles. See Figure 5. The robot will be reaching the target point by following the negative gradients. The method is applied widely in mobile robot navigation including implementation in a real time robot path planning [11], modification of the method to be use in dynamic environment [12] and hybridization of this method with other techniques such as GA [13], PSO [14] and FL [15].

Figure 5: Illustration of the Scheme of Artificial Potential Field

4. Heuristics Approach

The development of artificial intelligence method helps mobile robots to navigate more successfully in dynamic environment where the obstacles might be moving or stationery. These methods are most popular nowadays compare to conventional approaches since it can handle the uncertainty present in the environment and make decision. Few popular approaches in this field is being reviewed in this section including genetic algorithm (GA), particle swarm optimization approach (PSO) and ant colony optimization method (ACO).

4.1.  Genetic algorithm (GA)

Genetic algorithm (GA) is one of the heuristics method that has been used widely to solve constrained and unconstrained optimization problem in science and engineering field. In GA, all candidate solutions (called individuals) of the problem will be encoded into chromosomes which will undergoes few basic operations such as selection operator, crossover operator and mutation operator. The fitness value for each individual will be evaluated based on the objectives. In each generation, multiple individuals will be selected based on their calculated fitness value forming a new population to be used in the next iteration. Figure 6 presents the example of the basic step of this method.

Figure 6: Genetic Algorithm Basic Step

Few stopping conditions that can be used to determine termination include:

1. Generations – If a maximum number of generations has been produced.
2. Time Limit – Algorithm will stop if it has been running for a specific period of time.

• Fitness Value – If satisfactory fitness level has been reached for the population.

The comparison between this method and probabilistic RA method has been reported in [16]. Results show that GA produce a smoother path for robot navigation but more time consuming. In [17], a fitness function that optimizes the number of turns take by the mobile robot is suggested where in [18], a new binary encoding by using matrix is presented for mobile robot navigation in both static and dynamic environments.

4.2.  Particle swarm optimization approach (PSO)

Particle swarm optimization (PSO) is derived from the situation of a swarm of birds or a school of fish finding for food. This method mimics the behavior of these animals that doesn’t require any leader to lead the group the reach the food source. These swarm of animals do not know where the food is hidden or exactly located, but they have the information of their distance from it. If each single animal tries to reach the food source on their own, it is inefficient since large number of time will be needed and will cause havoc in the situation. Therefore, the best way is to follow the members who is nearest to the food source [5]. In reflect to the algorithm, each single animal in the search space represent the solution. Each of these solution or particle contain two information,

1. their own fitness value determines by the objective function.
2. the velocities which direct the solution to the target.

This algorithm is initialized with a set of solution. In every iteration, each particle will return their fitness value called pbest. The best pbest value in each iteration is recorded and stored as global best value, gbest. After getting these two values, the algorithm will calculate for the velocity and position of particles. This algorithm has few similarities with genetic algorithm such as starting the procedure with a set of randomly generated population and both methods evaluate the population through fitness value. This method has been implemented for navigation of an aerial robot in three dimensional unknown environments [19], humanoid robot [20] and in industrial robot [21].

4.3.  Ant colony optimization method (ACO)

Ant colony optimization method inspired from the biological situation of ants finding the shortest path between their nest and food source using pheromone trails. Since ants hardly use vision, they will lay pheromone trails when they’re moving from one place to another as a give signal to other ants. If the next ant decides to follow that path with certain probability, they will lay more pheromone to reinforce the trail. The more ants following the path, the stronger the pheromone. Pheromone of a shorter path builds up faster so more ants will follow it. This behavior is illustrated as in Figure 7.

Figure 7: Biological Situation of Ant Colony Optimization Method

In reflect to the algorithm, this algorithm requires some memory to restore data structures. This method has been applied widely in various field including bus routes, garbage collection, telecommunication networks, machine scheduling and composition of products. In [22], ACO is hybridized to be implemented for navigations of humanoids in cluttered environment where in [23], a new fuzzy approach is presented for diversity control of ACO.

5. Conclusion

This study discuss few commonly used classical approaches such as cell decomposition (CD), roadmap approach (RA), artificial potential field (AFP), and heuristics approaches such as genetic algorithm (GA), particle swarm optimization (PSO) approach and ant colony optimization (ACO) for mobile robot navigation. From the discussion, heuristics approaches are more popular and widely used compared to classical approaches due to its robustness and perform well in various environmental condition. This field is in high demand can be extended to several situations. Mobile robot path planning can be inosculated with multi sensor. The use of multi sensor improve mobile robot performance by giving extra information on the surrounding and able to reduced uncertainty given by single sensor. Few topics can be studied in depth related to multi mobile robots for example their task assignment, communication and cooperation between them and group path planning. Mobile robot path planning in high dimensional environment cooperated with static or dynamic obstacles can be another new focus area in this field.

Conflict of Interest

The authors declare no conflict of interest.

Acknowledgment

The authors would like to thank Universiti Malaysia Pahang for supporting part of this research through research grant RDU1703188.

1. H. Y. Zhang, W. M. Lin, A. X. Chen, “Path planning for the mobile robot: A review” Symmetry, 10(10), 450, 2018. https://doi.org/10.3390/sym10100450
2. J. Han, Y. Seo, “Mobile robot path planning with surrounding point set and path improvement” Applied Soft Computing, 57, 35-47, 2017. https://doi.org/10.1016/j.asoc.2017.03.035
3.  X. Y. Wang, G. X. Zhang, J. B. Zhao, H. Rong, F. Ipate, R. Lefticaru, “A modified membrane-inspired algorithm based on particle swarm optimization for mobile robot path planning” Int. J. Comput. Commun. Control, 10, 732–745, 2015. https://doi.org/10.15837/ijccc.2015.5.2030
4. A. Hidalgo-Paniagua, M. A. Vega-Rodriguez, J. Ferruz, N. Pavón, “MOSFLA-MRPP, multi-objective shuffled frog-leaping algorithm applied to mobile robot path planning” Eng. Appl. Artif. Intell, 44, 123–136, 2015. https://doi.org/10.1016/j.engappai.2015.05.0111
5.  B. K. Patle et al., “A review: On path planning strategies for navigation of mobile robot” Defence Technology, 15(4), 582-606, 2019. https://doi.org/10.1016/j.dt.2019.04.0111
6. P. T. Tunggal et al., “Pursuit algorithm for robot trash can based on fuzzy-cell decomposition” Int J Electr Comput Eng, 6(6), 2863-2869, 2016. https://doi.org/10.11591/ijece.v6i6.10766
7. A. Mark, C. Gill, Y. Z. Albert, “A cell decomposition-based collision avoidance algorithm FOR robot manipulators” Cybern Syst, 29(2), 113-135, 2010. https://doi.org/10.1080/019697298125759
8. R. Gonzalez, M. Kloetzer, C. Mahulea, “Comparative study of Trajectories Resulted from Cell Decomposition Path Planning Approaches” in 2017 21st International Conference on System Theory, Control and Computing (ICSTCC), Sinaia, 2017. https://doi.org/10.1109/ICSTCC.2017.8107010
9. L. Lulu, A. Elnagar, “A Comparative Study Between Visibility-Based Roadmap Path Planning Algorithms” in 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, Edmonton, Alta., 2005, https://doi.org/10.1109/IROS.2005.1545545
10.  O. Khatib, “Real Time Obstacle Avoidance for Manipulators and Mobile Robot” in 1985 IEEE International Conference on Robotics and Automation, St. Louis, MO, USA, 1985. https://doi.org/10.1109/ROBOT.1985.1087247.
11.  P. Vadakkepat, K. C. Tan, M. L. Wang, “Evolutionary Artificial Potential Fields and Their Application in Real Time Robot Path Planning” in 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512), La Jolla, CA, USA, 2000. https://doi.org/ 10.1109/CEC.2000.870304
12.  M. G. Park, M. C. Lee, “Artificial Potential Field Based Path Planning for Mobile Robots using Virtual Obstacle Concept” in 2003 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM 2003), Kobe, Japan, 2003. https://doi.org/ 10.1109/AIM.2003.1225434
13.  R. Raja, A. Dutta, K. S. Venkatesh, “New potential field method for rough terrain path planning using genetic algorithm for a 6-wheel rover” Robotics and Autonomous Systems, 72, 295-306, 2015. https://doi.org/ 10.1016/j.robot.2015.06.002
14.  P. H. Kuo, T. H. Li, G. Y. Chen, Y. F. Ho, C. J. Lina, “Migrant-inspired path planning algorithm for obstacle run using particle swarm optimization, potential field navigation, and fuzzy logic controller” The Knowledge Engineering Review, 32(5), 2017. https://doi.org/10.1017/S0269888916000151
15.  J. M. Abdel Kareem, M. H. Garibeh, E. A. Feilat, “Autonomous mobile robot dynamic motion planning using hybrid fuzzy potential field” Soft Computing, 16(1), 153-164, 2012. https://doi.org/10.1007/s00500-011-0742-z
16. C. S. Robert Martin, D. O. Anton Louise, T. U. Aristotle, A. B. Argel, P. D. Elmer, “Path Planning for Mobile Robots using Genetic Algorithm and Probabilistic Roadmap” in 2017 IEEE 9th International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM), Manila, 2017. https://doi.org/10.1109/HNICEM.2017.8269498.
17.  L. Chaymaa, B. Said, E. Ali, “Genetic algorithm based approach for autonomous mobile robot path planning” Procedia Computer Science, 127, 180–189, 2018. https://doi.org/10.1016/j.procs.2018.01.113
18.  B. K. Patle, D. R. K. Parhi, A. Jagadeesh, K. Sunil Kumar, “Matrix-binary codes based genetic algorithm for path planning of mobile robot” Computers and Electrical Engineering, 67, 708–728, 2018. https://doi.org/10.1016/j.compeleceng.2017.12.011
19.  M. A. Rendon, F. F. Martins, “Path following control tuning for an autonomous unmanned quadrotor using particle swarm optimization” IFAC-Papers on Line, 50(1), 325-330. 2017. https://doi.org/10.1016/j.ifacol.2017.08.054
20. P. B. Kumar, K. K. Pandey, C. Sahu, A. Chhotray, D. R. Parhi, “A Hybridized RA-APSO Approach for Humanoid Navigation” in 2017 Nirma University International Conference on Engineering (NUiCONE), Ahmedabad, 2017. https://doi.org/10.1109/NUICONE.2017.8325611
21.  M. Gao, P. Ding and Y. Yang, “Time-Optimal Trajectory Planning of Industrial Robots Based on Particle Swarm Optimization,” in 2015 Fifth International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC), Qinhuangdao, 2015. https://doi.org/10.1109/IMCCC.2015.410
22.  B. K. Priyadarshi, S. Chinmaya, R. P. Dayal, “A hybridized regression-adaptive ant colony optimization approach for navigation of humanoids in a cluttered environment” Applied Soft Computing, 68, 565–585, 2018. https://doi.org/10.1016/j.asoc.2018.04.023
23.  C. Oscar, N. Héctor, S. José, M. Patricia, V. Fevrier, “A new approach for dynamic fuzzy logic parameter tuning in ant colony optimization and its application in fuzzy control of a mobile robot” Applied Soft Computing, 28, 150–159, 2015. https://doi.org/10.1016/j.asoc.2014.12.002

(Click Here)

(Click Here)