search for




 

Local Path Planning of a Mobile Robot Using a Novel Grid-Based Potential Method
International Journal of Fuzzy Logic and Intelligent Systems 2020;20(1):26-34
Published online March 25, 2020
© 2020 Korean Institute of Intelligent Systems.

Jun-Ho Jung1 and Dong-Hun Kim2

1Department of Mechatronics Engineering, Kyungnam University, Changwon, Korea
2Department of Electrical Engineering, Kyungnam University, Changwon, Korea
Correspondence to: Dong-Hun Kim (dhkim@kyungnam.ac.kr)
Received January 20, 2020; Revised March 10, 2020; Accepted March 12, 2020.
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract

This paper proposes the local path planning of a mobile robot using a novel grid-based potential method. The proposed method can be easily applied to a robotic system in a real environment because it is designed based on actual sensors. This method solves the local minimum problems that occur frequently in the potential field. A new repulsive field is created between adjacent obstacles that a mobile robot cannot pass through by calculating the distance between the robot and the obstacles. The generated repulsion field causes a mobile robot to escape from the local minimum. MATLAB simulations are used to compare the proposed and conventional potential field methods.

Keywords : Potential function, Grid potential field, Local minimum, Path planning
1. Introduction

An autonomous mobile robot should create a route plan to move to the goal point by safely avoiding obstacles in its driving environment. The route plan is classified into global path planning and local path planning. Global path planning refers to creating optimal paths off-line in a situation where all the information about the environment provided to the mobile robot is known. Local path planning refers to the generation of optimal paths online by recognizing obstacles during driving through real-time sensors without providing priori information on the environment to the mobile robot. Global route planning knows all the information, making it easy to find the best route. However, it is difficult for a robot to avoid moving obstacles in a new environment. Local path planning quickly adapts to dynamic obstacles or changing environments. However, it is difficult to find an optimal path through this approach.

Studies on path planning include methods using fuzzy and neural network techniques [1], road maps [2], cell decomposition [3], and potential fields [46]. Among them, the potential field method has been used in several studies because its structure is simple and it is easy to understand. The potential field forms an attractive force between a mobile robot and a goal point, and generates a repulsive force between the mobile robot and obstacles. In potential fields, the mobile robot is moved to the goal point by the attractive field. When the mobile robot encounters an obstacle in a path when moving toward the goal point, it avoids the obstacle through the repulsive field generated between itself and the obstacle and moves safely to the goal point. However, there are several drawbacks to potential fields. First, mobile robots often fall into the local minimum in potential fields [79]. The local minimum is the point at which the mobile robot cannot exit from an area with adjacent obstacles. For example, in U-shaped obstacles, attractive fields and repulsive fields cancel each other out. Second, as the position of an obstacle is recognized as a point in the potential field, the application of the potential field methods to a robotic system in a real environment is difficult. This is because obstacles in a real environment have different sizes and shapes. Sensors that detect an obstacle recognize the surface of the obstacle. Thus, based on the line of sight (LOS) of a robot, it is difficult to implement the recognition of obstacles using the potential methods into the hardware. Thus, in this paper, we propose a grid-based potential field method to mitigate the aforementioned two limitations.

In the grid path planning method, a quadrilateral grid is generated by dividing the interval between the x- and y-axes according to a specified distance in a two-dimensional (2D) environment. Grid path planning recognizes all the cells in which obstacles exist as obstacles. As the moving robot avoids the recognized cells, it can move to the goal point more safely by avoiding the obstacle from a long distance. Most sensors that detect obstacles use grid-based cells. Sensors using the grid method can quickly recognize obstacles and obtain their location information. Path relaxation involves planning safe paths around obstacles for mobile robots [10]. However, this study introduces only a basic scheme of grid-based path planning.

The optimal path planning to avoid obstacles is achieved by applying the A* algorithm to the grid path [11, 12]. However, in the grid path planning, as the calculated path uses quadrilateral vertices or sides, a stepped path is designed in which the movement of the path is angled by 90?.

Smooth path generation using a B-spline was proposed [13]. It deals with aerial vehicles maneuvering in a 2D environment modeled with hexagonal cell representation, which features increased connectivity among cells over square cell representation. This method effectively provides a smooth path, but it cannot be applied in a real environment with obstacles.

A crowd simulation of a path planning model based on grid-potential fields was presented [14]. A terrain space that dis-cretizes a potential field into a regular grid was represented. However, the local minimum problem was still not solved. It was solved by using a grid map [15]. However, this method distinguishes between the obstacle area and safe area. Hence, it has a limitation in that the grid map has to be constructed without considering LOS.

