Previous approaches, such as reactive navigation using the shortest path algorithm,^1-3,37 assume that the location of the final goal determines the direction of motion of the robot. This assumption is based on the robot maintaining its direction toward the final goal. The fundamental guiding principle of reactive navigation is that the robot is virtually attracted to the goal and repelled by obstacles.

Fig. 1(a) shows a typical case of applying the shortest path algorithm to a simple environment. At first, the robot’s trajectory is a straight line between the robot and the goal; the robot then goes around the wall of the obstacle to take the shortest path to the goal. In this case, the shortest path algorithm is highly effective. However, Fig. 1(b) shows how this algorithm can fail when the robot is trapped by an obstacle in trying to follow the shortest path in a complex environment, i.e., when obstacles are encountered in the direction of the straight line between the robot and the goal. This case shows that it is not always effective for the robot to move in the direction of the final goal throughout the driving process. In the G2V algorithm strategy, a new sub-goal is determined using the end-point of the goal guidance vector in the laser measurement sensor (LMS) range. The new sub-goal is created at the location that represents the minimum risk by using obstacle deviation and pattern information in the HCF. A G2V guide is determined, where the starting point of the vector is the current location of the robot, and the end-point of the vector is the location of the sub-goal.

Fig. 1 
Illustration of the shortest path algorithm for (a) A simple environment and (b) A complex environment around the straight path between the robot and the goal

The G2V is used within the obstacle avoidance algorithm to guide the robot in the direction of minimum risk to avoid colliding with obstacles, as shown in Fig. 2. Fig. 2 shows that if the robot uses the shortest path algorithm in such an environment, the robot will fail to drive because of the numerous obstacles in the path of the goal attraction vector. The HCF used to determine the G2V is calculated by considering the location and scale of each obstacle and enables the robot to drive while avoiding nearby obstacles. The hazard cost function ensures that the robot avoids high risk areas, while remaining aligned with the goal. However, the shortest path remains fixed in the direction of the goal attraction vector regardless of the changes in the environment.

Fig. 2 
Schematic of the developed algorithm methodology of the G2V algorithm

An occupancy grid map for the positions of the robot and the obstacles is used in the algorithm. An occupancy grid is a M × N matrix that represents a 2-dimensional space. The cells containing zeros are free space where the robot can move, and the cells containing ones are obstacles into which the robot cannot move. The robot is represented by (x, y)∈R² and the drivable regions and the obstacles are represented as polygons, each of which comprises lists of vertices or edges.²⁶

An obstacle is modelled as a circle using three detection points from a laser measurement system (LMS), as shown in Fig. 3. The LMS obtains information for three points (P_k, Q_k, R_k) that are detected for an obstacle within sensing range. These three points are used to construct a unique circle centered at X_k^c with a radius r_k^circle using the equations in Table 1.²⁵ The robot is treated as a point mass; therefore, a virtual circular obstacle can be created using the radius of the circumscribed circle (r^robot) of the robot. These circular obstacles are filled with ones and recorded in the occupancy grid map.

Fig. 3 
Circular obstacle creation

The G2V G→k* uses the sub-goal (P_k^sgoal) as an end-point and the current robot location (P_k^robot) as a starting point in the grid map, as shown in Eqs. (1), (2) and Fig. 4.

Fig. 4 
Developed G2V algorithm

The continuously changing location of the sub-goal (P_k^sgoal) in an unknown environment is a key feature of the developed algorithm that is determined from the hazard cost function (HCF, S). This function is calculated for each grid cell within sensing range. The sub-goal with the lowest grid cell cost is chosen. The cost function S has three terms, as shown in Eq. (3).

The obstacle function (H_ij) is designed to minimize the risk from the obstacles in an unknown environment and to calculate the obstacle density in each grid cell within sensing range. A grid cell with a high obstacle density results in a high cost and is considered to be a dangerous point. The obstacle density is a function of the distance between each virtual circular obstacle (D_n^obs) and each grid cell (Pijlocal), and the radius of the virtual circular obstacle (r_n^obs) that is nearest to each grid cell, as shown in Eqs. (6) and (7). Crowding many obstacles into a small area results in a high calculated obstacle density that is difficult for the robot to drive through, as shown in Fig. 5. Hijnom is the normalized obstacle function. The parameters ε and η tune the value of this function.

