Path Finding in a Maze Using Breadth-First Search (BFS) Algorithm 

Problem Statement

Path finding is a fundamental problem in Artificial Intelligence where an intelligent agent must find a valid path from a starting position to a goal position while avoiding obstacles. In this practical, a maze is represented as a two-dimensional grid, and the Breadth-First Search (BFS) algorithm is implemented using Python to find the shortest path from the Start (S) node to the Goal (G) node. The algorithm explores the maze level by level using a queue and guarantees the shortest path in an unweighted grid.

Go through Jupyter Notebook Path Finding Using BFS

Objective

• To understand the concept of path finding in Artificial Intelligence.
• To represent a maze as a two-dimensional grid using Python.
• To implement the Breadth-First Search (BFS) algorithm for path finding.
• To find the shortest path from the Start (S) node to the Goal (G) node.
• To understand how Queue (FIFO) is used in BFS.
• To analyze the working of BFS through practical implementation.

Maze Representation

A maze is represented as a two-dimensional grid.

Value	Meaning
0	Free path
1	Obstacle or wall
S	Starting position
G	Goal position

Example:

S  0  0  1  0
1  0  1  0  0
0  0  0  0  1
0  1  1  0  0
0  0  0  G  0  

The agent can move:

Up
Down
Left
Right