Path Planning Algorithm in Python

Intelligence is the human species’ strength, and scientists have exploited it to better people’s lives. Artificial intelligence was then invented to augment human intelligence and build and thrive civilizations like never before. AI assists the user in solving challenges of varying complexity. AI can be used to address computational difficulties such as path search problems. Problems require the user to determine a path from one location to another, such as points A to B. Sometimes, the user must map problems to graphs, where nodes represent all possible outcomes.

Assume the user is required to navigate a massive maze. This maze is so large that manually locating the objective would take hours. Furthermore, once the user completes the maze “by foot,” it is supposed to move on to the next one.

Converting any problem into a search problem necessitates six steps:

A collection of all possible states in which the user could end up.
The initial and final states.
The last check (a way to check if the user is at the finished state).
A series of potential acts (in this case, different directions of movement).
A function for traversing (a position that may affect the user where it may end up.)
A series of state-to-state transportation charges. (which correspond to edges in the graph).

A* Algorithm

A* is a variation of the best-first algorithm that uses heuristic methods to attain optimality and completeness.

When a search algorithm has the assets of optimality, it guarantees that it may locate the best feasible solution, the shortest path to the finish state.

When A* enters a state, it calculates the cost, f(n) (n being the surrounding node), of traveling to all of the neighboring nodes and then enters the node with the lowest f value (n).

The following formula is used to calculate these values:

f(n) =g(n) + h(n)

Complete Induction

The number of nodes between node n and the finish node s on the shortest path between the two may be the induction parameter N.

Base N=0

If there are no nodes amid n and s, and h(n) is consistent, the user may use the following equation:

c(n,s)+h(s)≥h(n)

h*(n)=c(n,s)

It can be deduced that,

h∗(n)≥h(n)

In N = k nodes on the closest path from n to s, the user investigates the finish node n’s first successor (node m). Because we know there is a path from m to n and has k-1 nodes, the following equation is correct.

h∗(n)=c(n,m)+h∗(m)≥c(n,m)+h(m)≥h(n)

Implementation

It is a graph-structured direct implementation of A*. For the sake of easiness and brevity, the heuristic function is set to 1 for all nodes.

An adjacency list is used to denote the graph, with the keys representing graph nodes and the values being a list of edges with the corresponding surrounding nodes.

from collections import deque

class Graph:
    # example of adjacency list (or rather map)
    # adjacency_list = {
    # 'A': [('B', 1), ('C', 3), ('D', 7)],
    # 'B': [('D', 5)],
    # 'C': [('D', 12)]
    # }

    def __init__(self, adjacency_list):
        self.adjacency_list = adjacency_list

    def get_neighbors(self, v):
        return self.adjacency_list[v]

    # heuristic function with equal values for all nodes
    def h(self, n):
        H = {
            'A': 1,
            'B': 1,
            'C': 1,
            'D': 1
        }

        return H[n]

    def a_star_algorithm(self, start_node, stop_node):
        # open_list is a list of nodes which have been visited, but who's neighbors
        # haven't all been inspected, starts off with the start node
        # closed_list is a list of nodes which have been visited
        # and who's neighbors have been inspected
        open_list = set([start_node])
        closed_list = set([])

        # g contains current distances from start_node to all other nodes
        # the default value (if it's not found in the map) is +infinity
        g = {}

        g[start_node] = 0

        # parents contains an adjacency map of all nodes
        parents = {}
        parents[start_node] = start_node

As the code runs;

adjacency_list = {
    'A': [('B', 1), ('C', 3), ('D', 7)],
    'B': [('D', 5)],
    'C': [('D', 12)]
}

Output

Path found: ['A', 'B', 'D']
['A', 'B', 'D']

As a result, the best path from A to D, as determined by A*, is A->B->D.

Other useful articles: