Labo Algo
Labo Algo
Cette année le thème de la coupe de France de robotique se rapproche en partie du Problème du Voyageur de Commerce.
On me demande souvent quelles sont les applications du PVC, en voici une :-)
Le jeu de cette année est le Coconut Rugby : il s'agit de récupérer des petites balles souples (de la forme d'un petit
ballon de rugby) disposées sur le terrain, et de les amener ou lancer dans l'en-but adverse.
Il y a 8 balles posées à terre, disposées aléatoirement (mais symétriquement).
Il y a aussi 2 palmiers qui contiennent chacun 3 balles, mais sont aussi des obstacles.
Les robots sont placés de part et d'autre du terrain et doivent récupérer le maximum de balle avant de les placer dans le but adverse en les lançant ou en les emportant.
Bien entendu, connaître le chemin le plus court entre toutes les balles peut être un avantage décisif pour vaincre le robot adverse...
D'où le lien évident avec le PVC.
Voir les règles complètes sur : www.planete-sciences.org/robot/concours/coupe/reglement_coupe_2004.html
Considérons d'abord les 8 balles posées à terre et essayons de trouver le chemin le plus court.
On introduira par la suite des notions plus complexes...
Le problème posé ainsi ressemble fortement à un PVC classique, sauf que l'on ne doit pas retourner à la position initiale.
Mais cela ne change rien à la plupart des méthodes utilisées classiquement.
Ma première idée est que pour un nombre de balles aussi faibles, il n'est pas nécessaire d'utiliser une méthode très complexe.
D'autre part la rapidité est très importante, il faudra peut être recalculer plusieurs fois le chemin si des balles ont été déplacées ou récupérées par le robot adverse, et une partie de la CPU doit être consacrée à la gestion des différents "organes sensoriels" du robot et à son déplacement.
L'algorithme 2-opt me parait le plus adapté à cette tâche.
(L'expérience de tspgen me permet d'écarter la méthode des plus proches voisins...)
Essayons donc le 2-opt avec ce petit programme simple en C (200 lignes commentaires compris) : pvccoco-01
Ce programme est un des plus simple possible permettant de faire un 2-opt.
Lire le code source est un bon moyen de comprendre l'algorithme 2-opt (même si vous ne vous intéressez pas au Coconut Rugby :-)
PS : il ya plusieurs bugs corrigés dans les versions suivantes, mais la lecture de ce code source est tout de même conseillée
si vous voulez comprendre l'algorithme.
Voir les différents fichiers de l'archive pour l'utilisation.
J'ai initialisé les 8 balles et la position du robot comme dans l'exemple du "simulateur" fourni avec le règlement de la coupe (sauf erreur).
Ces positions sont définies dans le fichier paramétrable pos_balles.txt.
Elles sont comptées en "carreaux" par rapport au coin inférieur droit du plateau.
L'exécution consiste en 1 seul 2-opt : un parcours est pris au hasard puis un 2-opt est calculé.
L'algorithme est-il efficace ?
Voici quelques stats après 1000 exécutions : (lancer test1000.sh dans l'archive, si vous êtes sous Linux)
Lancement des 1000 exécutions : mar déc 23 23:26:37 CET 2003 Fin : mar déc 23 23:26:44 CET 2003 calcul des statistiques : 16.128990 : 157 16.469413 : 243 17.291268 : 471 17.543204 : 129
La rapidité est satisfaisante : 1000 exécutions en 7 secondes (sur un Athlon 1.33 GHz).
Par contre on remarque que l'optimum apparent (distance 16.13) n'est pas tout le temps atteint (16% du temps seulement).
La majorité des exécutions donne un parcours 7% au dessus de l'optimum (17.29).
Il faudra donc "booster" un peu l'algorithme.
Je vois plusieurs pistes (qui seront explorées un peu plus tard si j'ai le temps...) :
1. Lancer 10 fois l'exécution. On devrait trouver l'optimum presque à chaque fois... Inconvénient : c'est 10 fois plus lent.
2. Essayer d'ajouter l' "insertion-opt" dans l'algorithme comme je l'ai fait dans mon programme
tspgen. Les résultats devraient être meilleurs avec une perte de temps assez faible.
Autres défauts que je vois à ce programme (probablement plus graves que les 7% de dépassement de l'optimum) :
Un petit problème dans mes statistiques de la version précédente : le générateur aléatoire étant initialisé avec la fonction time() qui
retourne une seconde, les chiffres aléatoires étaient toujours les mêmes pendant une seconde, ce qui faussait les stats.
J'ai résolu cela en passant le nombnre d'itérations en argument du programme. De plus cela évite de lancer le programme plusieurs
fois... et le gain de temps est énorme.
Voici les nouvelles statistiques sur 100 000 itérations:
Lancement des 100000 exécutions : ven déc 26 00:22:42 CET 2003 Fin : ven déc 26 00:22:45 CET 2003 calcul des statistiques : Score Occur. Cumul. Ecart 16.128990 : 23.707% 23.707% (+0%) 16.469413 : 15.37% 39.077% (+2.11063%) 16.721349 : 2.5% 41.577% (+3.67264%) 16.912687 : 3.567% 45.144% (+4.85893%) 17.291268 : 17.712% 62.856% (+7.20614%) 17.430241 : 3.885% 66.741% (+8.06778%) 17.469413 : 9.779% 76.52% (+8.31064%) 17.498474 : 4.187% 80.707% (+8.49082%) 17.543204 : 1.45% 82.157% (+8.76815%) 17.970609 : 0.432% 82.589% (+11.4181%) 18.055200 : 2.072% 84.661% (+11.9425%) 18.128990 : 3.45% 88.111% (+12.4%) 18.213938 : 0.721% 88.832% (+12.9267%) 18.307136 : 1.757% 90.589% (+13.5045%) 18.488164 : 0.072% 90.661% (+14.6269%) 18.660751 : 0.59% 91.251% (+15.697%) 18.734541 : 2.446% 93.697% (+16.1545%) 18.877054 : 0.975% 94.672% (+17.038%) 19.148755 : 2.886% 97.558% (+18.7226%) 19.178306 : 0.051% 97.609% (+18.9058%) 19.424683 : 1.085% 98.694% (+20.4334%) 19.498474 : 0.036% 98.73% (+20.8909%) 19.962002 : 0.885% 99.615% (+23.7647%) 20.030234 : 0.331% 99.946% (+24.1878%) 20.123790 : 0.054% 100% (+24.7678%)
L'optimum est trouvé 23.4 % du temps. Et surtout la vitesse d'exécution passe à 100 000 itérations en 2 secondes... impressionnant.
Par contre on est parfois assez éloigné de l'optimum (20.12 au lieu de 16.12 au pire, soit + 24.7 %)
Mon autre idée était de rajouter l'insertion-opt :
Si on prend deux balles numérotées i et j, on teste si insérer la balle i entre j et j+1 amène un gain dans le temps de parcours.
De la même manière on teste l'insertion de la balle j entre i et i+1
Le principe est assez proche du 2-opt.
Si on utilise cet algorithme seul, il est assez moyennement performant :
Tests faits avec 100 000 essais :
L'optimum n'est atteint que dans 0.5% des cas,
Le moins bon score est éloigné de 60% de l'optimum,
J'ai compté 655 résultats différents (chemins proposé à la fin de l'exécution de l'algorithme), contre 25 seulement avec le 2-opt !
Là où cet algo devient intéressant c'est qu'il se combine plutôt bien avec le 2-opt.
Voici les stats sur 100 000 lancements avec parcours au hasard suivi de 2-opt suivi de insertion-opt :
Lancement des 100000 exécutions : ven déc 26 11:21:57 CET 2003 Fin : ven déc 26 11:22:01 CET 2003 calcul des statistiques : Score Occur. Cumul. Ecart 16.128990 : 29.747% 29.747% (+0%) 16.469413 : 15.618% 45.365% (+2.11063%) 16.721349 : 2.5% 47.865% (+3.67264%) 16.912687 : 9.45% 57.315% (+4.85893%) 17.291268 : 18.201% 75.516% (+7.20614%) 17.365058 : 0.57% 76.086% (+7.66364%) 17.469413 : 9.937% 86.023% (+8.31064%) 17.721349 : 0.556% 86.579% (+9.87265%) 17.970609 : 2.517% 89.096% (+11.4181%) 18.128990 : 3.372% 92.468% (+12.4%) 18.148755 : 1.169% 93.637% (+12.5226%) 18.233345 : 1.76% 95.397% (+13.047%) 18.488164 : 0.052% 95.449% (+14.6269%) 18.660751 : 0.42% 95.869% (+15.697%) 18.734541 : 0.291% 96.16% (+16.1545%) 18.877054 : 1.008% 97.168% (+17.038%) 19.128990 : 2.832% 100% (+18.6%)
Le temps de calcul est multiplié par 2 (4 secondes pour 100 000 itérations), mais l'optimum est atteint dans presque 30% des cas, le
moins bon score n'est plus qu'à +18.6% de l'optimum, et on a réduit les résultats à la fin de l'algorithme à 17 formes différentes.
Cette de limitation des trajets finaux est assez étonnante... cela mériterait qu'on se penche un peu plus sur la question.
Voici la liste de ces trajets :
16.128990 : 0-1-4-7-6-3-2-5-8- 16.469413 : 0-1-4-7-6-8-5-3-2- 16.721349 : 0-1-4-6-7-8-5-3-2- 16.912687 : 0-1-4-7-6-2-3-5-8- 17.291268 : 0-1-3-2-5-8-6-4-7- 17.365058 : 0-1-2-3-4-7-6-5-8- 17.469413 : 0-1-2-3-5-8-6-4-7- 17.721349 : 0-1-4-6-7-2-3-5-8- 17.970609 : 0-1-3-2-4-7-6-5-8- 18.128990 : 0-1-2-3-6-7-4-5-8- 18.148755 : 0-1-2-3-4-6-7-5-8- 18.233345 : 0-1-2-3-5-4-7-6-8- 18.488164 : 0-1-3-2-8-5-6-4-7- 18.660751 : 0-1-4-3-2-5-7-6-8- 18.734541 : 0-1-2-3-7-4-6-5-8- 18.877054 : 0-1-2-5-8-6-7-4-3- 19.128990 : 0-1-4-5-8-7-6-3-2-
Il s'agit des "optimum locaux" de l'algorithme pour ce problème. C'est à dire qu'une petite amélioration ne permet pas de passer à un
meilleure solution.
Ca c'est la thérorie... en pratique je vois que l'on pourrait passer facilement d'une solution à un autre dans certains cas :
Part exemple on peut passer de la solution de longueur 16.72 à celle de longueur 16.46 en inversant 2 balles : la 6 et la 7.
Cela montre un bug dans mon implémetation du 2-opt... les balles adjacentes ne semblent pas pouvoir être inversées.
En corrigeant ce problème cela devrait améliorer l'efficacité de l'algo et probablement diminuer le nombre de trajets finaux.
Essayons ça...
Après analyse, le problème ne vient pas d'un bug dans le 2-opt, mais du fait que l'on n'a pas assez passé complètement l'algorithme :
une fois qu'un trajet a été amélioré par une inversion 2-change, il reste certaines inversions qui n'ont pas été testées.
Si on lance 2 fois un 2-opt (au lieu de 2-opt + inversion-opt) on obtient un résultat nettement meilleur :
Lancement des 100000 exécutions : ven déc 26 12:30:13 CET 2003 Fin : ven déc 26 12:30:16 CET 2003 calcul des statistiques : Score Occur. Cumul. Ecart 16.128990 : 39.767% 39.767% (+0%) 0-1-4-7-6-3-2-5-8- 16.469413 : 26.168% 65.935% (+2.11063%) 0-1-4-7-6-8-5-3-2- 17.291268 : 25.26% 91.195% (+7.20614%) 0-1-3-2-5-8-6-4-7- 17.469413 : 1.181% 92.376% (+8.31064%) 0-1-2-3-5-8-6-4-7- 18.055200 : 2.766% 95.142% (+11.9425%) 0-1-2-5-3-4-7-6-8- 18.128990 : 4.833% 99.975% (+12.4%) 0-1-3-2-5-6-4-7-8- 18.307136 : 0.025% 100% (+13.5045%) 0-1-2-3-5-6-4-7-8-
De la même manière, si on change la procédure 2-opt pour qu'elle soit relancée dès que le trajet a été optimisé (donc modifié), on obtient un résultat encore meilleur :
Lancement des 100000 exécutions : ven déc 26 12:43:18 CET 2003 Fin : ven déc 26 12:43:21 CET 2003 calcul des statistiques : Score Occur. Cumul. Ecart 16.128990 : 42.127% 42.127% (+0%) 0-1-4-7-6-3-2-5-8- 16.469413 : 26.12% 68.247% (+2.11063%) 0-1-4-7-6-8-5-3-2- 17.291268 : 24.974% 93.221% (+7.20614%) 0-1-3-2-5-8-6-4-7- 18.055200 : 2.651% 95.872% (+11.9425%) 0-1-2-5-3-4-7-6-8- 18.128990 : 4.128% 100% (+12.4%) 0-1-3-2-5-6-4-7-8-
L'ajout de l'insertion-opt apporte une amélioration intéressante en supprimant les moins bons scores :
Lancement des 100000 exécutions : ven déc 26 13:01:09 CET 2003 Fin : ven déc 26 13:01:14 CET 2003 calcul des statistiques : Score Occur. Cumul. Ecart 16.128990 : 42.01% 42.01% (+0%) 0-1-4-7-6-3-2-5-8- 16.469413 : 26.389% 68.399% (+2.11063%) 0-1-4-7-6-8-5-3-2- 17.291268 : 29.002% 97.401% (+7.20614%) 0-1-3-2-5-8-6-4-7- 17.365058 : 2.599% 100% (+7.66364%) 0-1-2-3-4-7-6-5-8-
Et enfin, en généralisant l'idée : on calcule le 2-opt puis l'insertion-opt, et dès que le trajet a été amélioré par un 2-opt ou une insertion, on relance le calcul d'optimisation. On obtient alors un algorithme quasi-parfait : 73% de réussite, moins bon score 2% au dessus de l'optimum... 1 000 000 de trajets ont été calculés en 46 secondes.
Lancement des 1000000 exécutions : ven déc 26 13:27:00 CET 2003 Fin : ven déc 26 13:27:46 CET 2003 calcul des statistiques : Score Occur. Cumul. Ecart 16.128990 : 73.7456% 73.7456% (+0%) 0-1-4-7-6-3-2-5-8- 16.469413 : 26.2544% 100% (+2.11063%) 0-1-4-7-6-8-5-3-2-
Je crois qu'on peut s'arrêter là pour la version 2 de l'algorithme...
A faire pour la prochaine version :
Cette version prend en compte 14 balles. J'ai également créé un petit générateur de positions aléatoires (pour l'instant des positions aléatoires sur le terrain, pas forcément dans les positions prédéterminées ni symétriquement. Ce serait le cas de balles bien mélangées par les robots...)
Une correction importante : dans les versions précédentes, la lecture du fichier des positions avait un problème, seuls la partie entière des chiffres étaient lus... (mais cela ne changeait pas grand chose pour le problème précédent où la plupart des valeurs étaient entières)
Voyons le temps et l'efficacité avec 14 balles et 1 000 000 de trajets.
Lancement des 1000000 exécutions : sam déc 27 00:26:46 CET 2003 Fin : sam déc 27 00:29:26 CET 2003 calcul des statistiques : Score Occur. Cumul. Ecart 16.510160 : 71.666% 71.666% (+0%) 0-10-5-1-12-2-14-3-13-6-8-11-4-7-9- 16.736244 : 20.035% 91.701% (+1.36936%) 0-10-9-7-11-8-4-1-5-12-2-14-3-13-6- 16.755759 : 5.3722% 97.074% (+1.48756%) 0-5-1-10-9-7-4-11-8-6-13-3-14-2-12- 17.350667 : 2.7952% 99.869% (+5.09085%) 0-5-1-10-9-7-11-8-4-12-2-14-3-13-6- 19.000108 : 0.1308% 100% (+15.0813%) 0-14-3-2-12-1-5-10-9-7-4-11-8-6-13-
Le temps de calcul est de 160 s pour 1 000 000 de trajets calculés... C'est encore très raisonnable.
Admettons que l'on ait un processeur 10 fois moins puissant que le mien (133 MHz à la place de 1.33GHz) et
que l'on dispose de 1/10 de seconde pour calculer le trajet. On aurait le temps de le calculer 65 fois...
Cela nous laisserait de la marge pour un algo un peu plus élaboré comme un "Monte Carlo"... mais cette CPU restante sera peut être utilisée pour la gestion des obstacles...
Par contre la qualité du résultat dépend fortement du trajet considéré. Autre exemple sur d'autres positions de balles :
Lancement des 100000 exécutions : sam déc 27 00:20:50 CET 2003 Fin : sam déc 27 00:21:05 CET 2003 calcul des statistiques : Score Occur. Cumul. Ecart 17.215007 : 34.802% 34.802% (+0%) 0-1-13-7-9-12-8-11-2-6-4-3-14-5-10- 17.260866 : 25.62% 60.422% (+0.26639%) 0-1-13-10-5-7-9-12-8-11-2-6-4-3-14- 17.356592 : 12.504% 72.926% (+0.822451%) 0-1-13-9-7-10-5-14-3-4-6-2-11-8-12- 17.579026 : 11.851% 84.777% (+2.11454%) 0-1-13-7-10-5-14-3-4-6-2-9-12-8-11- 18.168478 : 1.516% 86.293% (+5.5386%) 0-13-1-12-8-11-2-9-7-10-5-14-4-6-3- 18.195540 : 9.242% 95.535% (+5.6958%) 0-13-1-12-11-8-9-7-10-5-2-6-4-3-14- 18.252367 : 1.148% 96.683% (+6.02591%) 0-10-5-14-3-4-6-2-9-7-13-1-12-8-11- 19.052682 : 3.317% 100% (+10.6748%) 0-13-1-12-8-11-3-14-4-6-2-9-7-10-5-
Dans ce cas on ne trouve pas l'optimum dans la majorité des cas, mais des solutions très approchées. On peut considérer cela comme suffisant.
Passons à un peu de maths avec la prise en compte des obstacles.
Si l'on veut aller du point A au point B, et qu'un obstacle (un palmier par exemple) se trouve en O.
Avec R le rayon d'encombrement du robot (pratiquement : largeur max du robot + rayon maxi de l'obstacle).
S'il y a collision possible, je considère que le robot doit allonger son parcours de 2 fois d (en suivant le trajet en rouge par exemple) pour éviter l'obstacle. Pratiquement, il se peut que le robot suive une trajectoire un peu différente, avec un seul point
intermédaire, par exemple, mais je laisse le soin au sous-programme de déplacement de choisir la manière d'éviter l'obstacle. Je
prend pour hypothèse que cela ne changera pas fondamentalement le résultat. A confirmer :-)
Comment calculer la longueur d ? C'est R moins la distance entre O et I. Avec I le point du segment [AB] le plus proche de O.
J'ai fait quelques fonctions pour calculer ça (à débugguer éventuellement...). Dans le reste de mon programme, le coût pour aller de la balle A à la balle B sera donc maintenant de distance(A, B) + 2d.
Evidemment des calculs de ce type ralentissent fortement le calcul des trajets...
D'après mes premières mesures le calcul est 10 fois plus lent en prenant en compte 2 obstacles.
Mais cela reste acceptable et il devrait y avoir moyen d'accélerer le calcul en utilisant un cache des distances entre les balles.
L'utilisation de ce cache améliore grandement les performances (au prix de quelques octets supplémentaire de mémoire) : 1 000 000 de trajets en 100 secondes, calcul du cache compris !
Lancement des 1000000 exécutions : sam déc 27 22:42:35 CET 2003 Fin : sam déc 27 22:44:17 CET 2003 calcul des statistiques : Score Occur. Cumul. Ecart 21.097287 : 15.116% 15.1168% (+0%) 0-10-9-5-1-7-4-11-8-6-13-3-12-2-14- 21.383017 : 71.950% 87.0675% (+1.35434%) 0-10-9-7-4-11-8-6-13-3-14-2-12-1-5- 21.423200 : 0.5171% 87.5846% (+1.54481%) 0-5-1-10-9-7-4-11-8-6-13-3-12-2-14- 22.502723 : 2.9937% 90.5783% (+6.66169%) 0-10-9-4-8-11-7-5-1-12-2-14-3-13-6- 22.610106 : 3.0083% 93.5866% (+7.17068%) 0-10-9-5-1-7-11-8-4-12-2-14-3-13-6- 22.936019 : 6.4134% 100% (+8.71549%) 0-5-1-10-9-7-11-8-4-12-2-14-3-13-6-
(Test avec 14 balles et 2 obstacles)
Ne reste plus qu'à conserver le meilleur de N itérations, pour être un peu plus certain d'un bon résultat. avec NB_ITER=5 cela donne :
Lancement des 1000000 exécutions : ven jan 2 19:57:54 UTC 2004 Fin : ven jan 2 20:01:05 UTC 2004 calcul des statistiques : Score Occur. Cumul. Ecart 21.097287 : 38.954% 38.954% (+0%) 0-10-9-5-1-7-4-11-8-6-13-3-12-2-14- 21.383017 : 60.831% 99.785% (+1.35434%) 0-10-9-7-4-11-8-6-13-3-14-2-12-1-5- 21.423200 : 0.0282% 99.813% (+1.54481%) 0-5-1-10-9-7-4-11-8-6-13-3-12-2-14- 22.502723 : 0.1097% 99.923% (+6.66169%) 0-10-9-4-8-11-7-5-1-12-2-14-3-13-6- 22.610106 : 0.0543% 99.977% (+7.17068%) 0-10-9-5-1-7-11-8-4-12-2-14-3-13-6- 22.936019 : 0.0226% 100% (+8.71549%) 0-5-1-10-9-7-11-8-4-12-2-14-3-13-6-
Sauf dans de rare cas, le meilleur trajet (ou un proche à 1.3%) est trouvé...
Voilà donc pour la version 3 :
Ce qui resterait à faire (mais je n'aurais plus de temps à consacrer à ce prog avant pas mal de temps...) :
Si quelqu'un apporte des améliorations je serai intéressé par le code source ... même s'il arrive après la coupe !
Labo Algo
Alexandre Aupetit, Avril 2004