This study aimed to develop conventional potential methods to achieve hardware implementation in a real environment. We deal with grid path planning by considering LOS. The local minimum problems are solved by the newly generated potential field integrating adjacent obstacle cells. Finally, the proposed method enables the escape from the local minimum and smooth path generation by using MATLAB simulation.

2. Potential Field

In the potential function, the attractive potential is an attractive force between a robot and a goal point [16]. The attractive potential function can be defined as

Ugoal(k)=-cge-(ψg(k)lg)2,ψg(k)=Pgoal-P(k),

where cg represents the magnitude of the force of attraction toward a goal point, which can control the speed of the robot. lg represents the range of the attractive potential. ψg represents the distance between the robot (P) and the goal point (Pgoal). In the attractive potential field, the mobile robot is provided high potential and the goal point is provided low potential. The mobile robot in a high position moves to the goal point as if from top to bottom. When the mobile robot reaches the goal point, it converges to zero. The corresponding force given by the negative gradient of the attractive potential is used for robot movement.

In the potential function, the repulsive potential is the repulsive force between a robot and an obstacle. The repulsive potential function can be defined as

Uobs(k)=coe-(ψo(k)lo)2,ψo(k)=|Pobs-P(k)|,

where co represents the magnitude of the repulsive potential and lo represents the range of the repulsive potential. ψo represents the distance between the mobile robot (P) and the obstacle (Pobs).

In the repulsive potential field, obstacles are provided high potentials, and in the absence of obstacles, zero potential is provided. The corresponding force given by the negative gradient of the repulsive potential is used for robot movement.

The total potential function is the sum of the attractive and repulsive functions. The final potential function can be defined as

Utotal(k)=Ugoal(k)+Uobs(k)=-cge-(ψg(k)lg)2+k=1Ncoe-(ψo(k)lo)2,

where N is the number of obstacles.

When a robot encounters a high repulsive potential in the moving area in the potential field, it moves to the goal point by avoiding obstacles in the low-potential direction.

3. Design of Grid Potential

In the proposed grid-based potential method, the potential parameters cg, lg, co, lo in Eq. (5) are not used as constants but as variables cg(k), lg(k), co(k), lo(k). This is because the variables are required to change the magnitude and range of the potential fields depending on the number of adjacent obstacles.

Thus, the total potential function can be defined as follows:

Utotal(k)=Ugoal(k)+Uobs(k)=-cge-(ψg(k)lg)2+k=1Nco(k)e-(ψo(k)lo(k))2,

where N is the group number of grid cells filled by obstacles.

A grid method based on LOS is required for using sensors that recognize obstacles in a robotic system in a real environment. Based on actual sensors, the distance and angle in the 2D space are divided into cell types consisting of several zones. Obstacles are represented as filled cells, and the robot recognizes filled cells as obstacles.

In Figure 1, two obstacles can be observed, and the robot detects the obstacles that are visible in the path toward the goal point through the sensor.

In conventional grid methods, the entire cell that exists as an obstacle is recognized, but not the obstacle surface based on LOS [14, 15]. This is challenging in a robotic system in a real environment. However, the proposed method can be easily applied to a robotic system in a real environment, as the sensor for obstacle recognition recognizes only the visible surface of neighboring obstacles.

The objective is to create an attractive potential. In Figure 2, the robot can recognize obs1 to obs4 when viewing in the direction of the goal point, but obs5 and obs6 are hidden by obstacles that cannot be recognized by the robot. Therefore, the obstacles obs5 and obs6 are not considered.

The robot determines that it can pass safely between obstacles if the distance between the obstacles is larger than the size of the robot. In this study, it is considered that the robot can move safely between obstacles when the size (dr) of the robot is greater than twice the distance between obstacles. It is also assumed that the size of a cell is twice that of the robot. Therefore, the robot can pass safely through a cell in an obstacle-free space. For example, in Figure 5, the distance between the obstacles obs1 and obs2 is sufficient for the robot to pass between them. However, the robot cannot pass between the adjacent obstacles obs2 and obs3. In a typical potential field environment, the robot falls into a local minimum, which is a narrow passage problem.

The obstacles shown in Figure 2 are indicated by a square grid type. However, the actual repulsive potential is represented by a circular shape, which results in a local minimum between the two obstacles. This study measures the distances between all the obstacles and determines whether the robot can pass through these distances, to solve the aforementioned problem. If it is determined that the robot cannot pass between obstacles, the proposed method creates a composite repulsive field to prevent the robot from falling into the local minimum.

The distance (di,i+1) between obstacles is defined as follows:

di,i+1=(obsxi-obsxi+1)2+(obsyi-obsyi+1)2,i=1,,m,

