Genetic movements

Some links may not be active (if the application is not in the folder env / applications / mouv_gen the distributed version).

See: Algorithmes génétiques

Why genetic algorithms (GA) ?
Principle
Content
The menus
The program
Use

Why genetic algorithms (GA) ?

The traditional analytical methods can solve only perfectlywell posed problems and which we know a resolution algorithm. But most of the real problems are not clearly established, and their solution, when it exists, is not necessarily computable in a finite time. A problem may have several solutions, or even not having one at all, what to do in this case if seeking the best possible compromise: it is not so much the search for the optimum that counts, but rather to improve what is possible.
The GA are an optimization method characterized by:
1) They work on arbitrary encoding parameters (and not the parameters themselves), which avoids introducing a meaning that would bias the search for solutions.
2) They work on populations, ie in parallel, which avoids falling into a local optimum
3) They use the values of the function (and not its derivatives or other special properties).
4) They use probabilistic transition rules (not deterministic).

Principle

This application shows:

1) How build genetic populations movements

and how cross them optimizing some function FITNESS.

2)How build trajectories

2 modes:

1) rotations defined by:
       angle an and axis xr,yr,zr
       giving rise to two types of trajectories: rotation and axis.

2) Quaternions of the form w,x,y,z, with:
       an=2*acos(w)
       x,y,z such as module(x,y,z)=sin(a/2)
       the quaternion w,x,y,z is a 4D unit vector 4D (a²+x²+y²+z²=1).
A volume i movement is defined by q quaternions trajectory obtenaid by interpolating spherically a list:
       q_i,1 q_i,2 ... q_i,nq of nq quaternions.
For sevaral volumes Shoulder, Humerus, Radius, Wrist, Fingers there are as many trajectories.

It will be seen that the quaternions give better results than the rotations:
better convergence
movements more "natural" click EXPL then AUTO(), change the two quaternions for diverse movements key, click again on AUTO(),left-click in the white frame to change the view.

3)How to write a function FITNESS optimization

This will only be active if comparisons causes particles genetics (encoding the initial random movements) with movements played (for READ) or defined interactively (by READin which case a message will say. This is done using the command dist 2 strings.

4) How to use these features

an arm which can be programmed for:
interactively emulate the capture of a real arm.
interact "intelligently" with a real actor he learns postures (in the application mouv_neur mouv_neur).

Note:

For programming in C (out anyflo) this application it will be necessary to:
1) programming genetic algorithms.
2) programming quaternions and their spherical interpolation.
3) programming interface for real-time interaction..
4) possibly programming neural networks for better recognition.

Definition movements

The rotational movements are defined in a file .rota of the form:

r_1,1 r_1,2 ... r_1,nq

r_2,1 r_2,2 ... r_2,nq

...

r_nv,1 r_nv,2 ... r_nv,nq

Where r_i,j=a,x,y,z is a rotation defined by its angle a and its axis x,y,z.
The quaternions mouvements are defined in file .quat of the form:

q_1,1 q_1,2 ... q_1,nq

q_2,1 q_2,2 ... q_2,nq

...

q_nv,1 q_nv,2 ... q_nv,nq

Where q_i,j=w,x,y,z is a quaternion.

These movements files may be builded from an real actor captures.

real-time interaction are interfaced require the capture and interpretation.

Content

Folder env

Containing:
*.rota: movements matrices files.

anyflo_video.js

Java scrypte launching video anyflo.

initb.h

Configuration file in folder distribution_eng/env and root distribution_eng.

mouv_gen.func

Function in anyflo language.

mouv_gen.htm

This file.

mouv_gen.js

Java scrypte launching the application.

The menus

Main menu
EXPL: submenu explanations.
CREATE: submenu creations.
GEN: genetic generation.
READ: submenu reading files mouvements.
INTER: interaction. biomecanic constrainst.
INI: initialization
ILLUM: yes/no illum.
SKIN: yes/no skin display.
EXT: yes/no ext.
FONC: displays names functions, click: displays it.
STEPbySTEP: step by step, click on CONTINUE (green) next image, click on X (red) exits this mode.
Warning: does not click on RETURN, launches again the program...

A flashing message indicates whenever the procedure, the menu box that need to click pulse for about 4 seconds.
EXIT: pour quit the program.

EXPL: submenu explanations

HEL: help.

ROTA: click on a bone name then change angle rota and the axis, the arm moves accordingly.
Click on ALL() selects all bones.
Click in the green frame changes the eye.

COMPLEX: isomorphism of planar rotations and complex numbers:
Change the components a and b of the unit complex number z=a+i*b represents the corresponding angle of cosinus a and of sinus b.

QUAT: isomorphism of spatial rotations and quaternions:
Change the rotation angle rota and the axis axe of ethe unit quaternion q=w+i*a+j*b+k*c, the red point P displayed on sphere radius 1 represents the corresponding rotation angle 2*acos(w) and axis OP.
Click in the green frame changes the eye.

