Research on Cellular Automata Fuzzy Logic Hybrid Control Systems Algorithm (CAFL)
This project started in the September 2006 time frame. Previous to that I had reread
Upon reading the book the first time, I could see how the notion of Cellular Automata could be applied to control systems and modelling. My line of thinking was that something in CA (Cellular Automata) could be used for control system and modelling as an alternative to traditional PID (Proportional, Integrator and Derivative) control. In fact from an algorithmic standpoint using the simple logic behind CA looked to me as if you could obtain closed form solutions to control systems and even software coding problems. By software coding problems, I mean translating the control system mathematics and algorithms into lines of software. This is typically done today in modern day control systems. Today more frequently than not designers of control systems are using a microprocessor or microcontroller in place of discrete hardware controls, such as op-amps and TTL logic.
In 2006 I read some articles on Fuzzy Logic and a Fuzzy Logic tutorial. I also did some reading on so called expert systems and AI(Artificial Intelligence), look in Wikipedia under any of these topics. I started "digging" down from Wikipedia into all of these categories, so that represents and provides reference to the path of my learning on the topic.
Researching Fuzzy Logic lead me to think that a merge of FL(Fuzzy Logic) and CA might be an approach to algorithms for a workable control system. I did some initial theoretical work which these notes outline. After this I wrote C language software that simulated CA-FL control systems using tables of numbers for input and feeding output to a file for analysis after the program had ran.
These notes are by no means complete and lack some of the background information on the topic. That would require a read of A New Kind of Science, all of it is available for reading on-line. Also a primer on Fuzzy Logic and how they work with control systems would be required reading as well. Refer to Wikipedia and the links given on this site. None the less these notes represent something I may continue to experiment with in the future. See also the page on software projects on this site for more information on cellular automata.(11/05/2007)
1.0 CA- Rule Chart
CA-shorthand Bit-Weight Binary
XXX 128 MSB 10000000
XX0 64 01000000
X0X 32 00100000
X00 16 00010000
0XX 8 00001000
0X0 4 00000100
00X 2 00000010
000 1 LSB 00000001
Rules take the form of if (LEFT = X AND CENTER = X AND RIGHT = X THEN Y = TRUE) OR (NEXT RULE)....OR (LAST RULE)
Ex: Rule 30
if(LEFT = X & CENTER !=X & RIGHT !=X) | (LEFT != X & CENTER =X & RIGHT =X) | (LEFT != X & CENTER =X & RIGHT !=X) | (LEFT != X & CENTER !=X & RIGHT =X) then next-element = TRUE
1.1. Compound Notation of rule 30: X00 | 0XX | 0X0 | 00X, rule 16 OR rule 8 OR rule 8 OR rule 4 OR rule 2
Rule 30 Chart
CA-shorthand Bit-Weight Binary
X00 16 00010000
0XX 8 00001000
0X0 4 00000100
00X 2 00000010
------------------------------------------------
The above OR'ed 30 00011110
2.0 FL - Matrix notation
Columns formed by current value or proportional error. Turned into a tristate logic of..
2.1.1. Is the error negative. The command(setpoint) is less than the measured value.
2.1.2. The error is zero. The command(setpoint) matches the actual.
2.1.3. Is the error positive. The command(setpoint) is greater than the measured value.
Rows are formed by the first derivative of the error. This is turned into a tristate logic of.....
2.2.1. Is the error-dot(1st Deriv of error) negative. The command(setpoint) will be less than the measured value in the future if the control output is maintained on its current course.2.2.2. The error-dot is zero. The command(setpoint) matches the actual and will continue if the control output is maintained on its current course and the system has reached equilibrium or has zero system inertia.
2.2.3. Is the error-dot positive. The command(setpoint) will be greater than the measured value in the future if the control output is maintained on its current course.
error = cmd - sig
col[0] col[1] col[2]
- 0 +
row[0] - N P P
DER row[1] 0 N NC P
row[2] + N N P
The center of the matrix is the control outputs. Depending on where the inputs fall they call out an element of the matrix which forms the output of the control system. The outputs are N-(a negative value) , P-(a positive value), NC-(no change, set output to 0).
The magnitudes of the outputs are chosen empirically based on system response. There is no reason that they have to be equal. IE: The N and P's for derivative behavior and error = 0 could be set higher or lower to control overshoot.
Deadbanding is possible, it is possible to form a deadband of non-action(zero output) around error = 0 or error-dot = 0. It can be of the form (error < 1 & error > -1) to form a deadband around the zero region. The idea is to open up a range around zero which is more realistic than hitting a discrete value in a real world system.
It is possible to extend the simple matrix to more values in either or both columns. An example follows.
error = cmd - sig
col[0] col[1] col[2] col[3] col[4]
V- - 0 + V+
row[0] V- N N P P P
row[1] - N n p p P
DER row[2] 0 N n NC p P
row[3] + N n n p P
row[4] V+ N N N P P
In the extended matrix there is a concept of very-negative and very-positive for both error and error-dot. Along with these inputs there are outputs designated small-n, small-p,large-N,large-P. These values represent both the empirically tuned small and large magnitudes for the control system output, based on the table lookup of the input values. The very-negative and very-positive thresholds are also empirically tuned along with any non-action deadbanding around the zero-point. All values can be chosen independently. Depending on the situation the negative and positive values may not even be symmetric. The error and error-dot input thresholds and output responses may also be chosen independently,depend on the needs of the control system.
3.0 CA-FL Merged
3.1. Striped down CA based on tristate input and output. Input based on error = cmd - sig.
(IF element = POSITIVE THEN SET OUTPUT NEGATIVE) | (IF element = NEGATIVE THEN SET OUTPUT POSITIVE) | (IF element = 0 THEN SET OUTPUT 0)
Note: Instead of setting a new element as an output in linear time, typical CA-machine behavior. The CA-FL uses the control output as an indirection, the output of the logic is directed to an element that represents the control output and will in time become an element of the system. IE: Apply an output and it will through cause and effect change the next-element in the CA system via the feedback loop.
3.2. Adding derivative and using a positive and negative CA-matrix. Deriv. is treated as yet another input element in the CA decision logic(such as CENTER NEIGHBOR CELL-LEFT NEIGHBOR CELL-RIGHT NEIGHBOR CELLS), both are treated as tristate inputs. The CA-matrix is split into a positive and negative cells for clarity.
(left columns error term, right columns error-dot)
Positive output Negative-Output Bit-Weight(magnitude)
NN PP 8
N0 P0 4
0N 0P 2
00 00 1
XX XX 0
3.3. Symmetric logic table
Bit-Weight CA-shorthand Logic Evaluation Control Output
8 NN-(IF error = positive AND error-dot = positive) output = POSITIVE
4 N0-(IF error = positive AND error-dot = 0 ) output = POSITIVE
2 0N-(IF error = 0 AND error-dot = positive ) output = POSITIVE
1 00-(IF error = 0 AND error-dot = 0 ) output = POSITIVE - Not Normally Used
0 XX-(IF error = DNC AND error-dot = DNC ) output = 0 - DNC(don't care, turn off outputs)
1 00-(IF error = 0 AND error-dot = 0 ) output = NEGATIVE - Not Normally Used
2 0P-(IF error = 0 AND error-dot = negative ) output = NEGATIVE
4 P0-(IF error = negative AND error-dot = 0 ) output = NEGATIVE
8 PP-(IF error = negative AND error-dot = negative) output = NEGATIVE
In order to get a CA like response; Changing an element in the next row based on the nearest neighbor rules. (See rule 30 above) The ANDed results above may be OR'ed together to form a rule in some instances. Such as Rule 8+4+2 = 14 output will set a certain value in a control system. EX:That is if NN|N0|0N occurs set fan = ON // Need better example, more reasoning for the OR'ing.
3.4. Negative and positive CA-table bit weight representations
CA-shorthand Bit-Weight Binary Pos-Out Binary Neg-Out CA-shorthand
NN 8 1000 NN
N0 4 0100 N0
0N 2 0010 0N
00 1 0001 00
XX 0 0000 0000 XX
00 1 0001 00
0P 2 0010 0P
P0 4 0100 P0
PP 8 1000 PP
3.4.1 Rules based output
A basic rationale is the more the bit weight drives away from zero the more responsive the control system should be to drive its system value to the setpoint. This is where the resemblance to FL comes in. The control output here is much like the FL center of the matrix being the control outputs. Remember from section 2 above, depending on where the inputs fall they call out an element of the matrix which forms the output of the control system. The FL outputs are N-(a negative value) , P-(a positive value), NC-(no change, set output to 0).
3.4.2 The magnitudes of the outputs in CA-FL are once again chosen empirically based on system response. There is no reason that they have to be equal. IE: The control output for the derivative behavior and error = 0 could be set higher or lower to control overshoot.
CA-shorthand Bit-Weight Binary Pos-Out Binary Neg-Out Control Output
NN 8 1000 10
N0 4 0100 5
0N 2 0010 1
00 1 0001 0
XX 0 0000 0000 0
00 1 0001 0
0P 2 0010 -1
P0 4 0100 -5
PP 8 1000 -10
3.4.3 Instead of the FL matrix in CA-FL we have a control output table. It is possible to create a rule such as Rule 14 for the example of fan on and off above by choosing a binary OR'ed combination of rules.
Rule 14 fan example
CA-shorthand Bit-Weight Binary Pos-Out Binary Neg-Out Control Output
NN 8 1000 FAN on
N0 4 0100 FAN on
0N 2 0010 FAN on
--------------------------------------------------------------------------
(NN|N0|0N) 14 1110 FAN on
3.5 Other terms, such as integration.
3.5.1 Basic terms are considered error, error-derivative, error-integrator. The analogy with the nearest neighbor rules from CA that the CA-FL control system uses for these are, present-position,future-position and past-position. Using all 3 gives a logic table similar to the CA rules for 3 nearest neighbors, LEFT,CENTER and RIGHT determining what the new element position down one row will do. Except in a control system past,current and future positions will determine the output of the control system which will change the 'element' (system value)through cause-effect feedback. The example control output values show how different control efforts can be chosen depending on the state of the past,present,future positions(Integrator,Proportional,Derivative).
(Example)
CA-shorthand Bit-Weight Binary Pos-Out Binary Neg-Out Control Output
NNN 128 MSB 10000000 8
NN0 64 01000000 6
N0N 32 00100000 6
N00 16 00010000 1
0NN 8 00001000 5
0N0 4 00000100 1
00N 2 00000010 1
000 1 LSB 00000001 0
XXX 0 00000000 00000000 0
000 1 LSB 00000001 0
00P 2 00000010 -1
0P0 4 00000100 -1
0PP 8 00001000 -5
P00 16 00010000 -1
P0P 32 00100000 -6
PP0 64 01000000 -6
PPP 128 MSB 10000000 -8
4.0 Consideration of mixed cases.
4.1 So far the examples have had only a negative or positive response separate combined with zero, to keep it simple. Other valid cases in the CA-FL control space such as NN0 or PP0, PN0 or NNP, etc. have not been considered and need to be expanded on.
One way to look at it is as a base 3 number system with 0,N,P and lay out the table according to that system. Call 0 = 0,N = 1, P = 2, for example. There are 3 symbol P,N,0 and the table must contain all combinations 3*3*3 = 27 of them. Any of them may occur during the operation of the control system. All of them need a binary representation and control output value assigned to them.
(Example)
CA-shorthand Posn. Bit-Weight Control Output
PPP 26 67108864 -8
PPN 25 33554432 0
PP0 24 16777216 -6
PNP 23 8388608 0
PNN 22 4194304 0
PN0 21 2097152 0
P0P 20 1048576 -6
P0N 19 524288 0
P00 18 262144 -1
NPP 17 131072 0
NPN 16 65536 0
NP0 15 32768 0
NNP 14 16384 0
NNN 13 8192 8
NN0 12 4096 6
N0P 11 2048 0
N0N 10 1024 6
N00 9 512 1
0PP 8 256 -5
0PN 7 128 -1
0P0 6 64 -1
0NP 5 32 1
0NN 4 16 5
0N0 3 8 1
00P 2 4 -1
00N 1 2 1
000 0 1 0
4.1.1 It is possible to declare mixed states as output = 0 as done above and just worry about states that do not mix N and P. In the real world however the current-position value with go from N to 0 and then overshoot on to P, while the future-position term with show a positive slope and serve as a leading indicator that the setpoint will be crossed. // Does this make sense, needs to be thought through more.
Approach setpoint from below. Current-position = N, Future-position = P OUTPUT = 1
Current-position = 0, Future-position = P OUTPUT = 0
Current-position = P, Future-position = 0 OUTPUT = -1 (Slope is zero when output is zero)
Current-position = 0, Future-position = N OUTPUT = 0
4.2 Instead of using a derivative, future-position could instead be a ded-reckoned predictor of what the error will be in the future(next timing loop,cycle or a period of time ahead for analog). The system could behave like an expert system and learn based on past experience what the next position might be and deduce the future-error from that.
past error = error(t-1) = cmd(t-1) - sig(t-1) (saved history from 1 unit of time before)
present error = error(t) = cmd(t) - sig(t)
future error = error(t+1) = cmd(t+1) - (ded-reckoned sig) where ded-reckoned sig = sig - slope of error per 1 unit of time
future error = present error - (past error - present error)
ex: past error = 75-25 = 50
present error = 75-26 = 49
future error = 49 - (50-49) = 49 - 1 = 48
4.3 Forward projections, navigation principle, using learned values to follow the shortest path.
4.3.1. The objective with future-position would be to project forward using the ded-reckoning analogy a position target one time period forward. Like in navigation where a fix is taken and from that position the ships position is reckoned by deducing it from heading and speed with corrections for wind & sea current direction and speeds. Then at some point a new fix is taken, from this new fix it is possible to look at the deviation-error in the estimated reckoning.
In the control system case this relationship is shifted. The control systems fix is the reading of the signal value(present-position), it then ded-reckons the next(future-position). Better yet it projects forward a line towards toward its target where error = 0. It projects this line forward a reasonable amount of time and uses this value as future position. This gives it a 'derivative-like' term that tells the control system which way to point and allows it to adjust its magnitude and direction(sign) accordingly. Futhermore this term could be a learned response based on past system behavior, it learns how to drive itself towards the setpoint, using a map of past cases. Also while it is approaching the setpoint it can keep track of how close its deduced future signal points are to the measured current values and apply course corrections based on this offset.
4.3.2 Past position can play an important role much like the typical integrator term in that if there is steady state system error it will appear in the past-position(signal history), from this a small offset can be generated to bring the system to the cmd = sig state.
4.3.3 An example.
Ex: The control system commands 75, the time = 0 signal is 25.
a. The error is 75-25 = 50 which is positive so the system applies an output of 6.
b. The control system commands 75, the time = 1 signal is 30. It sees that an output of 6 only raises it by 5. So it projects forward a future position of 35 based on an output of 6. It decides to increase its output to 7.
c. The control system commands 75, the time = 2 signal is 36. It sees that an output of 7 has raised it by 6. So it projects forward a future position of 42 based on an output of 6. It decides to maintain its output at 6.
d. The control system commands 75, the time = 3 signal is 41. It sees that an output of 7 has raised it by 5. So it projects forward a future position of 46 based on an output of 7. It decides to increase its output to 8.
e. The control system commands 75, the time = 4 signal is 47. It sees that an output of 8 has raised it by 6. So it projects forward a future position of 53 based on an output of 8. It decides to maintain its output at 8.
f. The control system commands 75, the time = 5 signal is 53. It sees that an output of 8 has raised it by 6. So it projects forward a future position of 59 based on an output of 8. It decides to maintain its output at 8.
g. The control system commands 75, the time = 6 signal is 59. It sees that an output of 8 has raised it by 6. So it projects forward a future position of 65 based on an output of 8. It decides to maintain its output at 8.
h. The control system commands 75, the time = 7 signal is 65. It sees that an output of 8 has raised it by 6. So it projects forward a future position of 71 based on an output of 8. It decides to maintain its output at 8.
i. The control system commands 75, the time = 8 signal is 71. It sees that an output of 8 has raised it by 6. So it projects forward a future position of 77 based on an output of 8. It decides to reduce the output to 5 based on the fact that an output at 8 raising it 6, when it needs only 4.
j. The control system commands 75, the time = 9 signal is 75. It sees that an output of 5 has raised it by 4. So it projects forward a future position of 79 based on an output of 5. It decides to reduce the output to 0 based on the fact that is at its setpoint.
k. The control system commands 75, the time = 10 signal is 76. It sees that an output of 0 has raised it by 1. So it projects forward a future position of 77 based on an output of 0. It decides to make the output -1 based on the fact that system inertia is raising it above the setpoint.
l. The control system commands 75, the time = 9 signal is 75. It sees that an output of -1 has raised it by 1. So it projects forward a future position of 74 based on an output of -1. It decides to set 0 based on the fact that is at its setpoint.
The system will stay in eqilibrium between states j,k,l indefinitely until either a new command level is set or some external force drives the setpoint up or down. The system could also save the fact that it should output 8 from the start when it starts from 25 to go to an amount greater than 50. This assumes that it is trying to obtain a ramp rate of 6 per unit time.
4.4 How does CA-FL do this control navigation.
4.4.1 ILP- Input Logic Predicate section
The first area it implements in software or hardware is its logic table.
Symmetric logic table
Bit-Weight CA-shorthand Logic Evaluation Control Output Baseline Value
8 NN-(IF error = positive AND error-dot = positive) output = POSITIVE 5
4 N0-(IF error = positive AND error-dot = 0 ) output = POSITIVE 1
2 0N-(IF error = 0 AND error-dot = positive ) output = POSITIVE 1
1 00-(IF error = 0 AND error-dot = 0 ) output = POSITIVE 0 - Not Normally Used
0 XX-(IF error = DNC AND error-dot = DNC ) output = 0 0 - DNC(don't care, turn off outputs)
1 00-(IF error = 0 AND error-dot = 0 ) output = NEGATIVE 0 - Not Normally Used
2 0P-(IF error = 0 AND error-dot = negative ) output = NEGATIVE -1
4 P0-(IF error = negative AND error-dot = 0 ) output = NEGATIVE -1
8 PP-(IF error = negative AND error-dot = negative) output = NEGATIVE -5
This could be implemented in software similarly to the FL table below.
error = cmd - sig
col[0] col[1] col[2]
- 0 +
row[0] - N P P
DER row[1] 0 N NC P
row[2] + N N P
4.4.2 PPF-Position navigation section (past-present-future)
It then has a section that keeps track of the following...
past error = error(t-1) = cmd(t-1) - sig(t-1) (saved history from 1 unit of time before)
present error = error(t) = cmd(t) - sig(t)
future error = error(t+1) = cmd(t+1) - (ded-reckoned sig) where ded-reckoned sig = sig - slope of error per 1 unit of time
Based on how close the future error(t+1) is to error(t), when it gets there! Make a predication and then check the prediction. The control system adjusts the baseline values up or down. The ideal system will approach its setpoint in the form of a tractrix curve. The tractrix is like pulling a cart with a steered front axle. Imagine the cart perpendicular to the direction that you start traveling. The cart will quickly turn while it starts moving, to pull in line with the direction of travel, without over shoot. The idea is for the model of the system ramp rate to follow this curve. The most efficient and shortest distance path, with out overshoot. In plain language this means the system comes on strong if it is far away from the setpoint but then tapers off just in time to pull in line with the system setpoint.
4.4.1: The cart is perpendicular to the axis. You pull the handle, the front axle swivels, 'predicting' the direction of travel.
4.4.2: The cart moves, its center, the midpoint between the front and rear axle and the midpoint across its breadth, is the present position of the cart.. This moves toward the line that you are traveling in which is the setpoint moving forward in time. Here we are considering the distance you travel the equivalent of time for this example.
4.4.3: The rear axle passes through the same point that the center of the cart does but it does so later, it does it a distance away from the point where the center crossed the line of travel. It represents the past-position.
4.4.4: Imagine what the cart does in equilibrium, all 3 points are in line with the direction that you are pulling, this is the objective of the control system.
4.4.5. The curve described by how the cart approached this line is called a tractrix.
4.4.6 Using PPF
To do this it needs a history array such as this...
error[t-1] future-error[t-1]
error[t] future-error[t]
By comparing error[t] against future-error[t-1] the system produces a value that allows it to change its output value from the baseline.
course-deviation = error[t] - future-error[t-1]
Control output = baseline + (course-deviation * gain)
The control system needs a model of the approach curve to allow it to approach the setpoint.
Control output = lim(curve)
It is applied as a limiter to control the ramp rate of the output. The system may be limited beyond this ramp-rate by other real world device limitations.
4.4.3 Table, expert system model based on past cases.
The system can be set up with a table that holds a history of what inputs will generate what responses. This gives it the ability to have certain starting points in the future. This also provides fault tolerance to 'cover' for missing sensors using the ??? table. It allows the system to operate with an open loop gain based on the ??? table to allow a best-fit procedure for the tractrix curve.5.0 Try example in code using error = cmd - sig, use the following logic to generate an output.
Symmetric logic table
Bit-Weight CA-shorthand Logic Evaluation Control Output
2 N-(IF error = positive ) output = POSITIVE 1
1 0-(IF error = 0 ) output = POSITIVE 0 - Not Normally Used
0 X-(IF error = DNC ) output = 0 0 - DNC(don't care, turn off outputs)
1 0-(IF error = 0 ) output = NEGATIVE 0 - Not Normally Used
2 P-(IF error = negative ) output = NEGATIVE -1
Use this style of coding based on this pseudocode in BASIC....
past present future
230 if point(x-1,y) <> 15 and point(x,y) <> 15 and point(x+1,y) <> 15 then pset(x,y+1),a[7]
240 if point(x-1,y) <> 15 and point(x,y) <> 15 and point(x+1,y) = 15 then pset(x,y+1),a[6]
250 if point(x-1,y) <> 15 and point(x,y) = 15 and point(x+1,y) <> 15 then pset(x,y+1),a[5]
260 if point(x-1,y) <> 15 and point(x,y) = 15 and point(x+1,y) = 15 then pset(x,y+1),a[4]
270 if point(x-1,y) = 15 and point(x,y) <> 15 and point(x+1,y) <> 15 then pset(x,y+1),a[3]
280 if point(x-1,y) = 15 and point(x,y) <> 15 and point(x+1,y) = 15 then pset(x,y+1),a[2]
290 if point(x-1,y) = 15 and point(x,y) = 15 and point(x+1,y) <> 15 then pset(x,y+1),a[1]
300 if point(x-1,y) = 15 and point(x,y) = 15 and point(x+1,y) = 15 then pset(x,y+1),a[0]
if(error > 0) then output = o[0]
else if(error < 0) then output = o[1]
else output = 0
5.1 Modify the Control output by using the following values
error[t-1] future-error[t-1]
error[t] future-error[t]
course-deviation = error[t] - future-error[t-1]
Control output = baseline + (course-deviation * gain)
5.2 ....
Original Build Date:11-06-2007
Last updated 11-07-2007