where m is the number of obstacles that can be recognized by the robot.

The distance (di,i+1) between obstacles is calculated in order from obstacles 1 to 4 recognized by the LOS of the robot. The distance (di,i+1) between the obstacles must be larger than the length (dr) of the robot, for the robot to pass safely between them. The condition to be satisfied is expressed as follows:

di,i+1>2dr.

As shown in Eq. (8), when the distance (di,i+1) between the obstacles is larger than twice the size of the robot (2dr), the robot can safely pass between them. However, if the distance between the obstacles (di,i+1) is smaller than twice the size of the robot (2dr), the robot cannot pass safely between the obstacles.

This paper proposes a new repulsive potential. A newly generated repulsive potential is located at the center of two adjacent obstacles and the range of the repulsive potential of the two obstacles is integrated. Therefore, the position of the repulsive potential to be generated can be defined as follows:

obsxi,i+1=obsxi+obsxi+12,obsyi,i+1=obsyi+obsyi+12.

The position of the repulsive potential function in Eq. (9) is defined as a vector, obsi,i+1=[obsxi,i+1obsyi,i+1].obsi,i+1 is located at the center of the obstacles obsi and obsi+1 according to Eq. (9).

The role of the new repulsive potential in Eq. (3) is to create a larger repulsive field than that generated by the two adjacent obstacles, causing the robot to evade at a location far from the adjacent obstacles. The weight of the new repulsive potential should cover the range of the two adjacent obstacles. Therefore, this weight controls the magnitude and range of the new repulsive potential.

Figure 3 shows the magnitude and range of the repulsive potential field. Figure 3(a) illustrates the magnitude and range of the repulsive potential field generated by an obstacle with cO = 2 and lo = 0.2. When the two obstacles are adjacent, the range of repulsive field to be generated should include the range of the two obstacles. Therefore, the range of the new repulsive potential field should be at least twice that of the repulsive potential field generated by the two obstacles. Figure 3(b) shows that the range of the repulsive field with lo = 0.7 is increased. However, the magnitude of the potential is reduced. When the magnitude of the potential decreases, the robot may not safely avoid obstacles and may approach the obstacles. Therefore, the magnitude of the new repulsive potential field should also be increased. Figure 3(c) shows that the magnitude of the repulsive potential field with co = 0.3 is increased. Therefore, the new repulsive potential field generated by adjacent obstacles increases the values of co and lo according to the number of adjacent obstacles.

Figure 4 shows the values of co and lo according to the number of obstacles. In Figure 4, n is the number of adjacent obstacles. Eqs. (10) and (11) are proposed for the design guideline of the values of co and lo. As the number of adjacent obstacles increases, co increases by 1.5 and lo increases by 0.5.

co(k)=1.5(n-1)+2,lo(k)=0.5(n-1)+0.2.

Consequently, the parameter values of the conventional potential functions are changed from constants to variables in the proposed potential functions.

As the number of obstacles increases, the position of the repulsive function can be defined as follows:

obsxi,j=obsxi++obsxjn,obsyin,im=obsyi++obsyjn,

where obsi and obsj are the first and last obstacles among the adjacent obstacles recognized by the LOS of the robot, respectively.

The repulsive potential generated according to Eq. (12) is located at the center of the adjacent obstacles. As the number of adjacent obstacles increases, the magnitude (co) and range (lo) of the repulsive potential increase.

Figure 5 shows that obs2 and obs3 are adjacent to each other where a large circle is created by the two obstacles. The large circle indicates the range of the repulsive potential generated from the position obs2,3. When the robot moves to the goal point, it avoids obs2 and obs3 through the new repulsive potential before approaching the two adjacent obstacles.

Thus, the robot can avoid obstacles without approaching them by applying variable potential parameters to the cells recognized using sensors.

4. Simulation

Comparative simulations between a conventional gird method and the proposed grid method are presented for the cases where a robot falls into a local minimum. In the conventional grid potential field, the magnitude and range of the attractive potential function are designed with cg = 3 and lg = 7. The magnitude and range of the repulsive potential function are designed with co = 2 and lo = 0.2.

Local minimum problems are generally caused in a U-shaped area (including area of parallel cells) or a narrow passage. As for adjacent obstacles in such an environment, the composite potential generated by each cell in the LOS generates a concave field, where the robot falls into a local minimum. In the proposed method, the potential generated by the center of cells in the LOS forms a convex field. Thus, the local minimum problem in a U-shaped area does not occur. In the case of a narrow passage, this problem is resolved naturally, as the length of a cell recognized by a sensor is set to be larger than the size of the robot. In a MATLAB simulation, three robots start from different positions and show different paths to the goal position according to their positions.

