Gyoomard Project

Yet Another GA Book

2009-07-26T07:43:00.001-07:00

I recently came across this book: "Practical Genetic Algorithms". I already studied 3 chapters, and found it really intresting. As the name implies it has a practical approach in which the authors try to explain the implementation details of GA.

In most of the GA books I've ever read the discussion of GA operators such as crossover or mutation is vague. Statements like "Mutation is to change non-junk part of the chromosome with some probability" are everywhere, and there is usually no distinction between real-valued and binary GAs. Conversely this books explains all these different variations with reasonable detail, and has good references to relevant papers. For example the book clearly describes different types of selection methods, different variations of crossover and mutation in both real-valued, and binary GAs, and for all of these it has references to papers where a more in-depth discussion could be found.

In short this book is a pragmatic tutorial on GA which has a good balance between theory an practice.

I guess anybody who has every worked with a GA can borrow a lot of ideas from this book in order to fine tune their implementation.

Step by Step

2009-04-27T15:47:00.001-07:00

Re-evaluation plan for Gyoomard is to assess the results of different stages step by step. This would mean to start off with no control and run the biped simulation as a Passive Dynamic Walker, then add a very simple control with a simple neural network. Finally achieving the full problem configuration.

Another main area for investigation the exact mechanism for the GA. It seems currently that the solver falls into local maximum points.

One other feature which can be added in the step by step progression is a support to help Gyoomard in the walking process. The support will be used for learning and then taken out at some future stage.

Blocked

2009-02-04T08:46:00.001-08:00

Gyoomard's evolution has come to a block so far. Hasn't been able to cover a longer distance. The whole Genetic Algorithm operations need to be revised, mutation of one per gene of a genome on an initial population of 50 doesn't seem to cover the search space in a suitable format.

8m

2009-01-24T04:57:00.000-08:00

8 meters has been the record for Gyoomard walk so far before falling down. This would be something like taking two steps.
There are many parameters needing to be tweaked and the overall code needs to be enhanced regarding efficiency.

Gyoomard is trying

2009-01-20T12:26:00.000-08:00

Gyoomard is undergoing training at the moment. Or better say Gyoomard's are being trained, evaluated, reproduced and evaluated again, until an elite genome is found that would be able to walk on a straight ground.

Generation 165 of the simulation is running currently and the best displacement so far has been 3.4 meters.

This is the first try in making Gyoomard walk and no expectations yet, lots of things need tweaks.

Lets see how things work out but the experience is very exciting already.

Gyoomard's brain is currently a CTRNN with 10 nodes, fully connected. Its body is comprised of a lower leg, upper leg and hip. 1 DOF knees and 2DOF hip joints.

Evolving Integrated Controllers using CTRNN

2009-01-20T02:11:00.001-08:00

The first attempt for evolving an integrated dynamical neural network as control system failed in 1994 in an experiment by Yamauchi, and Beer. As a result they recommended a modularized approach in which separate controllers were evolved for tasks such as reactive and sequencing behaviors and the learning task. They also used hard wired reinforcemennt signals as feedback into the learning module, which ruined the inital idea of an integrated (Not modularized) control system. Later on Harvey et al showed the possibility of evolving an integrated conroller system by evloving a CTRNN for controlling the behavior of a simulated khepera mini-robot. The details of their experiments could befound in the following paper:

Evolving integrate controllers for autonomous learning robots using dynamic neural networks

Overall points

2009-01-14T19:57:00.000-08:00

The following paper outlines the overall ideas regarding evolutionary robotics.

Evolutionary Robotics in Behavior Engineering and Artificial Life, Dario Floreano

There are two main areas covered in the study, the first being the use of evolutionary techniques to model robots which operate in specified constraints and have well known engineering goals. The second part studies the application of evolutionary methods in artificial life studies in general. Co-evolution is researched which seems to be a huge topic which has not been discovered much yet.

Morphological Computation

2009-01-03T19:49:00.000-08:00

The idea of Morphological Computation is how the morphology which is about the form of a robot is important in the overall behaviors and abilities and how the form can help the overall computation efficiency and hence called morphological computation.

The following paper provides a good discussion on the topic and examines a few cases where the sensor positions or type of material used for the robots helps in the development of robust systems which do not necessarily need to model everything internally and the form helps the overall information processing requirements.

Morphological computation: connecting body, brain and environment. Rolf Pfiefer and Fumiya Iida

GA library

2009-01-03T19:13:00.000-08:00

An open source Genetic Algorithms library in c++ from MIT:
http://lancet.mit.edu/ga/

The architecture seems to be flexible enough to enable extending the features or modifying the behaviors.

Controllers

2009-01-03T19:02:00.000-08:00

One of the main questions of this first milestone is how to model the controllers for the biped simulation.

The neural network will output the desired angle for every joint and we hope to apply a relevant torque to each joint in order to reach that desired angle. A PD controller can be assumed to control each joint, in this case a constant value for the proportional coefficient and one for the derivative coefficient needs to be assumed. Large values can make the physics simulation unstable and these values seem to need some tweaking. Other options are to use the built in features for PhysX motor enabled joints which can make the joint move at a specific speed or to a specific angle. The torque can be limited on these motor joints which should be a very good feature.

Some more testing on the model needs to be done in order to come up with this efficient control method for each joint.

This project from Ecole Polytechnique Federale De Lausanne mentions some problems associated with joint controllers, the solution selected in the project is to use a constant speed for the joint equal to the proportional coefficient. Teta_dot = k(delta_Teta). The justification being that larger difference in desired angle from existing angle needs larger values for velocity to move the joint.

Kendo Learning

2008-12-29T11:52:00.000-08:00

This website contains a demo of 2D Kendo players which operate by neural networks which are trained by GAs.

http://chi.valro.us/ai/genetic-kendo.html

Interesting project but the page doesn't contain details regarding the design although it seems pretty simple.

Coevolution and Distribution

2008-12-27T12:53:00.000-08:00

The idea of coevolution in genetic algorithms is very interesting. It might not be directly usable in the first milestone for Gyoomard which is the development of a pattern generator for walking but the idea should be valuable in the next milestones.

Distributed GAs use time and space to evlove and can be highly beneficial for parallel programming.

The following paper has a good discussion on the above topic:

Distributed Coevlotionary Genetic Algorithms for Multi-Criteria and Multi-Constrain Optimisatioin, Phil Husbands

CTRNN basics

2008-12-25T05:54:00.000-08:00

This paper:

On the Dynamics of Small Continuous-Time Recurrent Neural Networks, Randall Beer

provides a very good analysis of the inner workings for CTRNNs. There is an example problem solved using this kind of neural network.

For more scientific approaches to CTRNNs, you can follow this research:

Approximation of Dynamical Systems by Continuous Time Recurrent Neural Networks, Ken-ichi Funahashi and Yuichi Nakamura

This study involves a lot of mathematical background for these networks and describes the way in which they can model dynamical systems. Containing theorems and proofs.

ALife

2008-12-25T00:12:00.001-08:00

Artificial Life is the study of man-made systems that exhibit behaviors characteristic of natural living systems. It complements the traditional biological sciences concerned with the analysis of living organisms by attempting to synthesize life-like behaviors within computers and other artificial media. By ending the empirical foundation upon which biology is based beyond the carbonchain life that has evolved on Earth, Artificial Life can contribute to theoretical biology by locating life-as-we-know-it within the larger picture of life-as-it-could-be.[1]

Artificial Life is also the name of a course which is taught by Inman Harvey at Sussex University. This course is seminar based and the readings could be found here. Lecture notes are also accessible from the course home. The lectures cover things like GA, Co-evolution, SAGA (Species Adaptation Genetic Algorithms).

[1] - From: Artificial Life - Lecture1.

Background Reading

2008-12-24T06:21:00.000-08:00

There are lots of good documents to read in order to pursue the Gyoomard dream. We'll try to mention a few each time in these posts.

T. Reil and P. Husbands. Evolution of Central pattern Generators for Bipedal Walking in Real-time Physics Environments

This paper uses CTRNNs which are trained by GAs to evolve the walking motion for a biped. Our first milestone in Gyoomard project is to follow the study performed in this paper and prepare our simulation environment for further research. The CTRNN acts as a central pattern generator for the biped. MathEngine physics engine is the framework for the simulation. No sensor neurons are used in this study.

G. McHale and P. Husbands, Quadrupedal locomotion: GasNets, CTRNNs and Hybrid CTRNN/PNNs compared

Several techniques for evolving sensory motor systems of a four legged creature robot are tested in the above paper. GasNets have proven to be efficient in certain situations. ODE is used. This study uses sensor neurons to sense when the limbs touch the ground. A similar study has been done by the authors to compare many more different types of networks.

Quadrupedal ANN Architecture

2008-12-22T08:16:00.001-08:00

I was reading "Quadrupedal Locomotion: GasNets, CTRNNs and Hybrid CTRNN/PNNs Compared" by Gary McHale and Phil Husbands. In the Experimental Setup section the description of ANN architecture is a bit vague. I tried to visualize the Table2 as follows:

It seems a bit funny, but it is enough for our discussion.

The table is as below:

The problem comes when you consider this table wich shows the connection of sensory nodes with other nodes:

From the image above the connection between the sensory nodes and the mootor nodes are clear, but what are the nodes 1, 5, 9, 13. I'm not sure how the missing nodes are used.

Simulation Testbed

2008-12-21T00:05:00.000-08:00

A minimal simulation environment test bed has been developed so far. There are no automated controls yet and the pictures below display a sample biped trying to move its legs by manual control, (user control) and as is visible from the pictures, the user control is not very successful.
The goal for the first phase is to make the biped walk.

PhysX physic engine is being used for simulating the rigid body and joints dynamics. OpenGL is currently used for rendering the simple elements used for the biped.

Gyoomard

2008-12-20T22:24:00.000-08:00

The first King of the World and the first person alive in Persian Mythology. The "living mortal" is the meaning of the word.

Gyoomard is a research on the use of evolutionary computation for development of sensory motor neural networks for simulated characters.