Discussion :

[Remilia]

Bonjour, étant nouveau à l'algorithmique , (bien qu'ayant lu des cours) , j'expose ici mon problème. Toute piste , même petite serait d'une grande aide.

On a une colonie de robots composée de 2 sortes de robots : les boules et les batons. Les batons peuvent tourner autour des boules et s'en détacher (pas se répulser par contre). De plus, les boules sont "garnies" d'électroaimants à l'intérieur sur les 3 axes, et peuvent donc attirer les batons, qui ont des électroaimants sur leurs extremitées . Les batons ainsi que les boules peuvent prendre 3 polaritées : -, Neutre, +.

J'aimerais chercher un algorithme , possiblement récursif , pour partir d'une position A et arriver a une position B (les polaritées des électroaimants à la position B ne sont pas primordiales). Pour l'instant , mes simulations utilisent un arbre de recherche.... pour 6 robots , ça va, mais le nombre "max" est 2^64 , et bon ^^......

[gpcbitnik38]

j'ai pas compris comment se déplaçai tes robots en faite ^^.
et aussi une precision : le but est de faire parvenir tous tes robots au point B?

[Remilia]

Je m'explique. Les robots en forme de boule ont 6 électroaimants à l'intérieur, 2 dans chaque axes, avec 1 seul pôle pointant vers l'extérieur. Les batons de même mais uniquement a leurs extremités. Les aimants sur les 2 ne sont pas fait pour repousser , mais peuvent attirer à une distance x. Je veux partir d'une situation A, d'où je connais les pôles "sortants" des aimants, et je veux arriver à une configuration B, d'ont je m'en fiche des pôles. L'algo que j'utilise en ce moment est un graphe, de chaque combinaison de pôle possible en modifiant seulement 1 pôle d'1 microrobot et ainsi de suite...... sauf que la complexitée de ça c'est exponenciel, donc pour 10 bots ca marche, mais pour 2^64.....;

[gpcbitnik38]

ok j'ai toujours pas compris mais je pense pouvoir t'aider lol
en gros actuellement tu génères tout ton espace de solution jusqu'a ce que tu aboutisse a une solution correct c'est bien cela? on peut apparenter ton algorithme a un A* si j'ai bien compris.

pour aller plus vite je pense que tu vas devoir utiliser un algo d'optimisation numérique.
il faut dans un premier temps construire une fonction dite fonction cout. cette fonction évalue la pertinence d'un mouvement (dans ton cas c'est assez simple,on utilise la distance restante a parcourir (on pourra plus tard complexifier cette fonction pour prendre en compte des configuration d'électroaimant)).
ensuite il faut choisir un type d'algorithme (il y en a des tas et je connais simplement d'eux grande famille parmis ceux ci )
les algo par descente de gradient ( necessite une fonction cout derivable (ce qui est le cas ici))
les algo génétique.
(dans ton cas je n'ai pas bien compris mais si il existe un nombre important de configuration bloquante je te recommande les algo genetique. sinon un algo par descente de gradient sera plus efficace.)

description grossiere du fonctionnement de l'algo genetique.
chaque electroaimant est une entrée (on parle de gène) qui peut avoir 3 valeur ( allèles ) + - ou neutre
tu genères aleatoirement des combinaison possible des tous tes EA (on parle de population, le nombre d'individue est a fixer)
ensuite tu selectionne chaque individue et tu les compare entre eu (il existe plusieur metode de selection et de comparaison je te laisse te renseigner) (plus une combinaison te rapproche de B plus l'individue a un bon score)
les individus selectionnés te serve ensuite a générer la nouvelle population pour le mouvement suivant. la génération se fait par "accouplement" en "fusionnant des combinaisons", par mutation (en modifiant légèrement les candidats existant) et aléatoirement (permet de ne pas tomber dans un point bloquant)


tu réalise autant d'iteration (autant de population) qu'il n'en faut pour arriver assez proche de B

[kija13]

Bonsoir

Tu es sur de ton 2^64?
ça fait quand même beaucoup...

[Remilia]

Peut être que je ne comprends pas l'utilisation d'un algorithme génétique , mais comme tu semble confus avec mes (pas très claires) explications. Désolé de te demander ça , mais peux-tu expliquer ce que tu as compris de mes explications ? Sans ce soucier de comment ça marche; voici le problème :

On a deux espèces A & B. l'espèce A (bâtons) peut faire des angles avec d'autres de la même espèce autour l'espèce B (boules). l'espèce B peut également s'accrocher à l'espèce A et l'espèce B. Je veux générer une solution qui à partir d'une configuration X de départ et Y d'arrivée , fait X₁ , X ₂ etc... pour arriver à Y. Le problème étant "comment évaluer un déplacement comme étant "bon" ". Car de nombreuses solution apparaissant comme "bonnes" sont des impasses. La théorie génétique à l'air d'être adaptée , mais je ne comprend pas comment est-ce qu'elle s'applique à mon problème en "pratique". Comment dire qu'un EA est "bon" ? La config des EAs dans la solution finale (insert point godwin) n'est pas connue , seulement le positionnement et l'orientation des robots le sont. Et pour la plupart des "transformation" , cela va être séquenciel. X1 va créer X2 etc.. tout ne sera pas possible "en même temps"

Et, kija13, le 2^64 est le nombre max théorique de robots (espèce A et B confondues). Basiquement , comme il risque d'y en avoir beaucoup , autant tester avec le "pire" nombre pour le temps ^^