Improving mobile robot navigation by combining fuzzy reasoning and virtual obstacle algorithm

Abstract

In this paper, a new approach is developed for contributing in solving the problem of autonomous mobile robot navigation in unknown environments. This approach is built upon combining fuzzy reasoning and virtual obstacle algorithm to overcome the local minimum problem encountered in presence of concave obstacles by efficiently coordinating priorities between multiple reactive behaviors such as goal reaching, obstacles avoiding, wall following and emergency situations preventing. To achieve this objective, an array of ultrasonic sensors is mounted on the mobile robot providing the distance information between the robot and obstacles. This distance information is used by the virtual obstacle algorithm to calculate some sub-goals for determining the good motion direction to avoid robot trap in local region (emergency situation), since the fuzzy reasoning is used for behavior control of the mobile robot. All the reactive behaviors are mapped into one universe of discourse to guarantee a smooth transition between them especially when the robot moves through closely spaced obstacles. In this manner, the robot oscillations are significantly reduced. Some simulation results are presented to show the ability of the developed approach in performing successfully in complex and uncertain environments.

Keywords

Fuzzy reasoning behavior control emergency situation virtual obstacle algorithm local minimum recovery

1 Introduction

Autonomous mobile robot navigation in unknown environments is one of the most important problems in the field of robotics. Researchers have developed various methods by which mobile robots can complete their tasks without colliding with obstacles. In particular, methods using potential fields, genetic algorithms, neural networks, and Q-learning techniques have given diverse and useful results in known and unknown environments [14 –16]. The potential field method and its variants for use in unknown environments have been studied extensively in recent decades [6, 13]. The basic idea behind this method is to fill the robot environment with a virtual potential field in which the robot is attracted to the target position and is repulsive away from obstacles. Although, this method is fast and efficient, it has the following drawbacks and limitations as discussed in [20]:

Trap situations due to local minimums.

Oscillations in narrow passages and through closely spaced obstacles.

Aiming at the problems above, efficient improvements to the potential field method have been proposed. A. Masoud [1] suggested a non linear conditioning force called nonlinear anisotropic dampening force (NADF) for solving the narrow corridor problem in potential field-guided autonomous robots. Using this method, the problem of the oscillations is minimized and significant improvements in the speed of response and quality of the robot’s trajectory are achieved. Sun Ling et al. [18] proposed a virtual targets method for mobile robot real-time path planning using fuzzy control to generate the proper virtual targets and the virtual force field method to calculate the attractive forces generated by the virtual targets. To overcome the local minimum problem which this method suffers from, the authors proposed a simple algorithm which consists in adding a random distance and angle to the virtual target position. This algorithm works efficiently in the case when the robot is trapped in an equilibrium point, but it fails in presence of deep concave obstacles and the robot gets into an infinite loop. In this situation, adding a random distance and angle to the virtual targets is not effective; it could help the robot to get out of this situation but after having traveled several loops. Many other approaches have also been proposed to overcome these problems. Among these approaches, we find the virtual obstacle concept which is activated when the robot is taken in local minimums [9], the iterative potential field method which is built upon new potential functions that help to find the optimum path [5], and the dynamic collision map for collision-free motion planning in dynamic environments [7].

Hybrid intelligent systems including architectures based on fuzzy logic concepts have been proven to be good tools for real-time mobile robots navigation due to their capabilities in handling many real world complex problems involving imprecision, uncertainty and vagueness [2–4 , 19].

In this paper, a new approach based on a combination of fuzzy systems and a virtual obstacle algorithm is proposed, the motivation for the development of this approach is to present a simple, fast and robust method for mobile robot navigation in all types of environments. The proposed method is built upon a virtual obstacle algorithm for the construction of the emergency situations preventing behavior and fuzzy reasoning for efficiently coordinating priorities between the four following reactive behaviors: target reaching, obstacles avoiding, wall following and emergency situations preventing. Using this method the mobile robot can recover from the local minimum problem in real time. As the robot is guided towards the target based on fuzzy control, it maneuvers to avoid obstacles on its immediate path, and when it approaches or encounters concave obstacles where a local minimum is most likely to be occur, the emergency situations preventing behavior is activated and the virtual obstacle algorithm is invoked to compute intermediate points to be used as temporary path targets. Once the robot is outside of the local minimum, it continues its task by heading towards the closest path target under fuzzy behavior control using only the information provided by the ultrasonic sensors. The rest of this paper is organized as follows: In Section 2, the considered two–wheeled mobile robot is described. In Section 3, the fuzzy logic based reactive behaviors controller structure is presented and the principle of the proposed method is detailed. In Section 4, some simulation results and comparisons are presented to evaluate the effectiveness of the developed approach. Finally, some conclusions are made in Section 5.