MOUV: spherical interpolation of two quaternions:
Two quaternions q1=w1,x1,y1,z1 and q2=w2,x2,y2,z2 are represended by 2 points P1(red) et P2 (green) of the sphere radius 1.
Change the interpolation coefficient u, the point P representing the interpolated quaternion between q1 and q2 is displayed on the sphere between P1 and P2.
Change the quaternions on the scales.
The spherical interpolation formula is:
c1=(sin((1-u)*a))/sin(a) c2=(sin(u*a))/sin(a) q=c1*q1+c2*q2
AUTO(): automatic interpolation.
Click in the green frame changes the eye.

MOUVS:
One POSITION is represented by a quaternion.
One MOUVEMENT Élémentaire est représenté par une liste de quaternions interpolés. et de sinus b.
One MULTIPLE MOVEMENT (for exemple the arm bones) is represented by a list of such lists : a quaternions matrix.
Such movement has been stored on the disk by a file .rota

COD: encoding:
Change the float x of the interval [-1,1]
Integer e=ent(255*(x+1)/2) varie in the interval [0,255]
Its binary expression (0 and 1) is encoded on one byte (8 bits).
It is transformed into genomes of 8 characters 0 and 1 processed by a genetic algorythm.

ALGOGEN: genetic algorythm:
Choose n encoding characters number.
Click on ALEA() randomly generates 2 words of n characters.
Choose the break index, the 2 words are split, the first part of ethe first and the second part of the second are assembled to form the third.

CREATE: creations submenu

HEL: help.
ROTA: ROTATIONS (an,xr,yr,zr)
The trajectories are rotations defined by an angle an an an axis x,y,z.
QUAT: QUATERNIONS (w,x,y,z)
The trajectories are quaternions w,x,y,z.
A message says (ROTA default or QUAT), the numbers of ethe active memories and possibly INTER.