Figure 6(a) shows a case where a robot falls into a local minimum in front of two adjacent obstacles. This is the simulation result obtained using the conventional potential function method. The robot was trapped at the center point between the repulsive potentials generated by the two obstacles. At the center of the two obstacles, the range of repulsive potential generated by a cell was a circle, and the two circles generated by the cells overlapped. Hence, this point has the lowest potential. Figure 6(b) is the simulation result obtained using the proposed method. Figure 6(b) shows that the robot that started from the center avoided the local minimum through the new repulsive potential and reached the goal point.

Figure 7(a) shows the simulation result obtained using the conventional method. In Figure 7(a), an obstacle is composed of three cells in a U-shaped area where a robot tends to fall into the local minimum. Only one of the three robots that started in different positions safely reached the goal by avoiding obstacles. Figure 7(b) is the simulation result obtained using the proposed method. Figure 7(b) shows that a new repulsive potential was created at the center of the three obstacles. With the generated repulsive potential, the robots that started from the left and center arrived safely at the goal point by avoiding the U-shaped obstacle.

In Figure 8, the number of adjacent obstacles was increased to five to make the robots fall into a local minimum. Figure 8(a) is the simulation result obtained using the conventional method, where two robots were trapped in a space consisting of five adjacent cells. Figure 8(b) is the simulation result obtained using the proposed method. In Figure 8(b), even though the number of adjacent obstacles was increased, the parameter values of the newly generated repulsive potential were increased to make the field cover the range of all adjacent obstacles. All the robots safely arrived at the goal point by avoiding the local minimum through the proposed method.

From a comparison with the conventional method for the three cases, the proposed method shows that the robots can safely reach the goal without falling into the local minimum.

Table 1 presents a numerical comparison between the conventional and proposed methods. It shows the time step of path travel for each simulation. Compared with the conventional method, the proposed method shows that all the robots can safely reach the goal faster. In Table 1, the time step means total number of dots for a robot in each Figure 6, 7, and 8, which is time for path travel.

5. Conclusions

In this paper, we proposed a method to generate a new repulsive potential so that a robot avoids a local minimum in grid potential fields. The magnitude and range of the repulsive potential were designed by adjusting the weight of the generated repulsive potential based on the number of adjacent obstacles. As the grid map was only used by the sensor to recognize obstacles, the proposed method provided a smooth trajectory regardless of the grid cell when the robot was in motion.

Extensive simulation results confirmed the effectiveness of the local minimum solution based on the proposed potential field method. In addition, the proposed method can be easily applied to a robotic system in a real environment, as it is designed based on actual sensors in the LOS using grid cells.

Conflict of Interest

No potential conflict of interest relevant to this article was reported.

Acknowledgements

This study was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (No. NRF-2017R1A2B4011329).

Figures
Fig. 1.

Grid method.


Fig. 2.

Robot view of obstacles in the direction of a goal point.


Fig. 3.

Magnitude and range of the repulsive field: (a) co = 2, lo = 0.2, (b) co = 2, lo = 0.7, and (c) co = 3.5, lo = 0.7.


Fig. 4.

Weight change of the repulsive potential.


Fig. 5.

New repulsive field.


Fig. 6.

Local minimum with two parallel adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.


Fig. 7.

Local minimum with three U-shaped adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.


Fig. 8.

Local minimum with five U-shaped adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.


TABLES

Table 1

Time step of path travel for each simulation

Conventional methodProposed method
Robot1 in Figure 68478
Robot3 in Figure 68275
Robot3 in Figure 77774
Robot3 in Figure 88984

