AI is fundamentally motivated by the goal of solving problems of tremendous combinatorial complexity. These issues have been reduced to simple search issues over time.
In a route search issue, the goal is to discover a path from one place to another. There are ample different ways to translate search problems to graphs. In our instance, we'll use nodes to represent all of the potential states and edges to represent all of the possible routes.
As a result, the obvious next question is:
What is an A* Algorithm?
Let's suppose you have to make your way through a massive maze. This maze is so large that navigating it by hand would take a considerable amount of time. You're also expected to complete another maze after completing the first one "by foot."
As a result, we will reduce the maze to a simple search issue and develop a solution that can be used to any other maze we come across, as long as it has the same rules/structure.
To turn any issue into a search problem, we must first establish the following six terms:
- A list of all possible outcomes
- A list of all possible outcomes
- Checking to see whether we've reached the finish line
- A set of possible actions (in this case, different directions of movement)
- A traversal function (a function that will tell us where we'll end up if we go a certain direction)
- Costs for moving from one state to another (which correspond to edges in the graph)
If we can map junctions to nodes (red dots) and potential routes to suitable graph edges, then we can find a solution to the maze problem (blue lines).
Naturally, we define the start and end states as the intersections at which we enter the maze (node A) and want to leave the maze (node B).
Finally, we can talk about how to find a route from one point in the graph to another. BFS, DFS, and Dijkstra would be sufficient in basic situations (such as this one), where the produced graph has a limited number of nodes and edges.
Real-world issues have a much higher combinatorial complexity, thus dealing with a large number of nodes and edges is inevitable. For example, the fact that a Rubik's cube may be in so many different states makes it so difficult to solve. As a result, we'll need to utilize a guided algorithm. In this situation, A*, an intelligent search algorithm emerges.
Using the term "informed search" simply means that the algorithm has access to additional data from the start. As an illustration, consider the case of a search problem algorithm that has no prior knowledge of the environment.
However, a well-informed search problem algorithm might include figuring out the best route from your house to work using your sight (seeing which road gets you closer to your goal) or a map, as an example (knowing exactly how far away every single point is from your destination).
Unlike other graph-traversal algorithms, A* only takes a step if it seems promising and logical based on its functions. It keeps moving in the direction of the objective and ignores any less-than-optimal steps.
Artificially intelligent systems benefit greatly from the usage of A*, particularly in Machine Learning and game creation, since these systems mimic real-world situations.
Graph-traversal algorithms, their uses, and differences are all discussed in-depth on this page.
A* Algorithm Concept
A* is a version of the best-first algorithm that is based on the use of heuristic techniques to attain optimality and completeness.
When a search algorithm has the attribute of optimality, it guarantees that it will discover the optimal solution, in this instance the shortest route to the finish state. When a search algorithm has the attribute of completeness, it implies that it is certain to discover a solution to a given issue.
Each time A* enters a state, it computes the cost of travel, f(n) (n being the adjacent node), and then enters the node with the lowest value of f(n).
The following formula is used to compute these values:
g(n) is the value of the shortest route between the start and end nodes, and h(n) is a heuristic estimate of the value of the node.
To rebuild any route, we must associate each node with the relative with the optimum f(n) value. This also implies that when we review certain nodes, we must additionally update their most optimum relatives.
A*' algorithm efficiency is largely reliant on the heuristic value h(n), and depending on the kind of issue, a different heuristic function may be required to discover the optimum solution.
Developing such capabilities is not a simple job and is one of the basic challenges of artificial intelligence. Admissibility and consistency are the two basic characteristics that a heuristic function may have.
Admissibility and Consistency
A heuristic function h(n) is acceptable if it never exceeds the true distance between n and the target node.
As a result, the following formula holds true for any node n:
The actual distance between n and the target node is denoted by h*(n). However, if the function overestimates the actual distance but never by more than d, we may confidently conclude that the solution produced by the function is accurate to d (i.e. it does not overstate the shortest route between points A and B by more than d).
A given heuristic function h(n) is consistent if the estimated distance between the target n and any given neighbour is always less than or equal to the expected cost of reaching that neighbour:
The distance between nodes n and m is denoted by c(n,m). Furthermore, if h(n) is constant, we know the optimum route to every node that has been examined before. This indicates that this function performs optimally.
Implementation
This is an implementation of A* on a graph structure in its entirety. To keep things simple and concise, the heuristic function is specified as 1 for all nodes.
The graph is represented using an adjacency list, in which the keys correspond to the graph's nodes and the values to a list of edges that connect the nodes.
This section contains a Python implementation of the A* algorithm:
Consider the following weighted graph as an illustration:
We execute the code as follows:
And the output would be as follows:
As a result, the optimum route from A to D, as determined by A*, is A->B->D.
Conclusion
A* is a very strong algorithm with almost limitless potential. It is, however, only as good as its heuristic function, which may vary significantly depending on the nature of the issue.
It has found uses in a wide variety of software systems, ranging from machine learning and search optimization to game creation, where non-player characters must traverse complicated terrain and obstacles in order to reach the player.