where n = n th obstacle

where M= number of the grid cells within sensing range

where N = total obstacles

Fig. 5 
Hazard cost of an environment containing arbitrary obstacles: Six obstacles (shown as blue circles) were used in a 500 × 500 (cm) grid map. The primary contribution to the HCF potential comes from the interior of the dense obstacles

The goal-oriented function (T_ij) that maintains the orientation of the robot toward the final goal is found by calculating the Euclidean distance between each cell (Pijlocal) and the final goal (P^goal): Tijnom is the normalized goal-oriented function.

The penalty constant (ξ) equals the uncertain area that is ruled out in the local grid map-sensing range of the LMS.

The detectable rear obstacles and the sensing area outside the LMS range in a M × N matrix make up a considerable uncertain area for safe driving. The penalty constant serves as an artificial constraint on the sub-goal selection. The weighting factors (α, β) in the HCF serve to tune the motion of the robot. For instance, a large value of α results in the robot moving in the direction that offers the minimum risk, and an attractive goal corresponds to a large β value. Thus, tuning the weighting factors in the HCF affects robot motion. Fig. 6 shows the effect of varying the weighting factors (α, β) in the HCF. The value of α is increased by using five obstacles in a concentrated region. To avoid a high concentration of obstacles, increasing α creates a G2V in another direction.

Fig. 6 
HCF potential for various weighting factors (α, β)

The fuzzy input is represented by a linguistic fuzzy set with four members {VL, L, H, VH} with the membership function shown in Fig. 7(a) and is derived from simple numerical measures for estimating the pattern formula for the location of the obstacles within sensing range, as shown in Fig. 8. The numerical measures are estimated by calculating the correlation coefficient from Eqs. (12)-(14).²⁷ In robot driving, it is important to determine whether the pattern formed by the obstacles is complex or simple. The center of the obstacle (x_i, y_i) as detected by LMS is considered to be a scatterplot in the 2D plane. The scatterplot can have a linear or nonlinear pattern, as shown in Fig. 9. For instance, when a straight line can be fit through the data points, the obstacle pattern is linear, and the obstacles are distributed regularly making it less dangerous to drive. However, an irregular distribution corresponds to a relatively dangerous distribution of obstacles.

Fig. 7 
Membership functions for (a) Input and (b) Output

Fig. 8 
Estimating the obstacle pattern formula

Fig. 9 
Sign of the correlation coefficient (C_k^obs)

A correlation coefficient can be used to describe each of the variables x_i and y_i individually using a descriptive measure such as the standard deviation. The correlation coefficient is denoted by C_k^obs and is defined in Eq. (12). The quantities S_k^x and S_k^y are the standard deviations for the variables x_i and y_i, respectively, and S_k^xy is the covariance between x_i and y_i is defined in Eqs. (13) and (14). The value of the correlation coefficient (C_k^obs) ranges between -1 and 1: when C_k^obs is close to 1 or -1, a stronger pattern indicates a higher linearity in the data. In contrast, when C_k^obs is close to 0, the data points are scattered across all four areas and is there is no obvious pattern, as shown in Fig. 9.

The weighting factor α of the HCF is represented by a linguistic fuzzy set with four members {LS, M, S, HS}, with the membership function shown in Fig. 7(b), and is derived from the sets of rules given below.

• If C_k^obs is VL, THEN α is HS.
• If C_k^obs is L, THEN α is S.
• If C_k^obs is H, THEN α is M.
• If C_k^obs is VH, THEN α is L

For instance, the robot detects obstacles using the LMS, records the information on the circular obstacles in the grid map and calculates C_k^obs to estimate the pattern formula of the obstacles. If C_k^obs is VH, the pattern is complex and dangerous; thus, α is increased to minimize the risk, and HS is selected.