References
  1. Jiang, M, Yu, Y, Liu, X, Zhang, F, and Hong, Q 2012. Fuzzy neural network based dynamic path planning., Proceedings of 2012 International Conference on Machine Learning and Cybernetics, Xian, China, Array, pp.326-330. https://doi.org/10.1109/ICMLC.2012.6358934
    CrossRef
  2. Bhattacharya, P, and Gavrilova, ML (2008). Roadmap-based path planning - using the Voronoi diagram for a clearance-based shortest path. IEEE Robotics & Automation Magazine. 15, 58-66. https://doi.org/10.1109/MRA.2008.921540
    CrossRef
  3. Lingelbach, F Array. Path planning using probabilistic cell decomposition., Proceedings of IEEE International Conference on Robotics and Automation, New Orleans, LA, Array, pp.467-472. https://doi.org/10.1109/ROBOT.2004.1307193
    CrossRef
  4. Ge, SS, and Cui, YJ (2000). New potential functions for mobile robot path planning. IEEE Transactions on Robotics and Automation. 16, 615-620. https://doi.org/10.1109/70.880813
    CrossRef
  5. Jung, KM, and Sim, KB (2009). Path planning for autonomous mobile robot using potential field. International Journal of Fuzzy Logic and Intelligent Systems. 9, 315-320. https://doi.org/10.5391/IJFIS.2009.9.4.315
    CrossRef
  6. Zhu, Q, Yan, Y, and Xing, Z 2006. Robot path planning based on artificial potential field approach with simulated annealing., Proceedings of the 6th International Conference on Intelligent Systems Design and Applications, Jinan, China, Array, pp.622-627. https://doi.org/10.1109/ISDA.2006.253908
    CrossRef
  7. Yoon, HU, and Lee, DW (2018). Subplanner algorithm to escape from local minima for artificial potential function based robotic path planning. International Journal of Fuzzy Logic and Intelligent Systems. 18, 263-275. https://doi.org/10.5391/IJFIS.2018.18.4.263
    CrossRef
  8. Li, Q, Wang, L, Chen, B, and Zhou, Z 2011. An improved artificial potential field method for solving local minimum problem., Proceedings of 2011 2nd International Conference on Intelligent Control and Information Processing, Harbin, China, Array, pp.420-424. https://doi.org/10.1109/ICICIP.2011.6008278
    CrossRef
  9. Matoui, F, Boussaid, B, and Abdelkrim, MN 2015. Local minimum solution for the potential field method in multiple robot motion planning task., Proceedings of 2015 16th International Conference on Sciences and Techniques of Automatic Control and Computer Engineering (STA), Monastir, Tunisia, Array, pp.452-457. https://doi.org/10.1109/STA.2015.7505223
    CrossRef
  10. Thorpe, C, and Matthies, L 1984. Path relaxation: path planning for a mobile robot., Proceedings of OCEANS Conference, Washington, DC, Array, pp.576-581. https://doi.org/10.1109/OCEANS.1984.1152243
    CrossRef
  11. Warren, CW 1993. Fast path planning using modified A* method., Proceedings IEEE International Conference on Robotics and Automation, Atlanta, GA, Array, pp.662-667. https://doi.org/10.1109/ROBOT.1993.291883
    CrossRef
  12. Duchon, F, Babinec, A, Kajan, M, Beno, P, Florek, M, Fico, T, and Jurisica, L (2014). Path planning with modified a star algorithm for a mobile robot. Procedia Engineering. 96, 59-69. https://doi.org/10.1016/j.proeng.2014.12.098
    CrossRef
  13. Jung, DW (2011). Smooth path generation using hexagonal cell representation. Journal of the Korean Society for Aeronautical & Space Sciences. 39, 1124-1132. https://doi.org/10.5139/JKSAS.2011.39.12.1124
    CrossRef
  14. He, X, and Chen, L 2008. Path planning based on grid-potential fields., Proceedings of 2008 International Conference on Computer Science and Software Engineering, Hubei, China, Array, pp.1114-1116. https://doi.org/10.1109/CSSE.2008.879
    CrossRef
  15. Jeong, SM, Song, TH, Park, JH, and Jeon, JW 2008. The local minimum escape using the grid map., Proceedings of 2008 IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems, Seoul, South Korea, Array, pp.378-383. https://doi.org/10.1109/MFI.2008.4648095
    CrossRef
  16. Jung, H, and Kim, DH (2014). Potential-function-based shape formation in swarm simulation. International Journal of Control, Automation, and Systems. 12, 422-429. https://doi.org/10.1007/s12555-013-0133-6
    CrossRef
Biographies

Jun-Ho Jung has been under M.S. candidate course at kyungnam university, Korea, since 2019.His research interests include mobile robots and intelligent control.

E-mail: jhjeong451@naver.com


Dong-Hun Kim received his B.S., M.S., and Ph.D. degrees from the Department of Electrical Engineering, Hanyang University, Korea, in 1995, 1997, and 2001, respectively. From 2001 to 2003, he was a research associate under several grants in the Department of Electrical and Computer Engineering, Duke University, NC, USA. In 2003, he joined Boston University, MA, USA, as a visiting assistant professor under several grants at the Department of Aerospace and Mechanical Engineering. In 2004, he was engaged in post-doctoral research at the School of Information Science and Technology, the University of Tokyo, Japan. Since 2005, he has been a professor at the Department of Electrical Engineering, Kyungnam University, Korea. His research interests include swarm robotics, mobile robots, decentralized control of autonomous vehicles, intelligent control, and adaptive nonlinear control.

E-mail: dhkim@kyungnam.ac.kr