Path Finding in a Maze Using the A Search Algorithm

Problem Statement

Pathfinding is an important Artificial Intelligence problem in which an agent must find the shortest path from a starting position to a goal position while avoiding obstacles.

In this practical, the A* Search Algorithm is implemented using Python to solve a pathfinding problem in a two-dimensional maze. A* selects the most promising cell by considering both:

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

where:

• $g(n)$ = actual cost from the start cell to the current cell
• $h(n)$ = estimated distance from the current cell to the goal
• $f(n)$ = estimated total cost of the path  

Go through Jupyter Notebook

Short Introduction

A* is an informed search algorithm because it uses additional information called a heuristic to guide the search toward the goal.

Unlike BFS, which explores cells level by level, A* prioritizes cells that appear closer to the destination. Therefore, it generally explores fewer cells and reaches the goal more efficiently.

Maze Representation

Symbol/Value	Meaning
0	Free cell
1	Obstacle or wall
S	Starting position
G	Goal position

The agent can move:

• Up
• Down
• Left
• Right

Diagonal movement is not allowed.