However, if few obstacles (N_k^obs) are within sensing range, it is not meaningful to calculate C_k^obs. In this case, it is necessary to use the following rules. Using the rules given above, α always has a fixed small value for a low obstacle density, which creates a G2V in a direction that rapidly drives the robot toward the final goal.

• If N_k^obs is ZERO or < n, THEN α is LS.
• If N_k^obs is ≥ n, THEN α is estimated by C_k^obs.

The performance of reactive navigation algorithms, such as VFH, etc., can be enhanced by applying the G2V algorithm for obstacle avoidance. As previously mentioned, the G2V algorithm enables the robot to determine the optimal direction while avoiding obstacles, which can increase the success probability of achieving the final goal. Thus, the performance of the reactive navigation algorithm using the shortest path method is significantly improved by combining it with the G2V algorithm: in this method, the robot moves in the closest direction to the final goal in an open area (i.e., where there are no obstacles).

To verify the G2V algorithm, we combine the G2V algorithm with the virtual tangential vector (VTV) algorithm²⁵ in a simulation. The VTV algorithm is a reactive navigation algorithm, which uses the shortest path method with obstacle avoidance. The VTV drives a robot along the tangential direction to a virtual circular obstacle generated in real time. The weighted resultant vector of all the VTVs, the so-called weighted VTV (WVTV), which is defined for multiple obstacles. The WVTV is incorporated into a multi-objective optimization framework: the slope of the VTV can be easily obtained and the final VTV direction toward the goal is determined.

The modified vector field histogram (MVFH) algorithm decomposes the set of 540 directions from the LMS into an obstacle-containing area and an obstacle-free or open area by determining whether the normalized distance between the robot and an obstacle is smaller than a prescribed threshold or not. The middle vector in each open area is then obtained. The vector which makes the smallest angle with the goal attraction vector is selected among all the middle vectors.

The simulation was performed using a MATLAB program, and an LMS simulator was used with a detection range of 0.1 to 10 m, 270°, and an angular resolution of 0.5°. The LMS was used to measure the distance and the angle between the robot and an obstacle. The robot model was applied to an Ackerman vehicle with front steering with a robot of dimensions 2 (W) × 3 (L) m. The constraints on the robot model in the simulation were a maximum allowable steering angle of 30° and a robot step size of 1.5 m. A global positioning system (GPS) and an inertia measurement unit (IMU) were also used. Fig. 10 is a schematic of the simulation model, and Fig. 11 shows an example of the robot motion using the G2V algorithm.

Fig. 10 
Schematic of simulation model

Fig. 11 
Illustration of robot motion by a MATLAB simulation

In this section, the robot motion is illustrated using several simulations that were conducted for an environment similar to that of related studies. Fig. 12 shows that the G2V that was created for a simple environment of obstacles.

Fig. 12 
G2V creation in a simple environment of obstacles: starting point (Green circle), final goal (Green cross), G2V end-point (Blue cross), sensing range (Large red circle), and robot motion (Small red circle); weighting factors: α = 0.6, β = 0.4 (Fixed)

The end-point (Which is Shown as a Blue Cross) of the G2V was located to the right side of the obstacle in the sensing range (Which is Shown as a Non-Continuous Red Circle). The end-point was not close to the obstacle and was too far from robot, as shown in Figs. 12(a)-12(c). When the robot was on the right side of the obstacle, as shown in Figs. 12(d)-12(f), the end-point of the G2V was in the direction of the shortest distance to the final goal because there were no obstacles.

Fig. 13 shows the advantages that the developed algorithm offers over the VTV algorithm. When the VTV algorithm was used by itself, the robot moved along the A-B-C path between the obstacles to reach the goal in the shortest distance, as shown in Fig. 13(a). In the C-D path, the robot was trapped by three obstacles, which was similar to being trapped in a local minimum, because the robot moved the shortest distance in the diagonal direction to reach the goal.

