A Fuzzy Obstacle Avoidance Controller Using a Lookup-Table Sharing Method and Its Applications for Mobile Robots

Abstract

A Lookup-Table (LUT) based design enhances the processing speed of a fuzzy obstacle avoidance controller by reducing the operation time. Also, a LUT sharing method provides efficient ways of reducing the LUT memory size. In order to share the LUT which is used for a fuzzy obstacle avoidance controller, an idea of using a basis function is developed. As applications of the shared LUT-based fuzzy controller, a laser-sensor-based fuzzy controller and an ultrasonic-sensor-based fuzzy controller are introduced in this paper. This paper suggests a LUT sharing method that reduces the LUT buffer size without a significant degradation of the performance. The LUT sharing method makes the buffer size independent of the fuzzy system's complexity. A simulation using MSRDS (Microsoft Robotics Developer Studio) is used to evaluate the proposed method. To investigate the performance of the controller, experiments are carried out using a Pioneer P3-DX with LabVIEW as an integration tool. Although the simulation and experiments show little difference between the fully valued LUT-based method and the LUT sharing method in terms of the operation time, the LUT sharing method reduces almost 95% of the full-valued LUT-based buffer size.

1. Introduction

Autonomous navigation algorithms are applied to various applications for mobile robots to drive toward their target position without a remote control program. In the mapping step of an autonomous navigation application, the robot acquires the location and contour information of obstacles from sensors and updates its navigation map. A navigation path from the current position to the target position on the map is determined by the updated map data. If there are no changes in the map during the robot navigation process, obstacle avoidance is not necessary because a well-defined navigation path will lead the robot to the target position safely. Even in the event that unexpected obstacles suddenly appear on the navigation path, the robot is required to perform obstacle avoidance in order to navigate the planned path without colliding with these types of obstacles. To escape the unexpected obstacles and continue toward the target position under real-time navigation, the robot should determine its steering direction and velocity instantly. This paper is focused on performance improvement and implemental optimization for a fast real-time obstacle avoidance system of robot navigation.

There are several algorithms pertaining to robot obstacle avoidance, including potential field algorithms [1], vector field histogram algorithms [2], and fuzzy controller algorithms [3]. The fundamentals of fuzzy controller methods were presented by Wang [4], Palm [5], Passino [6], Aguirre [7], and others [8, 9]. As a result of these papers, fuzzy controller methods have more advantages in real-time applications because they provide simpler and more intuitive methods of robot obstacle avoidance. This is why we chose fuzzy controller methods for obstacle avoidance here. Mbede [10] proposed a neuro-fuzzy motion controller, and Lilly [11] presented a P/N fuzzy obstacle avoidance controller. Lilly's work provided a more intuitive method for robot obstacle avoidance through its use of negative fuzzy rules to eliminate redundant fuzzy rules. Kiendl [12] and Branson [13] also presented methods of utilizing negative rules in fuzzy systems. The fuzzy controller in this paper is based on the P/N rule fuzzy controller method proposed in Lilly's paper [11]. We verified the performance of the previous P/N rule fuzzy controller method using a robotics simulator in MSRDS (Microsoft Robotics Development Studio) 2008 [14]. We also devised an improved algorithm based on the previous P/N rule fuzzy controllers, verified them in a simulator, and experimented in a real environment.

In Section 2, the fundamentals of the P/N rule fuzzy controller and the full LUT-based design of the P/N fuzzy controller are introduced. The proposed LUT sharing method for the controller is described in Section 3. Section 4 and Section 5 present the laser range-finder-based 50-rule P/N fuzzy controller and the ultrasonic-sensor-based 18-rule P/N fuzzy controller, respectively. Simulation and experimentation results are shown in Section 6. Finally, concluding remarks are summarized in Section 7.

2. A Positive/Negative rule fuzzy controller and its full-LUT-based design

2.1 A Positive/Negative rule fuzzy controller

Fuzzy rules of traditional fuzzy systems only describe the operations that are to be run. In Positive/Negative (P/N) rule fuzzy system theory, the concept of negative fuzzy rules was introduced to prescribe actions to avoid rather than execute. Two types of rules, positive rules and negative rules, are used in a P/N rule fuzzy controller. Positive-rules derive the proper output of the P/N-rule-based fuzzy system, comparable to typical fuzzy system rules. In contrast, negative rules cause the fuzzy system not to produce improper fuzzy output. The P/N rule fuzzy system can be applied to obstacle avoidance for the autonomous navigation of mobile robots. Positive rules direct the robot to a target place and negative rules prevent the robot from colliding with obstacles. The effect of positive rules is dominant in a non-obstacle environment because negative rules begin to affect navigation only when obstacles appear on the navigation path of the robot. If the detected obstacles are far from the robot, negative rules rarely affect the system. As the obstacles come closer to the robot, the negative rules dominate the system.

