L'algorithme A* (A-star) est un algorithme de recherche de chemin très populaire utilisé en intelligence artificielle et en robotique pour trouver le chemin le plus court entre un nœud de départ et un nœud d'arrivée dans un graphe pondéré. En OCaml, nous pouvons définir cet algorithme en suivant une approche fonctionnelle.
Voici un exemple d'implémentation de l'algorithme A* en OCaml, avec des explications détaillées pour chaque étape :
1. Les Types Utilisés :
Nous n'avons pas besoin de définir explicitement les types utilisés, ceux-ci étant inférés par le système de type d'OCaml, mais par soucis de clareté, voici les types utilisés dans cet exemple.
type node = int * int type cost = float type 'a map = 'a array array type heuristic = node -> node -> cost type path = node list type path_cost = cost
- `node` : Type d'identifiant pour les nœuds.
- `cost` : Type de coût pour représenter la distance ou le poids des arêtes.
- `map` : Type pour représenter une carte simple. La généralisation de l'algorithme A*
utilise un graphe contenant des nœuds, avec pour chaque nœud, une liste de ses voisins avec
les coûts associés.
- `heuristic` : Fonction heuristique qui estime le coût restant pour atteindre la cible
à partir d'un nœud donné.
2. La Fonction A* :
Voici la fonction principale A* qui prend en entrée le graphe, le nœud de départ, le nœud cible, la fonction heuristique et renvoie le chemin le plus court (ou le chemin optimal) ainsi que son coût :
let rec a_star map start goal = let w = Array.length map.(0) in let h = Array.length map in let dirs = [ (1, 0, 1.0); (0, 1, 1.0); (-1, 0, 1.0); (0, -1, 1.0); ] in let rec search queue closed = match queue with | [] -> [] (* no path found *) | (current, path, g_cost) :: rest -> if current = goal then List.rev (current :: path) (* return *) else if List.mem current closed then search rest closed else let neighbors = let x, y = current in List.map (fun (dx, dy, c) -> (x + dx, y + dy, c)) dirs in let neighbors = neighbors |> List.filter (fun (x, y, _) -> x >= 0 && y >= 0 && x < w && y < h) |> List.filter (fun (x, y, _) -> map.(y).(x) = 0) in let new_paths = List.map (fun (x, y, cost) -> ((x, y), current :: path, g_cost +. cost) ) neighbors in let queue = List.sort (fun (p1, _, g1) (p2, _, g2) -> compare (g1 +. heu p1 goal) (g2 +. heu p2 goal) ) (List.rev_append new_paths rest) in search queue (current :: closed) in search [(start, [], 0.0)] []
- `a_star` : La fonction principale qui prend en charge la recherche de chemin en utilisant A*.
- `map` : La carte dans laquelle la recherche est effectuée.
- `start` : Le nœud de départ à partir duquel commencer la recherche.
- `goal` : Le nœud cible que l'on souhaite atteindre.
- `heuristic` : La fonction heuristique qui estime le coût restant pour atteindre le nœud cible depuis un nœud donné.
- `(path, path_cost)` : Le résultat de la fonction A*, c'est-à-dire le chemin optimal trouvé et son coût total.
`g_cost` peut également être retourné.
1. Initialisation :
La recherche commence avec un seul nœud de départ `(start, [], 0)` dans la
liste `queue`, où `path` est initialement vide et `g_cost`
(coût réel jusqu'au nœud actuel) est initialisé à 0.
2. Boucle principale :
- La fonction `search` explore les nœuds à partir de `queue`,
en choisissant à chaque étape le nœud avec le coût le plus bas (f = g + h).
- Si le nœud actuel est le nœud cible (`current = goal`), le chemin optimal
est trouvé et renvoyé.
- Sinon, les nœuds voisins du nœud actuel sont ajoutés à `queue` avec leur
chemin mis à jour et leur coût évalué en utilisant la fonction heuristique.
- Les nœuds déjà visités sont ajoutés à la liste `closed`.
3. Fonction `List.sort` :
- Trie la liste des nœuds dans `queue` en fonction de la fonction de coût
(f = g + h),
`g` étant le coût réel depuis le départ jusqu'au nœud courant, et `h`
l'heuristique prédisant le coût du nœud courant jusqu'à l'arrivée.
- La liste `queue` est maintenue triée en fonction des coûts des nœuds à explorer,
ainsi en explorant le premier nœud de cette liste, nous recherchons en priorité le nœud qui
a le plus de chance d'être le nœud le plus proche de l'arrivée.
4. Fonction `List.mem` :
- L'instruction (List.mem current closed) permet d'éviter d'explorer à nouveau
des nœuds déjà explorés.
5. Résultat :
- Une fois que le nœud cible est atteint, le chemin est inversé (`List.rev`) pour obtenir l'ordre correct du nœud de départ au nœud cible.
- Le paramètre `g_cost` peut également être retourné, afin de renseigner
sur le coût du chemin trouvé.
Cette implémentation utilise des fonctions de manipulation de listes standards comme `List.sort` pour trier les éléments de la liste en fonction de leur coût, ainsi que des fonctions d'accès aux éléments déjà visités telles que `List.mem` pour ne pas parcourir deux fois le même nœud.
Cette approche permet une implémentation claire et concise de l'algorithme A* en OCaml, en suivant les principes fonctionnels de manière élégante.
La fonction d'heuristique calcule la distance entre deux points.
(* heuristic function *) let heu (x1, y1) (x2, y2) = let x = x2 - x1 in let y = y2 - y1 in sqrt (float (x * x + y * y))
Les obstacles sont représentés par des `1`.
let map = [| [| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |]; [| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; |]; [| 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 1; |]; [| 0; 0; 0; 0; 0; 1; 1; 1; 0; 0; 0; |]; [| 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; |]; [| 0; 0; 0; 0; 1; 1; 0; 0; 0; 0; 0; |]; [| 0; 0; 0; 1; 1; 0; 0; 0; 0; 0; 0; |]; [| 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 0; |]; [| 0; 0; 0; 1; 0; 0; 0; 0; 0; 0; 0; |]; |] let () = let r = a_star map (0, 0) (10, 8) in let map = Array.map (fun line -> Array.map (fun d -> match d with | 0 -> '.' | 1 -> '#' | _ -> '?' ) line ) map in List.iter (fun (x, y) -> map.(y).(x) <- '*') r; List.iter (fun (x, y) -> Printf.printf " (%d, %d)\n" x y) r; Array.iter (fun line -> Array.iter (fun c -> Printf.printf " %c" c ) line; print_newline () ) map; ;;
$ ocaml a-star.ml
(0, 0) (1, 0) (2, 0) (3, 0) (4, 0) (5, 0) (6, 0) (7, 0) (8, 0) (8, 1) (8, 2) (8, 3) (8, 4) (8, 5) (8, 6) (8, 7) (9, 7) (9, 8) (10, 8) * * * * * * * * * . . . . . . . . . . * . . . . . . . . . . * # # . . . . . # # # * . . . . . . . # . . * . . . . . . # # . . * . . . . . # # . . . * . . . . . # . . . . * * . . . . # . . . . . * *
Pour réduire la quantité de calculs réalisés, vous pouvez aussi utiliser une fonction de calcul de distance Manhattan comme fonction heuristique, ce qui donnera également des résultats satisfaisants.
(* heuristic function *) let heu (x1, y1) (x2, y2) = let x = x2 - x1 in let y = y2 - y1 in (float (x + y))
Pour permettre les déplacements en diagonal, ajouter les directions possibles suivantes :
let dirs = dirs @ [ (1, 1, 1.4); (1, -1, 1.4); (-1, -1, 1.4); (-1, 1, 1.4); ] in
Dans les cas où il n'y a pas de chemin jusqu'au nœud cible, au lieu de ne retourner aucun résultat, il est possible de retourner un résultat partiel correspondant au chemin jusqu'au nœud accessible le plus proche avec :
match queue with
| [] ->
let new_goal =
List.hd (
List.sort (fun p1 p2 ->
compare
(heu p1 goal)
(heu p2 goal)
) closed
)
in
a_star map start new_goal