Fuzzy Logic in Perl
The Perl Journal June 2003
By Ala Qumsieh
Ala works at NVidia Corp. as a physical ASIC designer. He can be reached at [email protected].
Everyone has heard about how Fuzzy Logic (FL) is being used in many real-life applications such as traffic signal controls, automobile transmission control, cancer diagnosis, dam gate control for hydroelectric power plants, and elevator control. This article will show you how this is done, and will describe a new Perl module, AI::FuzzyInference, that allows you to write Perl programs that use Fuzzy Logic to make rational decisions.
In order to understand how the module works, it is helpful to know some of the theory behind Fuzzy Logic. What follows is a brief introduction to Fuzzy Logic and Fuzzy Inference Systems. A more detailed introduction can be found in an excellent tutorial by Jerry Mendel (http://sipi.usc.edu/~mendel/publications/ FLS_Engr_Tutorial_Errata.pdf). Please note that multiple terminologies exist to describe the same thing. What I will use might differ from that in the aforementioned tutorial.
Fuzzy Logic
Fuzzy Logic is an extension of regular two-valued logic that was developed by Lotfi Zadeh (L.A. Zadeh, "Fuzzy sets," Information and Control, vol. 8, pp. 338-353, 1965). In regular set theory, an element x either belongs to a set S, or it does not belong. For example, the element apple belongs to the set Fruits, but does not belong to the set Vegetables. We say that the element apple is a "member" of the set Fruits.
Problems start to arise when membership is not as easily determined. Consider, for example, the set of Round Objects. Is our apple a member of this set? Well, it depends on how round the apple is. In everyday life, we say "The apple is almost round." In order to take account of adverbs such as almost, sort of, and approximately, Zadeh extended regular set theory to allow for partial degrees of membership (DOM). This way, we can postulate that the degree of membership of our apple in the set of Round Objects is 0.8, while a pear's degree of membership is only 0.4, and that of a banana is 0.
Many people confuse fuzzy logic and probability. Although they look similar, they are completely different. As an example, consider two bottles filled with unknown liquids. The contents of bottle A have a probability of 0.9 of being a member of the set Toxic Liquids. The contents of bottle B have a fuzzy degree of membership of 0.9 in that same set. If I had to drink from one, I would choose bottle A because one time out of ten, the contents will not be toxic. Bottle B will always kill me because its contents are highly toxic (nine parts poison and one part water, say). Probability gives you the likelihood of the liquid being toxic. Fuzzy logic tells you how toxic it is.
Term Sets
It is very useful to be able to graphically depict what all this means. To do that, let's take another example. Let's try to categorize people based on their height. We can do so by defining three sets: Short, Average, and Tall. In FL, these three sets are called Term Sets of the variable Height, which is referred to as a "Linguistic Variable." Linguistic variables are variables that do not have defined numerical values, but are described by words or sentences. A 6' man is of average height, and a 6' woman is rather tall.
Let's define Average height as 6'. So, a 6' person has DOMaverage of 1. We can expect that for people progressively shorter than that, their DOM will be progressively smaller. Similarly for taller people. If we plot a graph of height versus DOM, it might look like Figure 1. This triangular shape of term sets is typical of Fuzzy Logic, and is mainly chosen for convenience. Other representations are possible, such as a bell-curve or Gaussian, but then computation becomes much more difficult. Corresponding term sets for Short and Tall can be similarly determined. Furthermore, term sets can overlap. A 6'3" person has DOM of 0.3 in the Average set, and a DOM of 0.6 in the Tall set.
An important thing to note here is that degrees of membership are highly dependent on the problem being investigated. For an average person, a 6'5" person is tall, but for the set of Basketball Players, such a person is of average height. Thus, in different contexts, the same term sets might have different shapes (thinner or fatter), and can shift and overlap by different degrees.
Set Theoretic Operations
In regular set theory, sets can be combined and manipulated using the logical operations of union, intersection, and complement. The same operations are extended to handle fuzzy sets in the following manner:
Union: The union C of two sets A and B is the maximum of the two sets. This means that for every element x, DOMC(x)= max(DOMA(x), DOMB(x)).
Intersection: The intersection C of two sets A and B is the minimum of the two sets. This means that for every element x, DOMC(x)=min(DOMA(x), DOMB(x)).
Complement: The complement C of a set A is defined as 1-A. So, for every element x, DOMC(x)=1-DOMA(x).
Note that in the case of two-valued logic, those definitions collapse to their binary counterparts: OR, AND, and NOT, respectively. Another important thing to note here is that those are not the only definitions for the fuzzy set theoretic operations. We are free to choose any definition as long as it reduces to the binary form in the case of two-valued logic. As a matter of fact, Zadeh's original definitions were:
Union: DOMA(x)+DOMB(x)-DOMA(x)DOMB(x)
Intersection: DOMA(x)DOMB(x)
Complement: 1-DOMA(x)
Other interpretations also exist.
Fuzzy Inference
Now we have just enough background to describe a Fuzzy Inference System (FIS). An FIS is a system that has a number of input variables and a number of output variables. Those variables are described by a number of term sets, and are related to each other via fuzzy rules. For example, a system with input variables QualityOfFood and QualityOfService, and output variable AmountOfTip might have the following rule:
If QualityOfFood is good AND QualityOfService is bad THEN AmountOfTip is small
The IF part is called the "precedent" while the THEN part is called the "consequent." Other rules can be defined for the remaining scenarios. For each variable (both input and output), term sets must be defined that span the whole universe of discourse of the variable, which is the range of possible values that the variable can take.
Now, given numerical values for its input variables, an FIS will use the fuzzy rules to compute a crisp numerical value for each of the output variables. This operation can be broken into four distinct steps.
Fuzzification
In this step, the values of the input variables are used to compute their degrees of membership into each term set. This is simply done by drawing a vertical line on the graph of each term set at the input variable's value, and noting where it intersects the graph. For example, if QualifyOfFood==0.6, then we calculate:
DOMqof_bad(0.6) = 0
DOMqof_good(0.6) = 0.9
DOMqof_excellent(0.6) = 0.2
and if QualityOfService == 0.3, then we calculate:
DOMqos_bad(0.3) = 0.7
DOMqos_good(0.3) = 0.2
DOMqos_excellent(0.3) = 0
Inference
Now, we examine all the defined rules, and for each rule, we compute a degree of support, which indicates the firing strength of that rule. This is done by looking at the precedent of the rule, and using fuzzy logic operations to combine the values of all its constituent parts to produce a single number. So, for the rule:
If QualityOfFood is good AND QualityOfService is bad THEN AmountOfTip is small
Degree of support will be 0.9 AND 0.7=min(0.9, 0.7)=0.7. This value is then used to implicate the term set small of the variable AmountOfTip. Implication modifies the shape of the term set. There are various methods, but the two most popular ones are scaling and clipping. In scaling, the whole term set is multiplied by the degree of support (0.7, in this case) to yield another term set. In clipping, the term set is clipped at the degree of support value to yield a trapezoidal term set.
Aggregation
In this step, all the implicated fuzzy term sets of the output variable are combined using fuzzy logic operations to yield one fuzzy set. For our SizeOfTip variable, this means that its three implicated term sets (corresponding to the original Big, Average, and Small term sets) will be combined to create one big set. A simple way to do that would be to take the maximum of the three sets at each point (see Figure 2).
Defuzzification
Finally, the aggregated term set of the last step is used to compute a single crisp value for our output variable. The most widely used method is to take the centroid of the term set as its crisp value. Other methods are possible including taking the maximum value, or the average of the peaks.
We can see here that if a rule is not satisfied very well, then its degree of support will be close to 0. This, then, will implicate its term set by a large amount, reducing the contribution of this rule to the aggregated fuzzy set. This will, in turn, reduce its effect on the computed values of the output variables.
Systems with multiple output variables can be treated as multiple systems, each with a single output variable.
Getting and Installing the Module
You can grab a copy of AI::FuzzyInference from your local CPAN mirror at http://search.cpan.org/author/aqumsieh. The latest version, as of this writing, is 0.03. You can install it using the traditional method:
perl Makefile.PL make make test make install
If you're on Windows, you can simply type "ppm install AI::FuzzyInference" at a command prompt. Alternatively, since it's all in pure Perl, you can unpack it in any place where perl will find it.
An Example: Balancing Act
Armed with our knowledge of FL and FIS's, we can now proceed to use AI::FuzzyInference in an example. Let's assume we have a solid horizontal 10-meter-long rod hinged exactly in its middle, with a ball placed on top of it. Furthermore, let's simplify things by assuming our world is two-dimensional, so we won't worry about the z-axis. We would like to be able to control our rod so as to balance the ball on it, and prevent it from falling off.
First, we have to create our AI::FuzzyInference object. That's easy since the constructor takes no arguments:
use AI::FuzzyInference my $fis = new AI::FuzzyInference;
Now, we have to define our input and output variables. We need variables to capture the states of the ball and the rod. For the ball, we define two variables: $velBall and $posBall. $velBall specifies the current velocity of the ball, where negative values indicate motion to the left. $posBall indicates the current position of the ball on the rod with 0 being the center of the rod and positive values to the right. Those will be our input variables. For the rod, we define a variable $thRod that is the angle the rod currently makes with the x-axis, where positive values indicate clockwise displacement. This is our output variable. This means that the angle that the rod makes with the horizontal is a function of the velocity and position of the ball.
To complete our variable definitions, we have to define the term sets associated with them. Those will be as defined in Figure 3. The way you pass this information to the AI::FuzzyInference object is as follows:
$fis->inVar(posBall => -5, 5,
far_left => [-4, 1, -2, 0],
left => [-4, 0, -2, 1, 0, 0],
center => [-2, 0, 0, 1, 2, 0],
right => [0, 0, 2, 1, 4, 0],
far_right => [2, 0, 4, 1],
);
The first argument of the inVar() method is the name of the input variable. The next two arguments define the limits of the values the variable can take (aka, the universe of discourse). The rest of the arguments are key-value pairs that define each term set along with its coordinates. Those coordinates are simply lists of x, y values. Successive points are connected together by a straight line. If the given coordinates of a term set do not span the whole universe of discourse, then AI::FuzzyInference will automatically extrapolate, by extending the first and last points horizontally, to complete the definition.
Similarly, we define our other input variable, $velBall. Our output variable, $thRod, is defined using the outVar() method, which has the exact same arguments as inVar().
The next step is to define the rules. Here, we use our common sense to decide what to do in each scenario in order to keep the ball on the rod. One rule can be:
If $posBall is far_left AND # ball is close to left edge of rod
$velBall is slow AND # ball almost stationary
THEN $thRod is medium_pos # lower the right edge by small # amount
In general, if all input variables have the same number of term sets, the number of possible rules is TSVARS where TS is the number of term sets for each variable, and VARS is the number of input variables. We use the method addRule() to define our rules. So, for the rule declared above, we write:
$fis->addRule(
'position = far_left &
velocity = slow' => 'thRod = medium_pos',
);
The arguments of addRule() are key-value pairs. We can define multiple rules in the same call to addRule(), or in multiple calls. The key of each pair is the precedent string, and the value is the consequent string. Spaces are completely optional and will be ignored. Each precedent and consequent string is composed of variable = term_set. Multiple precedents are combined using & and | for AND and OR, respectively. The equality can be reversed by using the ! symbol, such as position = !far_left.
We round off our program with a subroutine, calcNewData(), which calculates the position and velocity of the ball after one time step has elapsed. And that is it—we are now ready to relinquish control of the rod to our FIS. In each time step, we calculate the current position and velocity of the ball, and we pass them on to our FIS, which will spit out a new value for the angle of the rod. We do this by using the compute() method, which takes as input key value-pairs where the keys are the input variable names, and the values are the corresponding numerical values:
$fis->compute(posBall => 0.9, #current ball position
velBall => -1.5, #current ball speed
);
This is the procedure that does all the work going through the Fuzzification -> Inference -> Aggregation -> Defuzzification loop. After that, the value() method is used to get the newly computed value for the output variable thRod:
$thRod = $fis->value('thRod');
Then we loop back to the next time step. To better visualize this, the Perl program uses Tk to draw the rod with the ball balanced on top of it at each time step.
Running the program from random initial conditions, we can observe the behavior shown in Figure 4. The x-axis is time, and the y-axis is the position of the ball on the rod. As we would expect, the ball oscillates from one side to the other as our system struggles to control it. As the system gains more control of the ball, the oscillations die down.
Concluding Remarks
Rules. You do not have to define rules for ALL possible combinations of input variables. Any rule you do not define will not produce any change in the system when its associated scenario is encountered. Having said that, it is useful to specify as many rules as possible, since this will constrain your system more. In our case, we specify all the rules (see Listing 1; also available for download at http://www.tpj.com/source/), which enhances our chances of controlling the ball. Removing some rules might cause more oscillation before the ball stops, or even prevent the system from controlling the ball altogether.
Moreover, choosing the correct response for every combination of input variables might not be a very easy thing to do in itself. One problem is that those rules are not set in stone. So, what constitutes common sense to one person might be considered ridiculous to another. Another problem is the sheer number of rules needed as the number of variables increases. This easily becomes the case if we have four or five input variables or more. Therefore, most people design their FISs with the smallest number of input variables possible to keep things under control. Of course, this hasn't deterred other researchers from using various techniques and heuristics to tackle such problems. Some interesting approaches use evolutionary and biologically inspired techniques such as neural networks and genetic algorithms to make the system "evolve" and "learn" its own rules. But this is a topic for another article.
Variables. In this example, I chose a relatively simple system where the output is a function of only two variables. Some systems are even simpler and contain just a single input variable. Indeed, in our case, we could find rules that define the angle of the rod in terms of the ball's position only. Conversely, some systems are much more complicated. Initially, I designed the system to have three input variables: ball position, ball speed, and rod angle. The output variable was the change in the angle of the rod. I opted for the simpler version (yet not too simple) to avoid unnecessary complications. I would be interested in hearing from anyone who uses AI::FuzzyInference to design a system with more than two variables.
The AI::FuzzyInference Module
Finally, keep in mind that the module does not have too many checks integrated yet. So, if in your rules you use term sets or variables that are not defined (due to a typo for example), then the module will not warn you, and you might get "use of uninitialized value" warnings. Please check your code before you send in those bug reports :) Comments and suggestions regarding the module are greatly appreciated.
Listing 1
#!perl -w
use strict;
use Tk;
use Tk::LabEntry;
use AI::FuzzyInference;
use constant PI => 3.1415927;
use constant G => 9.81;
my $halfLenRod = 5;
my $timeStep = 0.05;
my $thRod; # between -30 and 30 degrees.
my $velBall; # ball's velocity. From -15 .. 15 m/s
my $posBall; # ball's position. From -5 .. 5 m
my $time = 0;
# initialize.
$thRod = -10;
$velBall = -2;
$posBall = 4;
# create the FIS.
my $fis = new AI::FuzzyInference;
# define the input variables.
$fis->inVar(posBall => -5, 5,
far_left => [-4, 1, -2, 0],
left => [-4, 0, -2, 1, 0, 0],
center => [-2, 0, 0, 1, 2, 0],
right => [0, 0, 2, 1, 4, 0],
far_right => [2, 0, 4, 1],
);
$fis->inVar(velBall => -15, 15,
fast_neg => [-9, 1, -3, 0],
medium_neg => [-9, 0, -3, 1, 0, 0],
slow => [-3, 0, 0, 1, 3, 0],
medium_pos => [0, 0, 3, 1, 9, 0],
fast_pos => [3, 0, 9, 1],
);
# define the output variable.
$fis->outVar(thRod => -30, 30,
large_neg => [-20, 1, -10, 0],
medium_neg => [-20, 0, -10, 1, 0, 0],
small => [-10, 0, 0, 1, 10, 0],
medium_pos => [0, 0, 10, 1, 20, 0],
large_pos => [10, 0, 20, 1],
);
# now define the rules.
$fis->addRule(
'posBall=far_left & velBall=fast_neg' => 'thRod=large_pos',
'posBall=far_left & velBall=medium_neg' => 'thRod=large_pos',
'posBall=far_left & velBall=slow' => 'thRod=medium_pos',
'posBall=far_left & velBall=medium_pos' => 'thRod=medium_pos',
'posBall=far_left & velBall=fast_pos' => 'thRod=medium_pos',
'posBall=left & velBall=fast_neg' => 'thRod=large_pos',
'posBall=left & velBall=medium_neg' => 'thRod=medium_pos',
'posBall=left & velBall=slow' => 'thRod=medium_pos',
'posBall=left & velBall=medium_pos' => 'thRod=medium_pos',
'posBall=left & velBall=fast_pos' => 'thRod=medium_pos',
'posBall=center & velBall=fast_neg' => 'thRod=large_pos',
'posBall=center & velBall=medium_neg' => 'thRod=medium_pos',
'posBall=center & velBall=slow' => 'thRod=small',
'posBall=center & velBall=medium_pos' => 'thRod=medium_neg',
'posBall=center & velBall=fast_pos' => 'thRod=large_neg',
'posBall=right & velBall=fast_neg' => 'thRod=medium_neg',
'posBall=right & velBall=medium_neg' => 'thRod=medium_neg',
'posBall=right & velBall=slow' => 'thRod=medium_neg',
'posBall=right & velBall=medium_pos' => 'thRod=medium_neg',
'posBall=right & velBall=fast_pos' => 'thRod=large_neg',
'posBall=far_right & velBall=fast_neg' => 'thRod=medium_pos',
'posBall=far_right & velBall=medium_neg' => 'thRod=medium_neg',
'posBall=far_right & velBall=slow' => 'thRod=medium_neg',
'posBall=far_right & velBall=medium_pos' => 'thRod=large_neg',
'posBall=far_right & velBall=fast_pos' => 'thRod=large_neg',
);
drawGUI();
MainLoop;
# this subroutine calculates the new values of the ball's position
# and velocity after a period of time $timeStep.
# Friction is not modeled.
sub calcNewData {
my $acc = G * sin ($thRod * PI / 180);
my $Vnew = $velBall + $acc * $timeStep;
my $dist = $velBall * $timeStep + 0.5 * $acc * $timeStep * $timeStep;
$velBall = $Vnew;
$posBall += $dist;
$velBall = 15 if $velBall > 15;
$velBall = -15 if $velBall < -15;
$time += $timeStep;
}
# This sub draws the gui.
sub drawGUI {
my $mw = new MainWindow;
my $canvas = $mw->Canvas(qw/-bg black -height 400 -width 600/)->pack;
$canvas->createLine(0, 0, 0, 0, qw/-width 2 -fill white -tags ROD/);
$canvas->createOval(0, 0, 50, 50, qw/-fill green -tags BALL/);
my $f = $mw->Frame->pack(qw/-fill x/);
my $dth;
$f->Button(-text => 'run',
-command => sub {
my $id;
$id = $canvas->repeat(100 => sub {
# update the ball's data.
calcNewData();
# check for termination conditions.
# stop if ball is almost stationary and the rod
# is almost flat.
if (abs($velBall) < 0.005 && abs($thRod) < 0.001) {
print "Simulation ended.\n";
$canvas->afterCancel($id);
return;
}
# stop if ball fell off the rod.
if ($posBall > $halfLenRod or $posBall < -$halfLenRod) {
print "Ball fell off the rod!\n";
$canvas->afterCancel($id);
return;
}
# compute the new angle of the rod.
$fis->compute(posBall => $posBall,
velBall => $velBall);
$thRod = $fis->value('thRod');
# update our drawing.
updateCanvas($canvas);
});
})->pack(qw/side left -ipadx 10/);
$f->LabEntry(-label => 'Ball Pos',
-textvariable => \$posBall,
)->pack(qw/-side left -padx 10/);
$f->LabEntry(-label => 'Ball Speed',
-textvariable => \$velBall,
)->pack(qw/-side left -padx 10/);
$f->LabEntry(-label => 'Rod Angle',
-textvariable => \$thRod,
)->pack(qw/-side left -padx 10/);
updateCanvas($canvas);
}
# This subroutine draws the rod at its current angle, and
# the ball at its current position.
sub updateCanvas {
my $c = shift;
my $ly = 200;
my $dy = int(40 * $halfLenRod * tan(PI * $thRod / 180));
$c->coords(ROD => 100, $ly - $dy, 500, $ly + $dy);
my $by = 150 + $posBall * $dy / $halfLenRod;
my $bx = 100 + (5 + $posBall) * 40;
$c->coords(BALL => $bx - 25, $by, $bx + 25, $by + 50);
}
# tangent sub.
sub tan { sin($_[0]) / cos($_[0]) }
