Path Finding with Heuristic Functions

Step 1: Define the A* Algorithm

This step involves defining the A* algorithm, which finds the shortest path from the start to the goal using a heuristic function. The heuristic function used here is the Manhattan distance. It returns the path from the start to the goal if one is found.

import heapq def a_star(grid, start, goal): def heuristic(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1]) directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] open_list = [] heapq.heappush(open_list, (0, start)) g_score = {start: 0} f_score = {start: heuristic(start, goal)} came_from = {} while open_list: _, current = heapq.heappop(open_list) if current == goal: path = [] while current in came_from: path.append(current) current = came_from[current] path.append(start) path.reverse() return path for direction in directions: neighbor = (current[0] + direction[0], current[1] + direction[1]) if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]) and grid[neighbor[0]][neighbor[1]] == 0: tentative_g_score = g_score[current] + 1 if neighbor not in g_score or tentative_g_score < g_score[neighbor]: came_from[neighbor] = current g_score[neighbor] = tentative_g_score f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal) heapq.heappush(open_list, (f_score[neighbor], neighbor)) return None

This step sets up the A* algorithm by defining the heuristic function, the movement directions, and the data structures for the open list and cost tracking. It returns the path from the start to the goal if one is found.

Step 2: Define the Visualization Function

This step involves defining a function to visualize the path found by the A* algorithm on a grid using matplotlib. The function visualizes the grid and the path found by the A* algorithm. It uses different colors to represent empty cells, obstacles, the path, the start, and the goal.

import matplotlib.pyplot as plt import numpy as np def visualize_path(grid, path, start, goal): grid = np.array(grid) for (x, y) in path: grid[x, y] = 2 # Mark the path grid[start[0], start[1]] = 3 # Mark the start grid[goal[0], goal[1]] = 4 # Mark the goal cmap = plt.cm.get_cmap('Accent', 5) bounds = [0, 1, 2, 3, 4] norm = plt.Normalize(vmin=0, vmax=4) plt.imshow(grid, cmap=cmap, norm=norm) plt.colorbar(ticks=[0, 1, 2, 3, 4], format=plt.FuncFormatter(lambda val, loc: ['Empty', 'Obstacle', 'Path', 'Start', 'Goal'][int(val)])) plt.title("A* Pathfinding Visualization") plt.show()

Step 3: Define the Grid and Start/Goal Positions

This step involves defining a larger grid for the pathfinding problem and specifying the start and goal positions. This step defines a 10×10 grid with some cells marked as obstacles (value 1). The start position is set to the top-left corner (0, 0) and the goal position to the bottom-right corner (9, 9).

grid = [ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0, 1, 1, 1, 0], [0, 0, 0, 0, 1, 0, 1, 0, 0, 0], [0, 1, 0, 0, 1, 0, 1, 0, 1, 0], [0, 1, 0, 0, 0, 0, 1, 0, 1, 0], [0, 1, 1, 1, 1, 1, 1, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 1, 0, 1, 1, 1, 1, 1, 1, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 1, 1, 0] ] start = (0, 0) goal = (9, 9)

Step 4: Run the A* Algorithm and Visualize the Path

The final step runs the A* algorithm on the defined grid and visualizes the path if one is found. If no path is found, it prints a message indicating that no path is available.

path = a_star(grid, start, goal) if path: print("Path found:", path) visualize_path(grid, path, start, goal) else: print("No path found")

Complete Code

Output:

Path found: [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 9), (2, 9), (3, 9), (4, 9), (5, 9), (6, 9), (7, 9), (8, 9), (9, 9)]

Heuristic functions play a critical role in artificial intelligence (AI), particularly in search algorithms used for problem-solving. These functions estimate the cost to reach the goal from a given state, helping to make informed decisions that optimize the search process.

In this article, we will explore what heuristic functions are, their role in search algorithms, various types of heuristic search algorithms, and their applications in AI.