2 Kinematics of the mobile robot and environment perception

2.1 Kinematic model

The schematic diagram of the considered two-wheeled mobile robot is described in Fig. 1, where (x_w, y_w) are the world coordinates and (x_m, y_m) are the local coordinates which are fixed to the robot center P. R is the radius of the wheel and L is the displacement from the center of the robot to the center of the wheel. The set (x, y) represents the position of the center P and θ is the orientation angle of the robot.

The kinematic model of the proposed differential mobile robot is given by the following equations: $[\begin{matrix} \dot{x} \\ \dot{y} \\ \dot{θ} \end{matrix}] = [\begin{matrix} cos θ & 0 \\ sin θ & 0 \\ 0 & 1 \end{matrix}] [\begin{matrix} v \\ w \end{matrix}]$ (1) $v = \frac{R}{2} (w_{r} + w_{l})$ (2) $w = \frac{R}{L} (w_{r} - w_{l})$ (3)

where v and w are the linear and rotational velocities of the mobile robot, w_r and w_l are the angular velocities of its right and left wheels.

2.2 Robot environment perception

This paper considers the case where the environment is totally unknown; an acquisition process is needed to acquire the information about the robot environment. For this purpose, seven ultrasonic sensors are mounted on the mobile robot as shown in Fig. 1. The sonar reflection from a sensor i represents the distance di, measured by the sensor i, between the robot and obstacles in the real world. These ultrasonic sensors are divided into three groups to detect obstacles to the left (sensor i = 1, 2, 3), front (sensor i = 3, 4, 5), and right locations (sensor i = 5, 6, 7).

In the proposed method, two types of variables are needed: n_L, n_R and n_F which are the numbers of ultrasonic sensors that sense an obstacle and belong to the same group (for the example shown in Fig. 1: n_L = 2, n_R = 0, and n_F = 1). The second type of variables is the distances between the robot and obstacles, these variables are defined as follows: $d_{L} = Mn {di} i = 1, \dots, 3$ (4) $d_{F} = Mn {di} i = 3, \dots, 5$ (5) $d_{R} = Mn {di} i = 5, \dots, 7$ (6)

where the values of d_L, d_F and d_R express the minimum distances between the robot and obstacles to the left, front and right locations, respectively. The variable φ_t represents the heading angle of the robot required to facing the target. It is given by the following equation: $φ_{t} = α - θ$ (7)

where α is the target angle and θ is the robot direction angle.

3 Fuzzy logic based behavior control architecture

In order to reach a specified target in a complex environment, the mobile robot at least needs the following reactive behaviors: target reaching (TR), obstacles avoiding (OA), wall following (WF), and emergency situations preventing (ESP). Figure 2 illustrates some examples of different behaviors situations.

In the proposed control strategy, the four reactive behaviors are formulated by fuzzy sets in which the fuzzy rules for all the behaviors are integrated in one rule base. In this manner the coordination between the different behaviors can thus be easily performed using only the data acquired from the robot ultrasonic sensors. Figure 3 illustrates the diagram of the proposed controller architecture which is built upon two fuzzy systems, one for reactive behaviors coordination and the other for motion control of the mobile robot. The emergency situations preventing behavior is built upon a virtual obstacle approach to recover from local minimum problems and improve the performances of the controller in presence of concave obstacles. The natural behavior in autonomous mobile robot navigation is to guide the robot towards the target. On its immediate path, the robot tries to avoid all obstacles and when it approaches or encounters concave obstacles where a local minimum is most likely to be occur, the emergency situations preventing behavior is activated and the virtual obstacle algorithm is invoked to compute the intermediate points to be used as temporary path targets. Once the robot is outside the local minimum, it continues its task by heading towards the closest path target under fuzzy behavior control using only the information provided by the sensors.

3.1 Fuzzy behavior controller design

A key issue of behavior based control is how to efficiently coordinate priorities between different reactive behaviors to achieve good navigation performances. In this way, in the proposed control strategy, all reactive behaviors are mapped into membership functions in one normalized universe of discourse. The fuzzy behavior controller has one single output which is the normalized value of behavior B_v and four input variables which are respectively the numbers of ultrasonic sensors that sense an obstacle to the left n_L, to the right n_R, in front n_F and the heading angle φ_t (see Fig. 1). Their membership functions are shown in Fig. 4. A part from the fuzzy rule base used in the proposed controller is shown in Table 1. The max-prod inference algorithm is used to evaluate the rules and the centre average method is used for deffuzification.

