Astarons



L'Astar (A*) est un algorithme d'intelligence artificielle de résolution de problèmes par exploration développé par Hart, Nilsson, et Raphael en 1968 Il s'agit d'un algorithme de type BFS (Best First Search : meilleur d'abord) basé sur une fonction d'évaluation du coût f(n) = g(n) + h(n)g(n) donne le coût pour atteindre l'état n à partir de l'état de départ et h(n) est une heuristique visant à estimer le coût pour aller de l'état n à l'état but. Si h(n) est admissible (ie si h(n) est inférieur ou égal au coût réel), alors l'algorithme trouve la solution optimale.

//	Notations
Pile Ouvert	// Liste des états à étudier classés selon f(n)
Liste Ferme	// Liste des états déjà développés

//	Algorithme
Ajout dans Ouvert de l'état initial
Ferme = 0
Tant que Ouvert est non vide
	Etat Pere = Depilage du meilleur état de Ouvert	// Etat qui minimise f(n)
	Si Pere = état but Alors
		Fin
	Ajout de Pere dans Ferme
	Etat[] Enfants = successeur de Pere
	Pour tous Enfant
		Si Enfant n'est pas dans Ferme Alors
			Calcul de f(Enfant)
			Empilage de Enfant dans Ouvert

A noter que la pile des états ouverts est triée selon f(n), c'est à dire en vue de minimiser le coût global de la solution.


Planification de chemin

La carte est un fractal (512x256) sur 256 niveaux d'altitudes. En vert, on a des limites infranchissables. Les niveaux de gris (calculés) représentent la liste des états fermés et les lignes blanches, la liste des états ouverts (du moins à la fin de la recherche).

Le coût f(n) est la somme des déplacements unitaires g(n), horizontaux et verticaux dans ce cas et de l'heuristique h(n) qui est ici la distance euclidienne entre l'état courant et l'état but.

Afin de compliquer la recherche, il y est considéré que descendre (en altitude) d'un niveau est moins couteux (-20 %) que de rester à la même altitude et que monter est plus couteux (+10%). Afin d'assurer la recherche du chemin optimal, il est considéré que le chemin parcouru est 10% moins intéressant que l'évaluation du chemin restant à parcourir (f = 0.9*g + h).


Résolution du jeu du taquin

Le jeu du taquin est un jeu datant du 19ème siècle dans lequel les pièces peuvent être coulissées afin de rétablir une configuration donnée.

devient :

La résolution du jeu du taquin a fait l'objet de nombreuses recherches. Il peut être résolu par l'algorithme A*. Richard E. Korf a étudié la résolution par un algorithme IDA*, dérivé de l'A*. Il a notamment défini pour cent états donnés le nombre d'états intermédiaires étudiés permettant l'atteinte de l'état but. D'une manière plus générale, la résolution par l'A* nécessite la prise en compte de plusieurs difficultés. Par la suite, il sera considéré que l'état but est le suivant :

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

En 1870, il fut proposé la somme de 1000 dollars à celui qui résoudrait le cas où les cases 14 et 15 étaient inversées. Or ce n'est pas possible. Tous les configurations ne sont pas solubles ; seule une sur deux l'est. Ceci est lié à la parité des permutations : le site eljjdx.canalblog.com propose une méthode de détermination de la solvabilité. Dans le cas du taquin carré de côté de longueur 3, le nombre de configurations permettant d'arriver à une solution telle que celle définie ci-dessus est de 0,5 x 9! = 181 440. Dans le cas du taquin carré de côté de longueur 4, le nombre de configurations permettant d'arriver à la solution définie ci-dessus est de 0,5 x 16! = 10 461 394 944 000.

En traitant 1 millions d'état par seconde, la résolution en force brute d'un taquin à 16 pièces nécessiterait environ 121 jours. Les travaux de R. Korf (en 1985) montrent qu'avec l'IDA*, le nombre d'état étudié peut-être ramené entre 500 000 et 6 000 000 d'états en utilisant la distance de Manhattan en heuristique.

J.C.Culberson et J.Schaeffer ont accéléré la résolution par l'utilisation de bases de données de motifs. Cette méthode consiste à précalculer le nombre de déplacements pour amener une partie des cases (un motif) à leur état but en prenant en compte la totalité des déplacements (y compris ceux de la case 0 et des cases ne figurant pas dans le motif). Cette méthode s'appuie sur le fait que si plusieurs heuristiques sont admissibles, alors leur maximum l'est aussi, conséquence de la relaxation du problème.

13 14 1 0
5 12 11 10
6 3 4 8
7 9 2 15
à ramener à l'état but :
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

En utilisant des motifs disjoints, R.E.Korf et A.Felner ont constaté que la somme des heuristiques était admissible, sous certaines conditions. Lors de la construction des bases de données, seuls les mouvements des cases du motifs sont comptabilisés. En complétant l'exemple ci-dessus, 8 déplacements sont nécessaires pour rétablir le motif jaune dans sa configuration but, 20 pour rétablir le motif rose et 15 pour rétablir le motif vert. L'heuristique vaut alors 8+20+15 = 43.

13 14 1 0
5 12 11 10
6 3 4 8
7 9 2 15
à ramener à l'état but :
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

Puisque la somme des heuristiques de motifs disjoints est une heuristique admissible et que le maximum d'heuristiques admissibles est une heuristique admissible, alors, l'utilisation de multiple base de données de motifs disjoints permet assurément d'améliorer la qualité de l'heuristique.

La construction des bases de données de motifs disjoints se fait par un algorithme d'exploration en largeur d'abord en étudiant tous les états possibles, en incluant la position de la case 0 (la case vide) et en partant de l'état final. Pour reprendre l'exemple un peu plus haut, dans le cas de la construction de la base { 10 à 15 }, puisque seuls les déplacements des cases vertes sont comptabilisés et que ceux-ci sont conditionnés par la position de la case 0, il n'est pas nécessaire de reconnaître les cases grises foncées { 1 à 9 } ; le nombre d'états à étudier est donc de 16 x 15 x 14 x 13 x 12 x 11 x 10 = 57 657 600 états. Il faut donc conserver en mémoire un index vers ces états afin de déterminer si l'état a déjà été étudié, mais aussi quel est le COUT MINIMAL pour l'atteindre. La structure (la classe) utilisée pour définir un motif ou un état du taquin (indépendamment du motif) est celle ci-dessous :

class Pattern
{
	long _id;		// L'état final étant 0x012345679abcdef
	byte _size;		// 3 pour un taquin 3x3, 4 pour un 4x4
	Pattern  _brother;	// Pour gérer sous forme de listes chaînées
	int _patternId;		// id ramené au masque des bases de données
	byte _steps;		// Distance parcourue depuis l'état de départ
}

Le champ _brother est utilisé pour définir des listes chaînées à 2 usages principaux. D'une part, selon l'emplacement de la case 0, un état parent peut avoir 2 à 4 enfants. D'autre part, lors de l'exploration en largeur d'abord, lorsqu'un état est supprimé de la liste, ses fils sont ajoutés en fin de liste : en utilisant le dernier élément d'une liste en boucle, il est facile d'ajouter des éléments en fin de liste ou de récupérer le premier élément. Avec cette méthode et cette classe, la construction des bases de données donne les résultats (dans un contexte informatique bien particulier) ci-dessous :

Longueur
du motif
Temps de
calcul (s)
Largeur
maximale
Nb d'états
étudiés
Nb de motifs
3~0,2~14 00043 6803 360
4~2,5~170 000524 16043 680
5~40~2 000 0005 765 760524 160
6~700~22 000 00057 657 6005 765 760

Dans le cas de motif de longueur 3, la mémoire nécessaire inclue le tableau des motifs (3 360 octets puisque la distance est inférieure à 127), le tableau des états pour éviter la redondance de calcul des états déjà calculés (43 680 octets) ainsi que la largeur maximale de l'exploration en largeur (~14 000 x taille de la structure permettant le parcours du graphe). Java oblige, la taille de la classe est de l'ordre de 40 octets (8 x 5 variables). Finalement, pour les longueurs 3, 4, 5 et 6, les mémoires constatées pour une base de données sont respectivement de l'ordre de 0,6 Mo, 7 Mo, 80 Mo et 900 Mo pour la construction et 3 ko, 43 ko, 512 ko et 5,5 Mo pour la base de données.

Le choix des motifs montrent des écarts importants selon les cases définissant les motifs et la taille des motifs. Cependant, il est clair que la qualité de l'heuristique peut être améliorée par l'utilisation de multiples bases de données. Cette idée est renforcée par la question de l'utilisation de la mémoire. En effet, la construction de multiples bases de données permet de meilleures performances pour une utilisation mémoire moindre.


Références

1. P.E.Hart, N.J.Nilsson and B.Raphael, 1968, A formal basis for the heuristic determination of minimum cost pasths
2. R.E.Korf, 1985, Depth-First iterative deepening : an optimal admissible tree search
3. J.C.Culberson and J.Schaeffer, 1998, Pattern databases
4. R.E.Korf and A.Felner, 2002, Disjoint pattern database heuristics
5. A.Felner, R.E.Korf and S.Hanan, 2004, Additive pattern database heuristics
6. R.C.Holte, J.Newton, A.Felner, R.Meshulam and D.Furcy, 2006, Maximizing over multiple pattern databases speeds up heuristic search


Annexes

Nb étapes Korf (1985) Culberson &
Schaeffer (1998)
18 x 5-5-5 9 x 6-6-3 10 x 6-6-3
1 edf7bc95602148a3 57 276 361 933 36 243 29 446 24 120 23 733
2 d54a9c8e23710fb6 55 15 300 442 104 602 12 852 6 885 6 782
3 e782dba49c50361f 59 565 994 203 1 136 069 349 185 274 859 251 843
4 5ca7fbe0821d3496 56 62 643 179 52 596 10 690 7 257 6 967
5 47eda39cb56f1280 56 11 020 325 187 116 60 256 58 733 56 717
6 e719c36f8b25a04d 52 32 201 660 65 161 4 285 3 694 3 651
7 2bf5d467c8a193e0 52 387 138 094 754 182 27 558 31 888 31 826
8 cbf380426d95e1a7 50 39 118 937 70 313 22 492 25 118 22 643
9 3e9b5482dc67a1f0 46 1 650 696 5 376 1 247 1 099 1 096
10 db890f7a436e5c21 59 198 758 703 919 680 207 014 129 220 128 621
11 59de637ca840f2b1 57 150 346 072 405 740 66 218 71 375 71 448
12 e19648c57230abdf 45 546 344 3 623 2 489 1 406 1 406
13 3652a0fe14dc98b7 46 11 861 705 8 284 7 540 4 664 4 651
14 7681b5ea349df20c 59 1 369 596 778 96 880 108 895 39 845 39 345
15 db4c189f65e273a0 62 543 598 067 534 876 508 404 262 584 257 010
16 1325a9f68edbc470 42 17 984 051 21 477 23 602 18 044 18 025
17 fe04b16d758932ac 66 607 399 560 613 740 464 727 166 287 164 147
18 60ec1f9ab472835d 55 23 711 067 11 095 14 574 8 096 7 987
19 7b83e06f14d95c2a 46 1 280 495 6 579 2 169 1 342 1 342
20 6cb3d79f2e8a4150 52 17 954 870 102 741 20 139 16 484 16 354
21 c8e6b47051af3d92 54 257 064 810 371 882 215 996 82 717 80 315
22 e391f845b7ad02c6 59 750 746 755 748 119 346 425 251 403 212 610
23 a93b0d2e56478f1c 49 15 971 319 30 445 6 380 14 943 14 429
24 73ed41a85c9b2f60 54 42 693 209 94 728 115 199 89 055 88 564
25 b42710af69e83d5c 52 100 734 844 88 543 33 251 17 106 17 012
26 573cfde80a96142b 58 226 668 645 450 264 289 608 142 719 142 396
27 e18f26039cad475b 53 306 123 421 75 511 103 722 59 373 58 957
28 de6c451093a2fb87 52 5 934 442 3 345 6 614 5 060 5 060
29 9802f14e3a75bd6c 54 117 076 111 85 889 20 760 12 015 11 895
30 cf261e485370ad9b 47 2 196 593 3 031 1 256 910 890
31 c8fd1054632b97ea 50 2 351 811 1 219 877 842 841
32 ea94d6582c7013bf 59 661 041 936 3 966 538 310 878 161 219 159 981
33 e35fb6d90a2c4178 60 480 637 867 496 454 112 446 57 762 56 911
34 6b78d2541a39e0cf 52 20 671 552 77 218 15 984 12 670 12 636
35 16ce32f845d907ba 55 47 506 056 5 028 20 323 11 933 11 911
36 c60473f1d98b2e5a 52 59 802 602 71 238 18 803 10 787 10 777
37 817cb0a59f6de234 58 280 078 791 290 466 77 953 37 926 37 870
38 7f82d63cb04a951e 53 24 492 852 38 011 12 823 12 110 11 901
39 904a1ef3c657bd82 49 19 355 806 36 323 25 350 23 912 22 649
40 b51e4ca027d39f68 54 63 276 188 129 719 60 529 54 731 52 243
41 8da9b3f6012ec547 54 51 501 544 133 814 64 011 97 401 94 920
42 45729ecd036b81fa 42 877 023 2 563 896 825 825
43 bfed19a4362c7580 64 41 124 767 242 465 105 819 63 319 59 714
44 c906835e24b7a1fd 50 95 733 125 75 611 9 141 10 128 9 770
45 3e97cf041856ba2d 51 6 158 733 20 047 10 306 8 032 7 797
46 8461ec2fda95370b 49 22 119 320 31 892 7 668 3 424 3 414
47 6a1ef835d02749bc 47 1 411 294 963 883 660 648
48 8b4673a92cfd015e 49 1 905 023 20 010 2 489 1 432 1 391
49 a024516cbd97f3e8 59 1 809 933 698 760 504 273 464 158 936 158 623
50 c5db2a097843e6f1 53 63 036 422 246 627 7 951 10 949 10 192
51 a284f01ebd36975c 56 26 622 863 102 211 27 707 27 185 26 727
52 a80c37621e4bfd95 56 377 141 881 307 787 26 671 36 646 36 605
53 e9cdf48a02173b56 64 465 225 698 476 433 274 672 174 681 156 116
54 cb08a2df547369e1 56 220 374 385 156 892 25 291 39 011 36 555
55 d8e39107f54ac26b 41 927 212 2 012 3 190 1 539 1 559
56 3f25b647c910dea8 55 1 199 487 996 478 569 358 096 185 563 178 864
57 5b694dc082fa173e 50 8 841 527 12 098 3 537 2 871 2 871
58 50f8461eab397c2d 51 12 955 404 30 184 5 586 3 425 3 419
59 fe67a10bc84925d3 57 1 207 520 464 214 422 244 345 189 920 188 842
60 bed123c4f795a680 66 3 337 690 331 6 086 900 773 363 617 036 595 932
61 6d32b95a17ce840f 45 7 096 850 16 820 7 094 3 694 3 670
62 46c0e29db83f7a15 57 23 540 413 40 979 53 463 24 230 23 963
63 8a9be17fd40c6253 56 995 472 712 779 656 47 098 75 053 73 532
64 52e07863bcdf4a91 51 260 054 152 249 683 30 843 43 551 43 247
65 7832ac46bd5f019e 47 18 997 681 26 226 10 852 6 738 6 698
66 b6ec351f80ad9742 61 1 957 191 378 1 367 159 287 116 222 918 221 045
67 7124836baf05ecd9 50 252 783 878 164 340 50 464 66 696 64 344
68 731dca52806bef49 51 64 367 799 30 420 23 501 22 172 21 419
69 605f1e492d8abc73 53 109 562 359 33 540 45 516 21 655 20 873
70 f13c406528e9da7b 52 151 042 571 192 382 75 556 45 225 45 188
71 570bc19af62384de 44 885 972 4 435 1 585 974 957
72 cfba45e0d7129836 56 1 031 641 140 128 658 105 700 38 915 38 443
73 6ea5f8713420c9bd 49 3 222 276 13 507 2 186 2 004 1 811
74 ed4bf86907312ac5 56 1 897 728 35 911 13 509 8 217 8 188
75 e40a651392dfc78b 48 42 772 589 79 080 64 180 52 707 52 584
76 fa8306951edb72c4 57 126 638 417 293 955 95 693 44 874 44 077
77 d24ce69f1a3b587 54 18 918 269 85 067 43 306 31 986 31 684
78 3ed64f895ca0271b 53 10 907 150 43 256 14 649 12 075 11 801
79 197bd53ec4286af 42 540 860 2 367 1 617 1 523 1 483
80 b0f8dc35a146e972 57 132 945 856 624 092 43 556 57 954 56 815
81 d09cb635f81a4e27 53 9 982 569 12 974 1 453 1 037 1 037
82 ea21d98b736cf540 62 5 506 801 123 1 207 363 287 192 402 878 399 675
83 c39145a26bf0e7d8 49 65 533 432 18 707 9 856 9 079 8 404
84 f8a70ce15963db42 55 106 074 303 90 085 54 038 58 624 56 433
85 47da1296c8e530bf 44 2 725 456 4 246 2 843 4 905 4 959
86 605abc921743e8df 45 2 304 426 18 457 2 449 2 028 2 001
87 95bad02186ec473f 52 64 926 494 36 177 15 849 16 665 16 559
88 f2cbed9513870a64 65 6 009 130 748 4 631 654 > 1 000 000 763 281 761 312
89 b174ad389e0f652c 54 166 571 097 480 785 65 458 57 168 56 007
90 5471bcefad862093 50 717 137 12 142 10 432 7 801 7 753
91 9752efcab3618d04 57 602 886 858 891 789 73 157 77 688 76 787
92 32790fc46b5e8da1 57 1 101 072 541 834 259 165 573 105 819 105 531
93 d9e6c81234075abf 46 1 599 909 2 634 8 917 10 251 10 702
94 57b80e9dac3f6142 53 1 337 340 30 078 6 483 6 624 6 373
95 436d7f90a58b2c1e 50 7 115 967 27 227 6 264 9 879 9 849
96 17fe2649cbd3085a 49 12 808 564 33 187 10 500 8 655 8 532
97 9e578f12a4d6c0b3 44 1 002 927 3 209 969 2 187 2 168
98 b3c52198aef74d6 54 103 526 883 108 344 64 063 63 258 60 806
99 7f40a925cbd613e8 57 834 477 694 154 128 57 202 37 185 36 057
100 b4086a5dc7e3129f 54 67 880 056 576 478 92 143 46 006 47 814
TOTAL 36 648 437 075 34 987 804 8 916 370 6 319 355 6 150 807