International Journal of Fuzzy Logic and Intelligent Systems 2020; 20(1): 26-34
Published online March 25, 2020
https://doi.org/10.5391/IJFIS.2020.20.1.26
© The 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)
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 noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
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
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 [4–6]. 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 [7–9]. 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.
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
where
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
where
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
where
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.
In the proposed grid-based potential method, the potential parameters
Thus, the total potential function can be defined as follows:
where
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
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 (
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 (
where
The distance (
As shown in
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:
The position of the repulsive potential function in
The role of the new repulsive potential in
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
Figure 4 shows the values of
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:
where
The repulsive potential generated according to
Figure 5 shows that
Thus, the robot can avoid obstacles without approaching them by applying variable potential parameters to the cells recognized using sensors.
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
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.
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.
No potential conflict of interest relevant to this article was reported.
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).
Magnitude and range of the repulsive field: (a)
Local minimum with two parallel adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.
Local minimum with three U-shaped adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.
Local minimum with five U-shaped adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.
E-mail: jhjeong451@naver.com
E-mail: dhkim@kyungnam.ac.kr
International Journal of Fuzzy Logic and Intelligent Systems 2020; 20(1): 26-34
Published online March 25, 2020 https://doi.org/10.5391/IJFIS.2020.20.1.26
Copyright © The 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)
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 noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
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
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 [4–6]. 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 [7–9]. 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.
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
where
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
where
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
where
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.
In the proposed grid-based potential method, the potential parameters
Thus, the total potential function can be defined as follows:
where
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
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 (
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 (
where
The distance (
As shown in
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:
The position of the repulsive potential function in
The role of the new repulsive potential in
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
Figure 4 shows the values of
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:
where
The repulsive potential generated according to
Figure 5 shows that
Thus, the robot can avoid obstacles without approaching them by applying variable potential parameters to the cells recognized using sensors.
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
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.
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.
No potential conflict of interest relevant to this article was reported.
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).
Grid method.
Robot view of obstacles in the direction of a goal point.
Magnitude and range of the repulsive field: (a)
Weight change of the repulsive potential.
New repulsive field.
Local minimum with two parallel adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.
Local minimum with three U-shaped adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.
Local minimum with five U-shaped adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.
Jinwan Park
International Journal of Fuzzy Logic and Intelligent Systems 2021; 21(4): 378-390 https://doi.org/10.5391/IJFIS.2021.21.4.378Young-In Choi, Jae-Hoon Cho, and Yong-Tae Kim
International Journal of Fuzzy Logic and Intelligent Systems 2020; 20(2): 96-104 https://doi.org/10.5391/IJFIS.2020.20.2.96Han Ul Yoon, and Dong-Wook Lee
International Journal of Fuzzy Logic and Intelligent Systems 2018; 18(4): 263-275 https://doi.org/10.5391/IJFIS.2018.18.4.263Grid method.
|@|~(^,^)~|@|Robot view of obstacles in the direction of a goal point.
|@|~(^,^)~|@|Magnitude and range of the repulsive field: (a)
Weight change of the repulsive potential.
|@|~(^,^)~|@|New repulsive field.
|@|~(^,^)~|@|Local minimum with two parallel adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.
|@|~(^,^)~|@|Local minimum with three U-shaped adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.
|@|~(^,^)~|@|Local minimum with five U-shaped adjacent cells. Planned path under (a) the conventional potential function method and (b) the proposed potential function method.