3.2 Fuzzy motion controller design

Fuzzy logic based control is applied to realize the mobile robot motion in an unknown environment with obstacles. As described in Section 2.1, the mobile robot has two independent driven wheels and seven ultrasonic sensors used to detect obstacles in the front, to the right and to the left of the robot. According to the distance information provided by the sensors and the current and target positions of the robot (see Fig. 3), the virtual obstacle algorithm calculates the values of n_L, n_F, n_R and φ_t (see Section 2.2) and transmits them to the fuzzy behavior controller which is responsible of deciding which behavior is to be executed. In a parallel way, the virtual obstacle algorithm calculates the values of d_it, φ_it and d_F and transmits them to the fuzzy motion controller. The variables d_it and φ_it represent the distance and angle between the current position of the robot and the intermediate target in the case when the E.S.P behavior is activated and between the current position of the robot and the final target otherwise. The variable d_F represents the minimum distance between the robot and obstacles in front location; it is used by the fuzzy motion controller to maximize the navigationspeed of the robot. So, the fuzzy motion controller receives in its inputs the normalized value of the behavior B_v, the intermediate distance d_it, the intermediate heading angle φ_it and the minimum distance in front d_F. The outputs of the motion controller are the two control signals of the robot’s left and right wheels velocities, w_l and w_r respectively. The centre of area method is used in this block for the deffuzification of the outputs. The membership functions of the inputs and outputs are shown in Fig. 5, and a part from the If-Then rules used to define the fuzzy algorithm of the inference engine of this stage is listed in Table 2.

3.3 Virtual obstacle algorithm design

In this section, we describe in detail a modified form of the virtual obstacle concept developed first in [9]. According to the information of the distance acquired from the ultrasonic sensors, the fuzzy behavior controller activates the emergency situations preventing behavior which invokes the virtual obstacle algorithm to calculate an intermediate target outside the concave obstacle. An example of emergency situation is illustrated in Fig. 6, where the values of the four input variables are respectively: n_L = 3, n_R = 3, n_F = 3, and φ_t = 6°. Using the following fuzzy rule:

“If n_L is B (Big) and n_R is B and n_F is B and φ_t is Z then B_v is ESP (Emergency Situation Preventing).”

The algorithm used for calculating the intermediate target is explained as follows:

- Step 1: Two line segments which are the nearest to the mobile robot detected by the ultrasonic sensors are constructed with ends AB and CD. The points A and C are the two first chronological points sensed simultaneously by the left and right sensors at time t = t1 (see Fig. 6). If there is continuity in sensing points of obstacles on both left and right sides, the robot is either inside a corridor or a concave obstacle. Then, if the distance between the two points P_L and P_R is lesser than three times the diameter of the robot. The robot is being trapped in a concave obstacle. At this moment (t = t₂), the Fuzzy Behavior controller declares an ESP behavior and the points B and D are chosen as the two last chronological points sensed by the left and right sensors respectively.

- Step 2: Midpoints E, and F of the following line segments BD and AC are selected. Then, points E, F and G are connected together with the length of the segment FG is one time the diameter of the robot. The robot must navigate out of the concave obstacle and go to free point G to avoid local minimum. During this time, only the ESP behavior is activated.

- Step 3: Once the robot reaches the point G, a virtual obstacle is constructed around the ends ABDC to prevent the robot from being taken in the same emergency situation for another time. After reaching the point G, other behaviors can be activated according to the information acquired from the sensors allowing the robot to continue its task towards the final target.

4 Simulation results

In this section, we test and examine the theory developed in the preceding sections. We start by comparing the performances of the fuzzy-virtual targets method proposed in [18] and the fuzzy based behavior controller proposed in this paper by using two different types of environment containing real trap situations. Then, we evaluate the improvements obtained by the integration of the virtual obstacles algorithm with the fuzzy based behavior controller.

4.1 Comparison criterions

In order to objectively measure the performance of the proposed method under various conditions, we consider the following three parameters:

Total course length L_t: It represents the total distance traveled by the robot between the start and target positions. It is given by the followingequation: $L_{t} = \sum_{k = 0}^{N} v_{k} τ$ (8)

Total course duration D_c: It represents the total time taken by the robot to travel between the start and the target positions. It is given by the following equation: $D_{c} = N τ$ (9)

