Overview:
Path-finding algorithms provide agents with the ability to find the shortest path between any two points in the environment. Path-finding requires agents to have knowledge of the environment, which includes the coordinates of accessible points on the map and possible routes between those points. This information can be represented as a navigation graph by considering graph nodes as specific locations on the map and the graph edges as the routes between them. The graph search algorithms can then be used to find the shortest path between the nodes.
Path-finding is crucial for navigating efficiently in a virtual environment. Since the navigable areas are represented using graph nodes and edges, the graph search algorithms are applicable and very useful in this case. There are many different search algorithms available.
This article discusses some of the graph theories and graph search algorithms, including Depth First Search (DFS), Breadth-First Search (BFS), Dijkstra’s and A* Algorithms and discusses which of these are best suited for agent navigation.
Graph Theory Concepts
A graph is a mathematical abstraction used to represent a set of objects in which some object pairs are linked together to show a relationship [1]. These objects are referred to as vertices or nodes and the connection between them is referred to as edges or lines. The edges can be directional or non-directional. A directed graph consisting of directional edges and five nodes is shown in the Figure below:
When two nodes are connected through an edge, they are referred to as adjacent nodes. An edge could also exist from one node to itself, which is referred to as a loop.
When the linked nodes of a graph form a hierarchical structure with parent and children nodes, the graph is referred to as a tree. Child nodes are the unexplored branches of a parent node. A node that does not have any children is referred to as a leaf node.
The number of edges and nodes in this thesis are indicated by the letters E and N respectively. In a weighted graph, the edges are assigned a number that is referred to as the weight or cost. Depending on the problem the weight could represent various quantities including length, time, and cost.
Based on the ratio of edges to nodes a graph can be either sparse or dense. Although there is no strict distinction between the two, a sparse graph has relatively few edges per node compared to a dense graph that has many. The number of edges in a dense graph is close to the maximal number of edges, which equals N 2 considering all the loop edges. Whenever possible the sparse graphs are preferred because they reduce complexity and uses less Central Processing Unit (CPU) power and memory.
Methods of Representing a Graph
A graph shows which vertices are adjacent to other vertices. There are two main methods for building and representing the data structure of a graph. These methods include using an adjacency matrix and an adjacency list [2].
Adjacency Matrix Representation of a Graph
The adjacency matrix is an n × n matrix where n is the number of graph vertices. The matrix shows whether there is a connection between any pair of nodes in the graph. Figure 2(a) shows an adjacent matrix that represents the graph of Figure 1. The ‘1’ value indicates that a connection exists from the node shown at the start of the row to the node at the start of the column. For instance, the ‘1’ value in the shaded cell (second row and fourth column) indicates that there is a connection from node B to node D. The ‘0’ value indicates that no connection exists between the corresponding nodes.
The advantage of using an adjacency matrix is that it is faster to find the connection and weight between two nodes. In some cases, it is preferable to use this representation, specially if the graph size is small. The disadvantage is that for graphs with a large number of vertices a large data structure is created, which takes up more memory and uses more CPU. The reason is that in this method many unnecessary values are stored for the null connections. The amount of space required for storing a graph using this method is proportional to N 2.
Adjacency List Representation of a Graph
The adjacency list represents all edges of a graph in a list. Figure 2(b) shows the representation of the graph in Figure 1 using the adjacency list method. The adjacency list only stores a linked list of adjacent edges for graph nodes and does not store the edges that do not exist. As a result, this representation is more compact and memory efficient. The amount of space required for storing a graph using this method is proportional to E + N . For this research the adjacency list is preferred because the particular graph generated to represent the map would consist of many vertices.
A navigation graph is a map of the environment that can be used by a robot or other agent to plan paths from one location to another. The graph is typically represented as a network of nodes and edges, with each node corresponding to a particular location and each edge corresponding to a possible path between two locations. The navigation graph can be used to find the shortest path between two locations or to plan a path that avoids obstacles or other hazards.
Consider a simulation environment that is made up of a grid of cells as shown below. Each cell represents a small area on the map that the agents are able to visit. Consider each graph node as the centre of a cell in the grid and the path between every two points is represented by a graph edge.
Each node represents the centre of an accessible cell in the environment. As a result, the nodes are formed in a grid-based structure. The edge between a pair of nodes represents a possible path between them. Most nodes are surrounded by eight other nodes except the nodes placed at the corners and borders of the map. Since this graph has relatively few edges per node, the graph is considered to be sparse.
Each edge of the graph is assigned a weight, which is calculated based on the Euclidean distance between the nodes. In a two-dimensional plane the Euclidean distance between two points P1(x1, y1) and P2(x2, y2) is calculated through the Pythagorean Equation:
distance = sqr[ (x1 − x2)2 + (y1 − y2)2 ]
In a big map where the number of cells and nodes is very large, the searching procedure can become very costly. To simplify the navigation graph only the nodes and edges that are essential to the search are included. These nodes would only represent the nodes that can be accessed by the agent and are navigable.
The movement of the agent is not restricted to the graph nodes and edges. The agents use the navigation graph as a guide to move in the environment and reach certain points on the map along the most efficient path.
Depth-First Search Algorithm
The Depth First Search (DFS) algorithm moves forward from a source node through the nodes of a branch as deep as possible until it reaches a node with no other unexplored branches. Then it backtracks to the previous node and searches its other unvisited branches [2].
This process continues until the entire graph has been searched or the target node is found. If the graph is unconnected then the algorithm is expanded to include a source node for each sub-graph. The above figure demonstrates the order in which the Depth First Search algorithm searches the nodes.
The figure below shows the path found between the source node (A) and target node (B) in a navigation graph using Depth First Search. The coloured nodes and edges are visited by the algorithm. The numbers written on the nodes indicate the order in which they have been visited.
The disadvantage of the Depth First Search Algorithm
When the graph is very deep the Depth First Search can easily become delayed by going too far down the wrong path. This can be prevented by using the Depth-limited search, which is very similar to Depth First Search except that it defines a maximum depth limit for the search [3]. However, deciding the right limit for the maximum search depth is hard and sometimes impossible. Although the Depth First Search guarantees to find the target node in the graph assuming at least one exists, it does not guarantee to find the best route to the target and does not take the cost of edges into account.
Breadth-First Search Algorithm
The Breadth-First Search (BFS) starts from the source node and searches all its ad- jacent nodes that are one edge away from the source. Then the algorithm searches all the nodes that are two edges away from the source. This number is incremented in each cycle to go deeper and search nodes further away from the source node. This process continues until the target is found or all the nodes are visited [2]. The figure below demonstrates the order in which this algorithm searches the nodes.
This search can be done faster by using a Bidirectional search, which runs two instances of the Breadth-First Search simultaneously from the source and the target and stops the search when these search instances meet at one node along the path [3].
If all edges of the graph are equal in length, the Breadth-First Search guarantees to find the shortest path to the target given enough time. The Figure below shows the steps this algorithm takes to find the path from source (A) to target (B) in a navigation graph. The numbers on the nodes indicate the order in which they have been visited by the algorithm. The dashed lines indicate each level of deepness in the graph branches. The black bold lines are all the edges that have been visited and the red bold line indicates the path found. The algorithm is ceased when it reaches the target node (B). In this example, it is assumed that all edges have approximately the same size, but the length of the edges is not the same.
The disadvantage of the Breadth-First Search Algorithm
Breadth-First Search is not optimal for weighted graphs [4]. The algorithm performs poorly in environments where the branching factor of the graph is large, which indicates each node has a large number of child nodes. Also, when multiple concurrent instances of searching are required this method is not efficient.
Dijkstra’s Shortest Path Algorithm
Dijkstra’s algorithm finds the shortest path (with the minimum cost) between a source node to every other node in a weighted graph [5, 6]. The graph must have non-negative edge costs for the algorithm to work. The algorithm can be stopped once the shortest path from the source node to the target node is determined, or else continued to find the shortest path to all the nodes of the graph.
In order to illustrate the procedure of the Dijkstra’s Algorithm a simple graph is considered, as shown in the Figure above. The following procedure describes the steps this algorithm goes through to find the shortest path from the source node (A) to the target node (B) of this graph.
- Firstly, all the nodes are marked as unvisited and the source node (A) is considered as the current node.
- A distance value is assigned to each node, which indicates the distance of the node from (A). At the start, the distance value is set to ‘0’ for (A) and to infinity for all the other nodes.
- The algorithm considers all the unvisited adjacent nodes to the current node and calculates their preliminary distance to (A). For each unvisited node adjacent to the current node, the preliminary distance is calculated by adding the cost of the edge between these nodes with the distance value of the current node (as shown in Figure 9). If the newly calculated distance is less than the previously stored distance, it is considered the new distance value for this adjacent node.
- When all the adjacent nodes of the current node are checked, it is marked as visited. The visited nodes are in green and the current node is in grey (as shown in Figure 10). The visited nodes are not checked again and their distance is considered the minimal distance to (A).
- If the target has not been reached or all the nodes have not yet been visited, the algorithm moves to an unvisited node with the lowest distance value and considers it the current node. In other words, the closest node to the source is selected and is set as the current node. Then the same procedures from step 3 are repeated for the current node until the target node (B) is found or all nodes have been visited (as demonstrated in Figure 10).
Figure 10 illustrates the rest of Dijkstra’s algorithm process for the graph in Figure 8 until all the nodes are visited (follow from left to right and top to bottom). When the search concludes, the shortest path from the source node to all the other nodes is found. Dijkstra’s algorithm is one of the most efficient graph search algorithms in weighted graphs with non-negative edge costs. Although this algorithm is faster than most of the other algorithms for graph traversal, it still examines a lot of edges.
The Figure below illustrates how the shortest path is found in a navigation graph using this algorithm. It is assumed that the horizontal and vertical edges have a cost of ‘1’ and the diagonal edges have a cost of ‘1.4’, which is the approximate Euclidean distance between the nodes. The numbers on the nodes indicate their distance value from the source (A). The algorithm is ceased when the shortest path is found, which is indicated in red bold colour.
Finding the shortest path in a navigation graph can be optimised significantly using the A* Algorithm.
A* Shortest Path Algorithm
The A* algorithm is an extension of Dijkstra’s algorithm, which takes a heuristic value into account for selecting the nodes in the process of finding the shortest path [7]. Different heuristic values can be used depending on the type of graph and the application. For example, in navigation graphs with tile-based topology, where movements are restricted to vertical and horizontal movements of equal length, the Manhattan distance can be considered as the heuristic value [4]. This value is the distance between the source and target points measured along vertical and horizontal axes. In other words, this distance would be equal to the number of tiles that needs to be passed from the source to the target tile.
In a navigation graph where spatial information is available the Euclidean (straight-line) distance between source and target nodes is used as the heuristic value. In other words, the heuristic value is an estimate of the distance between source and target nodes. In the A* algorithm, the heuristic value is considered when calculating the preliminary distance of an unvisited node adjacent to the current node as explained in step 3 of Dijkstra’s algorithm. Therefore, A* calculates the preliminary distance by adding the cost of the edge between these nodes to the distance value of the current node and the heuristic value. As a result, fewer edges need to be examined and the algorithm converges more quickly to the best path.
As shown in Figure 12 the A* algorithm finds the shortest path from source (A) to target (B) more efficient than the previously discussed algorithms. The yellow circles indicate the nodes visited along the shortest path, and the green circles indicate other visited nodes. The small number written at the top right of nodes is the Euclidean distance of that node from the target node (B).
Figure 13 shows an agent in the developed simulated environment, which is using the A* algorithm in order to find the path from its base location to a resource item. Compared with other path-finding algorithms the A* algorithm is the most efficient algorithm to find the shortest path between two nodes in a weighted graph (with positive edge costs). However, in the case where there are multiple resources available, Dijkstra’s algorithm has proved to be more efficient for finding the closest resource.
Both A* and Dijkstra’s algorithms are used depending on the situation and actions required. For instance, in the case of a resource-gathering simulation when an agent collects an item at a specific location or needs to travel between two specific points, the A* algorithm is best used to find the shortest path. On the other hand, when the agent needs to find the closest item to navigate to and collect then Dijkstra’s algorithm is best to be used. That is because when the virtual world contains multiple resources of the same type spread throughout the environment, by using Dijkstra’s algorithm, only one instance of the searching algorithm would be enough to find the closest item from all the available items.
Path Smoothing Algorithm
A twist to the A* algorithm would make the movement of agents smoother. A path-smoothing algorithm [4] is implemented in order to remove unnecessary edges from the path and therefore avoid the zigzag movements as shown in Figure 13. This algorithm checks the adjacent edges of the path and replaces them with one edge from the source of the first adjacent edge to the destination of the second adjacent edge if there is a possible direct link between them. It repeats this until all the adjacent edges are examined. The result creates a smoother and more efficient path as shown in Figure 14.
Since the navigation graph in this project is a sparse graph and has many nodes with a small ratio of edges to nodes, the adjacency list is the most efficient for representing the graph. Figure 15 shows the UML class diagram of the navigation graph.
The graph node is created using the (GraphNode) class, which encapsulates the following parameters:
- The index is a unique identifier.
- The position is a Vector3d representing the position of the node on the map.
- The extraInfo parameter stores information about the items near this graph node.
The graph edge is represented with the GraphEdge class, which encapsulates the following parameters:
- The fromNodeIndex parameter is the index of the source node that the edge is coming from.
- The toNodeIndex parameter is the index of the destination node that the edge is connected to.
- The cost parameter is the Euclidean distance of the nodes that which this edge is linked to.
- The type parameter represents the terrain of the path between the nodes.
Other than showing the connection and the distance between two nodes, the edge holds information regarding the terrain of the path that it is representing. The terrain might be of different types such as smooth road, bumpy surface, lake or hill. The type of terrain can influence the way an agent moves and its speed. For example, it would take longer for the agent to climb up the hill or swim through the lake compared to taking the road. These factors can be taken into consideration to find the most efficient path for an agent.
The NavigationGraph class creates a navigation graph that represents the navigable parts of the simulated world. This class holds all the nodes and edges of the graph. The load method is passed with a stream of data containing information about the nodes and edges to be added. This class also has methods for adding and removing graph nodes and edges at the runtime. When adding new nodes the addNode() method checks to ensure the node is not already present in the graph. Every node is given a unique index to be identified later. The addEdge() method adds the edge that is passed as its parameter to the graph after checking that it is unique. If the graph is directed, then a similar edge, pointing in the opposite direction is also added between the nodes. The class also has ‘accessors’ and ‘mutator’ methods to get access to specific nodes and edges and modify them.
Conclusion
This article discussed some graph theories and search algorithms for enabling agents with path-finding capabilities. The environment of agents in this project was mapped out and represented as a navigation graph for these techniques to work. In such a graph, the nodes are considered the accessible areas on the map and the graph edges are the routes between the nodes. An adjacency list is used to store a linked list of adjacent edges. This method is more compact and memory-efficient for the scenario of this research, compared with the adjacency matrix method.
Several search algorithms have been investigated to enable agents with path-finding capabilities. Some of these algorithms were discussed, including Depth-First Search, Breadth-First Search, Dijkstra’s and A* algorithms. Depth-First Search and Breadth-First Search algorithms are graph search algorithms that do not take edge costs into consideration. Depth-First Search guarantees finding the target node but the process is not time-efficient and the path may not be the best one. Breadth-First Search guarantees to find the best path (assuming the edges have equal cost), but it is not efficient as it searches for many unnecessary edges.
The Dijkstra’s and A* algorithms are among the most efficient ways for path-finding in a graph with non-negative edge costs. Dijkstra’s algorithm finds the shortest path from a source node to every other node. The A* algorithm is based on Dijkstra’s algorithm and considers a heuristic value to improve its efficiency. The heuristic value, in this case, is the Euclidean (straight-line) distance between the source and target nodes. The A* algorithm examines fewer edges compared to the other search algorithms and finds the shortest path more quickly. Both A* and Dijkstra’s algorithms are used to find the shortest path depending on the scenario.
The agent decides which algorithm to choose based on its state and goals. If the agent plans to move to a specific point on the map the A* has proved to be the most efficient. If the goal is to find the closest resource item from among a number of available items on the map, then using Dijkstra’s algorithm has better efficiency. Further information on how agents decide to use these algorithms to perform the resource-gathering task is provided in the implementation parts of this article.
References:
- J. L. Gross and J. Yellen. Handbook of Graph Theory. CRC Press, 2004.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press and McGraw-Hill, 2nd edition, 2001.
- S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall, Pearson Education, Inc., Upper Saddle River, NJ, USA, 2nd edition, 2003.
- M. Buckland. Programming Game AI by Example. Wordware Publishing, Inc., Plano, Texas, USA, 2005.
- R. Bhandari. Survivable Networks: Algorithms for Diverse Routing. Springer, 1999.
- E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, Springer Berlin, Heidelberg, Germany, 1:269–271, 1959.
- P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics SSC4, 4(2):100–107, July 1968.
Pingback: A Brief History of Artificial Intelligence - Brainy Loop