Title: The Proto Classifier System (PCS) Author name: Jan Ørbech Pedersen Address: Fuglebakken 58D DK-7000 Fredericia Denmark E-mail address:
[email protected]
Phone number: +45 30128418 Abstract:
The purpose of this work is to examine an implementation of LCS, which I call PCS (Proto Classifier Systems). It is my hypothesis that the PCS architecture can be used to a variety of AI tasks where I focus on a special instance of SLAM for autonomous mobile robots. My method is to simulate the SLAM problem in Mathematica and to provide further speculation. The simulation was a success and the AI vocabulary was used for further deliberation and plans for implementations. The importance of the experiment is that a robot with minimal sensor configuration can navigate its surroundings Keywords: Learning Classifier System, robotics, artificial intelligence, machine learning, knowledge representation.
1
Introduction
1.1
Sources of inspiration
Section 1 is the introduction, where I list my inspiration and the hypothesis I want to test. Section 2 described the experimental work used to test the hypothesis. Section 3 indicates further use of the model by showing a pure thought experiment in computer vision, section 4 is the conclusion and finally section 5 contains a reading list. My inspiration for PCS comes from three sources. The first is Jeff Hawkins who has analyzed the workings of the brain in [1]. Later he founded the Numenta company and introduced an inspirational architecture [2]. The second inspiration is from Learning Classifier Systems themselves [3]. The third inspiration is from Karl Poppers theory of knowledge [4] and his notion of a falsifiable theory. I discuss all three below. 1.1.1
Jeff Hawkins
Jeff Hawkins has analyzed the workings of the brain and one of his conclusions is that intelligence is based on prediction of sequences of patterns. The brain looks for input patterns, classifies these, aggregates into sequences and forms invariants. Invariants are entities in the brain, which are activated, no matter what sequences of input patterns are presented. For instance if you count the number of red and blue balls in a jar, the invariant 3 red balls and 1 blue ball is formed by both sequences RRRB and RBRR. The brain is made of columns of neurons organized in a hierarchical fashion and it is this organization, which implements the mentioned cognitive mechanism. Later these ideas are put in computer form in terms of the HTM (Hierarchical Temporal Memory) by Numenta. The notions of cell, cell-activation, synapses, potential synapses, dendrite segments and columns are introduced. All these constructs are heavily inspired by neural science and neural networks. I have been inspired by Numenta’s work in the following sense. His notion of a column corresponds to my classifier Niche, a sequence is a time sequence and a cell is a classifier. The organization into a hierarchy is accomplished by pointers between classifiers. 1.1.2
Learning Classifier Systems
Since John Holland and others introduced these ideas in the 70’s mountains of work has been done in terms of experimentation and theoretical analysis, which is a good starting point for any investigation. I choose LCS because I was already familiar with genetic algorithms and because I saw some similarities between these ideas and the ideas of Jeff Hawkins. I see a lot of versatility and simplicity in these models. The number of key concepts are few and the architecture as simple as you can get it. Special instances of these models are Turing complete, so you can program anything in them (given time and effort enough). 1.1.3
Karl Poppers philosophy of science
Page 2
Karl Popper introduced a theory and method of scientific inquiry relying on the falsification criterion, saying that any hypothesis should be able to be tested by an attempted counterexample before being accepted as scientific. Popper also had a more general outlook and regarded all knowledge to be “homologous” in that there are common traits to its formation and evolution. This holds for plants, animals, humans and scientific theories. Let me quote from [5]: “Thus the origin and evolution of knowledge may be said to coincide with the origin and the evolution of life, and to be closely linked with the origin and evolution of our planet earth. Evolutionary theory links knowledge, and with it ourselves, with the cosmos; and so the problem of knowledge becomes a problem of cosmology” I represent a proposition as a classifier and falsifiability as the testability of a classifier against an input message on the message list. A proposition that turns out to be false is mutated into a consistent (true) theory. A niche may be regarded as a theory. 1.2
The hypothesis
Before stating my hypothesis, let me discuss what a hypothesis is in my eyes. I want it at least to be scientific in Poppers sense, so it should be falsifiable, meaning that it can be tested. This is a somewhat paradoxical formulation. How can a hypothesis be true if it has a counterexample? I believe that he too naively assumed that absolute knowledge could be achieved and relied on the notions of truth and falsehood too much. I do not believe that universally true empirical statements are possible. Let me give an example. All swans are white. This may remain true until someone makes a genetically modified black swan. Another example is: quantum mechanics is valid. I don’t simply believe that the Schrödinger equation holds all the way down to even 1000 digit precision. My position is simply that no empirical statement is universally true and that any statement claimed to be so (logic, and parts of mathematics) is a limiting case. Let me state my experimental hypothesis: “A simulated robot in a world with only odometer and bumper sensors which moves randomly around there can make a map of that world” This is empirical because all the words map to empirical concepts. It is not completely true, because many counter-examples can be given, like a world with some hidden obstacles. It may have true interpretations and I will examine one such out of an infinity of possible ones. The many potential interpretations of the hypothesis and not its “truthfulness” makes it useful. Here is my interpretation of the hypothesis: World. A rectangle of fixed dimensions surrounded by walls that the robot can bump into. The world has a set of rectangular obstacles in it that the robot can also bump into. Each obstacle has random location, orientation and dimensions according to uniform, uniform and Gaussian distributions respectively. There are a constant number of these obstacles, which remain fixed at all time. Page 3
Randomly. When moving away from a wall edge, be it the room wall or obstacle wall the robot will move in a uniformly distributed angle [0,π] away from the wall and move on a straight line towards a new obstacle. Map. A fuzzy geometric model of the obstacles with fuzziness indicating how much the robot believes in the parameter with that fuzziness. Bumper sensor. Registers collision angle with obstacle edge upon collision. Odometer sensor. Registers how far the robot moved. Move around. The robot has a built in motion behavior module which controls how it moves around and how it interacts with obstacles. This module may define a random or deterministic motion scheme. The motion scheme is fine-tuned to the environment in question to enable a tractable inspection of it using the robots sensors and actuators. In my simulation I use random movements from rectangle to rectangle and moving around rectangles for a random number of times. 2
Testing the hypothesis
I implemented a Mathematica 10 simulation of the world and robot, which is documented in [6]. I was able to perform the learning process and have the robot discover about 70% of the obstacle rectangles and recovering the distances between all these. The remaining 30% remained hidden, because the robot never bumped into them due to its random motions and random locations of the obstacles. Before discussing my special architecture, I will describe classifier systems in general, in order to highlight my special instantiation of such systems. 2.1
Classifier Systems
A classifier system receives input from its environment in some form, which in general is some kind of string of values. In John Hollands original CS0 this was a binary encoded string. The input is places in an internal memory store, the message list [M]. The system determines a response based the input and performs the action, which potentially may alter the environment. The system has a rule base [N], which is used to match messages on the message list with a set of rules, or classifiers. The matching then results in an action to be taken by the system. Desired behavior is reinforced by scalar reinforcement, where some fitness or strength value stored in each classifier is used to control its behavior. The rule base is maintained by generating new rules and deleting less fit rules, the rule discovery phase. The system cycles through performance, reinforcement and discovery and learns about its environment this way.
Page 4
There are quite a lot of possible interpretations of this fuzzy description, however, some have crystalized into common practices due to historical circumstances and experience. The bucket brigade algorithm and Q-learning are commonly used for reinforcement, while a genetic algorithm is used for rule discovery. There may or may not be a message list and there is huge variation on the genomic representations used together with the used genetic operators. An example of a LCS can be found in [3], where the SCS a simple LCS is described. Here are some examples of classifiers: 01##:00000 and ##00:0001. The first parts before the colon are condition parts to be matched against some message of equal length on the message list. 0 and 1 are data, whereas # is a blank. Assume we have the message 0110 in the message list. This will match the first classifier but not the second. In the following, I will detail how I implemented each component of LCS, but first something about the brain. 2.2
The brain
Let me reproduce figure 4 from [1], which tells how the brain processes information:
Page 5
Figure 1. Here, three sensory modalities are shown, with arrows indicating potential dataflow and large arrows a sample dataflow.
In this figure, each box represents some agglomeration of neurons, like a column and the arrows are information flows. A downward flow fills the current input and makes predictions about what the subject will experience next. Jeff introduces the abstract notion of a sequence, which I find very useful. Take for instance saccadic eye movements executed when viewing a face, these results in sequences of actions and their associated sensory impressions. Examples include “eye eye nose mouth” and alternatively “mouth eye nose eye” Prediction here is Markov chain like in the sense that from mouth we may predict “eye” or “nose” with some probability, but not so much “pen” or “car”. Sequences move up in the up arrows and predictions downwards. The predictions are generated by the boxes. 2.3
The architecture
In the block diagram below, I have depicted the overall PCS architecture:
Page 6
Figure 2 The block diagram modelled as communicating UML processes. GA is the genetic algorithm, [N] is the rule set and the others are what their names indicate. Arrows indicate dataflow.
I will now describe the various blocks. 2.3.1
The environment
I use a robot resembling a robot vacuum cleaner located in a rectangular room with random rectangular obstacles as the environment. The input that the PCS gets from the environment comes from the robots sensor. I have an odometer sensor for recording how far the robot moves and a bumper sensor for recording impact angle and bump status for any obstacle wall. Both sensor inputs are encoded in a real valued sting and sent to the message list. The obstacles in the environment are rectangles representing furniture. They are placed in the room at uniformly distributed random locations and uniformly distributed random angles and with Gaussian distributed dimensions. The robot can also distinguish the room wall and rectangle edges. 2.3.2
The message list
In modern LCS architectures like the ZCS or XCS the message list has been removed for understandability and performance. I reintroduce it as a queuing mechanism and memory store for auxiliary information. I need a queue, because I handle sequences of messages and not just the latest message from the environment. Besides, I need to be able to pipe information around inside Page 7
the system, requiring more sophistication. The message list provides Turing completeness to the model and must not be misused for that same reason. 2.3.3
Matching
Fuzzy LCS was described in [7] pp 83-104, but no representation examples given. I use LR (Left/Right) triangular fuzzy numbers directly encoded in the chromosomes. LR numbers are three parameter numbers with mean, left, and right spreads. These and the trapezoidal numbers are the simplest you can get. The method follows the conventions of LFCS (Learning Fuzzy Classifier Systems) as far as I can read from the paper in [7]. For matching, the spread gives a kind of receptive field for any input patterns. I assume that all input data are real valued crisp numbers that needs to be matched against some CS fuzzy number. I simply use the membership function of the fuzzy LR numbers for pattern matching. When an input message needs to get matched by the classifiers in a niche, I match it against all classifiers there to create a match list. From here I select the one with the highest matching score and use it for further processing. 2.3.4
The rule set
My rule set of classifiers is partitioned into a number of niches [𝑁] = ⋃[𝑛]𝑖 , where each niche responds to a certain type of messages. This scheme is entirely consistent with traditional LCS, where it is easily implemented by having special ID tags in the condition part. Each niche represents a scale of time for the robots perceptive system. The niches can be visualized as a stack:
Figure 3 The N niches, with the high-level one at the top.
The low-level niches respond to short-duration events, while high-level niches respond to longduration events. For instance, fast control loops would be implemented in the low-level niches and planning and other goal oriented behavior in the high-level niches. A niche processes information from the niche below it and forms predictions, which are sent downwards again. It also integrates information and sends sequences to the niche above it. The whole process resembles the way the brain works. Page 8
I discovered that for representing complex structural information, having just the classifiers was too simple. Long trains of classifiers can be made to work together and reinforce each other. This is implemented in John Holland’s bucket brigade algorithm. The problem is that of averaging together irrelevant information and is reported in the literature. I decided for explicit pointers between classifiers. This can be implemented by having the classifiers ID tagged and then using these ID’s in other classifiers that point to them. The mutations themselves can be carried out by sending a message from niche N to niche N-1 with the information about the mutations needed. This method follows the LCS paradigm, but computational shortcuts are possible. The classifiers are then made up of a mixture of strings of integer and real valued values, both with associated spread values. Setting the spread to zero gives a crisp number. What can a spread value on a pointer be used for if it is not zero? If the ID numbers are equipped with a metric, we can simply interpret a pointer with spread as a pointer that points to a set of classifiers and not just one classifier. Take a default hierarchy in niche N-1 for instance. Let the pointer point to the top individual (the most generic one). Then we could interpret a pointer with spread to point to the individuals further down the default hierarchy tree. These fuzzy pointers address much more than their crisp values allow them to, but they do so in a way that fosters further use. Each classifier has a strength value, which tells how good it performs. 2.3.5
Reinforcement
Reinforcement is very simple in my model. Any classifier that has been selected during the matching phase simply gets its strength incremented by 1. This means that classifiers that are useful in the sense of being consistent with the outside world are rewarded. The others get no reward, a kind of indirect punishment. 2.3.6
Rule discovery
I have replaced the ubiquities genetic operators found in the literature with my own operator, which acts as both a mutation (niche N-1) and recombination (niche N-2) operator. It sequentially processes a time sequence from the niche below and generates a single message for the niche (N) above. It integrates the information from niche N-2 in doing so. It has pointers to some classifiers below and alters these in its recombination function. If it needs to modify the classifier at niche N-1 it uses its mutation function. This is rather complicated, so let me explain and first with a picture:
Page 9
Figure 4 Active classifier in niche N-1, points to a group of classifiers in niche N-2 and mutates these. Sends message to niche N.
In this picture, the active classifier is the one in niche N-1. It received a sequence of messages from below and now wants to integrate this. After having done that, it sends one message to the upper layer and alters the classifiers to which it points. We can now understand why the different niches have different scales of time. Each time say M messages are received from below only 1 message is sent to layer N, so layer N is M times slower than layer N-1. A classifier has been selected at some level N in the niche stack and has the potential to change itself and all classifiers pointed to by it. A classifier has strength and I adopt the convention that the stronger a classifier is, the more persistent is it towards change. In a sense, strength and spread play dual roles here. Spread control the matching phase (input), while strength controls the rule generating phase (output). A classifier is a string of CS numbers, so how in general should we implement the mutation and recombination algorithms? I cheat a little, because I make a map from the genotype into an internal phenotypical representation, where the actual operations take place. For instance if a line segment is represented by L, α, x, y (length, angle, and COG point) and if I need the endpoints I make a fuzzy map to these endpoints and end up with two fuzzy points. On these, I do the alterations and then an inverse fuzzy map back again. If I don’t get a CS number I make a small adjustment, like the maximal, minimal or average of the spreads depending on situation. If needed I can also represent LR fuzzy numbers in the genome itself. Here is a depiction of the process:
Page 10
Figure 5 Cognitive phenotypical recombination.
A glimpse in the literature will reveal that purist mutation and recombination in John Holland’s case are difficult to find, except in the case of function optimization. But then again, [8] always had a more general scope. Classifiers can represent complex information and I have seen hacks where different parts of the genome are recombined in very special application specific ways, depending in essence on the phenotype. I regard phenotypical genetic operators as an important step in making GA’s and classifiers more useful and less relying on computational dogma. 2.4
Specific implementation
In a robot control system, we deal with sequences of numeric values that work in unison. My concrete simulation uses a robot with two sensor, an odometer, giving numeric values and a bumper sensor, giving only a bump value. The robot senses its environment in a bump, move, bump, move mode. A sequence might therefore look as follows: B, 3.56, B, 6.87, B, 1.45, B, 6.23. If we remove the redundant B’s, we get 3.56, 6.87, 1.45, 6.23 so that at the lowest level of input to the robot we just have an ordinary numeric sequence. Let me illustrate one of the possible obstacles of the robots world:
Page 11
1.7
3.5
1.7
3.5 Figure 6 A rectangular obstacle
The robots behavior system dictates that it shall move a random number of times around the obstacle, which would give a sequence like 1.7, 3.5, 1.7, 3.5, 1.7. Such a sequence can be used for prediction, because after a 1.7, a 3.5 must always come and vice versa. This example assumes that the robot can exactly measure any rectangle edge distance. I made my model so realistic that this is not the case. The robot must move forwards L units, turn 90° to the right, attempt to bump into the obstacle and if it can turn back 90° and commence on its path. This complex activity pattern is necessary to compensate for a lacking a LIDAR or similar sensor and introduces sensor noise, as the length of a rectangle edge comes in steps of L. Simulation runs shows that the 90° turns and getting into track again introduces yet another error components so that we do not even get the distances in steps of L. If the robot moves around the rectangle, enough times some of these noisy values will cancel out, given that the robot averages together the results. The sensor noise is of no significance if the rectangles are different enough for identification and the pattern-matching algorithm is robust enough to allow this noise to appear repeatedly. After moving randomly around a rectangle, the robot moves in a random direction towards a new obstacle. It uses the inter-rectangle distances to construct a Euclidean Distance Matrix (EDM) by triangulation methods. This matrix can be transformed into precise coordinates of all obstacles up to an affine transform. The coordinates are not absolute because the room walls have been excluded for simplicity. Now the robot has a local map to be used for further predictions. Using trigonometry, the robot could calculate in what direction to move towards its next sub-goal. 2.4.1
The classifiers
My model is too simple for actions, because everything the robot does is determined beforehand. I use a “strategy” parameter in the spirit of [7]. This has the same length as the condition Page 12
parameter and defines for each value there its fuzziness. Each classifier has a strength (belief value) telling how well it matches the rectangles of the world. All values are real valued and bound in an interval of constant size, like [-10, 10], which implies a fuzzy remapping if any use it to be made of it. Integer valued parameters are also allowed (no bounds). I subdivide the classifier set [N] into 3 niches used to represent the 3 levels in the knowledge hierarchy. Niche0 contains line segments, Niche1 rectangles and Niche2 sets of rectangles of constant cardinality. Here is a depiction of this stack of niches:
Figure 7 the 3 niches used in my experiment.
At initialization, each classifier has maximal fuzziness, meaning that it will match up to a maximal degree to each input message. This usage of fuzziness gives me the possibility to define blanks that have a “degree of blankness”. Maximal fuzziness is like a blank, and minimal fuzziness is like a crisp data value. When the robot has discovered a rectangle edge, this edge is matched against all Niche0 classifiers for a maximal fit. The maximal fit then is the robots hypothesis about the encountered edge. Now we mutate the edge to its measured value and continue for the next edge. At the same time, we minimize the fuzziness. If we continue this way solely in Niche0, we would get a representation of all different edges, which the robot will ever encounter. Each different edge length discovered by the robot leads to a new classifier in Niche0 with maximal fuzziness, enabling a pattern match. This length is then “locked” by having the fuzziness set close to zero. Niche0 works as a coin sorting machine, it will put line segments (coins) of equal length into the same classifier (slot). It will also make new slots for new edge lengths. In Niche1 things now look messy, where there before would possible be some rectangles we have some non-aligned line segment lengths. Let us see how I repair things. I use Niche1 for prediction and averaging of information in Niche0. The trick deployed is to have a Niche1 classifier point to 4 different Niche0 classifiers in such a way that no two Niche1 classifiers share edges. We then feed the sequences of Niche0 classifiers to Niche1 in special long messages for processing. Here, information will flow back into Niche0 where further mutation of classifiers take place. The weakest classifiers mutate most easily meaning that their values have not been validated yet. This back flow of information is similar to Jeff Hawkins sequence prediction mechanism, however in my case the sophistication is higher because I allow for explicit geometric modelling of for instance rectangles. Page 13
Now for the mutation operator. Take two opposite edges in a Niche1 rectangle and look at their strength values. The lengths of the two edges are averaged together using the strength values and the result is copied to each edge resulting in equally long edges. Any position inconsistencies are fixed by a similar averaging scheme resulting in a perfectly rectangular shape. Assume that we have a Niche0 classifier, which has never been matched against a sensory datum before. This will have strength 0 because its value has never been used. Due to this special mutation/recombination operator, it will get a value when its opposing edge first gets one. Its strength remains zero, however. If the this classifiers value remains invalidated, it will forever thereafter after get its value from the opposing edge whenever that is validated. This mechanism ensures a sensible copying of information around internally in the classifiers. Strength and fuzziness play dual roles here. I use strength for controlling mutation and fuzziness for controlling matching. I mentioned that classifier edge lengths are matched against a measured classifier edge length. To represent a line segment one needs 4 numeric values, the two end points. One can calculate the fuzzy distance between these by using fuzzy geometry and then use the result by some custom comparison operator. In Niche1, dimensions of classifier rectangles mutate, whereas in Niche2, the locations of classifier rectangles mutate. I only use one classifier in Niche2 as there is only one actual world the robot moves in, because this is sufficient, and because the pointers from Niche2 to Niche1 are all constant in time. For this simple application, only Niche0 classifiers mutate and all others remain constant through time. Niche1 and Niche2 only mutate in an indirect fashion, because they both indirectly point at Niche0. Let me depict the world with the robot (an iRobot Roomba 630) and the Niche1 classifiers in it:
Page 14
Figure 8 The world and niche1 classifiers. The grey rectangles are obstacles, the purple ones classifiers with strength indicated by opaqueness. The small image is the robot at an edge of a rectangle.
2.5
Experiments
I did some automated computer experiments using the simulated solution. The purpose of these was to test the robustness of the solution against varying circumstances. The theory behind computer experiments can be found in [9]. I want to test against variations in rectangle size and step size L of the robot. These variables are called control variables, which I can adjust to control the computer experiment. 2.5.1
The null experiment
I started the whole report here by instantiating the robot hypothesis into one simulated experiment. This was a choice amongst an infinitude of possibilities. Similarly, we now have an infinitude of control variables in two dimensions to choose from. Should we follow the common strategy and sample that space using some probabilistic algorithm? I pondered this question and decided not so do so. Instead, I simply choose one point in the control variable space more or less at random. I call this point the null experiment. The null experiment is an arbitrary choice, just like the computer simulation itself was and for the same motivation. Some choice must be made eventually. I use the null experiment to test and debug the system. 2.5.2
The variations
I vary the control variables along each dimension of control variable space in a linear fashion and in 10 variations, giving several hours of run to time for such a repeated experiment. Here are the graphs from the null experiment, where the maximal and average strengths are also depicted.
Page 15
Figure 9 The percentage of covered nodes of the graph of the Euclidean Distance Matrix (EDM). 8000 generations and 10 repeated experiments with identical control parameters.
Figure 10 The percentage of covered edges of the graph of the Euclidean Distance Matrix (EDM). 8000 generations and 10 repeated experiments with identical control parameters.
Figure 11 The maximal strength of niche1 classifiers. 8000 generations and 10 repeated experiments with identical control parameters.
Figure 12 The average strength of niche1 classifiers. 8000 generations and 10 repeated experiments with identical control parameters.
We see that the covered nodes and edges remain constant take or give fluctuations due to random robot motion. This is expected as everything but the robot motion remains constant. Average strength increases linearly, which is expected because the robot keeps revisiting old rectangles. The maximal strength is more jumpy, also quite sensible, because revisits to the maximally strong rectangle should only happen after a while. Here comes 10 variations of robot step size from 70 to 140 in steps of 10:
Page 16
Figure 13 The percentage of covered nodes of the graph of the Euclidean Distance Matrix (EDM). 8000 generations and 10 repeated experiments with variations of robot step size from 70 to 140 in steps of 10
Figure 14 The percentage of covered edges of the graph of the Euclidean Distance Matrix (EDM). 8000 generations and 10 repeated experiments with variations of robot step size from 70 to 140 in steps of 10
Figure 15 The maximal strength of niche1 classifiers. 8000 generations and 10 repeated experiments with variations of robot step size from 70 to 140 in steps of 10.
Figure 16 The maximal strength of niche1 classifiers. 8000 generations and 10 repeated experiments with variations of robot step size from 70 to 140 in steps of 10.
For covered nodes and edges, we see a decrease in performance as the step size increases. This is expected as increased step size implies more sensor noise, because the robot cannot discriminate clearly between obstacles anymore. Here comes 10 variations of rectangle sizes from 0.5 to 0.8 in steps of 0.03333:
Page 17
Figure 17 The percentage of covered nodes of the graph of the Euclidean Distance Matrix (EDM). 8000 generations and 10 repeated experiments with rectangle sizes from 0.5 to 0.8 in steps of 0.03333.
Figure 18 The percentage of covered edges of the graph of the Euclidean Distance Matrix (EDM). 8000 generations and 10 repeated experiments with rectangle sizes from 0.5 to 0.8 in steps of 0.03333.
Figure 19 The maximal strength of niche1 classifiers. 8000 generations and 10 repeated experiments with rectangle sizes from 0.5 to 0.8 in steps of 0.03333.
Figure 20 The average strength of niche1 classifiers. 8000 generations and 10 repeated experiments with rectangle sizes from 0.5 to 0.8 in steps of 0.03333.
For covered nodes and edges we see that an increase in rectangle size gives less performance. This is explained by the smaller rectangles simply giving the robot larger opportunity to visit more rectangles because less rectangles remain hidden. In conclusion, all variations from the null experiment could be explained and the quality of the solution degraded gracefully as a function of the variations. 3
Prospects
I have demonstrated a simple experiment where some control variables were altered. This experiment was itself an expansion of a single case, the null experiment with all variables fixed. I will now discuss some further prospects of my model illuminating its usefulness.
Page 18
First, the model I demonstrated was overly simple. The hierarchical structure of the pointers was a tree structure and the usual mutation and recombination operators were missing. Is this not a deficiency compared to the LCS paradigm? I will argue that this is not the case even for my simple model. The recombination operator in Niche1 acts as a mutation operator there, altering the classifiers pointed at in Niche0. However, down there the operator acts as a true recombination operator. It takes two opposite side of a rectangle and does averaging, a recombination operator. The difference between my case and the traditional case is that my choices are not random; they depend on pointers from Niche1. Imagine as an alternative implementation, however, a very large classifier in Niche1 or using the tree connectivity all the way to Niche2. Then you get the traditional picture of two classifiers chosen arbitrarily but not random from anywhere in the classifier population. The restriction that the connectivity is a tree can also be relaxed to a partial order allowing classifiers at level N to point to the same classifier at level N-1. There may also be a partial order of Niches instead of a strict linear order. 3.1.1
The cognitive model
To exploit these possibilities, let me discuss my model as a cognitive model. The metaphorical vocabulary of a cognitive model makes it possible for the programmer to formulate implementations in an intuitive way and plays the same role as abstracted geometric models does for the electrical or other kind of engineer. The existing metaphors of the LCS paradigm includes notions like: memory, learning, knowledge, abstraction, not to mention quite a few biological metaphors. I will extend this vocabulary in the following, but let me first depict my ideas:
Figure 21 The notions of context and composition along the vertical plane together with the notions of specialization and abstraction along the horizontal plane.
Page 19
In this figure, I have introduced 4 new cognitive words, which will now be explained. In the figure, the two top classifiers belong to one level, the three next to the next lower level and the bottom two to the next lower level again. All classifiers have 4 data values and 4 fuzziness values with gray level indicating high crispness. The composition of a classifier is the subtree to which it points. If we think of a classifier as a concept, like a car, the composition shows naively how the car is constructed in terms of engine, doors, and wheels and so on. In my implementation, the composition of a rectangle defines exactly the line segments it is made up of. The context shows on the other hand what concepts point to a given concept. Take a sparking plug, in some car representations this component may not need any detail and is therefore common to all particular cars. Any time we refer to the sparking plug, we will need to refer to the context of it, is it in a Volvo, Mazda or Lada? Abstraction and specialization are inherited from the common LCS vocabulary and are related to the existence of a default hierarchy. Abstraction means that the fuzziness values have been relaxed and contrary, specialization means that they have been made more crisp. In a traditional crisp LCS the default hierarchy forms a partial order relation, but in our case we may use fuzzy relation to model the connectivity, given that we can find a reasonable way to define how specialized one classifier is relative to another. The message sent from an instance to its class can be thought of as a pointer from the. Taken together with the inter-niche pointers these form a huge non-cyclic graph, with indirect pointers defined by pointer composition. An abstract classifier is pointed to by more upper level classifiers than its instances. This implies that abstract concepts have a larger context than concrete ones. The notions of abstraction and specialization are horizontal in my model and the notions of context and composition are vertical in the model. 3.1.2
A larger example
Let me illustrate these ideas with a larger example, requiring some time and resources to implement, however. We have a robot with the same actuators and sensors as the simulated robot, but with a camera atop of it, just like the menacing Dyson eye vacuum cleaner robot. We are given some computer vision computational primitive beyond simple pixel representation and want to implement computer vision using the primitives and the robot. Imagine that the eye can rotate at will (also vertically). We will use this eye balling behavior to implement the computer vision system. The eye software is very simple, it can only register shapes that are centered in the visual field, with degrading precision at the eye boundaries. These shapes are tagged with ID numbers and sent to the classifier system. How can we now implement more advanced computer vision? The same strategy with active perception as before is used.
Page 20
Now assume that the world is made up of rectangular pieces of furniture, but with legs instead of side walls. Each piece of furniture is therefore geometrically defined by its 4 legs. Each leg looks like each other leg at a distance, but there are two kinds of furniture, chairs and tables. The chairs are square and identical, whereas the tables are rectangular and all different. The robot it placed at a random location in the room and with random initial camera position. It must now map this world and we need to understand how. Let us start simple. How will it identify a leg for instance? It has detector software that coarsely identifies that there is some object at the periphery of its visual retina. A simple rule makes the robot rotate the camera to center the object for further identification. The robot can only detect legs at certain discrete distances, so it has one classifier for each of these distances. In order to represent the leg concept it has a default hierarchy with the general leg concept being more general than the specific distance instances. This should be an easy geometrical thing to implement. We need a mechanism that activates the general leg classifier whenever one of its instances is activated. We simply send a message from specific instance to general classifier whenever the specific instance classifier is activated. This message then propagates all the way up the default hierarchy. This makes out a pattern matching inference engine, which ensures consistent activation of patterns. Then you may object that such a mechanism is not needed in ordinary LCS architectures. In my case, I have joined the “signature” of a classifier with certain message types that will accept them. I have so to speak made a niche inside the niche. Each level of the default hierarchy is in its own sub-niche. The niche notion is a key innovation of my design and sub-niches are a consistent extension. Messages also have signatures, but they are hardwired for a particular niche. The notion of automatic niche-formation is beyond my current speculations, but I have some ideas here. Now let me discuss computer vision. The robot can only spot legs at certain exact distances so it moves towards a leg until a match has been done. This is leg recognition, as simple as you can get it. If there are small changes to the legs, like dirt, this information is recorded in the specific leg classifiers. The robot also generates and stores a guess of location of the leg in its classifier. As location is yet another specialization, our default hierarchy needs at least 3 levels. The highest layer contains the general leg classifier with any generic structural information, like parametric geometry. The middle layer contains the distance specific sensory impressions of legs and another competing middle layer contains leg positions, identifying each leg. Now I assume that the robot moves around in this world, recording leg instances and somehow using an algorithm similar to the rectangle simulation makes predictions about leg locations. These are possible to predict for the same geometric reasons, but complications arise because of the random movements and many inter-leg distances not belonging to a piece of furniture. When the robot has moved between two legs and pointed the camera at the destination leg a sample of sensory impressions have been collected to form a sequence. We can sequentially integrate these sensory impressions and use them for prediction. For instance, the dirt spot on the leg should grow as we approach it. This sensory integration resembles the rectangle side averaging encountered in my simulation and is a true recombination operator. Now things are more complex and image processing techniques are required. Page 21
The mentioned leg representation follows almost by the book the practice from object oriented modelling. The difference is that all classifiers in a niche has the same amount of information. It is only the fuzziness that tells them apart. I have hardwired the default hierarchy which implements the “class hierarchy”, but given a sophisticated enough representation of the matching and messaging system everything could maybe be auto-generated. The computer vision method is a balance between active perception and innate perception. Here, innate perception is whatever computer vision primitives have been built into the robot beforehand and active perception takes advantage of the robots actuators and classifier system. The notions are interchangeable, however. Imagine that the robot can recognize an object in its entire visual retina; then there is no need to move the camera. Alternatively, imagine that some very complex three-dimensional objects are present; then suddenly camera movement is necessary. 3.1.3
Formalization of the large example
Let me finally formalize this larger example a bit by indicating its implementation in the PCS framework in line with what I did for the simulation example. This will then aid in any computer implementation and can be transformed into the documentation and planning needed for such an implementation. 3.1.4
The environment
I assume that we are dealing with a physical toy like robot with the mentioned actuator and sensor capabilities give or take what is possible to either buy or stuff together cheap and fast. I assume that the world is simply a living room with the furniture in it. This gives less possibility for random variations of say large pieces of furniture like bookshelves, but chairs and tables can be moved about a bit. Can individual furniture legs be distinguished by such a robots vision system? This depends on the chosen model and the possibility and time frame to hack the code. So some open sourced code should be chosen. Anyhow, the environment can be hacked by attaching differently colored pieces of paper to the legs. A completely rectangular sized environment may be difficult to get at, but then just hardcode the room walls in the robot for an easy solution so that obstacle discovery remains the only problem. 3.1.5
The message list
The message list has been discussed before and its structure will depend on the structure of the matching and rule set. 3.1.6
Matching
I use the same internal representation with LR fuzzy numbers, but use these also for the genetic encoding. Input are always strings of real numbers. The question now comes how to an image into a string of real numbers. Luckily, this question has been answered by the computer image processing community and algorithms for edge detection and shape detection exist in abundance today. The problem of detecting a leg (square or circular cut) with its color gradient and boundary edges is an easy problem; at least this is my assumption here. I assume that the robots vision system can single in on the most prominent leg it can see and process that one. The output of this stage Page 22
then is a numeric string with parameterized edge boundaries and for a square leg also the middle edge. The color gradient is given in some parameterized form showing start and stop values between lines and type of gradient (constant for square legs and not so for circular). 3.1.7
The rule set
The same generic layered structure as in the simulated case is used. The leg representation is severely complicated as compared to the line segments of the simulated case. One problem is that legs are not distinguished by geometric dimension any more, but by texture or other random features, or possibly are indistinguishable for the robot. In the simulated case, indistinguishable rectangle pairs where simply ignored and assumed to be noise. The case of indistinguishable objects is handled in generality by the prediction mechanism. No objects are indistinguishable for the internal representation even though they may be so for the sensory system. The only way the classifier system can handle this is by filling out the details using its prediction mechanisms, a process called reification in psychology. For our case, this implies looking around at the chair and table legs to see what statistical regularities are in place and hardcoding these into the model, once again to arrive at a simple solution. This could be that legs of one chair are identical and that some but not all chairs are identical. We either hardcode the number of different pieces of furniture or we do not, the latter case being the most difficult. The hardcoded leg information is placed in a default hierarchy with a root leg instance that is most general and has maximal fuzziness for all values. Below this are leg specializations for each piece of furniture and below again specializations for special legs with dents or structural damage. For structural damage we use the composition architecture and have pointers to structure elements in a lower level niche, assuming that this is fast processing by the robot. General structural damage is modelled by having the pointer point to a general classifier in the lower niche. Besides identifying each leg, I use special perceptive objects that identify how a leg looks at a certain distance. This is to aid the matching process. This representation is orthogonal to the specific leg representation and common to all specific legs. It exists below the generic leg instance and includes geometric information. Leg location is the third branch in the default hierarchy and simply contains the coordinates of the leg. As in the simulated case, a room is composed of furniture and furniture is now composed of legs and not line segments as before. 3.1.8
Reinforcement
Here I use the same mechanism as in the simulated case. 3.1.9
Rule discovery
Rule discovery follows the generic model highlighted above and I need to describe how it is implemented precisely. Each specific leg is composed of its sensory impression instances, so that Page 23
the robot integrates these when it moves towards a leg. The predictions here are texture and type, so that a square edge remains square and texture is invariant. Each piece of furniture is composed of its leg instances, some generic and some specific. Once again, texture and type can be predicted to some degree, but also location, because it can be calculated by triangulation. Furniture location is predicted exactly as in the simulated case. 3.1.10 The classifiers I need a 4th layer below the leg layer for the leg sensory impressions, requiring more computational power from the robot, however as each time the robot moves some inches towards a leg it will have to run one learning cycle. Here is the depiction:
Figure 22 the 4 niches used in the thought experiment
4
Conclusion
I have introduced the PCS in a semi-formal manner with a well worked out simulation example and showed that further deliberation using the conceptual framework of PCS is possible. In order to proceed with the computer vision example, one would need to formalize all informal statements using simple set theoretic notions and then code, test and debug the whole thing either in Mathematica or (preferably) on a real robot. 5
Bibliography
[1] J. Hawkins, On Intelligence, Times Books, 2004. [2] I. Numenta, "Hierarchical Temporal Memory," Numenta, Inc., 2011. [3] D. E. Goldberg, Genetic Algorithms in search optimization & machine learning, Addison Wesley, 1989. [4] K. R. Popper, The Logic of Scientific Discovery, Hutchinson Education, 1959. [5] K. R. Popper, All Life is problem solving, Routledge, 1999. [6] J. Ø. Pedersen, "PCS - Mathematica," The Mathematica Journal, 2015. [7] P. L. Lanzi, W. Stolzmann and S. W. Wilson, Learning Classifier Systems, Springer Verlag, 1998. Page 24
[8] J. H. Holland, Adaptation in Natural and Artificial Systems, Michigan: The MIT Press, 1992. [9] T. J. Santner, B. J. Williams and W. I. Notz, The Design and Analysis of Computer Experiments, Springer Verlag, 2010. [10] M. Mitchell, An Introduction to Genetic Algorithms, The MIT Press, 1998. [11] D. E. Goldberg, The Design of Innovation, Norvell: Kluwer Academics Publishers, 2002. [12] L. A. Zadeh, "Fuzzy Sets," Information and Control, pp. 338-353, 1965. [13] Y. C. Jiaming Xu, "Euclidean Distance Reconstruction from Partial Distance Information," pp. 1-11. [14] P. J. I. S. D. Raghu Meka, "Guaranteed Rank Minimization via Singular Value Projection," pp. 1-17, 19 October 2009. [15] "Classical Scaling," in Modern Multidimensional Scaling, Springer Verlag, 2005, pp. 261-264. [16] E. E. J. J. Buckley, "Fuzzy plane geometry I: Points and lines," Fuzzy Sets and Systems, pp. 179187, 1997. [17] D. G. Debjani Chakraborty, "Analytical fuzzy plane geometry II," Fuzzy Sets and Systems, pp. 84-109, 2014. [18] D. G. Debjani Chakraborty, "Analytical fuzzy plane geometry I," Fuzzy Sets and Systems, pp. 66-83, 2012. [19] E. E. J. J. Buckley, "Fuzzy plane geometry II: Circles and polygons," Fuzzy Sets and Systems, pp. 79-85, 1997. [20] B. S. A. N. G. A. Paulo A. Jimenez, "Optimal Area Covering using Genetic Algorithms," IEEE, pp. 1-5, 2007. [21] C. Jacob, Illustrating Evolutionary Computation with Mathematica, Morgen Kaufmann, 1997. [22] H. J. Zimmermann, Fuzzy Set theory and its applications, Kluwer Academic Publishers, 2001. [23] L. Bull and T. Kovacs, Foundations of Learning Classifier Systems, Springer Verlag, 2005. [24] J. Drugowitsch, Design and Analysis of Learning Classifier Systems, Springer Verlag, 2008. [25] J. H. Holland, K. J. Holyak, R. E. Nisbett and P. R. Thagard, Induction, MIT press, 1986. [26] M. de Berg, O. Cheong, M. van Kreveld and M. Overmars, Computational Geometry, Springer Verlag, 2008. [27] T. M. Mitchell, Machine Learning, McGraw-Hill, 1997. [28] S. Russell and P. Norvig, Artificial Intelligence, Prentice-Hall, Inc., 1995. [29] S. M. LaValle, Planning Algorithms, Cambridge University Press, 2006. [30] R. Siegwart, I. R. Nourbakhsh and D. Scaramuzza, Autonomous Mobile Robots, MIT press, 2011. [31] R. C. Arkin, Behavior-based Robotics, MIT press, 1998. [32] R. R. Murphy, Introduction to AI robotics, PHI, 2000. [33] I. Lakatos, Proofs and Refutations, Cambridge University Press, 1976. [34] R. A. Brooks, Cambrian Intelligence, MIT press, 1999. Page 25
[35] S. Thrun, W. Burgard and D. Fox, Probabilistics Robotics, MIT press, 2006. [36] G. Dissanayake, "A Review of Recent Developments in Simultaneous Localization and Mapping," ICIIS, pp. 477-482, August 2011. [37] W. L. Brogan, Modern Control Theory, Prentice-Hall, 1991. [38] D. Rodriguez-Losada, F. Matia, A. Jimenez and R. Galan, "Consistency improvement for SLAM-EKF for indoor environments," IEEE ICRA, pp. 418-423, May 2006. [39] L. Tran and L. Duckstein, "Comparison of fuzzy numbers using a fuzzy distance measure," Fuzzy Sets and Systems, pp. 331-341, 2002. [40] D. Dubois and H. Prade, Fuzzy Sets and Systems: Theory and Applications, Mathematics in Science and Engineering, 1980.
Page 26