2.2 Full-LUT-based design of a Positive/Negative rule fuzzy controller

For secure navigation for mobile robots, the computation delay of the obstacle avoidance controller is one of the most important factors. To reduce the delay, we decided to reduce the computational complexity of the controller. It is not to be denied that faster decision when avoiding obstacles contributes to more accurate avoidance. In our design, we adopted a P/N fuzzy controller method which is simpler and more intuitive for robot obstacle avoidance. However, fuzzy membership functions formed as Gaussian distribution curves are the most critical problem related to fast operations because the fuzzy controller should process numerous floating point operations to calculate the fuzzy membership degrees. The computations for fuzzy membership degrees could be a burden that causes difficulties with real-time navigation. Therefore, we attempted to reduce the computations for membership degrees through the use of the LUTs of membership functions. The basic idea is that the fuzzy controller does not need to calculate the membership function degree upon the receipt of sensor data each time, as all membership functions and their each output values corresponding to their input values are previously determined according to the characteristics of the function. Therefore, it is possible to store all membership function data in the LUTs in advance and search for membership degrees from the LUTs without any computational time. Fig. 2 illustrates the process of obtaining fuzzy membership degrees from the LUT. The LUT buffers of all fuzzy membership functions are shown in Fig. 3. If the fuzzy controller obtains each membership degree from LUT buffers, the robot can reduce the processing time and perform more frequent obstacle-avoidance operations because the operation delay in the multiplication of the floating point operands is eliminated.

Figure 1.

Fuzzy membership degree acquisition on lookup-table based architecture

Figure 2.

Lookup-table (LUT) buffers of full-LUT-based architecture

Figure 3.

Fuzzy membership degree acquisition using a shared lookup-table

3. Lookup-Table sharing method

It is quite attractive to use LUTs that are capable of rapid operations in a fuzzy controller, but there are also disadvantages in a LUT-based design. To maintain the LUTs of membership functions, the fuzzy controller should guarantee a sufficient size of the buffer memory for the LUTs. Because a large LUT memory is a burden on the system, we tried to reduce the memory through the use of a shared LUT. The shared LUT contains the function values of a basic Gaussian distribution function that we defined. The equation of the basis function can be expressed as follows:

$$f_{basis}=e^{-\frac{x_{trans}{}^2}{2{\sigma }_{BasisFunction}{}^2}}$$

(1)

The variance of the basis function, σ _{BasisFunction} , is set to 128 for the 50-rule P/N fuzzy controller. This idea stems from the fact that all membership functions of our fuzzy controller are based on a Gaussian distribution which is characterized by the variance (σ) and the center (c). Therefore, each membership function's output value is simply obtained from the basis function by converting the input value x _input into the proper converted value X _Converted , which is calculated as follows:

$$x_{Converted}=\frac{{\sigma }_{BasisFunction}}{{\sigma }_{MembershipFunction}}(x_{input}-c_{MembershipFunction}).$$

(2)

The input data from a laser range finder (LRF) are discrete and are converted into integer values so that they can be used as the indexes of the LUTs. The shared LUT is also indexed by integral numbers to simplify the use of buffers. Because the calculation result, x _Converted , can contain a decimal fraction value, it is not possible to provide the output value of the original membership function using the shared LUT because it provides only the output values of integral inputs. Although we cannot use non-integer indexes, we can obtain an approximate value by rounding off x _Converted to its nearest integer.

As shown above, f _basis is a Gaussian distribution function; hence, the left part of the basis function in the shared LUT can be eliminated to remove redundancy. The absolute values of the inputs are used to generate an indexing address corresponding to the left part of the basis function. Finally, the indexing address of the shared LUT is calculated as follows:

$$Addres{s}_{LUT}=\left|round(\frac{{\sigma }_{BasisFunction}}{{\sigma }_{MembershipFunction}}(x_{input}-c_{MembershipFunction})\right|.$$

(3)

Fig. 3 shows a diagram of the fuzzy membership degree acquisition process using the LUT sharing method. The Address Generator generates the indexing address of the shared LUT, Addresslut; the calculated address is proper for the characteristics of each of its membership function. In each indexing address, 32-bit floating point data is stored. Also, the range of indexing address is between 0 and 511, as shown in Fig. 3. If the calculated address, Addresslut, exceeds a length of 511, we change the value to 511 and the LUT releases 0 as the output. This also indicates that we consider output values below 0.000000119 as 0 in order to reduce the buffer size.

After reading the output of the function from the shared LUT, Compensator compensates for the output value, as it is not identical to an expected membership degree. However, this may not be necessary when the errors between the shared LUT outputs and the original output values are too small to affect the navigation performance. We confirmed this in simulations and determined it was feasible to eliminate Compensator from the design.

4. 50-Rule P/N Fuzzy Controller for Laser-Range-Finder-based Obstacle Avoidance

4.1 Design of 50-Rule P/N Fuzzy Controller

The 50-rule P/N fuzzy controller is designed with two types of input parameters, the first is sensor data from a laser range finder and the second is the relative target position based on the current position of the robot. Fig. 4 shows the measurement data from the laser range finder. The laser range finder sensor provides the distance vectors of directions over 180 degree with an angular resolution of 0.5 degrees. To simplify the fuzzy system, we converted the scale of inputs into integer values by multiplying the input value by 2. Once the target position is determined, the position is a constant on the navigation map. However, the relative target position varies according to changes of the current robot position. As the robot moves, the robot controller should update the relative target position, which consists of a target distance and a target direction. The output of the fuzzy controller is the steering direction of the robot. In a real application, however, the controller converts the direction information into values for steering, as in the velocities of two wheels.

Figure 4.

Measurement of the laser range finder

In the 50 P/N fuzzy rules, 25 positive rules are related to the target position and 25 negative rules are related to the positions of multiple obstacles. The fuzzification of the 50-rule P/N fuzzy controller for the laser-range-finder-based obstacle avoidance method is explained in the next section.

4.2 Fuzzification

Fuzzification of the input is described by the membership functions shown in Fig. 5. Each membership function of a fuzzy input is a Gaussian distribution function. These are expressed as Eq. (4)

$$f(x)=e^{\begin{array}{cc}-& \frac{{(x-c)}^2}{2{\sigma }^2}\end{array}},$$

(4)

Figure 5.

Membership functions of the designed 50-rule fuzzy controller

where c denotes the center of the distribution and σ denotes the variance of the function. Table 1 represents the c and σ values of each fuzzy membership function. The fuzzy sets Hard Left (HL), Soft Left (SL), Straight (S), Soft Right (SR), and Hard Right (HR) are for the fuzzy inputs of the target or the obstacle direction. In addition, Zero (Z), Very Near (VN), Near (N), Far (Far), and Very Far (VF) are related to the fuzzy inputs of the target or the obstacle distance. The output fuzzy sets Hard Left (HL), Left (L), Soft Left (SL), Straight (S), Soft Right (SR), Right (R), and Hard Right (HR) are for positive rules, while $\overline{HL}$ , $\bar{L},\overline{SL},\bar{S},\overline{SR},\bar{R}$ , and $\overline{HR}$ are for negative rules.

Table 1.

Characteristics of the Fuzzy Membership Functions of the 50-rule P/N Fuzzy Controller

		Target		Obstacle
		Center (c)	Variation (σ)	Center (c)	Variation (σ)
Direction (degree×2)	HL	−120	36	−120	36
	SL	−60	36	−60	36
	S	0	36	0	36
	SR	60	36	60	36
	HR	120	36	120	36
Distance (mm)	Z	0	6000	500	300
	VN	10000	6000	1000	300
	N	20000	6000	1500	300
	F	30000	6000	2000	300
	VF	40000	6000	2500	300

4.3 Rule Base

The expert-provided positive rule base is shown in Table 2 and the negative rule base is given in Table 3. The positive rule base can be represented by the following rules:

Table 2.

Rule Base of the 25-rule Positive Fuzzy System (Expert-Provided)

Steering Direction		Target Direction
		HL	SL	S	SR	HR
Target Distance	Z	HL	HL	S	HR	HR
	VN	HL	L	S	R	HR
	N	L	L	S	R	R
	F	L	SL	S	SR	R
	VF	SL	S	S	S	SR

Table 3.

Rule Base of the 25-rule Negative Fuzzy System (Expert-Provided)

Steering Direction		Obstacle Direction
		HL	SL	S	SR	HR
Obstacle Distance	Z	$\overline{HL}$	$\overline{HL}$	$\bar{S}$	$\overline{HR}$	$\overline{HR}$
	VN	$\overline{HL}$	$\bar{L}$	$\bar{S}$	$\bar{R}$	$\overline{HR}$
	N	$\bar{L}$	$\bar{L}$	$\bar{S}$	$\bar{R}$	$\bar{R}$
	F	$\bar{L}$	$\overline{SL}$	$\bar{S}$	$\overline{SR}$	$\bar{R}$
	VF	$\overline{SL}$	$\bar{S}$	$\bar{S}$	$\bar{S}$	$\overline{SR}$

• Rule 1P

  If x_{TargetDirection} is HL and x_{TargetDistance} is Z then y is HL

• Rule 2P

  If x_{TargetDirection} is HL and x_{TargetDistance} is VN then y is HL

• Rule 3P

  If x_{TargetDirection} is HL and x_{TargetDistance} is N then y is L

  ⋮

• Rule 25P

  If x_{TargetDirection} is HR and x_{TargetDistance} is VF then y is SR.

The negative rule base in Table 3 is represented in the same manner of the above rules, as follows:

• Rule 1N

  If x_{ObstacleDirection} is HL and x_{ObstacleDistance} is Z then y is not HL

• Rule 2N

  If x_{ObstacleDirection} is HL and x_{ObstacleDistance} is VN then y is not HL

• Rule 3N

  If x_{ObstacleDirection} is HL and x_{ObstacleDistance} is N then y is not L

  ⋮

• Rule 25N

  If x_{ObstacleDirection} is HR and x_{ObstacleDistance} is VF then y is not SR.

The notation of the membership degree of each fuzzy set is expressed as shown in Table 4. The weight of the positive rule 'Rule 1P' is determined by the multiplication of μhl and μz, and the weight of 'Rule 2P' is calculated by the multiplication of μhl and μvn. The same approach is applied to the other rules. The combined degree of the positive rule 'Rule 1P' and its corresponding negative rules is calculated as follows:

$${\mu }_1=\left(offset+{\mu }_{HL}\cdot {\mu }_Z\right){\displaystyle \prod _{i=1}^{\#ofObstacle}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\bar{Z}}_i}\right)}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\overline{VN}}_i}\right)\left(1-{\mu }_{{\overline{SL}}_i}\cdot {\mu }_{{\bar{Z}}_i}\right)$$

(5)

Table 4.

Membership Degrees of Input Fuzzy Sets

Degrees of positive-rule fuzzy sets		Degree of negative-rule fuzzy sets
HL	μHL	HL	$\mathrm{\mu }\overline{HL}$
SL	μsl	SL	$\mathrm{\mu }\overline{SL}$
S	μs	S	$\mathrm{\mu }\bar{S}$
SR	μsr	SR	$\mathrm{\mu }\overline{SR}$
HR	μhr	HR	$\mathrm{\mu }\overline{HR}$
Z	μz	Z	$\mathrm{\mu }\bar{Z}$
VN	μvn	VN	$\mathrm{\mu }\overline{VN}$
N	μn	N	$\mathrm{\mu }\bar{N}$
F	μf	F	$\mathrm{\mu }\bar{F}$
VF	μvf	VF	$\mathrm{\mu }\overline{VF}$

Similarly, the other combined degrees are calculated as follows:

$$\begin{array}{l}{\mu }_2=\left(offset+{\mu }_{HL}\cdot {\mu }_{VN}\right){\displaystyle \prod _{i=1}^{\#ofObstacle}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\bar{Z}}_i}\right)}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\overline{VN}}_i}\right)\left(1-{\mu }_{{\overline{SL}}_i}\cdot {\mu }_{{\bar{Z}}_i}\right)\hfill \\ {\mu }_3=\left(offset+{\mu }_{HL}\cdot {\mu }_N\right){\displaystyle \prod _{i=1}^{\#ofObstacle}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\bar{N}}_i}\right)}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\bar{F}}_i}\right)\left(1-{\mu }_{{\overline{SL}}_i}\cdot {\mu }_{{\overline{VN}}_i}\right)\left(1-{\mu }_{{\overline{SL}}_i}\cdot {\mu }_{{\bar{N}}_i}\right),\hfill \\ {\mu }_4=\left(offset+{\mu }_{HL}\cdot {\mu }_F\right){\displaystyle \prod _{i=1}^{\#ofObstacle}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\bar{N}}_i}\right)}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\bar{F}}_i}\right)\left(1-{\mu }_{{\overline{SL}}_i}\cdot {\mu }_{{\overline{VN}}_i}\right)\left(1-{\mu }_{{\overline{SL}}_i}\cdot {\mu }_{{\bar{N}}_i}\right),\hfill \\ {\mu }_5=\left(offset+{\mu }_{HL}\cdot {\mu }_{VF}\right){\displaystyle \prod _{i=1}^{\#ofObstacle}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\overline{VF}}_i}\right)}\left(1-{\mu }_{{\overline{SL}}_i}\cdot {\mu }_{{\bar{F}}_i}\right),\hfill \\ {\mu }_6=\left(offset+{\mu }_{SL}\cdot {\mu }_Z\right){\displaystyle \prod _{i=1}^{\#ofObstacle}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\bar{Z}}_i}\right)}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\overline{VN}}_i}\right)\left(1-{\mu }_{{\overline{SL}}_i}\cdot {\mu }_{{\bar{Z}}_i}\right),\hfill \\ {\mu }_7=(offset+{\mu }_{SL}\cdot {\mu }_{VN}){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{HL}}{}_{{}_i}\cdot {\mu }_{\bar{N}}{}_{{}_i})(1-{\mu }_{\overline{HL}}{}_{{}_i}\cdot {\mu }_{\bar{F}}{}_{{}_i})(1-{\mu }_{\overline{SL}}{}_{{}_i}\cdot {\mu }_{\overline{VN}}{}_{{}_i})(1-{\mu }_{\overline{SL}}{}_{{}_i}\cdot {\mu }_{\bar{N}}{}_{{}_i}),}\hfill \\ {\mu }_8=(offset+{\mu }_{SL}\cdot {\mu }_N){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{HL}}{}_{{}_i}\cdot {\mu }_{\bar{N}}{}_{{}_i})(1-{\mu }_{\overline{HL}}{}_{{}_i}\cdot {\mu }_{\bar{F}}{}_{{}_i})(1-{\mu }_{\overline{SL}}{}_{{}_i}\cdot {\mu }_{\overline{VN}}{}_{{}_i})(1-{\mu }_{\overline{SL}}{}_{{}_i}\cdot {\mu }_{\bar{N}}{}_{{}_i}),}\hfill \\ {\mu }_9=\left(offset+{\mu }_{SL}\cdot {\mu }_F\right){\displaystyle \prod _{i=1}^{\#ofObstacle}\left(1-{\mu }_{{\overline{HL}}_i}\cdot {\mu }_{{\overline{VF}}_i}\right)}\left(1-{\mu }_{{\overline{SL}}_i}\cdot {\mu }_{{\bar{F}}_i}\right),\hfill \\ {\mu }_{10}=(offset+{\mu }_{SL}\cdot {\mu }_{VF})\hfill \\ {\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SL}}{}_{{}_i}\cdot {\mu }_{\overline{VF}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\bar{Z}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\overline{VN}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\bar{N}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\bar{F}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\overline{VF}}{}_{{}_i}),}\\ {\mu }_{11}=(offset+{\mu }_S\cdot {\mu }_Z)\hfill \\ {\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SL}}{}_{{}_i}\cdot {\mu }_{\overline{VF}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\bar{Z}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\overline{VN}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\bar{N}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\bar{F}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\overline{VF}}{}_{{}_i}),}\\ {\mu }_{12}=(offset+{\mu }_S\cdot {\mu }_{VN})\hfill \\ {\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SL}}{}_{{}_i}\cdot {\mu }_{\overline{VF}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\bar{Z}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\overline{VN}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\bar{N}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\bar{F}}{}_{{}_i})(1-{\mu }_{\bar{S}}{}_{{}_i}\cdot {\mu }_{\overline{VF}}{}_{{}_i}),}\\ {\mu }_{13}=(offset+{\mu }_S\cdot {\mu }_N)\hfill \\ \begin{array}{cc}& \end{array}\times {\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SL}}{}_i\cdot {\mu }_{\overline{VF}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\overline{VN}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{F}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\overline{VF}}{}_i)},\\ {\mu }_{14}=(offset+{\mu }_S\cdot {\mu }_F)\hfill \\ \begin{array}{cc}& \end{array}\times {\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SL}}{}_i\cdot {\mu }_{\overline{VF}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\overline{VN}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{F}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\overline{VF}}{}_i)},\\ {\mu }_{15}=(offset+{\mu }_S\cdot {\mu }_{VF})\hfill \\ \begin{array}{cc}& \end{array}\times {\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SL}}{}_i\cdot {\mu }_{\overline{VF}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\overline{VN}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{F}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\overline{VF}}{}_i)},\\ {\mu }_{16}=(offset+{\mu }_{SR}\cdot {\mu }_Z){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\overline{VN}}{}_i)},\hfill \\ {\mu }_{17}=(offset+{\mu }_{SR}\cdot {\mu }_{VN}){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\overline{VN}}{}_i)(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\bar{F}}{}_i)},\hfill \\ {\mu }_{18}=(offset+{\mu }_{SR}\cdot {\mu }_N){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\overline{VN}}{}_i)(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\bar{F}}{}_i)},\hfill \\ {\mu }_{19}=(offset+{\mu }_{SR}\cdot {\mu }_F){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\bar{F}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\overline{VF}}{}_i)},\hfill \\ {\mu }_{20}=(offset+{\mu }_S\cdot {\mu }_{VF})\hfill \\ \begin{array}{cc}& \end{array}\times {\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\overline{VF}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\overline{VN}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{F}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\overline{VF}}{}_i)},\\ {\mu }_{21}=(offset+{\mu }_{HR}\cdot {\mu }_Z){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\overline{VN}}{}_i)},\hfill \\ {\mu }_{22}=(offset+{\mu }_{HR}\cdot {\mu }_{VN}){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\overline{VN}}{}_i)},\hfill \\ {\mu }_{23}=(offset+{\mu }_{HR}\cdot {\mu }_N){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\overline{VN}}{}_i)(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\bar{F}}{}_i),}\hfill \\ {\mu }_{24}=(offset+{\mu }_{HR}\cdot {\mu }_F){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\overline{VN}}{}_i)(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\bar{F}}{}_i),}\hfill \\ {\mu }_{25}=(offset+{\mu }_{HR}\cdot {\mu }_{VF}){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\overline{SR}}{}_i\cdot {\mu }_{\bar{F}}{}_i)(1-{\mu }_{\overline{HR}}{}_i\cdot {\mu }_{\overline{VF}}{}_i)}.\hfill \end{array}$$

(6)

4.4 Defuzzification

Finally, the output value of the 50-rule P/N fuzzy controller is calculated as the weighted average of all output fuzzy sets:

$$(\begin{array}{c}\begin{array}{cc}y=\frac{w_{HL}\cdot HL+w_L\cdot L+w_{SL}\cdot SL+w_S\cdot S}{w_{HL}+w_L+w_{SL}+w_S}& (w_{HL}+w_L+w_{SL}\ge w_{HR}+w_R+w_{SR}),\end{array}\\ \begin{array}{cc}y=\frac{w_{HR}\cdot HR+w_R\cdot R+w_{SR}\cdot SR+w_S\cdot S}{w_{HR}+w_R+w_{SR}+w_S}& (w_{HL}+w_L+w_{SL}<w_{HR}+w_R+w_{SR}).\end{array}\end{array}$$

(7)

The weights of the output fuzzy sets are as follows:

$$\begin{array}{c}{w}_{HL}={\mu }_1+{\mu }_2+{\mu }_6,\\ w_L={\mu }_3+{\mu }_4+{\mu }_7+{\mu }_8,\\ w_{SL}={\mu }_5+{\mu }_9,\\ w_S={\mu }_{10}+{\mu }_{11}+{\mu }_{12}+{\mu }_{13}+{\mu }_{14}+{\mu }_{15}+{\mu }_{20},\\ w_{SR}={\mu }_{19}+{\mu }_{25},\\ w_R={\mu }_{17}+{\mu }_{18}+{\mu }_{23}+{\mu }_{24},\\ w_{HR}={\mu }_{16}+{\mu }_{21}+{\mu }_{22}.\end{array}$$

(8)

5. 18-Rule P/N Fuzzy Controller for Ultra-sonic Sensor based Obstacle Avoidance

5.1 Design of 18-Rule P/N Fuzzy Controller

The 18-rule P/N fuzzy controller is designed as an ultrasonic sensor based obstacle avoidance system for mobile robots. Unlike the laser range finder, ultra-sonic sensors implemented here have an angular resolution of 30° and are arranged with 7 sensors, as shown in Fig. 6. Each sensor detects the nearest obstacle in front of the sensor within a distance from 25mm to 3m using a 30° angular range. Because its angular resolution is relatively low compared to a laser range finder, we designed a simpler fuzzy controller based on 18 rules. In a manner similar to that of the 50-rule P/N fuzzy controller, 9 positive rules are related to a target position and 9 negative rules are related to the positions of multiple obstacles.

Figure 6.

Implementation of the ultrasonic sensors for the 18-rule fuzzy obstacle avoidance fuzzy controller

5.2 Fuzzification

Fuzzification of the 18-rule P/N fuzzy controller can be described by the membership functions shown in Fig. 7. Each membership function is a Gaussian distribution function. Table 5 represents the c and σ values of each fuzzy membership function. The fuzzy sets, Left (L), Straight (S), Right (R), are for the fuzzy inputs of the target or the obstacle direction. Also, Zero (Z), Near (N), and Far (Far) are related to the fuzzy inputs of the target or the obstacle distance. The output fuzzy sets Hard Left (HL), Left (L), Soft Left (SL), Straight (S), Soft Right (SR), Right (R), and Hard Right (HR) are for positive rules, while $\overline{HL,}\bar{L},\overline{SL},\bar{S},\overline{SR,}\bar{R}$ , and $\overline{HR}$ are for negative rules.

Figure 7.

Membership functions of the designed 18-rule fuzzy controller

Table 5.

Characteristics of Fuzzy Membership Functions of the 18-rule P/N Fuzzy Controller

		Target		Obstacle
		Center (c)	Variation (σ)	Center (c)	Variation (σ)
Direction (degree×2)	HL	−120	36	−120	72
	S	0	36	0	72
	HR	120	36	120	72
Distance (mm)	Z	0	1500	700	150
	N	15000	1500	1200	150
	F	30000	1500	1700	150

5.3 Rule Base

Each rule base of positive and negative rules is shown in Table 6 and Table 7, respectively. The positive rule base can be represented by following rules:

Table 6.

Rule Base of 9-rule Positive Fuzzy System (Expert-Provided)

Steering Direction		Target Direction
		L	S	R
Target Distance	Z	HL	S	HR
	N	L	S	R
	F	SL	S	SR

Table 7.

Rule Base of the 9-rule Negative Fuzzy System (Expert-Provided)

Steering Direction		Obstacle Direction
		SL	S	SR
Obstacle Distance	Z	$\overline{HL}$	$\bar{S}$	$\overline{HR}$
	N	$\bar{L}$	$\bar{S}$	$\bar{R}$
	F	$\overline{SL}$	$\bar{S}$	$\overline{SR}$

• Rule 1P

• If x_{TargetDirection} is L and x_{TargetDistance} is Z then y is HL

• Rule 2P

• If x_{TargetDirection} is L and x_{TargetDistance} is N then y is L

• Rule 3P

• If x_{TargetDirection} is L and x_{TargetDistance} is F then y is SL

• Rule 4P

• If x_{TargetDirection} is S and x_{TargetDistance} is Z then y is S

• Rule 5P

• If x_{TargetDirection} is S and x_{TargetDistance} is N then y is S

• Rule 6P

• If x_{TargetDirection} is S and x_{TargetDistance} is F then y is S

• Rule 7P

• If x_{TargetDirection} is R and x_{TargetDistance} is Z then y is HR

• Rule 8P

• If x_{TargetDirection} is R and x_{TargetDistance} is N then y is R

• Rule 9P

• If x_{TargetDirection} is R and x_{TargetDistance} is F then y is SR

The negative rule base in Table 7 is also represented as follows:

• Rule 1N

• If x_{ObstacleDirection} is L and x_{ObstacleDistance} is Z then y is not HL

• Rule 2N

• If x_{ObstacleDirection} is L and x_{ObstacleDistance} is N then y is not L

  ⋮

• Rule 9N

• If x_{ObstacleDirection} is R and x_{ObstacleDistance} is F then y is not SR.

The combined degrees of the 9 positive rules are calculated as follows:

$$\begin{array}{c}{\mu }_1=(offset+{\mu }_L\cdot {\mu }_Z){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\bar{L}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)},\hfill \\ {\mu }_2=(offset+{\mu }_L\cdot {\mu }_N){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\bar{L}}{}_i\cdot {\mu }_{\bar{N}}{}_i)},\hfill \\ {\mu }_3=(offset+{\mu }_L\cdot {\mu }_F){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\bar{L}}{}_i\cdot {\mu }_{\bar{F}}{}_i)},\hfill \\ {\mu }_4=(offset+{\mu }_S\cdot {\mu }_Z){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{F}}{}_i)},\hfill \\ {\mu }_5=(offset+{\mu }_S\cdot {\mu }_N){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{F}}{}_i)},\\ {\mu }_6=(offset+{\mu }_S\cdot {\mu }_F){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{N}}{}_i)(1-{\mu }_{\bar{S}}{}_i\cdot {\mu }_{\bar{F}}{}_i)},\\ {\mu }_7=(offset+{\mu }_R\cdot {\mu }_Z){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\bar{R}}{}_i\cdot {\mu }_{\bar{Z}}{}_i)},\\ {\mu }_8=(offset+{\mu }_R\cdot {\mu }_N){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\bar{R}}{}_i\cdot {\mu }_{\bar{N}}{}_i)},\\ {\mu }_9=(offset+{\mu }_R\cdot {\mu }_F){\displaystyle \prod _{i=1}^{\#ofObstacles}(1-{\mu }_{\bar{R}}{}_i\cdot {\mu }_{\bar{F}}{}_i)}.\end{array}$$

(9)

5.4 Defuzzification

The output value of the 18-rule P/N fuzzy controller is also calculated as the weighted average of all output fuzzy sets:

$$(\begin{array}{c}\begin{array}{cc}y=\frac{w_{HL}\cdot HL+w_L\cdot L+w_{SL}\cdot SL+w_S\cdot S}{w_{HL}+w_L+w_{SL}+w_S}& (w_{HL}+w_L+w_{SL}\ge w_{HR}+w_R+w_{SR}),\end{array}\\ \begin{array}{cc}y=\frac{w_{HR}\cdot HR+w_R\cdot R+w_{SR}\cdot SR+w_S\cdot S}{w_{HR}+w_R+w_{SR}+w_S}& (w_{HL}+w_L+w_{SL}<w_{HR}+w_R+w_{SR}).\end{array}\end{array}$$

(10)

The weights of output fuzzy sets are as follows:

$$\begin{array}{c}{w}_{HL}={\mu }_1,\\ w_L={\mu }_2,\\ w_{SL}={\mu }_3,\\ w_S={\mu }_4+{\mu }_5+{\mu }_6,\\ w_{SR}={\mu }_7,\\ w_R={\mu }_8,\\ w_{HR}={\mu }_9.\end{array}$$

(11)

6. Simulation and Experiments

A simulation of the designed 50-rule P/N fuzzy controller was performed on MSRDS (Microsoft Robotics Developer Studio). The simulation was performed using an Intel® Core™ 2 Quad 2.4GHz CPU and 3.24GB RAM computer system. Fig. 8 shows a robot navigation map of the graphic simulator. A simulation robot navigates from the starting position to the target position on the map. If there are no obstacles in the map, the robot sets its path as a straight line from the starting position to the target position. If there are obstacles on the navigation path, the robot must change and update its path to avoid the obstacles. To evaluate the proposed method on the simulator, we created a service module for each fuzzy controller method and inserted it into the MSRDS Visual Programming Language (VPL) diagram. The service modules were programmed in the C# programming language and created by the Microsoft Visual Studio compiler. The sensor modules and driving service modules of the graphic simulator were imported using the service libraries of MSRDS. Because a graphic simulation environment requires high-performance processors, the simulation was performed on a high-performance computer system. In this case, the target systems of our method are mobile robot systems. Therefore, we used high-performance computer systems that may not be applicable to mobile embedded systems only for the graphical simulation. We also considered the processing time only for the fuzzy operation because the simulation system uses most of the processing time for graphical operations.

Figure 8.

Simulation map of MSRDS (Microsoft Robotics Developer Studio)

Table 8 presents the implementation results of each design. The buffer size of the full-LUT shown in Fig. 2 is (204+8469+847) × 4 bytes, while that of the shared LUT presented in Fig. 3 is 512 × 4 bytes. The processing clock cycle of each design in the table is the average computation of the clock cycles used in the avoidance operations during the navigation process from the starting position to the target position on the map. A fuzzy controller without LUT does not require a buffer for the LUT(s), but it does need 8 times as much time for the fuzzy operation compared to the full-LUT-based fuzzy controller. If all membership functions have LUTs, the operation time can be greatly reduced. However, this requires about 38Kbytes of LUT memory. The simulation result for the LUT sharing method showed that the fuzzy controller can operate well only with 5.34% of the full LUT's memory size. Although the controller requires about 1.5 times more operation time than the full-LUT-based design, the comparative reduction of the memory size is more advantageous for the system. In brief, the simulation results show that the LUT-based fuzzy controller greatly reduces the computational latency and obviously enhances the performance of a real-time obstacle avoidance system for an autonomous robot. Also, the LUT sharing method offers an approach that uses LUT-based architecture without the additional expense of added buffer memory. Figs. 9, 10, and 12 show the results, which were verified in the experiments based on a mobile robot (Pioneer P3-DX). Figs. 11 and 13 show the experiment processes in a cluttered environment for the result shown in Figs. 10 and 12, respectively.

Figure 9.

Fuzzy controller implementation for obstacle avoidance with the LabVIEW application on a mobile robot (Pioneer P3-DX)

Figure 10.

Experimental result for obstacle avoidance while navigating from the starting position (0, 0) to the target position (900, 5400) in a cluttered environment

Figure 11.

Experiment process in a cluttered environment for the result shown in Fig. 10

Figure 12.

Experimental result of obstacle avoidance while navigating from the starting position (0, 0) to the target position (−4300, 0) in a cluttered environment

Figure 13.

Experiment process in a cluttered environment for the result shown in Fig. 12

Table 8.

Buffer size and processing cycles of each fuzzy controller

	Calculatin g w/o a LUT	Using the full LUT	Sharing a LUT
Buffer size of the lookup table (bytes)	0	38,080	2,048
Clock cycles per 1 avoidance (cycles)	427,390	84,797	127,494

7. Conclusions

This work sought to implement a real-time mobile robot system that uses relatively less power. To perform faster operations in real-time systems, using faster processors may be enough for the controller. However, there are limitations when designing a low-power system with only high-performance processors. It is necessary to reduce the operation clock frequency to lower the power consumption because a high clock frequency elevates the power consumption of the system. All of these factors make it clear that a reduction of the operational complexity is a better answer for both faster operation and lower power consumption.

We utilized LUT(s) to eliminate the calculation of the membership degrees, which can be complicated and reiterative. Thus, we designed a full-LUT-based fuzzy controller, with which the average operation time is reduced to 20% of the time required by the fuzzy controller without LUT(s). However, the full-LUT design requires the buffers to contain all of the membership function values. To reduce the buffer size, we attempted to share the LUT for the membership functions. While the simulation results showed that the proposed LUT sharing method requires 50% more operation cycles on average compared to the full-LUT-based design, the proposed method saves 94.5% of the original LUT buffer size. The results show that the LUT sharing method can be more worthwhile for real-time mobile robots because it is approximately 3.35 times faster than the use of a fuzzy controller without LUT(s).

In conclusion, this work can provide advantages to real-time obstacle avoidance systems for use in mobile robots because the LUT-based fuzzy controller design enables faster obstacle avoidance while the LUT sharing method provides compactness of the controller by reducing most of LUT buffers.