Rate of oscillations R_o: In fact, the robot oscillates when it changes the direction of the navigation. So, monitoring the instantaneous rotational velocity (w_k) constitutes an important criterion to evaluate the rate of oscillations which is given by the following equation: $R_{o} = \frac{1}{N} \sqrt{\sum_{k = 0}^{N} w_{k}^{2}}$ (10)

where v_k and w_k (Equations (2) and (3)) represents the linear and rotational velocities of the mobile robot at the moment k, τ represents the duration of the calculation step and N is the number of calculation steps between the starting moment of the robot and the moment of its arrival to the target position.

4.2 Results and comparisons

To show the effectiveness of the proposed approach, a series of simulations have been conducted by using arbitrarily constructed environments including obstacles. The position of all the obstacles is unknown; the robot is aware of its start and final positions only. All of simulations have been done in MATLAB/SIMULINK environment using the robot’s kinematic model given by Equation (1). The numerical value of the duration of the calculation step τ is 0.01 s in all the simulations. The values of L_t, D_c, R_o and N are variable and depend on the length and the form of the robot’s trajectory. Their numerical values are given in Table 3.

We start the simulation by using the fuzzy-virtual targets method proposed in [18]. The graphs of Fig. 7 show the navigation trajectories and the control signals of the robot’s left and right wheels. In Fig. 7(a), the robotsucceeds in avoiding the obstacles and reaching the final target. But in Fig. 7(b), where a deep concave obstacle has been introduced in the workspace, the robot is easily trapped in a local minimum; it gets in an infinite loop and couldn’t reach the final target. Another important disadvantage of this method is the necessity of accelerating and decelerating the robot (see Fig. 7(c) and (d)) to reach the high number of virtual targets which are often very close to the robot. This phenomenon decreases the navigation speed and increases the rate of oscillations of the robot.

By using the proposed fuzzy behavior controller combined with the virtual obstacle algorithm, we succeed in improving significantly the quality of the navigation trajectories and the control signals of the robot’s left and right wheels. The graphs of Fig. 8 show clearly the advantage provided by this combination. Indeed, when the robot is being trapped in a local minimum, the ESP behavior is activated and the virtual obstacle algorithm is invoked to calculate the intermediate target (point G in Fig. 8(b)) to which the robot should move, then a virtual obstacle is constructed to prevent the robot from being taken in the same local minimum another time. In this manner, the robot can easily leave the emergency situation and continue its task towards the final target.

To demonstrate more the capabilities of the proposed combined method, a more complicated environment has been selected, it is similar to the one used in [18]. We start the simulation by using the fuzzy-virtual targets method. In Fig. 9(a), the robot succeeds in avoiding the obstacles and reaching the final target. But in Fig. 9(b), where the positions of the obstacles OBS1, OBS2 and OBS3 have been arranged to create a deep trap situation, the robot is easily trapped in a local minimum. Adding a random distance and angle to the virtual target, as given in [18], to get the robot out of this situation is not efficient and the robot runs in an infinite loop and couldn’t reach the final target. By using the proposed combined method, a smooth navigation is obtained which is clearly illustrated by the graphs of Fig. 10. In Fig. 10(b), the robot succeeds in getting out of the deep trap situation and reaching the final target in minimum time and oscillations, which proves the effectiveness of the proposed method even in very complicated environments.

Finally, by comparing the two methods, each one is taken under its best conditions; we can conclude that the proposed combined approach improves the performances of navigation on several levels: the rate of oscillations and length of the trajectory are minimal. The duration of the course is minimal and proportional to the distance between the start and target positions (see Table 3). The integration of the virtual obstacle algorithm contributes to prevent the robot from being trapped in local minimums created by concave obstacles. The fuzzy-virtual target method has two main disadvantages; the first one is its vulnerability to local minimums problem especially in presence of deep concave obstacles where the robot gets into an infinite loop and couldn’t reach the final target. The second one is the phenomenon of the acceleration and deceleration in the control signals due to the high number of virtual targets that the robot should reach. This phenomenon increases the rate of oscillations and decreases the speed of navigation of the robot.

5 Conclusion

In this paper, we have contributed in solving the problem of autonomous mobile robot navigation in unknown environments by combining fuzzy reasoning and virtual obstacle algorithm for the following points: First, solving the problem of local minimum (trap situations) by integrating the virtual obstacle algorithm which is invoked every time there is an emergency situation to calculate some sub-goals for determining a collision free path that the robot should follow to reach its destination without been taken in local minimums. Second, minimizing the rate of oscillations when the robot moves near the walls and obstacles by efficiently coordinating priorities between the four reactive behaviors. In this manner, a smooth transition between the different behaviors is guaranteed and the quality of the robots trajectory is highly improved.