Fig. 13 
G2V results: (a) Using only the VTV algorithm and (b) Using the proposed algorithm with fuzzy control of the weighting factors

However, using the developed algorithm enabled the robot to avoid the obstacle traps on the C-D path, as shown in Fig. 13(b). The area to the left of the sensing range of the robot had a high HCF cost; therefore, the obstacle avoidance mechanism caused the robot to follow a detour-like path away from the obstacles. Thus, the robot moved along the curved path A-B-C-D-E. Note that the robot turned around the points B, C and D.

Fig. 14 shows the simulation results that were obtained using fuzzy reactive control for the weighting factors in a complex environment made by many circle obstacles. The robot was initially surrounded by scattered obstacles (A-B), resulting in high values for the HCF cost and the weighting factor α. When the robot steered to the left, α changed progressively to a low value (HS-LS, 0.85-0.60) as the obstacle pattern became simple relative to the robot coordinates. The complex obstacle pattern on the B-C path resulted in a fuzzy output of HS for α again. Then, α decreased the fuzzy output from HS to LS progressively toward the final destination, and the robot successfully reached the destination.

Fig. 14 
Simulation results for fuzzy reactive control in a complex environment: (a) Robot motion (Red: G2V algorithm, Green: VFH algorithm), (b) The variations in the weighting factor (α) with each step, (c) Coordinates of the G2V end-point (Blue: x, Green: y) and (d) Variation in the correlation coefficient (C_k^obs) with each step; the coordinate axes were set at an artificial wall

This result shows that the proposed algorithm offered the advantage that the robot responded effectively in many obstacles. For instance, the robot’s motion along the A-B-C path showed that a complex environment of obstacles could be avoided to minimize risk. The robot’s motion along the C-D-E paths showed that the robot moved efficiently through a short distance toward the goal. However, when the VFH algorithm was used by itself, the robot was trapped by dense obstacle as shown in Fig. 13(a). Finally, 500 times of the simulation results, a success ratio of the proposed algorithm is higher than the VFH and A* algorithm, as shown in Table 2. The position of obstacles was randomly changed for each simulation. VHF algorithm use only bits of the given information to determine a guidance direction by using a histogram of the measured obstacle density distribution. A* algorithm does not consider the steering motion and safety factors of the robot. Therefore, the success rate of the VHF and A* algorithm is lower than that of the G2V algorithm.

We also tested the developed algorithm in a narrow alley and a U-Shaped environment. Fig. 15(a) shows that the robot moved into the middle of the narrow alley relatively safely. The shortest distance algorithm would have caused the robot to move along a wall edge in the direction of the closest goal. Thus, the developed algorithm performed better than the shortest distance algorithm for this environment.

Fig. 15 
Simulation results for a narrow alley and a U-shaped environment: (a) A narrow alley, (b) The U-shaped region was smaller than the sensing range (Entrance width: 10 m), (c) The U-shaped region was larger than the sensing range (Entrance width: 10 m, starting from the outer edge) and (d) The U-shaped region was larger than the sensing range (Starting from the inner edge), Sensing range: 15 m

From Figs. 15(b) to 15(d) show the simulation results for the U-Shaped obstacle. Fig. 15(b) shows that the obstacle was smaller than the sensing range (15 m), such that the robot detoured to the outside of the U-Shaped obstacle, because the inside of the U-Shaped obstacle represented a high HCF cost.

Fig. 15(c) shows the robot motion for a U-Shaped obstacle that was larger than the sensing range. The robot initially moved into the U-Shaped region, moved back when the obstacle was detected, and detoured safely around the obstacle.

Fig. 15(d) shows the simulation result when the robot started from the inner side of the obstacle. The robot initially moved toward the open area of the U-Shaped region and then moved again toward the inside of the U-Shaped region, because the obstacle was not detected when the robot escaped from the U-Shaped region. The robot then escaped from the U-Shaped region. In this case, the robot’s behavior was inefficient.