Choose:
1) The encoding bits number nb (2^nb), small convergenceis better (since genomes are small) but small precision).
2)nb particles number of the genetic (randomly generated movements, angles and axes atr translated in binary strings by rhe function lire_rota() and are the genetic individuals.

GEN: genetic generation

HEL: help.
If INTER is not cative the arm movement is generated from the better particle.
The command Muta[2]=generate genetice(1)ajust(Muta[0,2],k) expresses is regenerated (automatically modifying the mutate coefficient, variable on the scale muta) crossing (probability proba) and mutating (probability muta) optimizing function FITNESS().
pend pendulum movement.
Individuals are displayed with strings 0 and de 1 on red scales representing their evaluations.
AJUST: mutation est automatically adjusted to thr global evaluation of the population.
STOP: stops cross overs, the genetic does not evoluate anymore.

READ: movements files reading submenu

HEL: help.
READ click on nnn.rota loads this file overwriting all other memories.
ADD: click on nnn.rota adds this file to other read memories.
SUP: deletes all memories.

The arm is animated accordingly.

INTER: interaction

Click in the small box appears in which a small arm (shown possible camera image)
rotation axis or change rota and axis.
Or choose a numebr (under the particles).
the corresponding particle is decoded into a motion about which all particles will tend. la particule correspondante est décodée en un mouvement vers lequel vont tendre toutes les particules. The arm is stabilized in a position close

BIO: biomecanic constrainst

Some limits are fixed on rotations (radius/humerus) and axes (radius, fingers).

The program

Functions
Variables

Functions

Main menu:
mouv_gen(): main function.
externes(): external cariables declaration.
init(): initializations.
generate_menu(): generating the menus.
MEN(): 1st main menu MEN function.
HEL(): main menu help function.
INI(): reinitializations.
ILLUM():yes/no illum.
SKIN(): skins display.
EXT(): yes/no ext.
FONC(): functions display.
fonc_FONC(): called each image if FONCis active.
STEPbySTEP():step by step mode.
EXIT(): exits program.
DEUX_POINTS(): inhibits display ofscales, menus, messages, texts.

Submenu EXPL
EXPL(): submenu EXPL 1st function.
EXPL_HEL(): help of EXPL.
fonc_EXPL(): called each image if EXPL is active.
EXPL_ROTA(): rotation explanations.
fonc_EXPL_ROTA(): called each image if EXPL_ROTA is active.
EXPL_COMPLEX(): explanations about the unit complex numbers associated to a planar rotation.
fonc_EXPL_COMPLEX(): called each image if EXPL_COMPLEX is active.
EXPL_QUAT(): explanations about the unit quaternions associated to a spatial rotation.
fonc_EXPL_QUAT(): called each image if EXPL_QUAT is active.
MOUV(): explianation about the quaternions spherical interpolation.
fonc_EXPL_MOUV(): called each image if EXPL_MOUV is active.
AUTO(): automatic interpolation.
EXPL_MOUVS(): expanations about several movements.
fonc_EXPL_MOUVS(): called each image if EXPL_MOUVS is active.
EXPL_COD(): explanations about the movement encoding.
fonc_EXPL_COD(): called each image if EXPL_COD is active.
EXPL_ALGOGEN(): explanations about the genetic algorythms.
fonc_EXPL_ALGOGEN(): called each image if EXPL_ALGOGEN is active.
ALEA(): genomes random generations.
croiser(): two genomes cross over.
aff_mot(): display of a word (float encoding).

Submenu CREATE
CREATE(): CREATE.
CREATE_HEL(): help.
fonc_CREATE(): called each image if CREATE is active.
CREATE_ROTA(): rotation trajectories validation.
CREATE_QUAT(): quaterniuon trajectories validation.

Submenu GEN
GEN(): 1st function of submenu GEN.
GEN_HEL(): help GEN.
fonc_GEN(): called each image if GEN is active.
GEN_AJUST(): mutation automatic adjustment.
GEN_STOP(): stops the cross overs.

Submenu READ
READ(): 1st function of the submenu READ.
READ_HEL(): help of ethe submenu READ.
READ_READ(): enable read overw.
READ_ADD(): enable read add.
fonc_READ(): called each image if READ is active.

INTER function:
INTER(): validation de l´interaction.
fonc_INTER(): appelée à chaque image si INTER est validée.

Interaction

F0(): called once at the beginning of the interaction.
F5(): called each image after the volumes display, allows displaying scales and process with et texts on the image.

User functions:
dim_screen(): computes dimensions according to the screen size.
set_message(): initializing a flashing message.
SET_BIT(): compute de:
       Nb_Bit=Nb_Bit0[2];Max=(2^Nb_Bit)-1;
       Format=string(Nb_Bit),"B";
       Nb_Bit_quat4*Nb_Bit;
coder_bras(): arm movement encoding.
lire_rota(): read a movements file nnn.rota in the current memory.
cou_vol(): changes the selectioned volume color.
ALL(): selection all volumes.
aff_quat(): displays a quaternion.
aff_genome(): displays a genome.
ini_mot(): words initialization.
rendre_visible(): displays volume or skin.
rendre_invisible(): inhibits the display.
modif_param(): displays the parameters input scales.
STOP_PERIODE(): stops flashing menus.
VOL_QUAT(): returns the arm position evaluation with respect to memory num.
tourner_Vol0(): rotatesvolumes Vol0 in memory -1 (INTER mode).

Conction functions:
cons_bras(inc): building an arm index inc.
cons_rotule(): building a rotle (shoulder and wirst).
cons_doigt(): building a finger.
cons_doigt_1(): building a phalange.
cons_peau_main(): building skins.
cons_peau(): building a skin.
regenerates the particles when the model changes (by INTER) or when a file is read (for READ) to destabilize the genetic that could reach an equilibrium position and evolve anymore (since cross over of identical particles does change not).

Evaluation function:
FITNESS(): evaluation function, automatically called for each genetic particle and at each image.
note(): returns note of the particle p is 1-dist(m,p) with dist(m,p)=distance chains m and p =ratio of the number of different characters and the same indices in the two chains with the common number of characters in two chains.

Encoding decoding:
CODAGE(): spatial rotation transformation (an,xr,yr,zr) into a quatrenion (w,x,y,z) then encoding on 4*Nb_Bit characters 0 and 1.
DECODAGE_ROTA(): decoding a genome (this genome coding a rotation) into a rotation.
DECODAGE_ROTA_QUAT(): decoding a genome (this genome coding a rotation) into a quaternion.
DECODAGE_QUAT_QUAT(): decoding a genome (this genome coding a quaternion) into a quaternion.

Tajectories generation:
GEN_TRAJ()
GEN_TRAJ_ROTA(): rotation trajectories generation.
GEN_TRAJ_QUAT(): quaternion trajectories generation by spherical interpolation.

Variables

Nb_Bit: encoding bits number initialized to 8, its increase improves convergence but at the expense of time calculated. The other constants are computed from its value in the function SET_BIT().
Max=(2^Nb_Bit)-1: encodin maximum value.
Format=chaine(Nb_Bit),"B": used by the command chaine(Format,v); to the integer encoding.
Nb_Bit_quat=4*Nb_Bit: rotation or quaternion encoding bits number.
Sem_AUTO: automatic interpolation (1), manually (0).
Inc=200: increment value of the number of the volumes discribing an arm to another.
Lead,Shoulder,Humerus,Radius,Poignet,Pouce,Indexe,Majeur,Annulaire,Petit,Doigts: bones names.
Peau_Bras,Peau_Main,Peau_Pouce,Peau_Indexe,Peau_Majeur,Peau_Annulaire,Peau_Petit: skins names.
Nb_Part: genetic individuals (particules) number.
Nb_Quat: number of quaternions that make up a basic movement.
Nb_Vol: animated volumes number.
Nb_Mem: number of memories encoding read movements.
Ni: trajectory images number.
Num: number of the selectioned volume.
Dim_Mot,Cassure,Mot1,Mot2,Mot3,Mot0: words used by EXPL_ALGOGEN.
Pend: pendulum (or not) movement.

Uses

Movement recognition
Hybridation