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 ^^

[anapurna]

salut,

j'essai de comprendre
tu as deux espèces A & B
Pour l'espèces A on peut :
1° ) faire des angles avec d'autres A pour contourner B (Point de contact aux bouts des bâtons ? )
2° ) il est possible de s'accrocher a l’espèce B (en bout ou partout ? )
Pour l'espèces B on peut :
2° ) il est possible de s'accrocher a l’espèce B dans 6 direction (déplacement en 3D ? )

si je comprend bien le but étant d'aller le plus vite possible d'un point X a un point Y (Pour les deux espèce de robot ?)
donc si je comprend bien il faut prendre en compte les influences des autres robots car un robots seul ne peut pas avancer ...
il faut absolument qu'il soit en contact avec un autres ?

[Remilia]

Le principe est d'aller le plus vite d'une "architecture" A à une autre, par exemple un cube de ces robots qui font un triangle après.

Sinon , quelque rectifications de mes explications pourries.

En gros l'espece A est un baton qui peut s'accrocher par les extêmités à l'espèce B une boule, les batons peuvent aller partout autour de la boule ( en 3d comme tu dis ) ils peuvent s'attirer entre eux ( A et A, A et B , B et A, B et B )
Les influences des autres robots est ce qui donne ses "capacités" au miens, sinon , ce sont de vulgaires batons / boules avec des aimants dedans.

J'ai réussi une ébauche d'algo en descente de gradient en considérant les robots comme des points dans l'espace et un vecteur (avec d'autre points relatifs au centre du robot pour définir sa forme ) et maintenant je me demande s'il y a plus efficace.

Avec cette ébauche d'algo va un moteur physique que je coderais après qui va "prendre" les mouvements de l'autre algo et les transformer en "robot n° XX active son électroaimant E avec le pole P pendant delta T secondes)

[anapurna]

salut ,

d’après ta description et par principe le plus rapide est l'accumulation des bâtons, les boules servant de rotule ou de cale lors

avez vous lu cet article qui devrais fortement vous intéresser

[wiwaxia]

Bonjour,

Les précisions successives que tu donnes au sujet de ton système appellent les remarques suivantes:

1°) Le nombre de robots en interaction (N = 2⁶⁴ ~ 1.8E19): dans le cas très favorable où il n'interviendrait pour chacun d'eux que deux états possibles ("0" ou "1"), individuellement représentables par un bit ⁽¹⁾, cela fait pour mémoriser l'ensemble (N/8) octets, soit environ 2.3 millions de téraoctets: cela dépasse largement les capacités de tous les ordinateurs existants.
Les simulations des ensembles à (N) entités, réalisées sur les meilleures machines, ne font intervenir "que" quelques centaines (au mieux quelques milliers) de particules (molécules ou ions), selon la complexité des interactions; et ton PC ramera sérieusement à partir d'une centaine (en supposant le programme mis au point, et le code pas trop lourd).
Peut-être as-tu été impressionné par les scènes de bataille de Star Wars, ou du Seigneur des Anneaux ?
Il te faut donc revoir sérieusement ton effectif à la baisse, et tu pourras t'estimer heureux si ça marche pour N = 10 ou 20 . Après, tu pourras monter avec prudence à 40 ou 60 ...

... 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 ...

Non justement, puisque tu ne saurais tester un programme dont l'exécution bloque indéfiniment la machine ! Il faut au contraire partir d'un faible effectif, et voir ensuite l'évolution du temps de calcul.

2°) En quoi consiste l'évolution du système ? Tu évoques tantôt un mouvement d'ensemble, tantôt un réarrangement,

... J'aimerais chercher un algorithme , possiblement récursif , pour partir d'une position A et arriver a une position B ...

... Je veux partir d'une situation A, d'où je connais les pôles "sortants" des aimants, et je veux arriver à une configuration B ...

... Je veux générer une solution qui à partir d'une configuration X de départ et Y d'arrivée , fait X1 , X 2 etc... pour arriver à Y ...

ce qui a déconcerté les intervenants précédents.

a) En l'absence de forces extérieures, il n'y a pas de mouvement d'ensemble, et le barycentre du système reste fixe. On observera donc une réorganisation interne du système, avec modification des distances et orientations mutuelles des robots - ce qui laisse entrevoir un algorithme suffisamment costaud pour décrire leurs déplacements et leurs basculements ... on y reviendra.

b) Tu souhaites ne faire intervenir que des attractions mutuelles entre aimants:

... Les aimants sur les 2 ne sont pas fait pour repousser , mais peuvent attirer à une distance x ...

alors que les forces produites sont attractives ou répulsives, selon les signes des "masses magnétiques" en interaction (dont tu parais oublier qu'elles sont toujours appariées).
Tu supprimerais de plus , avec la répulsion, le basculement caractéristique des aimants, conséquence de l'action d'un couple de forces de sens opposés.
Il y a cependant plus grave: en l'absence totale de forces répulsives, le système finirait par se contracter en un point, à l'exception des robots non aimantés qui, indifférents au voisinage, resteraient immobiles.
Par conséquent, il intervient au moins de fortes répulsions à courte distance, révélant l'existence d'un volume fini et incompressible pour chacun des objets en interaction.

c) Les 'bâtons' apparaîtront les plus mobiles, parce qu'ils se réduisent à des dipôles uniques alors que les boules en comportent 6 (ce n'est pas une question d'inertie mécanique); tu observeras le plus souvent une évolution monotone et banale, les dipôles venant se blottir les uns contre les autres, en position antiparallèle, ou formant de petits cycles.

3°) La modélisation des robots risque de faire apparaître de légères difficultés, dont tu ne te doutais peut-être pas ...
Le comportement de tels objets est beaucoup plus complexe que celui d'un atome d'hélium, ou d'une balle de ping-pong.
a) Comme cela se passe à priori dans l'espace

... Le principe est d'aller le plus vite d'une "architecture" A à une autre, par exemple un cube de ces robots qui font un triangle après ...
... En gros l'espèce A est un bâton qui peut s'accrocher par les extrêmités à l'espèce B une boule, les bâtons peuvent aller partout autour de la boule ( en 3d comme tu dis ) ils peuvent s'attirer entre eux ( A et A, A et B , B et A, B et B )

il faudra représenter la position de chaque centre par un vecteur de (R³): r = OM = (x, y, z);
b) les bâtons sont des dipôles, dont l'orientation spatiale est caractérisée par un vecteur moment magnétique: P = (P_x, P_y, P_z);
c) les boules constituent un système beaucoup plus complexe, éventuellement réductible à un octaèdre comportant une masse magnétique (+m) en chacun de ses 6 sommets, et une autre (-6*m) en son centre; son orientation sera caractérisée par deux vecteurs unitaires orthogonaux (u, v).
Dans ce dernier cas, il s'agit d'un entité magnétique multipolaire, dont les lignes de champ présentent de nombreuses boucles dans l'espace environnant, et qui imposera aux bâtons une disposition beaucoup plus compliquée que celle que tu sembles espérer.
Je crois que tu as implicitement pensé à un monopôle magnétique, qui malheureusement n'existe pas, ou à une bille constituée d'un métal ferromagnétique, qui attire les aimants.

Quant à l'expression des interactions, il n'est même pas question d'y songer.
(1) Remarquons simplement qu'en attribuant à chaque entité 2 (ou 3) vecteurs, soit 6 (ou 9) réels qui en précision étendue seront codés sur (6 ou 9)*10 = 60 (ou 90) octets, soit 480 (ou 540) bits, on déborde de trois ordres de grandeur l'évaluation initiale ... Cela renforce bien sûr le premier argument.

Le modèle physique d'un ensemble de sphères chargées pourrait constituer, par analogie, un bien meilleur point de départ; on pourrait y trouver:
a) (2*N₁) petites boules, de charges (±q₁), groupées par paires de charges opposées, et toujours en contact avec leur voisine;
b) quelques grosses boules de charges (±q₂), aléatoirement réparties dans l'espace.
La représentation d'une particule se réduit alors à deux données, sa charge (q_i = ±1 ou ±q) et la position de son centre r_i = (x_i, y_i, z_i), soit un ShortInt et 3 trois Extended qui occuperont (1 + 3*10) = 31 octets: c'est quand même moins encombrant !

Si tu arrivais à coder l'évolution de ce système, ce serait déjà pas mal ...

[Remilia]

Merci de ta réponse extrêmement complète, je vais essayer d'implémenter cette piste ^^
Pour ce qui est du "monopole" magnétique, le fabricant d'électroaimants fait en sorte que la répulsion soit la plus faible possible.Et oui je me rends compte de l'absurdité de 2^64 robots :p

Mais dans tout les cas, merci beaucoup !!!! ^-^