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
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.
Kinematics of the mobile robot and environment perception
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:
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.
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:
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:
where α is the target angle and θ is the robot direction angle.
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.
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.
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.
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:
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.
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:
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:
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:
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.
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.
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.