Before carrying out any kind of maintenance, programmers should become familiar with some concepts used within the BOTS Project. Most of these are explained in this section.
In the Autumn semester, we decided to break the project into three components: the Environment, the Brain (Genetic Programming) and GUI (Graphic User Interface). At that stage, the template editor was seen as an entirely separate program. Eventually the name was changed from SED (erroneously standing for Simulated Environment Designer) to TED, and viewed as the fourth component of the project.
These four major components, and the way they relate to each other, can be seen in the context diagram below. Although the user help system is sometimes referred to as a separate component, it is not featured in the context diagram, since it spans both TED and the GUI component.
More information of the context diagram and other data flow diagrams can be found in section 4.1, starting on page 14 of this document.
The Brain provides a genetic programming and program evaluation service to the Graphic User Interface and Environment components, respectively. It optimises the rule sets (S-expressions, sometimes called control algorithms) of individual simulated robots in the population, and executes these rule sets.
The Brain handles sensor input and sends actions as output to the Environment. The Brain is also responsible for the evaluation of the robot population at the end of each generation.
The Brain uses the GP Variables within its S-expressions to evaluate the performance of each robot. If the Brain feels that the evolution is occurring too slowly it can use various other algorithms to change the Brains of each robot and see how they perform.
The fitness of each robot reflects how well that robot is performing. The robots with the highest fitness levels are those most likely to be selected as the basis for the next generation or robots.
Coupling with other components is achieved via sockets, communicating using the CBEP protocol. For more information about CBEP, please refer to section 4.7.2, starting on page 90 of this report.
The Environment handles the interaction between each individual robot and its surrounding environment. It provides each bot with input for their sensors, and a method of execution for their desired actions. It consists of code that implements Collision Detection, Sensor Input and Action Output. Also contained within the Environment Component are methods for creating, destroying and modifying any object defined within the BOTSsim Object Hierarchy.
The Environment also keeps track of the fitness of each robot and it rewards and deducts fitness according to what actions each robot performs. Environment Variables define what fitness rewards and deductions should be made.
The Environment also controls the animation aspect of the simulation. Environment Variables are also used within this aspect of the Environment. The animation is what allows the user to see how the robots are evolving--getting better at their allocated tasks.
The code for the environment is highly object-orientated. The BOTSsim Object Hierarchy is merely a tree that defines the properties for each object using inheritance and property definitions. Inheritance allows one object to inherit properties from it's parent object, this is a very useful thing when programming in an Object Oriented language.
The Environment is connected to TED and the GUI via Delphi's internal coupling mechanisms. The Environment is connected to the Brain via sockets, communicating using the CBEP protocol.
The GUI of the simulation encompasses every Dialogue and Window that you can access within the BOTSsim Application. The purpose of the GUI is to provide the user with an easy way to control and view the simulation. The way we have structured the GUI allows the user to have an extremely high level of control over how the simulation runs. The application's structure has been set out in a logical way so that navigation within the application is highly intuitive.
The GUI is connected to TED and the Environment via Delphi's internal coupling mechanisms. The GUI is connected to the Brain via sockets, communicating using the CBEP protocol.
TED allows users to design their Environment Template, which is the environment upon which each Environment during the simulation is based upon. For example, a template representing a factory floor.
TED allows you to create, destroy, and modify walls, Bots, block distribution areas and block receptacles. TED provides a high level of control for the user so that they can design any Environment Template you can imagine.
The design is only limited by the number of walls, Bots, block distribution areas and block receptacles that are available for creation within the Environment Template.
One of the major problems that we have found is finding a good fitness function. This section lists most of the ones we explored.
Where R is the number of blocks picked up and placed in their bins. Unfortunately, this was based on a false understanding of Koza's code. Since he comes for a program optimisation standpoint, his system selects bots with a lower score, rather then a higher score.
Where D is the distance from the bot to the next target (either a Block or a Bot). This of course failed for the same reason as the first.
This was very good at encouraging bots to run towards a bin. However, as a side effect of picking up a block, the robot was punished. This was because when a bot picked up, a block the reward for picking up was less then the punishment for being further away for the next target.
This function was one of the most complex mathematical ones we tried. While being good at breeding bots that picked up blocks, it was very poor at evolving bots that moved towards blocks. Because of this complexity, we where unable to analyse its behaviour.
We thought that by squaring the Raw fitness we would be able to overcome the side effect in (3). However, the fitnesses generated were not large enough for this to work.
Where W is the distance between diagonally opposite points of the world. This one works quite well, except it has trouble evolving the drop behaviour.
The current fitness function is:
If bots have not picked up:
Fitness := ClosestBlock + (2000 * Diagonal) If bots have picked up but not droped:
If (BlockDist>BinDist) then
Fitness := BinDist + (1000 * Diagonal)
Fitness := (1500 * Diagonal) - BlockDist When bots have at least 1 hit:
Fitness:=(500*Diagonal) - Raw Fitness
In terms of behaviour, this is the best function we have found to date. However, there appear to be some problems with it, and we have not been able to determine exactly what they are.
Mirroring is a technique we devised to speed up genetic programming. We had to look for such a shortcut because we realised we would be short of time several weeks ago.
The idea of mirroring is based on decomposing the bots' objectives into four stages:
The difference between stages 1 and 2 is almost identical to the difference between stages 3 and 4. Since we have developed a fitness function which encourages bots to find blocks and pick them up (stages 1 and 2), performing stages 3 and 4 probably only requires mirroring the rule sets that the first two stages develops.
Mirroring is a technique inspired by Mark. In this technique, we take the original rule set, and copy it. We then modify the copy, swapping functions and terminals referring to bins with functions and terminals referencing blocks. We also swap the "Pick Up Block" action for the "Drop Block" action. Next we put the original and mirrored individuals under a new if-HasBlock function. The new, mirrored individual is placed within the body of the then clause, and the old individual in the body of the else clause. The resulting individual should be capable of finding a bin and dropping a block into it after it has found a block and picked it up.
While this is not a very pure Genetic Programming approach, given our lack of time and resources, it was felt that it was better to use specialised operators like this and possibly improve our result than to get no further at all.
Unfortunately, in practice, mirroring does not work. This is because the first two steps and the last two steps are not similar enough. For one thing, the bots' initial orientation with respect to distribution areas is rarely the same as their initial orientation with respect to bins. Mirroring would work in symmetrical environments, but such instances are unusual. In short, mirroring is too simple a solution for our complex genetic programming problem.