Implémentation de A * Pathfinding en Java

1. Introduction

Les algorithmes de recherche de chemin sont des techniques de navigation sur les cartes , nous permettant de trouver un itinéraire entre deux points différents. Différents algorithmes ont des avantages et des inconvénients différents, souvent en termes d'efficacité de l'algorithme et d'efficacité de l'itinéraire qu'il génère.

2. Qu'est-ce qu'un algorithme de recherche de chemin?

Un algorithme de recherche de chemin est une technique permettant de convertir un graphe - composé de nœuds et d'arêtes - en une route à travers le graphe . Ce graphe peut être tout ce qui doit être parcouru. Pour cet article, nous allons tenter de traverser une partie du système de métro de Londres:

(La «carte du métro aérien du métro de Londres DLR Crossrail» par sameboat est sous licence CC BY-SA 4.0)

Cela a beaucoup de composants intéressants:

  • Nous pouvons ou non avoir un itinéraire direct entre nos points de départ et d'arrivée. Par exemple, on peut passer directement de «Earl's Court» à «Monument», mais pas à «Angel».
  • Chaque étape a un coût particulier. Dans notre cas, c'est la distance entre les stations.
  • Chaque arrêt n'est connecté qu'à un petit sous-ensemble des autres arrêts. Par exemple, «Regent's Park» est directement relié à seulement «Baker Street» et «Oxford Circus».

Tous les algorithmes de recherche de chemin prennent en entrée une collection de tous les nœuds - les stations dans notre cas - et les connexions entre eux, ainsi que les points de départ et d'arrivée souhaités. La sortie est généralement l'ensemble de nœuds qui nous mènera du début à la fin, dans l'ordre dans lequel nous devons aller .

3. Qu'est-ce que A *?

A * est un algorithme de recherche de chemin spécifique , publié pour la première fois en 1968 par Peter Hart, Nils Nilsson et Bertram Raphael. Il est généralement considéré comme le meilleur algorithme à utiliser lorsqu'il n'y a aucune possibilité de précalculer les routes et qu'il n'y a aucune contrainte sur l'utilisation de la mémoire .

La complexité de la mémoire et des performances peut être O (b ^ d) dans le pire des cas, donc même si cela déterminera toujours l'itinéraire le plus efficace, ce n'est pas toujours le moyen le plus efficace de le faire.

A * est en fait une variante de l'algorithme de Dijkstra, où des informations supplémentaires sont fournies pour vous aider à sélectionner le prochain nœud à utiliser. Ces informations supplémentaires n'ont pas besoin d'être parfaites - si nous avons déjà des informations parfaites, la recherche de chemin est inutile. Mais mieux c'est, meilleur sera le résultat final.

4. Comment fonctionne A *?

L'algorithme A * fonctionne en sélectionnant de manière itérative quelle est la meilleure route jusqu'à présent et en essayant de voir quelle est la meilleure prochaine étape.

Lorsque nous travaillons avec cet algorithme, nous avons plusieurs éléments de données dont nous devons garder une trace. Le «jeu ouvert» est l'ensemble des nœuds que nous envisageons actuellement. Ce ne sont pas tous les nœuds du système, mais plutôt chaque nœud à partir duquel nous pourrions passer à l'étape suivante.

Nous garderons également une trace du meilleur score actuel, du score total estimé et du meilleur nœud précédent actuel pour chaque nœud du système.

Dans ce cadre, nous devons être en mesure de calculer deux scores différents. L'un est le score à obtenir d'un nœud à l'autre. La seconde est une heuristique pour donner une estimation du coût de n'importe quel nœud à la destination. Cette estimation n'a pas besoin d'être précise, mais une plus grande précision donnera de meilleurs résultats. La seule exigence est que les deux scores soient cohérents l'un avec l'autre - c'est-à-dire qu'ils sont dans les mêmes unités.

Au tout début, notre ensemble ouvert se compose de notre nœud de départ, et nous n'avons aucune information sur les autres nœuds.

À chaque itération, nous allons:

  • Sélectionnez le nœud de notre ensemble ouvert qui a le score total estimé le plus bas
  • Supprimer ce nœud de l'ensemble ouvert
  • Ajoutez à l'ensemble ouvert tous les nœuds que nous pouvons atteindre à partir de celui-ci

Lorsque nous faisons cela, nous calculons également le nouveau score de ce nœud vers chaque nouveau pour voir s'il s'agit d'une amélioration par rapport à ce que nous avons jusqu'à présent, et si c'est le cas, nous mettons à jour ce que nous savons sur ce nœud.

Cela se répète ensuite jusqu'à ce que le nœud de notre ensemble ouvert qui a le score total estimé le plus bas soit notre destination, à quel point nous avons notre route.

4.1. Exemple travaillé

