Primarily,
the focus of this project is to study the use of genetic programming and
illustrate the possibility of solving problems without explicit
programming. In order to accomplish
this a specific example will be used.
However, before continuing the reader should be familiar with the
following section explaining the basics of evolution, genetic programming and
the closely related field of artificial life.
1.1 Evolution
Jean Baptiste Lamark first conceptualised evolution in the 18th century, he was however unsuccessful in his attempt to prove his theories. Darwin, on the other hand, was able to prove his work and so became the founder of the theory of evolution. The Darwinian principle of ‘survival of the fittest’ can be observed throughout the natural world. Darwin's most famous example is the finches he found on a collection of islands. These finches have different beaks according to the environment they have found themselves in. Other examples include moths that evolved to cope with the colours created by pollution.
DNA is an integral part of evolution and is the ‘code’, which depicts form and shape, during evolution much of this information is inherited by subsequent generations. The information that describes the object is called the genotype. DNA instructs the body's cells how to create and run all its functions, like a reference table or handbook for each cell. An asexual organism that reproduces effectively recreates a clone of its self, this form of evolution is used by simple organisms with a limited life span but can cause problems for more complex life forms. The problem being that no method of adaptation is allowed from generation to generation, diversity is important in the survival of a species. A species must survive within a given environment and as few environments are ever stable the species must be able to adapt to its surroundings. If any one organism can increase its chances of survival then it is far more likely to reproduce - a dead fertile creature has no chance of reproduction! In effect, a species has to change in order to survive, to stay still a species has to keep on moving forward, and moving forward is done by adaptation, this can take more that one form. Mutation in asexual systems can lead to adaptation but also leads to a high chance of useless or even detrimental mutation. The best current solution is recombination of genes and the process for this is sexual reproduction. By recombining similar sets of genes the resulting DNA is a combination of working parts and therefore more likely to result in a satisfactory set of instructions. This also has the advantage of allowing for selective mating, a commonly if not exclusively used strategy.
1.2 Genetic Programming
Genetic programming is a means of evolving a species of initially randomly defined individuals without giving an explicit definition of the goal. So, initially we start with a mass of random genetic material; this mass may be regarded as our population of individuals. The suitability of each individual may be evaluated using the Darwinian principle of ‘survival of the fittest’, meaning that the strongest (strength being a measure of an individuals ability to approach a goal state) individual is given a greater chance of survival. Individuals can be selected for reproduction in a number of different ways, as in the natural world priority of selection is usually given to the fittest individuals. Reproduction is achieved using the naturally occurring genetic operations of crossover (sexual recombination) and mutation, crossover being the operation by which genetic material is combined from each parent to create offspring. For example in order to create offspring we would start by transferring genetic material from one parent until it is decided to ‘cross over’. At this point we would start copying from the second parent, this crossover could occur many times during reproduction but it is usual to have a crossover rate of between 10 and 30 percent. The reason for this value (10 to 30 percent) is explained later but briefly, excessive crossover carries a high risk of destroying good instructions. Mutation is the process by which a gene is inverted during reproduction; for example, in binary terms this would be the inversion of a 1 to a 0 or vice versa. In a typical lifespan an individual will have its fitness evaluated, be selected for reproduction N time’s dependent on its fitness and then die to give way to the new population. By continuing this process for each individual in each generation the overall fitness of the population should evolve towards an optimal fitness level. Genetic programming is a highly probabilistic approach to problem solving, using probability and randomly generated matter at each step in the evolutionary process, thus, anything can happen and nothing is guaranteed.
1.3 Artificial Life
Artificial Life ("aLife") is the name given to a discipline that studies natural life by attempting to engineer biological systems within computers. ALife complements the traditional analytical approach of biology with a synthetic approach in which, rather than studying biological systems to analyse the way they work, systems are implemented - within computers - that behave like living organisms. In an attempt to fully explain the role of aLife perhaps we should consider our definition of real life:
Life n. (pl. lives. pr. ~vz.) State of functional activity and continual change particular to animals and plants before death, animate existence.
Oxford
Dictionary
For the purpose of this explanation it is also important to see life in terms of its evolutionary capability, thus life must also be seen as capable of reproducing itself, adapting to its surrounding environment and must be capable of independent actions i.e. not dependent on external decision making. ALife is not necessarily mans attempt to mimic real life but an attempt to explore the benefits available to us by implementing lifelike situations within a computer. ALife is only artificial in the sense that it is man-made, a psychologist may argue that we cannot dismiss the possibility of digital life simply on the grounds of our unfamiliarity with such a species. In a typical aLife system an environment is created within which a community of digital ‘creatures’ are placed which in turn must learn to live by following, and in many cases exploiting a set of rules which govern their existence. Typically, the community is capable of selective reproduction and mutation as in genetic programming and therefore is capable of evolution. The system concludes that the community will either die or survive by approaching a satisfactory solution to the problem being studied.
1.4 Project Aim
Given the preceding description of the field of study it should now be easier to understand some of the aims, issues and implications associated with developing an evolutionary system. The aim of the project is to implement and study a system of evolutionary programming. Specifically, to prove that through the use of evolutionary programming it is possible to evolve a population of robots towards a given goal without the use of explicit programming. Initially each robot will be given a random set of instructions with which to navigate its environment, the robots will be assigned a fitness score dependent on their ability to pick up and deposit randomly placed rubbish in randomly placed bins. After each individual in the population has been tested, some individuals will be selected to reproduce; this selection will be based on a fitness proportionate strategy, similar to the Darwinian ‘survival of the fittest’ principle described earlier. Reproduction will use the naturally occurring genetic operations of crossover and mutation, after reproduction the current population is discarded to make way for a new generation of robots. As in natural evolution there is no single stop condition therefore, the program will be written in such a way that data will be output to a file as it progresses. This will allow the progress of evolution to be evaluated and a decision to be made about the success of the program execution. In addition to the basic system of evolution, investigation into the effects of implementing different selection strategies will be conducted. This study is primarily to identify how each strategy will effect the evolution and diversity of the population of robots. The following are examples of strategies that may be chosen for further investigation:
Ø Elitist Strategies
Ø Panmictic Strategies
Ø Roulette Wheel Selection
Ø Localisation Issues
Ø Naturally occurring strategies found in human and animal cultures
Ø Incest Prevention
Ø Disassortive
A substantial amount of research will be conducted to determine the various selection strategies found in the mammal kingdom. Undertaking such research will pre-empt investigation into the different selection strategies that can be observed and their affect on the evolution and fitness of the population. Additionally this will require analysis of efficient and representative implementations of each strategy in order to effectively mimic those employed in the natural world.
Although the following quote may seem a little extreme the idea it presents is one I am intrigued to investigate. Through the development of this project I hope to gain an understanding of the possibilities for creating artificial beings which could exist within a level of independence, as the quote suggests. Already I am impressed and surprised with some of the findings of my preliminary research into these areas.
“We are very near to the time when virtually no essential human function, physical or mental, will lack an artificial counterpart. The embodiment of this convergence of cultural developments will be the intelligent robot, a machine that can think and act as a human, however inhuman it may be in physical or mental detail. Such machines could carry on our cultural evolution, including their own construction and increasingly rapid self-improvement, without us, and without the genes that built us. When this happens our DNA will find itself out of a job, having lost the evolutionary race to a new kind of competition.”
[1] Hans Moravec, Mind
Children, 1988.
Since the invention of the first calculating machine computational power has risen thousandfold for every 20 years, perhaps this vision is not so far away after all!
Designing an evolutionary program is a task laden with complexity, such a system exhibits complexity and entropy on a grand scale, it is a system to which Chaos Theory is explicitly inherent. Chaos Theory is concerned with the explanation of seemingly disordered systems in an ordered way, in short, it states that the behaviour of a chaotic system is not random but simply very complex. In fact to accurately predict the behaviour of any reasonably heterogeneous aLife or evolutionary learning system would alone be justified grounds for a copious amount of research. Therefore, at this stage any design regardless of methodology must be seen as being exhibitive of the final program and not as a definitive solution. System design methodologies using data flow and entity relationship diagrams would reflect the operation and flow of data within the system but would be restrictive in its flexibility and physically very large, therefore difficult to follow. Formal methods offer a viable solution to the specification of such a complex system, using Z as a tool it is possible to specify the rules to which the system must abide rather than attempting to specify a concrete solution to an abstract domain. State transition diagrams may also be utilised in an attempt to describe the change of state in the system after some arbitrary process. It is anticipated that only a selection of procedures will be specified in this way, the suitability of each procedure will be determined according to its necessity and certainty. In addition a prototype approach will be used which will be written in a modular and flexible way, this will allow behavioural analysis to be conducted at a simplified level in an attempt to increase understanding of the core attributes and issues of successful genetic programming. This prototype will be adaptable and will ultimately be used as the basis for the final program. Procedures not specified in Z will be described in pseudo code.
The subject of this study is fundamentally homologous with the role of genetic algorithms in a biological or natural environment, because of this substantial research has been conducted into the structure and behaviour of such systems. The following section explains the findings that have direct relevance to the system being implemented.
3.1 DNA (deoxyribonucleic acid)
The heritable information of complex organisms is contained in one or more structures, found in the nucleus of each cell, called chromosomes, these chromosomes hold long chains of deoxyribonucleic acid, or DNA. As mentioned earlier, DNA is the substance that instructs the body’s’ cells how to create and run all its functions, DNA is common to all forms of life on Earth and is contained within the chromosomes of all living creatures. Although DNA is a biological matter it can be interpreted as a simple string of characters consisting of only four characters representing the nucleotide bases of adenine (A), cytosine(C), guanine (G) and thymine (T). Although this is slightly simplified as different font styles are used to represent various interpretations of these nucleotides the symbolisation of DNA is a relatively simple domain to understand. This is complicated however when one considers that the human body contains around 2,870,000,000 nucleotide bases, in fact, even a simple bacterial organism contains some 4 million nucleotide bases. Two aspects of DNA functionality are of relevance to this study, firstly information can be stored as a sequence of nucleotide bases (characters), and secondly that each strand of a DNA molecule can be used as a template to recreate another strand.
3.2 Genotype & Phenotype
Living material is unique in that its composition and form is represented in two radically different formats, called the phenotype and genotype. The physical material itself – such as an arm, a cell, or a leaf from a plant - constitutes its phenotype. On a simplistic level the phenotype is what is visible by eye or microscope, including the full complement of shapes, behaviours, developmental dynamics, chemical composition and functional composition, of all parts of the physical organism.
In addition, genetic representations are infused throughout all biological tissues. These are inscribed in a code in DNA molecules. Every cell contains a complete genetic description, not only of its own phenotype but also that of the whole organism encompassing it. A fat cell in the stomach contains the complete genetic information for not only itself, but for the teeth, neurons and eyes as well. Every piece of visible tissue carries hundreds or thousands of these genetic representations in the chromosomes of its cells. These genetic descriptions do not simply describe the formation of a body part but are a part of a larger more elaborate machine, which causes a body part to be developed from those descriptions.
The genotype is the full complement of the genetic information, which as described is encoded in every body cell; it is a major determinant of the phenotypic attributes of the organism. The genotype is responsible for ensuring that the offspring from two people is a child and not a dog, mouse or prickly bush! However, genes are not exclusively responsible for a person's phenotype, the environment also plays an essential role. The field of Linguistics is an excellent example of how an environment affects phenotypic traits for example a French baby develops French speech whereas an English baby develops English speech. In general phenotypic traits are specified or "determined" by a combination of genetic and environmental factors.
For the purpose of this study it makes sense to conceptualise the genotype as an indication of an individual’s potential ability and the environment as a system used to evaluate how well the individual’s potential is realised. The way genes interact with the environment is complex, in reality the situation is more complicated than this simplistic model. The phenotype is an emergent property; that is to say that it is greater than the sum of its parts e.g. human thought is reliant on nearly all the cells that make up the brain. If you cut out sections the results are completely different. Therefore, a single cell is incapable of thought and is an emergent property of all the cells of the brain.
The degree to which genes specify phenotype is another variable that differs from aspect to aspect. This is an area which psychologists would call nature versus nurture. To what extent does the environment depict our behaviour and consequently how completely does our upbringing determine our personalities? It is fairly obvious that the age at which a child’s molars appear depends primarily on genes and that the environmental condition largely determine when they disappear. On the other hand, the importance of genes to the criminal personality or of the environment to intellectual development is bitterly contested. These are questions, which the science of genetics simply has not matured enough to be able to resolve, and is a field that has been approached in recent years by psychologists rather than biologists. At the moment biologists know far more about our phenotype than our genotype. Without a full understanding of both the phenotype and genotype the questions posed earlier will lie unanswered or at least without a scientific proof until a breakthrough is found.
3.3 Natural Selection
Natural selection can be described as the process an individual uses in order to select an appropriate mate. In a natural environment there are many selection strategies at work simultaneously, the analysis of these is a laborious task which requires much observation. For most ungulates selection is based on spatially localised dominance and individual fitness, however generalising about selection strategies is difficult given the diversity of species and the plasticity of a species’ implementation of a strategy given a range of differing environments.
3.4 Reproduction
As in all natural systems adaptation is integral to survival, in all biological systems this is achieved by reproduction whether that be asexual or sexual recombination. For the system of study we will concentrate on sexual reproduction between two individuals. Reproduction alone would achieve very little, a simple copy of an individual does not allow for adaptation. If reproduction alone were used then applying Darwin’s principle of ‘survival of the fittest’ would eventually produce a population of clones, these clones would be unable to cope with a change in environment and would subsequently die. In order to allow for adaptation, genetic operators are used to transform an individuals genetic make up:
3.4.1 Crossover
All living things that survive do so in order to serve as progenitors for a new generation and, as mentioned, in order to survive each generation must have the ability to adapt to combat the change in environmental pressures. Meiosis is the process by which cells are drawn together and combine with their homologues. Crossover occurs during recombination and is the reciprocal exchange of material between two paired chromosomes during meiosis, resulting in the transfer of a block of genes from each chromosome to its homologue. Explained simply crossover takes genetic material from both parents and mixes the material in a structured way in order to create an offspring of the original genetic material.
3.4.2 Mutation
Mutation is a change in the character of a gene that is perpetuated in subsequent divisions of the cell in which it occurs.
Biology is the scientific study of life; the problem with biology is that all research is concerned with life as we know it, that being life based on carbon-chain chemistry. As with all scientific studies, to draw conclusions from only one example would be very difficult. Synthetic biology allows us to examine biology from a unique perspective, the way we implement synthetic biology, which in essence is artificial life, is by creating a man made interpretation of life as we know it. The following section explains how we achieve the synthesis of artificial life using biological genetics as an origin.
4.1 Selection Strategies
Evolutionary programs predominantly use fitness proportionate selection strategies, this means that a higher probability of selection for reproduction is given to individuals with higher fitness. The majority of systems use a strategy termed ‘roulette wheel selection’, in this system each individual is given a probability which is proportionate to both its own fitness and the fitness of the remaining population, the following table illustrates this:
|
Individual |
Fitness |
Cumulative Score |
Probability of Selection |
|
1 |
23 |
23 |
0.146 |
|
2 |
89 |
112 |
0.567 |
|
3 |
45 |
157 |
0.287 |
Table 4.1 – Example of selection probability.
For the purpose of the study a roulette wheel selection strategy will be used throughout the prototyping phase, after which the emphasis of the project will move towards analysing how different selection strategies alter the diversity and success of the system.
4.2 Reproduction
The role of reproduction in computing terms is to provide a means of adaptation and evolution, eventually leading to increased fitness and a step towards a solution to the situation being studied.
4.2.1 Crossover
Crossover is a part of the recombination process whereby an attempt is made to create new, improved instruction sets in an attempt to reach a satisfactory conclusion. The most important part of recombination is crossover, in which the system seeks to construct better solutions by combining the features of good existing ones. Crossover relies heavily on a random number generator, which is used to determine whether, and where to perform the crossover. Historically, many methods have been used to implement crossover on a computing level, the simplest form of crossover is one point crossover whereby firstly, the entire population is paired off at random as potential parents. Secondly, pairs of solutions are chosen to undergo crossover where the probability of crossover is determined by the random number generator. If the random number stipulates that crossover will not occur, then both solutions are transferred to the new population unchanged. However, if crossover is approved, then exchanging all the bits following a randomly selected locus on the genotype creates two new – hopefully improved - solutions. For example, if crossover after position five is proposed between parents:
1 0 0 1 1 1 0 1 and 1 1 1 1 0 0 0 0, the resulting offspring are:
1 0 0 1 1 0 0 0 and 1 1 1 1 0 1 0 1
which replace their parents in the population.
A slightly more complex operator, introduced by Cavicchio, is two-point crossover in which two points are randomly selected and the bits between (and including) those positions are exchanged. Where the crossover point exceeds the genotype length a wrap around method is employed. Thus, if crossover between points six (selected first) and two is proposed for strings
1 0 0 1 1 1 0 1 and 1 1 1 1 0 0 0 0, the resulting offspring are
1 1 0 1 1 0 0 0 and 1 0 1 1 0 1 0 1.
Whereas, if crossover is between points two (selected first) and six, the offspring are
1 1 1 1 0 0 0 1 and 1 0 0 1 1 1 0 0.
De Jong tested multiple point crossover operators and found that performance is degraded as more crossover points occur. Although it is essential to introduce some changes in order evolve new, improved solutions too many alterations make the probability of destroying the good features of a solution unacceptably high. Therefore an effective implementation will balance exploitation and exploration.
As an example of how heuristic methods can be used to improve performance, Booker suggested that is was possible to improve the recombination process by stipulating that crossover should only occur where a difference in genotype would occur e.g. if
1 0 1 0 1 0 1 1 and 1 1 0 1 1 0 1 1
are chosen as parents, then only exchanges involving bits two, three or four will result in offspring differing from their parents.
It is difficult if not impossible to accurately predict how a system will respond to the implementation of these techniques. The system of study will be using a multiple crossover approach, a random number will decide whether or not to crossover, this decision will take place for every bit in the genotype. In order to make the system flexible a constant will be declared and used to test the suitability of crossover rates, it is anticipated and inferred by previous studies that a rate of 20 to 30 percent will provide suitable exploration of the possible solutions without destroying already positive results.
4.2.2 Mutation
Mutation is an essential part of any genetic system. The purpose of the mutation process is to provide insurance against the irrevocable loss of genetic information and hence to maintain diversity within the population. For instance, if every solution in the population has 0 as the value of a particular bit, then no amount of crossover will produce a solution with a 1 there instead. Every bit of every solution is potentially susceptible to mutation. Each bit has a probability of mutation determined again by the random number generator, the probability is usually around 0.01 or less. This may sound insignificant until we consider that the size of each individual could be around 200 bits and with over 300 individuals in the population this represents a significant rate of mutation per generation. Obviously, if mutation is approved, the bit changes value (in the case of a binary coding from 0 to 1 or 1 to 0). Mutation in the system of study will be implemented similarly to that of crossover whereby a random number will determine the probability of mutation for each bit in the genotype.
4.3 Self Creating Procedures
The genotype of each robot is essentially an encoded version of the rules that the robot must use to navigate its world. In order to move around within the world a robot must have a way to apply its rules. This is achieved by treating the decoded genotype as a procedure which is compiled and executed whilst the program is running, in a sense each robot is a program itself. During each reproduction phase two robots collaborate to create a new program which is a variant of the substance of each robot.
4.4 Chaos Theory
Chaos Theory, as already mentioned has considerable significance to the
system of study. Chaos Theory attempts
to explain what appears as disorder in an ordered way, most natural processes
can be seen as chaotic such as weather systems or the tidal system. What makes
these systems chaotic is the way that the results of one operation have
implications on the next stage and can still be seem to be having an effect
many stages later. An example of a natural chaotic system:
“The flapping of a single butterfly's wing today produces a tiny change in the state of the atmosphere. Over a period of time, what the atmosphere actually does diverges from what it would have done. So, in a month's time, a tornado that would have devastated the Indonesian coast doesn't happen. Or maybe one that wasn't going to happen, does.
(Ian Stewart, Does God Play Dice? The
Mathematics of Chaos, pg. 141)
It is anticipated that the
system created will seem similar to these natural systems, a slight change to a
robot in generation one, such as mutation, could completely change the overall
success of the system (adversely or advantageously). Therefore occurrences which appear to be happening at random may
actually be a reaction to an operation which happened many generations
earlier. Chaotic systems are not simply
random but very, very complex and can be highly unpredictable, systems such as
this have a large dependency on their initial conditions, a small change in
initial conditions can drastically change the long term behaviour of the
system. As complex as chaotic systems
may be they can be defined by a few simple features:
ü Chaotic systems are deterministic; they have something determining their behaviour.
ü Chaotic systems are very sensitive to the initial conditions.
ü Chaotic systems appear disordered, even random, but are not. Beneath the apparently random behaviour is order and direction.
In this world of order, chaos rules!
In the natural world genotypes are used to inscribe the characteristics of its originator, as in the real world a genotype will be used to specify the characteristics of each robot. Every robot in the population lives by a set of instructions and it is these instructions which are held within the genotype the suitability of these instructions to the environment is a measure of the robots fitness. Individuals in the population are represented as fixed length arrays, the length of these strings will be determined by calculating how many instructions would be needed to create a ‘perfect robot’ plus an allowance for redundant or erroneous instructions. Although the concept of a ‘perfect robot’ is used to infer the required array size, a ‘perfect robot’ is by no means the objective of the system. If we wanted a robot to perform in a specific, predictable manner we might as well use explicit programming techniques to achieve the goal, the ingenuity of a system such as this is that the robots will evolve mannerisms that achieve results by exploitation of the rules imposed upon them. A recent example of a similar system is documented in the British Computer Societies Jan ’98 publication of The Computer Bulletin (p18). The idea of Adrian Thompson was to use genetic algorithms to produce a circuit, which could discriminate between two audio tones, the result of the system was that a circuit was developed which performed the task better and quicker than any explicitly designed circuit. Although the success of the circuit is not fully understood some points are clear, firstly, the circuit operates in analogue not digital, secondly, that it uses either the capacitive effects or electromagnetic inductance of the field programmable gate arrays to create a highly effective solution. Another point that may be of interest to microprocessor enthusiasts is that Adrian was so determined to separate his system from the human conventions of microprocessor design that the system he used had no concept of a system clock!
As described earlier robots will be required to pick up litter and deposit it in bins, both of which will be randomly placed throughout the environment. Therefore, robots will need to be capable of movement within the world and will need to have some information about the objects surrounding it. A robot should be capable of executing instruction such as:
v If litter is to the right then turn right
v If stood on a bin and carrying litter then drop litter into bin
v If litter is less than 3 spaces forward then move forward
So, the robot will need an indication of direction and distance for every piece of litter and bin around it, this will be controlled by a sense function which will scan the surrounding area and return the required variables. In order to implement the robot genotype an array of bits will be used, each instruction in a robot’s genotype is effectively an ‘if’ statement. From the following examples it can be seen that an operator, action and operands will be used to construct each instruction, the implementation of each instruction can be accomplished using 9 bits to represent the instruction, the first two bits represent the first operand:
|
Value |
Operand |
|
00 |
Bin Distance |
|
01 |
Bin Direction |
|
10 |
Litter Distance |
|
11 |
Litter Direction |
Table 5(a) – Instruction explanation (bits 1 & 2)
The second two bits represent the operator:
|
Value |
Operator |
|
00 |
= |
|
01 |
> |
|
10 |
< |
|
11 |
/= |
Table 5(b) - Instruction explanation (bits 3 & 4)
The next two bits can represent either the distance or direction from an object determined by the last bit of the first operand (i.e. if the last bit of the first operand is a one then the value represents direction):
|
Value |
Distance(in spaces) |
Direction |
|
|
Value |
Meaning |
||
|
00 |
0 |
0 |
North |
|
01 |
1 |
1 |
East |
|
10 |
2 |
2 |
South |
|
11 |
3 |
3 |
West |
Table 5(c) - Instruction explanation (bits 5 & 6)
The final 3 bits are used to represent the action to be taken should the statement prove correct:
|
Value |
Operator |
|
000 |
Move Forward |
|
001 |
Turn Backward |
|
010 |
Turn Left |
|
011 |
Turn Right |
|
100 |
Pickup |
|
101 |
Drop |
Table 5(d) - Instruction explanation (bits 7,8 & 9)
A few examples of robot instructions and their binary equivalents:
|
Binary Instruction |
Meaning |
|
000000000 |
If Bin Distance is 0 spaces away(on) then Move Forward |
|
111111101 |
If
Litter Distance is not three spaces
away then Drop |
|
010101011 |
If Bin Direction is greater than 1(East) then Turn Right |
Table 5(e) - Instruction explanation (sample instructions)
Each robot will be tested in a variety of randomly generated environments and will be assigned a fitness score depending on its success within those environments. This score will be held along with the robot’s genotype to indicate its suitability for selection for reproduction.
The world will be implemented as a two-dimensional array with each position occupied by characters representing bins, litter or free spaces. The robot will be given free movement within the world and although a bin could occupy a space, in the theoretical world the size of each space can be seen as being big enough to support both the bin and robot simultaneously.
In an attempt to create a population of robots whose instruction sets will be successful in any environment, as stated previously, each robot will be tested in a number of different environments. The environments or test worlds will be created randomly and each will contain a set amount of litter and bins, these amounts will be altered throughout program execution. In order to examine how robots react to increases and decreases in both bins and litter. It is anticipated that the world will be implemented as a 10 by 10 grid wherein each cell in the world will either contain a bin, litter or nothing. Effectively the world is a room with litter, bins and solid walls, one issue with systems such as this is to make the world toroidal i.e. if a robot were to move over the border of the world then it would appear at opposite side, effectively the world becomes spherical. For this study an attempt has been made to implement a system that could plausibly be implemented in our own environment. As such a non-toroidal world effectively recreates the situation of a robot in a closed room collecting and disposing of litter, the solid walls also help to create a robot who’s characteristics now include wall and more importantly corner avoidance. A typical world used to test each robot will look similar to that shown in figure 5(f).
A robot’s success in the world will be evaluated by analysing how much litter it has managed to both pick up and deposit. A robot that fails to execute either of these actions but who shows the ability to move effectively within the world will acquire a greater score than the robot who simply spins on the spot. A comprehensive analysis will be performed in order to establish the appropriate allocation of points for each of the actions, this may be changed for different selection strategies to achieve maximum success.
It is not yet decided where the robot will initially be placed in the world however it is anticipated that this will either be decided randomly or will be the calculated center of the world to avoid bias towards lateral or longitudinal movement. This decision will be made during the prototype phase by experimentation, as will many other issues such as amount of instructions per robot, scoring strategies and probability of crossover and mutation.
Rubbish Bin
. Figure 5(f) – A Sample World.
Although it has been stated previously that a formal method or more precisely Z, is to be used in the design process, the initial decision to use Z for the whole of the design proved time consuming, unwieldy and deficient in many areas. One major concern was that Z has no concept or way of modeling for random numbers that are of critical importance to any system that displays chaotic behaviour, such as this. Despite this Z is an excellent tool for modeling the functionality of the system at quite an abstract level and will be used to specify some of the more imperative functions of the system, which will benefit from unambiguous specification in Z.
In addition to the use of Z, pseudo code algorithms will also be used in an attempt to specify the function of each part of the system. Although a prototype has been used throughout the project the pseudo code will only reflect the design of the final system and not each stage in the prototype development this would be both lengthy and unnecessarily complicated.
It should be noted that any system such as this is designed quite loosely and will inevitably be subject to change. To attempt to predict the behaviour of the system is senseless, since to predict the effect of different probability factors, population sizes, genotype lengths etc would be futile and excessively time consuming. The most effective way to assess these factors is through experimentation and examination of the results. The prototype system will allow for this analytical approach, however, changes may need to be made to ensure the success of each selection strategy.
Figure 6(a) shows flowchart typically used in genetic programming circles to describe the lifecycle of the system from population conception through to program termination. Although this flowchart is not directly used to aid program design, it does give a clear indication of the fundamental steps required to create the system.
Figure 6(a) – Flowchart of a Genetic Program
Pseudo Code
To ensure ease of alteration, many constant variables will be used to make testing of different values uncomplicated. The list of expected constants and example values follow:
v Population_Size 100
v Life_Span 30
v Lower_Bound 1
v Upper_Bound 10
v Amount_Litter 10
v Amount_Bins 5
v Mutation_Probability 1
v Crossover_Probability 20
v Object [[Bin_Distance] [Bin_Direction]
[Rubbish_Distance] [Rubbish_Direction] ]
v Operation [ [ = ] [>] [<] [!=] ]
v Action [ [Forward] [Backward] [Left] [Right] [Pickup]
[Drop] ]
v Directions [ [North 0] [East 1] [South 2] [West 3] ]
v Size_Of_Genotype 90
v Instruction_Size 9
v Sense_Long -2
v Sense_Lat -3
The first step in the program is to create an initial population of robots; each robot should be given random instructions:
Procedure
Initialise_Population
Introduce Inst
For each individual in the population
For each bit in the genotype
Insert random number between 1 and 2Instruction_Size into Inst
End For
Add Robot with inst as its genotype into the population
End For
End
Procedure
Next is the procedure to create a random environment or test world, which will include bins and rubbish in random locations:
Procedure
Create_Test_World -> Test_World
Introduce Index, Y & X
Create a 2 dimensional array of size Upper_Bound * Upper_Bound called Test_World
Initialise Test_World locations to 0
For Index from 1 to Amount_Bins
Set X to be a random number between 1 and Upper_Bound
Set Y to be a random number between 1 and Upper_Bound
While Test_World(X,Y) is occupied
Set X to be a random number between 1 and Upper_Bound
Set Y to be a random number between 1 and Upper_Bound
End While
Set Test_World(X,Y) to ‘b’
End For
For Index from 1 to Amount_Litter
Set X to be a random number between 1 and Upper_Bound
Set Y to be a random number between 1 and Upper_Bound
While Test_World(X,Y) is occupied
Set X to be a random number between 1 and Upper_Bound
Set Y to be a random number between 1 and Upper_Bound
End While
Set Test_World(X,Y) to ‘r’
End For
End_Procedure
In order to establish the fitness of each robot we must have a method of testing the robots, the next few procedures describe how the robots are moved around and allocated scores in the test world:
Procedure
Move_Robot
Introduce i, j, Score and Act
Create 2 dimensional array of size Upper_Bound * Upper_Bound called Temp_World
For each individual in the population
Set Temp_World to Test_World
Initialise Robot_Starting_Position
Make_Procedure( Current Robot Genotype ) -> Act;
For I from 1 to Life_Span
Set_Senses(Sense(Current Robot Position))
Act() -> Score
Add Score to Current Robot Fitness
End For
Set Test_World to Temp_World
End For
End
Procedure
Procedure
Make_Procedure(Individual) -> Action
Introduce I, RobotRules
Set RobotRules to (‘procedure; if ‘,
Generate_Rule (Individual (1)),
For I from 2 to Size_Of_Genotype
‘elseif ‘,
Generate_Rule (Individual (I),
End For
‘endif;’,
‘endprocedure;’)
Set Action to evaluate(RoboRules)
End Procedure
Procedure Generate_Rules (rule) -> statement
Introduce val
Set statement to ‘ ‘
Add evaluate (Object ((rule Logical_AND 112) + 1)) to statement
Shift rule 2 places right
Add evaluate (Operation ((rule Logical_AND 112) + 1)) to statement
Shift rule 2 places right
Convert ((rule Logical_AND 112) + 1) to decimal and add to statement
Shift rule 2 places right
Add ‘then’ to statement
Add evaluate (Action ((rule Logical_AND 1112) + 1)) to statement
Add ';' to statement
End
Procedure
Procedure
Set_Senses (objects)
Introduce object
Set Bin_Distance to 4
Set Rubbish_Distance to 4
Set Bin_Direction to 4
Set Rubbish_ Direction to 4
For each object in objects do
If object (2) is rubbish and object (1) is less than Rubbish_Distance
Set Rubbish_Distance to object (1)
Set Rubbish_Direction to object (3)
End If
If object (2) is bin and object (1) is less than Bin_Distance
Set Bin_Distance to object (1)
Set Bin_Direction to object (3)
End If
End For
End
Procedure
Procedure sense (position)
Introduce i, j, x, y
Set x to position (1)
Set y to position (2)
Create and return a list containing:
[ For i from Sense_Long to abs (Sense_Long)
For j from Sense_Lat to abs (Sense_Lat)
If (x + i and y + j are within the bound of the world and the space Test_World (x + i, y + j) is occupied
Create the list:
[ Abs (i) + abs (j), Test_World (x+i, y+j),
Relative_Direction (i, j)
]
End If
End For
End For
]
End
Procedure
Procedure
Relative_Direction (i, j)
Introduce face
If i equals 0 and j equals 0
Set face to 4
Else If abs (i) is less than or equal to abs (j)
If j is greater than 0
Set face to East
Else
Set face to West
End If
Else If i is greater than 0 then
Set face to South
Else
Set face to North
End If
Return (face – Currently_Facing) Logical_AND 3
End
Procedure
Procedure
Forward -> score
If Robot is at least one space from the bounds of the world
If Robot is facing North
Subtract 1 from Robot x position
Else If Robot is facing South
Add 1 to Robot x position
Else If Robot is facing West
Subtract 1 from Robot y position
Else If Robot is facing East then
Add 1 to Robot Y position
End If
Set score to 20
End If
End
Procedure
Procedure
Backward -> score
Set facing to (Facing + 2) Logical_AND 3
Set score to 1
End
Procedure
Procedure
Right -> score;
Set facing to (Facing + 1) Logical_AND 3
Set score to 1
End
Procedure
Procedure
Left -> score;
Set facing to (Facing + 3) Logical_AND 3
Set score to 1
End
Procedure
Procedure
Pickup -> score;
If Robot is stood in same space rubbish
Empty Current position
Add 1 to the amount of rubbish the robot is carrying
Set score to 100
End If
End
Procedure
Procedure
Drop -> score
If robot is carrying rubbish and current position is shared by a bin or empty
Subtract 1 from the amount of rubbish being carried
If current position is shared by a bin
Set score to 300
Else
Set content of current space to 'r'
Set score to 100
End If;
End If
End
Procedure
Procedure
Roulette_Wheel_Selection;
Introduce Sum, Index, Pos, Offspring, Parent1, Child1, Child2
Create a new array called New_Population of size Population_Size
Reset Fittest_Robot to have 0 fitness
Set Generation_Mean to 0
For index from each robot in population do
Output robot fitness to a file
Add this robot fitness to Generation_Mean
Add this robot fitness to Sum
If this robot is fitter than Fittest_Robot
Save this robot to Fittest_Robot
End If
Set robot fitness to Generation_Mean
End For
Set Generation_Mean to Generation_Mean / Population_Size
For Offspring from 1 by 2 to Population_Size - 1
Set Pos to a random number between 1 and Sum
Set Index to 1
While index is less than or equal to Population_Size and robot at Index
position in array has fitness less than Pos
Add 1 to Index
End While
Set Parebt1 to index
Set Pos to a random number between 1 and Sum
Set Index to 1
While index is less than or equal to Population_Size and robot at Index
position in array has fitness less than Pos
Add 1 to Index
If Robot is found but is the same as Parent1 Set Pos to a random number between 1 and Sum Set Index to 1
End If
End While
Reproduce the Genotype of Parent1 & Index Giving Child1 & Child2
Add Child1 & Child2 to New_Population
End For
Set Population to New_Population
End
Procedure
Procedure
Reproduce (Robot1, Robot2) -> Newrobot1 -> Newrobot2;
Introduce bot1, bot2, bot3, Xmask, Mutemask, Mutemask2, instindex, genepos
Reset Xmask to a set of 1’s of size Size_Of_Genotype
Reset Mutemask & Mutemask2 to sets of 0’s of size Size_Of_Genotype
Reset bot1, bot2, bot3, Newrobot1, Newrobot2 to sets of 0’s of size
Size_Of_Genotype / Instruction_Size
For genepos from 1 to Size_Of_Genotype do
If a random number less than 100 is less than Crossover_Probability
Set Xmask (genepos) to 0
End If
If a random number less than 1000 is less than or equal to
Mutation_Probability
Set Mutemask (genepos) to 1
End If
If a random number less than 1000 is less than or equal to
Mutation_Probability
Set Mutemask2 (genepos) to 1
End If
End For
Set instindex to 1
For genepos from 1 to Size_Of_Genotype
Set bot1 (instindex) to bot1 (instindex) *2 + Xmask (genepos)
Set bot2 (instindex) to bot2 (instindex) *2 + Mutemask (genepos)
Set bot3 (instindex) to bot3 (instindex) *2 + Mutemask2 (genepos)
If genepos mod Instruction_Size = 0
Add 1 to instindex
End If
End For
Set Xmask to bot1, Set Mutemask to bot2 & Set Mutemask2 to bot3
For instindex from 1 to Size_Of_Genotype / Instruction_Size
Set Newrobot1 (instindex) to (Robot1 (instindex) Logical_AND
Xmask (instindex)) Logical_OR (Robot2 (instindex)
Logical_AND (Logical_NOT Xmask (instindex)))
Logical_EOR Mutemask (instindex)
Set Newrobot2 (instindex) to (Robot2 (instindex) Logical_AND
Xmask (instindex)) Logical_OR (Robot1 (instindex)
Logical_AND (Logical_NOT Xmask (instindex)))
Logical_EOR Mutemask2 (instindex)
End For
End
Procedure
Formal Design in Z
In order to demonstrate the design in an unambiguous manner two procedures have been chosen for specification in Z, although this provides an effective representation of the intended program it can be seen from the following example that Z cannot represent random operations. We can say that each location will contain the value r, b or 0 but we cannot specify that this will be decided randomly. In this sense Z has been used as a tool to specify the rules by which the system must exist and as a representation of the intended program implementation.
Reproduction
Reproduction
genotype : seq[000000000 .. 111111111]
parent1? : genotype
parent2? : genotype
child1! : genotype
child2! : genotype
Õ parent1, parent2, child1, child2 : genotype; i : 1 .. rules; j : 1 .. 9 |
{Õj : 1..9 | (Ö m1 : 0..1 • m1 <> parent1?(ij)) ( Ö m2 : 0..1 • m2 <> parent2?(ij))
(child1!(ij) = parent1?(ij) ^ child2!(ij) = parent2?(ij) ) V
(child1!(ij) = m1?(ij) ^ child2!(ij) = parent2?(ij) ) V
(child1!(ij) = parent1?(ij) ^ child2!(ij) = m2?(ij) ) V
(child1!(ij) = m1?(ij) ^ child2!(ij) = m2?(ij) ) V
(child1!(ij) = parent2?(ij) ^ child2!(ij) = parent1?(ij) )
• j'= j + 1}• i’= i + 1 ^ j =1
Create Test World
Create_Test_World
Loc_Content : [ r, b, 0].
TestWorld! : iseq[iseq[Loc_Content]
RB0? : Loc_Content
TestWorld! = { Õy : TestWorld | { Õx : ran(head y) | ran(head x)) = [RB0?]
• x` = tail x } • y` = tail y }
7.1 Optimisation
Initially and in accordance with previous studies the program was running slowly, it was taking between 45 seconds and 1 minute per generation. Although the performance was slightly faster than previous studies mainly due to the hardware being used - a Pentium 200MMX with 48Mb of memory running Poplog on Linux platform – this is still slow. It was decided that some time would be spent in code optimisation because if this proved successful the time spent optimising would be recouped by the time saving in program run-time. Another area of concern was that the student version of Poplog has a memory limit of 200Kb, this proved to be a problem due to inefficient disposal of exhausted data structures, also because the size of the data structures being used were unexpectedly large.
7.1.1 Optimisation for Size
The first stage in the optimisation process was to solve the memory problems as this actually caused the program to crash, whereas slow execution could be tolerated, for the time being anyway. Initially it was thought that ensuring that all data structures where disposed of as soon as they became expendable could solve the problem. Although this identified some oversights in the design of the program and allowed the program to run for slightly longer periods of time it did not stop the program from crashing through ‘out of memory’ errors. At this point the program was using integers to represent each bit in the robot’s genotype, this meant that each robot using 90 integers to represent its genotype when actually this could be achieved using only 90 bits. The use of bit operators was introduced into the program and all large structures were converted to bits, this meant a space saving of 90% was achieved. This had a massive effect on program execution, as well as allowing the program to run indefinitely, the speed of execution was improved by approximately 40% in particular the reproduction and population initialisation functions experienced speed improvements of 60%.
7.1.2 Optimisation for Speed
Through optimising the system to use smaller structures a time saving had already been experienced, however, it was evident that introducing fast operators and fast iterations could achieve further improvements. These fast operations work by omitting the type checking performed by normal operators and iterative loops, for this reason it is important that the program is tested thoroughly to ensure that all types are concurrent with the types expected by the operation. The testing section demonstrates how the type checking was conducted. Through using fast operators the speed of execution was improved to the extent that the program now takes only five seconds per generation, that’s a speed saving of 88.89%!
7.2 Testing
The program has been developed as a prototype system, which means that much of the testing has occurred as and when it has been necessary. Standards have been followed during testing which ensures semantic and type compatibility correctness. Many traditional programs may use a system whereby success is depicted by how accurately an expected output matches the actual result, in a program as chaotic as this it would be unfeasible to attempt to predict the behaviour of many parts of the system to any degree of accuracy. The string ‘investigation’ in the expected column will represent a variable or procedure whose behaviour is unpredictable, either a þor a ý to represent whether the variable content or procedure result is satisfactory. Table 7.2 indicates the format of the testing strategy, the results of testing other procedures are included in Appendix C.
Create Test World
Test Subject |
Type Of Arguments |
Resulting Type |
Expected Result |
Actual Result |
|
Procedure Create_Test_World -> Testenv |
N/A |
2D Array |
Investigation |
þ |
|
For index from 1 to Amount_Bins do |
All Integers |
N/A |
N/A |
N/A |
|
Random(Upper_Bound) -> index_x |
Integer |
Integer |
Random No between 1 and Upper_Bound |
As Expected |
|
Random(Upper_Bound) -> index_y |
Integer |
Integer |
Random No between 1 and Upper_Bound |
As Expected |
|
'b' -> testenv(index_x, index_y) |
Char -> Array Position |
N/A |
‘b’ inserted into array |
As Expected |
|
While (testenv (index_x, index_y) ) /= 0 do |
Array (Integer, Integer) /= Integer |
Boolean |
True or False |
As Expected |
|
For index from 1 to Amount_Litter do |
All Integers |
N/A |
N/A |
N/A |
|
Random(Upper_Bound) -> index_x |
Integer |
Integer |
Random No between 1 and Upper_Bound |
As Expected |
|
Random(Upper_Bound) -> index_y |
Integer |
Integer |
Random No between 1 and Upper_Bound |
As Expected |
|
'r' -> testenv(index_x, index_y) |
Char -> Array Position |
N/A |
‘r’ inserted into array |
As Expected |
Initial Performance
The following data was taken before the optimisation process
and although at this stage the program was running slowly, it was evident that
evolution was taking place, figure 7(a) shows the very first successful
evolution of the program:
Figure 7(a) – Graph of Initial Performance.
This chart shows a ten point moving
average of the average robot fitness per generation over 600 generations, in
addition a power curve has been fitted to this data. It can be seen that the initial fitness was relatively low (200)
until a large improvement occurred at generations 11 through 16. This established a population of much fitter
robot but unfortunately no substantial improvement occurred after this
point. A common failure of genetic
programs is premature convergence, this happens when the population becomes
very similar and so diversity in the population is reduced. When so many individuals are similar
reproduction has little effect on the fitness of the population crossover
between two analogous parents will produce a cloned child. Once premature convergence has occurred the
only way to progress is by mutation but this can lead to detrimental mutation
as easily as beneficial mutation.
During the prototype stage of development I soon noticed that a tool was
needed to identify the progress of each program run and to help identify
problems such as premature convergence.
Researchers in genetic programs frequently envision the output of their
programs as landscapes with peaks and troughs representing the improvement or
depreciation in success, a program called MatLab was used to create surface
plots of 
each generation. The
resulting graph from run 1 of the program is shown in figure 7(b), however due
to the cost of the full version of MatLab I have been restricted to
Figure 7(b) – Surface Plot of Initial Performance.
using the student version. This version restricts the user by insisting that at least one dimension of any 3D plot has less than 32 data items, in order to achieve this an averaging function was applied to each of the individuals fitness data. Fortunately, this has had a beneficial effect as through averaging the plot is smoothed and effectively shows the result of the program without the eccentric fluctuations of the raw data. Substantial programming and an understanding of the functionality of MatLab was needed to create the program which displays the graphs such as that shown in figure 7(b) because of this the code developed to achieve this is included in Appendix B. However it was felt that the design of this particular program was beyond the scope of the study.
It can be seen from figure 7(b) that areas of low fitness are shown in blue as troughs and areas of high fitness as red peaks, the azimuth and elevation of the viewpoint can be altered to achieve a representative view of the data. It can be seen from this plot that premature convergence has occurred, this is evident by the fact that the whole population mirrors all peaks and troughs in any one generation indicating that all robot’s are so similar that a change in environment affects each robot in the same way. A healthy run would show that whilst maintaining an average increase in fitness throughout generations, individuals in the same generation would maintain diversity from their homologues by achieving varied fitness scores. Figure 7(c) shows the progress of one of the robots in this first run, the (simplified) instructions (genotype) that one of the robots from this run robot evolved are shown in table 7(d).
As the robots evolve their performance is recorded using two files, the first of which records the fitness of each robot in every generation. The second file records the average fitness of each generation, the score of the fittest robot and the decoded rule set of the fittest robot. An example from both of these files is included in Appendix E.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Start |
|
Pickup |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Drop*2 |
|
|
Pickup |
|
|
|
|
|
|
Pickup |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Stuck! |
|
|
|
|
|
|
|
|
|
Figure 7(c) – Route Taken By An Initial Robot.
Instruction
1 |
IF rubbish direction is 1 then move forward |
Instruction 2 |
IF bin direction is 2 then move forward |
Instruction 3 |
IF rubbish distance is not 3 then pickup |
Instruction 4 |
IF rubbish distance is 1 then turn pickup |
Instruction 5 |
IF bin distance is 2 then turn left |
Instruction 6 |
IF bin distance is 0 then drop |
Instruction 7 |
IF bin direction is 2 then turn backwards |
Instruction 8 |
IF bin distance is 0 then drop |
Instruction 9 |
IF rubbish direction is 4 then turn left |
Table 7(d) – Instructions of An Initial Robot.
Although many of the instructions seem to have random effects they have actually evolved over many generations and consistently achieve good results, this particular robot has learnt to exploit the tendency of the program to create environments in which this instruction set has success. On a lighter note, during the prototype phase I had (without realising) designed the system to allow the robot to pickup whenever it landed on an occupied space, when analysing the system I spent quite some time wondering why the environment kept changing at random intervals. What was actually happening was that some robots were learning that picking up bins achieved the same reward as picking up litter, in fact, at times robots were depositing bins into rubbish, due to the logic of the system this caused the bins to disappear! If the robot put the bin into an unoccupied space an extra piece of litter was created, the robot was scoring points for creating mess!
The results of this initial run were very successful, however it was worrying that the program took so long to run, although the program execution was expected to be slow, it was decided that optimisation at this point could lead to quicker execution. Another point to consider was that the evolution of the robots was initially very quick but subsequently became relatively static. Investigation revealed that the reason for this was the scoring strategy, not enough points were being awarded for dropping litter. Robots were moving around picking up litter but whenever litter was dropped it was occurring randomly rather than robots learning that dropping litter was an advantageous strategy, this was soon rectified by simply increasing the score awarded to robots as they drop litter.
The purpose of all selection strategies is to give a greater
chance of paternity to the individuals with highest fitness, in general all
selection strategies adhere to Darwin’s theory of survival of the fittest. The selection strategy has a colossal effect
on the behaviour of the system, without a selection strategy evolution could
not be guaranteed and most likely would simply create random fluctuations from
the initial population fitness. This is
proved by figures 9(a) and 9(b), this simulation was achieved by implementing
random parent selection, obviously this selection process had no concept of the
fitness of the robot.
Figure 9(a) – A random selection process (Line Chart)
Figure 9(a) – A random selection process (Surface Plot)
During the research of this project many selection strategies have been implemented and many more have been considered, selection strategies commonly used in genetic programs and artificial life simulations are well documented and easily implemented. Natural selection strategies however, are much more difficult to study and require a certain amount of generalisation in order to create a computerised interpretation of their performance. A significant effort has been concentrated on the mating habits of ungulates, one finding is that many species exhibit great plasticity in their application of selection strategies, for example, in one environment they may adopt one system and another system may be used in slightly different surroundings. It should be noted that in order to give strategies a reasonable chance of success the scoring mechanism needs to be changed, it should not therefore be concluded that a higher score represents a better strategy. Rather than simply examining the fitness score it is the consistency and extent of evolution that is being studied. This section describes many of the strategies examined and how some of them were implemented, the strategies which where picked for implementation show the results of evolution as line charts representing the average fitness of each generation and as a surface plot representing the fitness of each individual. The mating strategies used by ungulates exclusively fit into one of three categories:
9.1 Spatially Localised Dominance
Spatially localised dominance, or territorialism, is widespread in ungulates and is the largest single category of selection strategies. In natural systems the territory is a defended area of some kind which is usually marked in a manner, such as urination.
9.1.1 Black Rhinoceros
Black Rhinoceroses operate two separate types social behaviour. A rhino is either an exclusive member of a territorial group or is considered a satellite. A satellite is able to co-occupy territories held by dominants and will be tolerated so long as it adopts subordinate behaviour. To implement this a system was designed which identified robots and grouped them according to their location within the world, this was considered a social group. Dominant robots where then allowed to reproduce, a simulated dice was used to decide when to allow a satellite robot to rove into the group and mate within the social group.
9.1.2 Vicugna
This ungulate operates two social groups firstly dominant males roam the environment as small, loose groups of bachelors usually less than 6 males, although some larger grouping does occur, and secondly harem groups of females. The harem is guarded with vigilance by the dominant vicugna, however a certain amount of tolerance to members of the same social group does occur.
9.1.3 Gorilla
The gorilla lives by a strict system of hierarchy; a dominant
male or silverback will protect a harem of females, the social groups are
usually quite small containing around four females and their young. This system was implemented by dividing
robots into packs according to their final position in the test world a random number
between 1 and the number of packs is then generated which indicates which group
to start mating. The dominant robot is
identified and this robot operates a harem mating strategy, the results of this
are shown in figures 9.1.3(a) and 9.1.3(b).
The two figures indicate that the gorilla strategy was quite
disappointing, evolution is evident in both graphs, however, it seems very
unstable and further investigation showed that the environment largely dictated
evolution. The redeeming factor in this
implementation is that it produced some exceptionally fit individuals achieving
(raw) scores of over 7000.
Figure 9.1.3(a) – Gorilla Performance (Line Chart)
Figure 9.1.3(b) – Gorilla Performance (Surface Plot)
9.2 Mobile Dominance
This category is similar to spatially localised dominance in that it involves a dominant male protecting a harem of potential mates, it differs however in that the male tends to protect the area in which he happens to be rather than moving around with the harem.
9.2.1 Mountain Zebra
Mountain zebras live in family groups containing 2 to 16 animals and also as smaller bachelor groups. Within the family an absolute dominance hierarchy is adopted with the stallion being the dominator. Like black rhinos, mountain zebra also tolerate satellite bachelors.
9.2.2 Eland
The eland is a highly mobile species and inhabit large overlapping home ranges. There is no marking of territory and so movement throughout home ranges is relatively unhindered, however during mating season an absolute hierarchy is adopted whenever a male temporarily enters a herd.
9.3 Exclusive Home Sites
This category of social organisation is rare; it is limited to only two species - the warthog and the hippopotamus, which operate extremely similar selection strategies.
9.3.1 Warthog (and Hippoptamus)
The female warthogs form social groups of up to ten animals, each group occupies a fixed home range, which does not seem to be defended. Male warthogs live singly or in unstable groups, they associate with females temporarily during the mating season when they will defend only the female they are with.
In addition to these naturally occurring selection strategies many of the already documented strategies used within the fields of artificial life and genetic programming have been implemented:
9.4 Elitism
This is the process by which only the dominant individuals are selected for reproduction, in most systems this is implemented by sorting the generation by fitness. A designated amount of fit individuals are grouped together, individuals from this preeminent group are then selected randomly to act as parents. A known problem with this strategy is that evolution is often inhibited by premature convergence. The results of implementing this strategy are show in figures 9.4(a) and 9.4(b).
Figure 9.4(a) – Elitist Performance
(Line Chart)
Figure 9.4(b) - Elitist Performance
(Surface Plot)
It is surprising that the elitist strategy seems to have worked so well, it was expected that the performance would reach an early peak at which point the lack of diversity within the population was expected to inhibit evolution. In actual fact convergence does not seem to have occurred at all. Figure 9.4(b) shows that diversity is maintained even up to generation 300. Although a certain amount of convergence has occurred and later in the evolution it can be seen that the environment has dictated the success of the much of the population, even at this point there is enough variation in the instruction sets of each robot to support further evolution.
9.5 Roulette Wheel
Roulette wheel selection provides a strategy where each
individual’s chance of selection is directly proportionate to its fitness. This is achieved by setting the fitness of
each individual to the sum of all preceding individuals added to the fitness of
the individual directly after testing.
A random number between 1 and the sum of all fitnesses is generated; the
individual who’s newly calculated fitness is equal to or greater than the random
number is selected for reproduction.
The results of this strategy are shown in figures 9.5(a) and 9.5(b).
Figure 9.5(a) – Roulette Wheel Performance (Line Chart)
Figure 9.5(b) - Roulette Wheel Performance (Surface Plot)
As can be seen from these results the roulette wheel strategy
creates a consistently successful system of evolution, diversity is also
maintained as can be seen by the dimples in the surface of figure 9.5(b). Evolution is initially very fast at which
point no large improvement is made to the overall fitness of the population
although a small improvement occurs consistently over the remaining
generations.
9.6 Result of Study
It is quite self evident that the most effective selection strategy for the litter-clearing robot is the first strategy that was implemented – the roulette wheel. This was the only strategy that achieved consistent evolution whilst maintaining reasonable diversity within the population. The elitist strategy was effective in producing comparably fit individuals but evolution was more fluctuant. The gorilla strategy promoted diversity in the population however due to the grouping nature of the strategy robots learnt to exploit this, often to the extent that up to 80% of individuals often occupied the same space. This meant that even unfit individuals where allowed to mate as they had exploited the rules to achieve group membership.
This project has described a very complex system of evolutionary learning and introduced the reader to fields such as Genetics, Artificial Life and Chaos Theory in a manner that is hoped to be both informative and gripping.
Preceding the decision to implement this system I had absolutely no knowledge of artificial life or evolutionary learning, in particular the science of genetics in both biological and computerised systems was regarded as interesting but beyond my learning capacity. Although my understanding of genetics is limited to the domains described throughout the report, I have developed a substantial knowledge of the genre of program which utilise genetics and would be confident of my ability to understand and analyse such systems.
The only disappointment encountered was that a greater amount of selection strategies could have been investigated. However, it was evident early in the investigation that the best strategy was the first to be implemented - the roulette wheel. Although further strategies were available for implementation, with experience the effect of these strategies could be hypothesised with reasonable accuracy.
As the project has developed there have been many areas of artificial life, which although falling outside of the realms of this project have created more than a spark of interest and will no doubt be investigated subsequent to the project submission.
C Langton, C Taylor, J Farmer, S Ramussen Artificial Life II, 1992
Oxford University Press / AND Software Concise Oxford Dictionary (CD), 1995
The British
Computer Society The
Computer Bulletin, January [1] 1998
R
Barrett, A Ramsay, A Sloman POP
11 - A Practical Language for Artificial Intelligence, 1985
The Math Works Inc. The Student edition of MATLAB,
1995
Kenneth E Kinnear Advances
In Genetic Programming, 1994
William & Wilkins Stedmans Medical
Dictionary, 1994
Lawrence Davis Handbook of Genetic
Algorithms, 1991
[1] Hans Moravec Mind
Children, 1988
Antonis Diller Z – An
introduction to Formal Methods,
1994
Dr A Oswald Student
Project Handbook, 1996
John R Koza Genetic
Programming, 1993
R Forsyth Machine
Learning - Principles and
Techniques, 1984
W Allee The
Social Life of Animals, 1941
13.1 Web Sites
Sussex University – School of Cognitive & Computer Sciences - www.cogs.susx.ac.uk
Brandeis University – aLife Library - www.brandeis.edu/~zippy/alife-library
Genetic Programming Notebook – www.jrabbit.com/~js
Santa Fe Institute – aLife Web Site - http::/alife.santafe.edu
Table 4.1 – Example of selection probability..................... 12
Table 5(a) – Instruction explanation (bits 1
& 2)............... 18
Table 5(b) - Instruction explanation (bits 3
& 4)................ 19
Table 5(c) - Instruction explanation (bits 5
& 6)................ 19
Table 5(d) - Instruction explanation (bits 7,8
& 9)............ 20
Table 5(e) - Instruction explanation (sample
instructions) 20
Figure 5(f) – A Sample World................................................ 22
Figure 6(a) – Flowchart of a Genetic Program.................. 24
Table 7.2 – Test Strategy........................................................... 44
Figure 7(a) – Graph of Initial Performance........................ 45
Figure 7(b) – Surface Plot of Initial
Performance............. 46
Figure 7(c) – Route Taken By An Initial Robot................. 48
Table 7(d) – Instructions of An Initial Robot..................... 48
Figure 9(a) – A random selection process (Line
Chart)... 50
Figure 9(a) – A random selection process
(Surface Plot) 51
Figure 9.1.3(a) – Gorilla Performance (Line
Chart).......... 54
Figure 9.1.3(b) – Gorilla Performance (Surface
Plot)....... 55
Figure 9.4(a) – Elitist Performance (Line
Chart)................ 57
Figure 9.4(b) - Elitist Performance (Surface
Plot).............. 57
Figure 9.5(a) – Roulette Wheel Performance
(Line Chart) 58
Figure 9.5(b) - Roulette Wheel Performance
(Surface Plot) 59
pr(' ------------------------------------------------');pr(newline);
pr('| Title : aLife Less Ordinary |');pr(newline);
pr('| Description : A program to evolve a group |');pr(newline);
pr('| of robots to collect |');pr(newline);
pr('| and dispose of litter on a |');pr(newline);
pr('| shop floor |');pr(newline);
pr('| Date : 01/03/98 |');pr(newline);
pr('| Version : 7.0 |');pr(newline);
pr('| Author : Andy J Noon |');pr(newline);
pr(' ------------------------------------------------');pr(newline);
;;; Constant Declaration
vars
popsize = 100, ;;; Robots per generation
lifespan = 30, ;;; Moves per robot life
genebits = 92, ;;; Amount of bits in robot genotype
notrandom = 2, ;;; (Fitness & Carrying bits)
instsize = 9, ;;; Each rule depicted by this amount of bits
lowerbound = 1,;;; Test arena lower bound
upperbound = 20, ;;; Test arena upper bound
litter = 20, ;;; Amount of litter placed in test arena
bins = 10, ;;; Amount of bins placed in test arena
mutateprob = 1,;;; n/1000% value to avoid packing and unpacking
Xprob = 20, ;;; n/100% value " " " "
RoboStartPos = [5 5], ;;; Starting position of robot
genmean = 0, ;;; Stores the mean fitness of each generation
FitRobot, ;;; Stores the genotype of the fittest robot
testworld = [], ;;; Initialise test arena
population, ;;; Initialise population
;;; Rules & Codes (rule sub components)
Pre_op = [['bin_dist '] ;;; Pre operand values
['bin_dir ']
['rub_dist ']
['rub_dir ']],
Ops = [['= '] ;;; Operands (fast operands used
['fi_> '] ;;; where available)
['fi_< ']
['/= ']],
Val = [['0'] ['1'] ['2'] ['3']], ;;; Distance or
;;;Direction values
Then_Part = [['Forward() '] ;;; Robot actions
['Backward() ']
['Right() ']
['Left() ']
['Pickup() ']
['Drop() ']
['Unused() ']
['Unused() ']],
ruleshift = [2 2 2 3],;;; No. of bits needed for each rule
;;; sub component
RoboRules, ;;; Text interpretation of robot genotype
bin_dist, ;;; Stores distance to nearest bin
bin_dir, ;;; Stores direction of nearest bin
rub_dist, ;;; Stores distance of nearest rubbish
rub_dir, ;;; Stores direction of nearest rubbish
global_i, ;;; Globally visable index to progress through
;;;population
outfile, ;;; File used to store fittest robot from each
;;;generation
outfile2, ;;; File used to store fitness of all robots
topX = 20, ;;; Used for elitist s.s., select the top X robots
North = 0, ;;; Used to calculate which way the robot should South = 2, ;;; turn
East = 1,
West = 3,
Facing, ;;; Holds the direction the robot is currently facing
selection = ['roulette_wheel() ';;; Allows us to decide which 'gorilla() ' ;;; selection strategy to use
'elitist(topX) '
'random_control() '];
;;; Robot record and population array declaration
defclass robot
{
genotype, ;;; Coded rules by which robot navigates the world carrying, ;;; Record of how much rubbish a robot is carrying
fitness, ;;; Fitness of robot
RobotPos ;;; Position of robot in testworld
};
;;; Create array to hold population of robots
newarray([1 ^popsize]) -> population;
load XSL; ;;; Add-in file supplied by S.Lynch.
;;;------------------------------------------------------------------
;;; Create a population of robots with random life skills
;;;------------------------------------------------------------------
define InitPopul;
;;; Lexically defined variables
lvars
gene = [],
inst = [],
indexpop,
indexgene;
;;; code to create population of robots
;;; phenotype consists of n instsize sized instructions and a fitness value
;;; making up one genebits sized individual
fast_for indexpop from 1 to popsize do
fast_for indexgene from 1 to ((genebits fi_- notrandom) /
instsize) do
random(2 ** instsize) -1 -> inst;
inst :: gene -> gene;
endfast_for;
consrobot(gene, 0, 1, RoboStartPos) ->
population(indexpop); ;;; add robot to population
[] -> gene;
endfast_for;
enddefine;
;;;-----------------------------------------------------------------
;;; Create random test arena with randomly placed aisles & rubbish,
;;; bins in each corner
;;;-----------------------------------------------------------------
define CreateArena() -> testenv;
;;; Lexically defined variables
lvars
index_x,
index_y,
index;
;;; code to create random test environment
newarray([^lowerbound ^upperbound ^lowerbound ^upperbound], 0)
-> testenv; ;;; 2D arrray ;;; init 0
;;; place bins (randomly)
fast_for index from 1 to bins do
random(upperbound) -> index_x;
random(upperbound) -> index_y;
while (testenv(index_x, index_y)) /= 0 do
random(upperbound) -> index_x;
random(upperbound) -> index_y;
endwhile;
'b' -> testenv(index_x, index_y);
endfast_for;
;;; place litter
fast_for index from 1 to litter do
random(upperbound) -> index_x;
random(upperbound) -> index_y;
while (testenv(index_x, index_y)) /= 0 do
random(upperbound) -> index_x;
random(upperbound) -> index_y;
endwhile;
'r' -> testenv(index_x, index_y)
endfast_for;
enddefine;
;;;-----------------------------------------------------------------
;;; Reproduce two individuals using crossover and mutation
;;;-----------------------------------------------------------------
define Reproduce(robot1, robot2) -> newrobot1 -> newrobot2;
;;; Lexically defined variables
lvars
bot1 = [],
bot2 = [],
bot3 = [],
Xmask = [], ;;; Binary masks to decide when to Xover
Mutemask = [], ;;; and Mutate
Mutemask2 = [],
instindex,
genepos;
[] -> newrobot1;
[] -> newrobot2;
;;; Initialise Masks
fast_for genepos from 1 to (genebits fi_- notrandom) do
1 :: Xmask -> Xmask;
0 :: Mutemask -> Mutemask;
0 :: Mutemask2 -> Mutemask2;
endfast_for;
;;; Initialise Robots
fast_for genepos from 1 to ((genebits fi_- notrandom) /
instsize) do
0 :: bot1 -> bot1;
0 :: bot2 -> bot2;
0 :: bot3 -> bot3;
0 :: newrobot1 -> newrobot1;
0 :: newrobot2 -> newrobot2;
endfast_for;
;; Create the masks that decide when to Xover & Mutate
fast_for genepos from 1 to (genebits fi_- notrandom) do
if (random(100) <= Xprob) then
0 -> Xmask(genepos);
endif;
if (random(1000) <= mutateprob) then
1 -> Mutemask(genepos);
endif;
if (random(1000) <= mutateprob) then
1 -> Mutemask2(genepos);
endif;
endfast_for;
1 -> instindex;
;;; Convert these lists of integers to binary (i.e. an integer of
;;; size < 2^instsize)
fast_for genepos from 1 to (genebits - notrandom) do
bot1(instindex) fi_* 2 + Xmask(genepos) ->
bot1(instindex);
bot2(instindex) fi_* 2 + Mutemask(genepos) ->
bot2(instindex);
bot3(instindex) fi_* 2 + Mutemask2(genepos) ->
bot3(instindex);
if genepos mod instsize = 0 then
instindex fi_+ 1 -> instindex;
endif;
endfast_for;
bot1 -> Xmask; ;;; For the sake of clarity
bot2 -> Mutemask;
bot3 -> Mutemask2;
undef -> bot1; ;;; ----- Optimisation ------
undef -> bot2; ;;; Get rid of unneeded
undef -> bot3; ;;; variables
;;; Create new Robots (Parent1 AND Xmask OR Parent2 AND NOT
Xmask EOR Mutemask = New Robot)
fast_for instindex from 1 to ((genebits - notrandom) /
instsize) do
(robot1(instindex) fi_&& Xmask(instindex)) fi_||
(robot2(instindex) fi_&& (fi_~~ Xmask(instindex)))
fi_||/& Mutemask(instindex)
-> newrobot1(instindex);
(robot2(instindex) fi_&& Xmask(instindex)) fi_||
(robot1(instindex) fi_&& (fi_~~ Xmask(instindex)))
fi_||/& Mutemask2(instindex)
-> newrobot2(instindex);
endfast_for;
undef -> Mutemask; ;;; ------ Optimisation ------
undef -> Mutemask2;
undef -> Xmask;
enddefine;
;;;---------------------------------------------------------------------
;;; Stats Procedure (Used by elitist / gorilla strategy)
;;;---------------------------------------------------------------------
define calc_mean_&_fitness;
lvars index;
;;; This procedure calculates the mean of a generation and
;;; saves the fittest robot
;;; It also outputs each robots fitness to a stats file
consrobot(0, 0, 0, 0) -> FitRobot;
0 -> genmean;
fast_for index from 1 to popsize do
writesp_item(outfile2, population(index).fitness);
genmean fi_+ population(index).fitness -> genmean;
if population(index).fitness fi_> FitRobot.fitness then
consrobot(population(index).genotype,
;;; save the fittest robot
;;; without using a pointer
population(index).carrying,
population(index).fitness,
population(index).RobotPos)->
FitRobot;
;;; to fittest robot position
endif; ;;; as details will change.
endfast_for;
intof(genmean / popsize) -> genmean;
enddefine;
;;;-----------------------------------------------------------------
;;; Sort Procedure (Used by elitist strategy)
;;;-----------------------------------------------------------------
define Sort_by_fitness;
;;; This procedure performs an decending sort on a generation
;;; It implements a bubble sort algorithm
lvars index,
temp,
moved = true;
while moved do
;;; Keep sorting until no changes are needed
false -> moved;
fast_for index from 1 to (popsize - 1) do
if population(index).fitness <
population(index+1).fitness then
population(index) -> temp;
population(index+1) -> population(index);
;;; Switch Robots
temp -> population(index+1);
true -> moved;
endif;
endfor;
endwhile;
enddefine;
;;;------------------------------------------------------------------
;;; Selection Procedure (Elitist)
;;;------------------------------------------------------------------
define elitist(top_cats);
;;; Implements an Elitist selection strategy
lvars royals,
offspring,
parent1,
parent2,
child1,
child2,
newpop = newarray([1 ^popsize]);
intof(popsize / top_cats) -> royals;
calc_mean_&_fitness();
Sort_by_fitness();
fast_for offspring from 1 by 2 to popsize - 1 do
random(royals) -> parent1;
random(royals) -> parent2;
;;; Mate two of the most fit robots
while parent2 = parent1 do
;;; making sure both parents are different
random(royals) -> parent2;
endwhile;
Reproduce(population(parent1).genotype,
population(parent2).genotype) -> child1 -> child2;
consrobot(child1, 0, 1, RoboStartPos) ->
newpop(offspring);
consrobot(child2, 0, 1, RoboStartPos) ->
newpop(offspring fi_+ 1);
endfast_for;
newpop -> population;
undef -> newpop; ;;; ------ Optimisation ------
enddefine;
;;;---------------------------------------------------------------------
;;; Recce Procedure (returns the coordinates of surrounding area)
;;;---------------------------------------------------------------------
define recce(position, distance) -> community;
;;; Returns a list of all the robots in the surrounding the current
;;; position, the area of search is indicated by distance variable
lvars x,
y;
[] -> community;
fast_for x from position(1) to (position(1) + (distance * 2))
do
fast_for y from position(2) to (position(2) + (distance *
2)) do ;;; Look around current position and
if (x <= upperbound) and (y <= upperbound) then
;;; add all the robot positions found
;;; to community
[%x, y%] :: community -> community;
endif;
endfast_for;
endfast_for;
enddefine;
;;;------------------------------------------------------------------
;;; Selection Procedure (Gorilla)
;;;------------------------------------------------------------------
define gorilla;
;;; Implement the Gorilla Strategy
lvars new_pop_size = 1,
packsize = 1, ;;; No. of positions around location to search
index,
x = 1,
y = 1,
child1,
child2,
fit = 0,
best = 0,
;;; Indicated the dominant robot
pack = [],
;;; Harem of robots
locations = [], ;;; Position of each robot in the harem
groups = [], ;;; List of all harems found
newpop = newarray([1 ^popsize]);
calc_mean_&_fitness();
;;; The following while loop initialises all the lists describing
;;; the harems, position of robots in harem and position of each
;;; robot in the harem in the population
while y fi_<= upperbound do
recce([%x, y%], packsize) -> locations;
1 fi_+ x fi_+ (packsize fi_* 2) -> x;
if x fi_> upperbound then
1 -> x;
1 fi_+ y fi_+ (packsize fi_* 2) -> y;
endif;
[] -> pack;
fast_for index from 1 to popsize do
if member(population(index).RobotPos, locations) then
index :: pack -> pack;
endif;
endfast_for;
pack :: groups -> groups;
endwhile;
;;; Now we will find a harem to use and reproduce
while new_pop_size < popsize do ;;; Keep going until we have
;;;enough new robots
[] -> pack;
random(length(groups)) -> index;;;; Select a harem to use
;;; Make sure it has > 1 robot in the harem (inc. dominator)
while length(groups(index)) < 2 do
random(length(groups)) -> index;
endwhile;
groups(index) -> pack;
fast_for index in pack do ;;; Identify dominant robot
if population(index).fitness > fit then
index -> best;
population(index).fitness -> fit;
endif;
endfast_for;
;;; remove dominant robot from harem
REMOVE_IF(pack, procedure(n);
n = best;
endprocedure) -> pack;
fast_for index in pack do
if new_pop_size < popsize then
Reproduce(population(best).genotype,
;;; reproduce dominant robot with harem members
population(index).genotype) -> child1 ->
child2;
consrobot(child1, 0, 1, RoboStartPos) ->
newpop(new_pop_size);
consrobot(child2, 0, 1, RoboStartPos) ->
newpop(new_pop_size fi_+ 1);
new_pop_size fi_+ 2 -> new_pop_size;
endif;
endfast_for;
endwhile;
newpop -> population;
undef -> newpop; ;;;------ Optimisation ------
enddefine;
;;;------------------------------------------------------------------
;;; Control Selection Procedure (Random)
;;;------------------------------------------------------------------
define random_control;
;;; Defines a completely random selection strategy to use as a control
lvars index,
child1,
child2,
parent1,
parent2,
newpop = newarray([1 ^popsize]);
calc_mean_&_fitness();
fast_for index from 1 by 2 to popsize fi_- 1 do
random(popsize) -> parent1;
random(popsize) -> parent2;
Reproduce(population(parent1).genotype,
population(parent2).genotype) -> child1 -> child2;
consrobot(child1, 0, 1, RoboStartPos) -> newpop(index);
consrobot(child2, 0, 1, RoboStartPos) ->
newpop(index fi_+ 1);
endfast_for;
newpop -> population;
undef -> newpop; ;;; ------ Optimisation ------
undef -> child1;
undef -> child2;
enddefine;
;;;-----------------------------------------------------------------
;;; Selection Procedure (Roulette Wheel)
;;;-----------------------------------------------------------------
define roulette_wheel;
lvars
sum = 0,
index,
pos,
offspring,
parent1,
child1,
child2,
newpop = newarray([1 ^popsize]);
consrobot(0, 0, 0, 0) -> FitRobot;
0 -> genmean;
fast_for index from 1 to popsize do ;;; allocate each robot
writesp_item(outfile2, population(index).fitness);
genmean fi_+ population(index).fitness -> genmean;
sum fi_+ (population(index).fitness) -> sum; ;;; an amount of positions
;;; proportionate to its score.
;;; save the fittest robot
;;; without using a pointer
;;; to fittest robot position
;;; as details will change.
if population(index).fitness fi_> FitRobot.fitness then consrobot(population(index).genotype, population(index).carrying, population(index).fitness,
population(index).RobotPos) -> FitRobot; endif; sum -> population(index).fitness;
endfast_for;
intof(genmean / popsize) -> genmean;
fast_for offspring from 1 by 2 to popsize fi_- 1 do
random(sum) -> pos; ;;; select value for first parent
1 -> index;
while (index fi_<= popsize) and
(population(index).fitness fi_< pos) do
index fi_+ 1 -> index; ;;; step through endwhile; ;;; population until parent is found
index -> parent1; ;;; get correct robot and
;;; set this position as first parent
random(sum) -> pos; ;;; select value for second parent
1 -> index;
while (index fi_<= popsize) and
(population(index).fitness fi_< pos) do
index fi_+ 1 -> index;
if (index = parent1) and (population(index).fitness
fi_> pos) then
random(sum) -> pos;
;;; make sure both parents are different
1 -> index;
endif;
endwhile;
Reproduce(population(parent1).genotype,
population(index).genotype) -> child1 -> child2;
consrobot(child1, 0, 1, RoboStartPos) ->
newpop(offspring);
consrobot(child2, 0, 1, RoboStartPos) -> newpop(offspring
fi_+ 1);
endfast_for;
newpop -> population;
undef -> newpop; ;;; ------ Optimisation ------
undef -> child1;
undef -> child2;
enddefine;
;;;-----------------------------------------------------------------
;;; Print the test world
;;;-----------------------------------------------------------------
define PrintWorld(testworld);
;;; Prints out the state of the test world
lvars rows, cols;
pr("---------------------");
pr(newline);
fast_for rows from 1 to upperbound do
pr("|");
fast_for cols from 1 to upperbound do
pr(testworld(rows, cols));
pr("|");
endfast_for;
pr(newline);
endfast_for;
pr("---------------------");
pr(newline);
enddefine;
;;; -------------------------------------------------------------------
;;; Generate Rules
;;; -------------------------------------------------------------------
define genrule(rule) -> statement;
;;; Decode the binary genotype to a string
lvars val;
' ' -> statement;
statement <> eval(Pre_op((rule fi_&& 2:11) fi_+ 1)) ->
statement;
rule >> ruleshift(1) -> rule;
statement <> eval(Ops((rule fi_&& 2:11) fi_+ 1)) -> statement;
rule >> ruleshift(2) -> rule;
statement <> eval(Val((rule fi_&& 2:11) fi_+ 1)) -> statement;
rule >> ruleshift(3) -> rule;
statement <> ' then ' -> statement;
statement <> eval(Then_Part((rule fi_&& 111) fi_+ 1)) ->
statement;
statement <> ';' -> statement;
enddefine;
;;; -----------------------------------------------------------------
;;; Perform Action
;;; -----------------------------------------------------------------
define Forward -> score;
;;; Move forward
if ((population(global_i).RobotPos)(1) fi_< upperbound and
(population(global_i).RobotPos)(1) fi_> lowerbound and
(population(global_i).RobotPos)(2) fi_< upperbound and
(population(global_i).RobotPos)(2) fi_< lowerbound) then ;;; Check robot is allowed to move forward
if Facing = North then
;;; Move forward and adjust position accordingly
((population(global_i).RobotPos)(1) fi_- 1) ->
(population(global_i).RobotPos)(1);
elseif Facing = South then
((population(global_i).RobotPos)(1) fi_+ 1) ->
(population(global_i).RobotPos)(1);
elseif Facing = East then
((population(global_i).RobotPos)(2) fi_+ 1) ->
(population(global_i).RobotPos)(2);
elseif Facing = West then
((population(global_i).RobotPos)(2) fi_- 1) ->
(population(global_i).RobotPos)(2);
endif;
10 -> score;
endif;
enddefine;
define Backward -> score;
;;; Turn 180 degrees
(Facing fi_+ 2) fi_&& 3 -> Facing;
1 -> score;
enddefine;
define Right -> score;
;;; Turn clockwise
(Facing fi_+ 1) fi_&& 3 -> Facing;
1 -> score;
enddefine;
define Left -> score;
;;; Turn Anti-clockwise
(Facing fi_+ 3) fi_&& 3 -> Facing;
1 -> score;
enddefine;
define Pickup -> score;
;;; Pick litter up
if (testworld((population(global_i).RobotPos)(1),
(population(global_i).RobotPos)(2)) = 'r') then
;;; If stood on rubbish
0 -> testworld((population(global_i).RobotPos)(1),
;;; Take rubbish off floor
(population(global_i).RobotPos)(2));
population(global_i).carrying fi_+ 1 ->
population(global_i).carrying;
;;; Record how much litter a robot is carrying
100 -> score;
endif;
enddefine;
define Drop -> score;
;;; Either put rubbish in a bin or one the floor
if (population(global_i).carrying fi_> 0) and
(testworld((population(global_i).RobotPos)(1),
(population(global_i).RobotPos)(2)) /= 'r') then
;;; Cannot put litter on top of litter
population(global_i).carrying fi_- 1 ->
population(global_i).carrying;
if
testworld((population(global_i).RobotPos)(1),
(population(global_i).RobotPos)(2)) = 'b' then
;;; Put litter in bin
400 -> score;
else
'r' ->
testworld((population(global_i).RobotPos)(1) (population(global_i).RobotPos)(2));
;;; Put litter on floor
100 -> score;
endif;
endif;
enddefine;
define Unused -> score;
;;; Dummy Rule
0 -> score;
enddefine;
;;; ----------------------------------------------------------------
;;; Self Creating Procedure
;;; ----------------------------------------------------------------
define makeproc(indiv) -> Action;
;;; Self creating procedure
lvars i;
('procedure; if ',
<> genrule(indiv(1)),
fast_for i from 2 to ((genebits - notrandom) /
instsize) do
<> 'elseif ',
<> genrule(indiv(i)),
endfast_for
<> 'else Unused();',
<> 'endif;',
<> 'endprocedure;' ) -> RoboRules;
;;; Create a string depicting the procedure to use
eval(RoboRules) -> Action;
;;; Compile the string
enddefine;
;;; -----------------------------------------------------------------
;;; Return Direction of food relative to robots position
;;; -----------------------------------------------------------------
define Rel_Direction(i, j);
;;; Returns the direction the food is relative
;;; to the direction the robot is facing
lvars face;
if (i = 0) and (j = 0) then
4->face; ;;; Robot is sat on object
elseif abs(i) fi_<= abs(j) then
if j > 0 then
East->face;
else
West->face;
endif;
elseif i > 0 then
South->face;
else
North->face;
endif;
(face fi_- Facing) fi_&& 3; ;;; Calculates the direction the
;;; robot needs to turn
enddefine;
;;; -----------------------------------------------------------------
;;; Sense Robots Surrounding Area
;;; -----------------------------------------------------------------
define sense(position);
lvars i, j, x, y;
position(1) -> x;
position(2) -> y;
[%fast_for i from -2 to 2 do
fast_for j from -3 to 3 do
if (x fi_+ i fi_>= lowerbound) and (x fi_+ i fi_<=
upperbound) and
(y fi_+ j fi_>= lowerbound) and (y fi_+ j fi_<=
upperbound) and
testworld(x fi_+ i, y fi_+ j) /= 0 then
[%abs(i) fi_+ abs(j),
testworld(x fi_+ i, y fi_+ j),
Rel_Direction(i, j)%];
endif;
endfast_for;
endfast_for%];
enddefine;
;;; ---------------------------------------------------------------
;;; Set variables according to sense data
;;; ---------------------------------------------------------------
define setsenses(objects);
lvars object;
4 -> bin_dist;
4 -> bin_dir;
4 -> rub_dist;
4 -> rub_dir;
fast_for object in objects do
if (object(2) = 'r') and (object(1) fi_< rub_dist) then
object(1) -> rub_dist;
object(3) -> rub_dir;
endif;
if (object(2) = 'b') and (object(1) fi_< bin_dist) then
object(1) -> bin_dist;
object(3) -> bin_dir;
endif;
endfast_for;
enddefine;
;;; -----------------------------------------------------------------
;;; Move Robot According to Rules
;;; -----------------------------------------------------------------
define MoveRobot;
lvars i, j, Score, tempworld, Act;
newarray([^lowerbound ^upperbound ^lowerbound ^upperbound], 0)
-> tempworld;
fast_for global_i from 1 to popsize do
fast_for i from lowerbound to upperbound do
fast_for j from lowerbound to upperbound do
testworld(i, j) -> tempworld(i, j);
endfast_for;
endfast_for;
East -> Facing;
[%RoboStartPos(1), RoboStartPos(2)%] ->
population(global_i).RobotPos;
makeproc(population(global_i).genotype) -> Act;
fast_for i from 1 to lifespan do
setsenses(sense(population(global_i).RobotPos));
Act() -> Score;
Score fi_+ population(global_i).fitness ->
population(global_i).fitness;
endfast_for;
fast_for i from lowerbound to upperbound do
fast_for j from lowerbound to upperbound do
tempworld(i, j) -> testworld(i, j);
endfast_for;
endfast_for;
endfast_for;
undef -> tempworld;
enddefine;
;;; -----------------------------------------------------------------
;;; Testing
;;; -----------------------------------------------------------------
define RoboWorld(filename, filename2, strategy);
lvars
index, dummy, fname, fname2;
1 -> ranseed;
pr(selection(strategy));pr(newline);
gensym(filename) -> fname;
gensym(filename2) -> fname2;
write_open(fname) -> outfile;
write_open(fname2) -> outfile2;
InitPopul();
fast_for index from 1 to 5000 do
repeat 3 times
CreateArena() -> testworld;
MoveRobot();
endrepeat;
eval(selection(strategy));
writesp_item(outfile2, index);
writeln_item(outfile2, ' ');
makeproc(FitRobot.genotype) -> dummy;
writesp_item(outfile, index);
writeln_item(outfile, genmean);
writesp_item(outfile, RoboRules);
writeln_item(outfile, FitRobot.fitness);
spr(index);
spr(genmean);
spr(FitRobot.fitness);
pr(newline);
endfast_for;
write_close(outfile);
write_close(outfile2);
enddefine;
;;;-----------------------------------------------------------------
;;; INVOKE LIFE
;;; "I've created a monster!"
;;;-----------------------------------------------------------------
;;;trace MoveRobot;
false -> popgctrace;
RoboWorld("fit_", "all_", 2);
Main
Program
% Main Program to load menubar.m for the
% Invokes menubar.m to display the main menu
% A.J.Noon – Jan 1998
% The button labels (no need for a close as this is added later) .....
labels = str2mat(...
'Load File ', ....
'Surface Plot ');
% The callbacks for the buttons .....
callbacks = [....
'loadfile'
'melsurf '];
% Invoke Menubar(name, title, button_labels, callbacks) .....
melmenu('MENU', 'Robot Analysis Tool', labels, callbacks)
Menu
Bar Program
function choices(nom,header,labels,callbacks)
%CHOICES Create a list of choices with uicontrols and callbacks.
if ~isstr(nom) | ~isstr(header) | ~isstr(labels) | ~isstr(callbacks)
error('Requires string arguments.');
end
if nargin < 4
error('Not enough input arguments.')
end
global CHOICELIST
global CHOICEHANDLES
nom = deblank(nom);
if isempty(nom)
error('Requires non-blank string argument.')
end
% ensure list doesn't go into figure 1
figs = sort(get(0,'Children'));
openfigs = size(figs);
if ~isempty(figs)
cf = gcf;
if cf == 1
cf = [];
end
else
cf = [];
end
fig1 = 1;
if isempty(figs)
figs = figure('visible','off');
fig1 = 0;
end
if figs(1) ~= 1
figs = [figure('visible','off'); figs];
fig1 = 0;
end
matchn = 0;
CHOICELIST;
CHOICEHANDLES;
for i = 1:size(CHOICELIST,1)
if strcmp(nom,deblank(CHOICELIST(i,:)))
matchn = i;
break;
end
end
if ~matchn
CHOICEHANDLES = [CHOICEHANDLES; 0];
if isempty(CHOICELIST)
CHOICELIST = nom;
else
CHOICELIST = str2mat(CHOICELIST, nom);
end
matchn = size(CHOICEHANDLES,1);
else
matchh = 0;
for i = 1:size(figs,1)
if figs(i) == CHOICEHANDLES(matchn)
matchh = i;
break;
end
end
if matchh
figure(CHOICEHANDLES(matchn));
return
end
end
xedge = 30;
ybord = 30;
width = 150;
yedge = 35;
height = 35;
rect = [50, 50, 300, 400];
CHOICEHANDLES(matchn) = figure('Position',rect,...
'number','off', ...
'name',nom,...
'resize','off',...
'colormap',[],...
'NextPlot','new',...
'Menubar','none');
% Place header
header=uicontrol( 'style','text',...
'units','normal',...
'position',[.05,.91,.9,.09 ],...
'string',header,...
'Horizontal','center');
set(header,'backg',get(gcf,'color'),'foreg',[1 1 1]-get(gcf,'color'))
h2=uicontrol( 'style','text',...
'position',[50, 350, 200, 25 ],...
'string','Main Menu',...
'Horizontal','center');
set(h2,'backg',get(gcf,'color'),'foreg',[1 1 1]-get(gcf,'color'))
h3=uicontrol( 'style','text',...
'position',[50, 15, 200, 25 ],...
'string','Author - A.J.Noon',...
'Horizontal','center');
set(h3,'backg',get(gcf,'color'),'foreg',[1 1 1]-get(gcf,'color'))
but(1) = uicontrol( 'Style', 'Pushbutton', ....
'Position', [75, 300, width, height], ....
'String', deblank(labels(1,1:16)), ....
'Callback', callbacks(1,1:8));
but(2) = uicontrol( 'Style', 'Pushbutton', ....
'Position', [75, 250, width, height], ....
'String', deblank(labels(2,1:16)), ....
'Callback', callbacks(2,1:8));
but(3) = uicontrol( 'Style', 'Pushbutton', ....
'Position', [75, 200, width, height], ....
'String', deblank(labels(3,1:16)), ....
'Callback', callbacks(3,1:8));
but(4) = uicontrol( 'Style', 'Pushbutton', ....
'Position', [75, 150, width, height], ....
'String', deblank(labels(4,1:16)), ....
'Callback', callbacks(4,1:8));
but(5) = uicontrol( 'Style', 'Pushbutton', ....
'Position', [75, 100, width, height], ....
'String', deblank(labels(5,1:16)), ....
'Callback', callbacks(5,1:8));
% Create Close button
but(6) = uicontrol( 'Style', 'Pushbutton', ....
'Position', [75, 50, width, height], ....
'String', 'Exit', ....
'Callback', 'close_it');
if ~isempty(cf)
figure(cf)
end
Load
File Program
% Load datafile and allow the filename to be used within calculations
close(figure(1));
data = input('Enter Filename (in quotes i.e. ''file'') : ');
load(data);
index = 1;
varname = [];
for i = 1 : size(data,2)
if data(i) == '\'
varname = [];
index = 1;
else
varname(index) = data(i);
index = index + 1;
end
end
main
Surf
Plot Program
% Display datafile as a surface scan allowing for
% change of colour map, shading, azimuth, elevation
% and allowing the user to spinmap !!!!!!!!
close(figure(1));
win(1)=figure;
azimuth = -37;
eliv = 30;
colmaps = [.....
'gray '
'hot '
'cool '
'bone '
'copper'
'pink '
'flag '
'prism '
'jet '];
% I think these are all the schemes, some are not so good
set (win(1),'NumberTitle', 'off', ....
'Menubar', 'figure', ....
'Position', [50,50,900,600], ....
'Name', 'Surface Scan');
btn(1) = uicontrol( 'Style', 'Pushbutton', ....
'Position', [780, 500, 120, 35], ....
'String', 'Interpolated', ....
'Callback', 'shading interp');
btn(2) = uicontrol( 'Style', 'Pushbutton', ....
'Position', [780, 460, 120, 35], ....
'String', 'Flat', ....
'Callback', 'shading flat');
btn(3) = uicontrol( 'Style', 'Pushbutton', ....
'Position', [780, 420, 120, 35], ....
'String', 'Faceted', ....
'Callback', 'shading faceted');
btn(4) = uicontrol( 'Style','Pushbutton', ....
'Position', [780, 380, 120, 35], ....
'String', 'Spin Map', ....
'Callback', 'spinmap(inf);');
popmnu = uicontrol(win(1), 'Style', 'Popup', ....
'Backgroundcolor', [0.75, 0.75, 0.75], ....
'String', 'Gray|Hot|Cool|Bone|Copper|Pink|Flag|Prism|Jet', ....
'Position', [780, 340, 120, 200], ....
'Callback', 'colormap(colmaps(get(popmnu,''value''),1:6))');
btn(5) = uicontrol( 'Style','Pushbutton', ....
'Position', [200, 550, 120, 35], ....
'String', 'Surface', ....
'Callback', ['surf(eval(varname));',....
'title(''Robot Fitness'')']);
btn(6) = uicontrol( 'Style','Pushbutton', ....
'Position', [600, 550, 120, 35], ....
'String', 'Mesh', ....
'Callback', ['mesh(eval(varname));',....
'title(''Robot Fitness'')']);
slider1 = uicontrol(win(1), 'Style','slider',...
'Position', [780, 270, 120, 20],...
'Min',-180,'Max',180,'Value',azimuth,...
'Callback', ['azimuth = get(slider1, ''value'');',...
'set(s1val,''String'',num2str(azimuth));',...
'view(azimuth,eliv)']);
slider2 = uicontrol(win(1), 'Style','slider',...
'Position', [780, 210, 120, 20],...
'Min',-180,'Max',180,'Value',eliv,...
'Callback', ['eliv = get(slider2, ''value'');'...
'set(s2val,''String'',num2str(eliv));',...
'view(azimuth,eliv)']);
s1val = uicontrol(win(1), 'Style','text',...
'Position', [840, 300, 50, 20],...
'String',num2str(get(slider1,'value')));
s2val = uicontrol(win(1), 'Style','text',...
'Position', [840, 240, 50, 20],...
'String',num2str(get(slider2,'value')));
s1label = uicontrol(win(1), 'Style','text',...
'Position', [780, 300, 60, 20],...
'String', 'Azimuth');
s2label = uicontrol(win(1), 'Style','text',...
'Position', [780, 240, 60, 20],...
'String', 'Elivate');
btn(7) = uicontrol( 'Style','Pushbutton', ....
'Position', [780, 160, 120, 35], ....
'String', 'Default View', ....
'Callback', ['azimuth = -37;',...
'eliv = 30;',...
'view(azimuth,eliv);',...
'set(s1val,''String'',num2str(azimuth));',...
'set(s2val,''String'',num2str(eliv));',...
'set(slider2,''value'',eliv);',...
'set(slider1,''value'',azimuth)']);
but(8) = uicontrol( 'Style', 'Pushbutton', ....
'Position', [780, 0, 120, 35], ....
'String', 'Close', ....
'Callback', 'close');
surf(eval(varname));
title('Robot Fitness');
colormap(hot);
shading interp;
Initialise Population
Test Subject |
Type Of Arguments |
Resulting Type |
Expected Result |
Actual Result |
|
For indexpop from 1 to popsize do |
All Integers |
N/A |
N/A |
N/A |
|
For indexgene from 1 to ((genebits – notrandom) / instsize) do |
All Integers (genebits – not random) must be divisible by instsize |
N/A |
N/A |
N/A |
|
Random(2 ** instsize) –1 -> inst |
Integer |
Integer |
Random No between 0 and 2^instsize |
As Expected |
|
Inst :: gene -> gene |
Integer :: list -> list |
List |
List with integer added to head |
As Expected |
|
consrobot(gene, 0, 1, RoboStartPos) -> population(indexpop) |
Record(list, integer, integer, list) -> array position |
Record |
Record inserted into array position |
As Expected |
|
[] -> gene |
Lists |
List(empty) |
Empty List |
As Expected |
Set Senses
Test Subject |
Type Of Arguments |
Resulting Type |
Expected Result |
Actual Result |
|
Procedure Create_Test_World -> Testenv |
N/A |
2D Array |
Investigation |
þ |
|
For index from 1 to Amount_Bins do |
All Integers |
N/A |
N/A |
N/A |
|
Random(Upper_Bound) -> index_x |
Integer |
Integer |
Random No between 1 and Upper_Bound |
As Expected |
|
Random(Upper_Bound) -> index_y |
Integer |
Integer |
Random No between 1 and Upper_Bound |
As Expected |
|
'b' -> testenv(index_x, index_y) |
Char -> Array Position |
N/A |
‘b’ inserted into array |
As Expected |
|
While (testenv (index_x, index_y) ) /= 0 do |
Array (Integer, Integer) /= Integer |
Boolean |
True or False |
As Expected |
|
For index from 1 to Amount_Litter do |
All Integers |
N/A |
N/A |
N/A |
|
Random(Upper_Bound) -> index_x |
Integer |
Integer |
Random No between 1 and Upper_Bound |
As Expected |
Create Test World
Test Subject |
Type Of Arguments |
Resulting Type |
Expected Result |
Actual Result |
|
Procedure Create_Test_World -> Testenv |
N/A |
2D Array |
Investigation |
þ |
|
For index from 1 to Amount_Bins do |
All Integers |
N/A |
N/A |
N/A |
|
Random(Upper_Bound) -> index_x |
Integer |
Integer |
Random No between 1 and Upper_Bound |
As Expected |
|
Random(Upper_Bound) -> index_y |
Integer |
Integer |
Random No between 1 and Upper_Bound |
As Expected |
|
'b' -> testenv(index_x, index_y) |
Char -> Array Position |
N/A |
‘b’ inserted into array |
As Expected |
|
While (testenv (index_x, index_y) ) /= 0 do |
Array (Integer, Integer) /= Integer |
Boolean |
True or False |
As Expected |
|
For index from 1 to Amount_Litter do |
All Integers |
N/A |
N/A |
N/A |
|
Random(Upper_Bound) -> index_x |
Integer |
Integer |
Random No between 1 and Upper_Bound |
As Expected |
|
Random(Upper_Bound) -> index_y |
Integer |
Integer |
Random No between 1 and Upper_Bound |
As Expected |
|
'r' -> testenv(index_x, index_y) |
Char -> Array Position |
N/A |
‘r’ inserted into array |
As Expected |
aLife Less Ordinary
To prove that
through the use of Evolutionary Programming it is possible to evolve a
population of robots towards a given goal.
Initially each robot will be given a random set of instructions with
which to navigate its environment which will include obstacles in the form of
aisles, the robots will be assigned a fitness score dependant on their ability
to pick up and deposit randomly placed rubbish in pre-placed bins. After each individual in the current
population has been tested some individuals will be selected to reproduce, this
selection will be based on a fitness proportionate strategy and reproduction
will use the naturally occurring genetic operations of crossover and
mutation. As in natural evolution there
is no single stop condition therefore the program will output data to a file as
it progresses, this will allow the progress of the evolution to be evaluated
and a decision to be made about the populations success. It is estimated that each run of the program
could last for up to eight hours.
File 1 – All Robots
9 9 9 1 6 1 1
4 101 5 49 101 3 1 7 20 1 4 13 46 5 2 19 101 1 10 33 4 47 101 1 104 101 9 101 1
101 101 1 2 6 101 3 3 105 61 20 6 20 2 1 50 1 1 1 8 1 111 9 65 8 1 65 67 101 1
91 79 10 79 6 2 14 1 13 1 2 4 1 2 1 6 65 4 48 9 10 3 1 4 4 1 17 101 101 214 101
9 1 101 1
.
.
.
4813 4813 2 6
1 4339 4813 4813 6 4813 4813 4813 4813 4813 4813 2 4813 2 4813 4813 2 4813 4813
4813 4813 6 6 2 4813 6 4813 4813 4813 4813 4813 6 6 4813 4813 2 4813 4813 6
4813 2 4813 6 4813 4813 6 6 4813 2 4813 2 4813 4813 4813 6 4813 4813 1 2 4813
4813 4813 2 4813 4813 4813 2 4813 4813 2 6 4813 2 4813 6 4813 4813 2 4813 4813
4813 2 2 4813 4813 4813 2 4813 4813 4813 6 4813 4813 4813 4813 2 316
File 2 – Fit Robots
1 31
procedure; if rub_dist fi_> 1 then
Backward() ;elseif rub_dir fi_< 2
then Drop() ;elseif rub_dir = 2 then
Right() ;elseif bin_dist fi_< 2 then
Unused() ;elseif rub_dist fi_< 0
then Backward() ;elseif bin_dist
fi_> 3 then Unused() ;elseif
rub_dist fi_< 1 then Pickup() ;elseif bin_dir /= 2 then Unused() ;elseif bin_dir = 1 then Unused() ;elseif bin_dir fi_< 2 then Right() ;else unused(); endif;
endprocedure; 214
.
.
.
316 3076
procedure;
if rub_dir = 2 then Right()
;elseif rub_dir = 3 then Drop()
;elseif bin_dir = 2 then Forward()
;elseif rub_dist fi_> 0 then
Forward() ;elseif rub_dist /= 0 then
Right() ;elseif rub_dist = 3 then
Unused() ;elseif rub_dist fi_< 3
then Pickup() ;elseif bin_dist /= 3 then
Forward() ;elseif bin_dist = 1 then
Backward() ;elseif rub_dist = 2 then
Drop() ;else Unused();endif;endprocedure; 4813