A comparison between the fuzzy-virtual targets method and the proposed combined method has been conducted to highlight the difference between the two methods especially in presence of deep concave obstacles.

We have synthesized in this paper a complete method for the improvement of the navigation performances in unknown and complex environments. The limitations of the classical methods, specifically the problem of oscillations and that of the local minimum have been minimized and in some cases eliminated.

References

Ahmed Masoud

, Solving the narrow corridor problem in potential field-guided autonomous robots, Proc of the IEEE, International Conf on Robotics and Automation, Barcelona, Spain, 2005, pp. 2909–2914.

Pandey

and Parhi

D.R.

, Matlab simulation for mobile robot navigation with hurdles in cluttered Environment using minimum rule based fuzzy logic controller, 2nd International Conf on Innovations in Automation and Mechatronics Engineering, Procedia Technology, Elsevier 14 (2014), 28–34.

Mamdani

E.H.

and Assilian

, Application of fuzzy algorithms for control of simple dynamic plant, Proc of the Institute of Electrical Engineers 1974, pp. 1585–1588.

Abdessemed

, Benmahammed

and Monacelli

, A fuzzy-based reactive controller for a non-holonomic mobile robot, Robotics and Autonomous Systems, Elsevier 47 (2004), 31–46.

S.S.

and Cui

Y.J.

, New potential functions for mobile robot path planning, IEEE Trans on Robotics and Automation 16(5) (2000), 615–620.

Mbebe

J.B.

, Huang

and Wang

, Fuzzy motion planning among dynamic obstacles using artificial potential fields for robot manipulators, Robotics and Autonomous Systems,Elsevier 32 (2000), 61–72.

Cho

K.B.

and Cho

S.Y.

, The concept of collision-free motion planning using a dynamic collision map, International Journal of Advanced Robotic Systems 145(11) (2014), 1–9.

Zadeh

L.A.

, Outline of a new approach to the analysis of complex systems and decision process, IEEE Trans on Systems, Man and Cybernetics 3 (1973), 28–44.

Chengquing

, Ang

M.H.

Jr , Krishnan

and Ser Yong

, Virtual obstacle concept for local-minimum-recovery in potential- field based navigation, Proc of the IEEE, International Conf on Robotics and Automation, San Francisco, CA, 2000, pp. 983–988.

10.

Ting

, Macnab

C.J.B.

and Magierowski

, Reactive robot navigation utilizing nonlinear control, International Journal of Advanced Robotic Systems 100(11) (2014), 1–10.

11.

Hamzah

M.I.

and Abdalla

T.Y.

, Mobile robot navigation using wavelet network and fuzzy logic, International Journal of Computer Applications 79(10) (2013), 4–10.

12.

Sugeno

and Nishida

, Fuzzy control of a model car. Fuzzy Sets and Systems, Elsevier, North Holland, 1985, pp. 103–113.

13.

Tsourveloudis

N.C.

, Valavanis

K.P.

and Hebert

, Autonomous vehicle navigation utilizing electrostatic potential field and fuzzy logic, IEEE Trans on Robotics and Automation 17(4) (2001), 490–497.

14.

Daei

, Shirazi

H.M.

, Askari

and Ghanavati

, Service robot navigation based on Q-learning and fuzzy logic, International Journal of Robots, Education and Arts 1(2) (2011), 1–9.

15.

Khatib

, Real-time obstacle avoidance for manipulators and mobile robots, The International Journal of Robotics Research 5(1) (1986), 90–98.

16.

Obe

and Dumitrache

, Adaptive neuro-fuzzy controller with genetic training for mobile robot control, International Journal of computers, Communications and Control 7(1) (2012), 135–146.

17.

Carelli

and Freire

E.O.

, Corridor navigation and wall-following stable control for sonar-based mobile robots, Robotics and Autonomous Systems, Elsevier 45 (2003), 235–247.

18.

Lining

, Rui

, Weidong

and Zhijiang

, Mobile robot real-time path planning based on virtual targets method, pp. , Proc of the IEEE, Third International Conf on Measuring Technology and Mechatronics Automation (2011), 568–572.

19.

Munaf

and Al-Din

, Decomposed fuzzy controller for reactive mobile robot navigation, International Journal of Soft Computing and Engineering 2(4) (2012), 140–149.

20.

Koren

and Borenstein

, Potential field methods and their inherent limitations for mobile robot navigation, Sacramento,California, Proc of the IEEE, Conf of Robotics and Automation, 1991, pp. 1394–1404.