Par exemple, commençons par «Marylebone» et essayons de trouver notre chemin vers «Bond Street».

Au tout début, notre ensemble ouvert se compose uniquement de «Marylebone» . Cela signifie qu'il s'agit implicitement du nœud pour lequel nous avons le meilleur «score total estimé».

Nos prochains arrêts peuvent être «Edgware Road», avec un coût de 0,4403 km, ou «Baker Street», avec un coût de 0,4153 km. Cependant, «Edgware Road» est dans la mauvaise direction, donc notre heuristique d'ici à la destination donne un score de 1,4284 km, alors que «Baker Street» a un score heuristique de 1,0753 km.

Cela signifie qu'après cette itération, notre ensemble ouvert se compose de deux entrées - «Edgware Road», avec un score total estimé à 1,8687 km, et «Baker Street», avec un score total estimé à 1,4906 km.

Notre deuxième itération commencera alors à partir de «Baker Street», car il a le score total estimé le plus bas. De là, nos prochains arrêts peuvent être «Marylebone», «St. John's Wood »,« Great Portland Street », Regent's Park» ou «Bond Street».

Nous ne travaillerons pas sur tout cela, mais prenons «Marylebone» comme un exemple intéressant. Le coût pour s'y rendre est à nouveau de 0,4153 km, mais cela signifie que le coût total est maintenant de 0,8306 km. De plus, l'heuristique d'ici à la destination donne un score de 1,323 km.

Cela signifie que le score total estimé serait de 2,1536 km, ce qui est pire que le score précédent pour ce nœud. Cela a du sens car nous avons dû faire un travail supplémentaire pour aller nulle part dans ce cas. Cela signifie que nous ne considérerons pas cela comme une voie viable. En tant que tel, les détails de «Marylebone» ne sont pas mis à jour et ne sont pas rajoutés à l'ensemble ouvert.

5. Implémentation Java

Now that we've discussed how this works, let's actually implement it. We're going to build a generic solution, and then we'll implement the code necessary for it to work for the London Underground. We can then use it for other scenarios by implementing only those specific parts.

5.1. Representing the Graph

Firstly, we need to be able to represent our graph that we wish to traverse. This consists of two classes – the individual nodes and then the graph as a whole.

We'll represent our individual nodes with an interface called GraphNode:

public interface GraphNode { String getId(); }

Each of our nodes must have an ID. Anything else is specific to this particular graph and is not needed for the general solution. These classes are simple Java Beans with no special logic.

Our overall graph is then represented by a class simply called Graph:

public class Graph { private final Set nodes; private final Map
    
      connections; public T getNode(String id) { return nodes.stream() .filter(node -> node.getId().equals(id)) .findFirst() .orElseThrow(() -> new IllegalArgumentException("No node found with ID")); } public Set getConnections(T node) { return connections.get(node.getId()).stream() .map(this::getNode) .collect(Collectors.toSet()); } }
    

This stores all of the nodes in our graph and has knowledge of which nodes connect to which. We can then get any node by ID, or all of the nodes connected to a given node.

At this point, we're capable of representing any form of graph we wish, with any number of edges between any number of nodes.

5.2. Steps on Our Route

The next thing we need is our mechanism for finding routes through the graph.

The first part of this is some way to generate a score between any two nodes. We'll the Scorer interface for both the score to the next node and the estimate to the destination:

public interface Scorer { double computeCost(T from, T to); }

Given a start and an end node, we then get a score for traveling between them.

We also need a wrapper around our nodes that carries some extra information. Instead of being a GraphNode, this is a RouteNode – because it's a node in our computed route instead of one in the entire graph:

class RouteNode implements Comparable { private final T current; private T previous; private double routeScore; private double estimatedScore; RouteNode(T current) { this(current, null, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } RouteNode(T current, T previous, double routeScore, double estimatedScore) { this.current = current; this.previous = previous; this.routeScore = routeScore; this.estimatedScore = estimatedScore; } }

As with GraphNode, these are simple Java Beans used to store the current state of each node for the current route computation. We've given this a simple constructor for the common case, when we're first visiting a node and have no additional information about it yet.

These also need to be Comparable though, so that we can order them by the estimated score as part of the algorithm. This means the addition of a compareTo() method to fulfill the requirements of the Comparable interface:

@Override public int compareTo(RouteNode other) { if (this.estimatedScore > other.estimatedScore) { return 1; } else if (this.estimatedScore < other.estimatedScore) { return -1; } else { return 0; } }

5.3. Finding Our Route

Now we're in a position to actually generate our routes across our graph. This will be a class called RouteFinder:

public class RouteFinder { private final Graph graph; private final Scorer nextNodeScorer; private final Scorer targetScorer; public List findRoute(T from, T to) { throw new IllegalStateException("No route found"); } }

We have the graph that we are finding the routes across, and our two scorers – one for the exact score for the next node, and one for the estimated score to our destination. We've also got a method that will take a start and end node and compute the best route between the two.

This method is to be our A* algorithm. All the rest of our code goes inside this method.

We start with some basic setup – our “open set” of nodes that we can consider as the next step, and a map of every node that we've visited so far and what we know about it:

Queue openSet = new PriorityQueue(); Map
    
      allNodes = new HashMap(); RouteNode start = new RouteNode(from, null, 0d, targetScorer.computeCost(from, to)); openSet.add(start); allNodes.put(from, start);
    

Our open set initially has a single node – our start point. There is no previous node for this, there's a score of 0 to get there, and we've got an estimate of how far it is from our destination.

The use of a PriorityQueue for the open set means that we automatically get the best entry off of it, based on our compareTo() method from earlier.

Now we iterate until either we run out of nodes to look at, or the best available node is our destination:

while (!openSet.isEmpty()) { RouteNode next = openSet.poll(); if (next.getCurrent().equals(to)) { List route = new ArrayList(); RouteNode current = next; do { route.add(0, current.getCurrent()); current = allNodes.get(current.getPrevious()); } while (current != null); return route; } // ...

When we've found our destination, we can build our route by repeatedly looking at the previous node until we reach our starting point.

Next, if we haven't reached our destination, we can work out what to do next:

 graph.getConnections(next.getCurrent()).forEach(connection -> { RouteNode nextNode = allNodes.getOrDefault(connection, new RouteNode(connection)); allNodes.put(connection, nextNode);   double newScore = next.getRouteScore() + nextNodeScorer.computeCost(next.getCurrent(), connection); if (newScore < nextNode.getRouteScore()) { nextNode.setPrevious(next.getCurrent()); nextNode.setRouteScore(newScore); nextNode.setEstimatedScore(newScore + targetScorer.computeCost(connection, to)); openSet.add(nextNode); } }); throw new IllegalStateException("No route found"); }

Here, we're iterating over the connected nodes from our graph. For each of these, we get the RouteNode that we have for it – creating a new one if needed.

We then compute the new score for this node and see if it's cheaper than what we had so far. If it is then we update it to match this new route and add it to the open set for consideration next time around.

This is the entire algorithm. We keep repeating this until we either reach our goal or fail to get there.

5.4. Specific Details for the London Underground

What we have so far is a generic A* pathfinder, but it's lacking the specifics we need for our exact use case. This means we need a concrete implementation of both GraphNode and Scorer.

Our nodes are stations on the underground, and we'll model them with the Station class:

public class Station implements GraphNode { private final String id; private final String name; private final double latitude; private final double longitude; }

The name is useful for seeing the output, and the latitude and longitude are for our scoring.

In this scenario, we only need a single implementation of Scorer. We're going to use the Haversine formula for this, to compute the straight-line distance between two pairs of latitude/longitude:

public class HaversineScorer implements Scorer { @Override public double computeCost(Station from, Station to) { double R = 6372.8; // Earth's Radius, in kilometers double dLat = Math.toRadians(to.getLatitude() - from.getLatitude()); double dLon = Math.toRadians(to.getLongitude() - from.getLongitude()); double lat1 = Math.toRadians(from.getLatitude()); double lat2 = Math.toRadians(to.getLatitude()); double a = Math.pow(Math.sin(dLat / 2),2) + Math.pow(Math.sin(dLon / 2),2) * Math.cos(lat1) * Math.cos(lat2); double c = 2 * Math.asin(Math.sqrt(a)); return R * c; } }

We now have almost everything necessary to calculate paths between any two pairs of stations. The only thing missing is the graph of connections between them. This is available in GitHub.

Let's use it for mapping out a route. We'll generate one from Earl's Court up to Angel. This has a number of different options for travel, on a minimum of two tube lines:

public void findRoute() { List route = routeFinder.findRoute(underground.getNode("74"), underground.getNode("7")); System.out.println(route.stream().map(Station::getName).collect(Collectors.toList())); }

This generates a route of Earl's Court -> South Kensington -> Green Park -> Euston -> Angel.

The obvious route that many people would have taken would likely be Earl's Count -> Monument -> Angel, because that's got fewer changes. Instead, this has taken a significantly more direct route even though it meant more changes.

6. Conclusion

Dans cet article, nous avons vu ce qu'est l'algorithme A *, comment il fonctionne et comment l'implémenter dans nos propres projets. Pourquoi ne pas prendre ceci et l'étendre pour vos propres usages?

Peut-être essayer de l'étendre pour prendre en compte les échanges entre les lignes de métro, et voir comment cela affecte les itinéraires sélectionnés?

Et encore une fois, le code complet de l'article est disponible sur GitHub.