Build search-based pathfinding agents using Breadth-First Search (BFS) and A* search on grid systems, configure heuristics, and compare execution efficiencies inside a VM.
The diagram below displays the node expansion comparison between Breadth-First Search (BFS) and A* Search. BFS explores in concentric waves (exploring many nodes), whereas A* uses a Manhattan distance heuristic to guide the path directly toward the goal node, expanding fewer states.
2. Part 1: Step-by-Step Action Items & Key Execution Steps
STEP 1
Activate Python Virtual Environment
Point the terminal execution environment to the course conda sandbox environment.
$ conda activate ds_ai_ml
This targets execution to the active python virtual packages directory.
STEP 2
Create Project Folders inside Linux VM
Create a dedicated folder for the project files inside your guest VM home folder directory.
$ mkdir -p ~/Projects/classical_ai && cd ~/Projects/classical_ai
This sets up the working directory layout for the search code.
STEP 3
Create pathfinder script file in VS Code
Launch VS Code and create a new script file inside the project workspace folder.
Launch VS Code via terminal "code ." -> Right-click in explorer tree -> click New File -> Type: warehouse_agent.py -> Press Enter
This registers an empty file `warehouse_agent.py` inside the active editor workspace.
STEP 4
Load Pathfinder calculations logic
Paste the grid representations, BFS search, and A* search code blocks into the empty file.
Click warehouse_agent.py -> Paste python code from Part 2 below -> Save file via Ctrl + S
This populates the file with grid and queue mapping code.
STEP 5
Execute pathfinding search script
Run the validation script using the python engine to compare search algorithms.
$ python warehouse_agent.py
This compiles grid arrays, runs BFS and A* search loops, and prints comparative path node maps to the console screen.
3. Operational Pipeline Architecture
The flowchart below outlines the agent pathfinding pipeline. It details grid definitions, starting search loops, computing heuristics, comparing execution steps, and printing grid visual maps.
4. Part 2: Complete Deliverable Assets & Production Templates
To implement the pathfinding logic, we will write a Python script that defines a warehouse grid, runs BFS and A* search loops, and prints a comparison of the results. Below is a line-by-line explanation of the code, followed by the combined script.
Step-by-Step Code Construction
Lines 1 - 4
Import Priority Queue libraries
Include system collections and priority queue APIs in the script.
from queue import Queue, PriorityQueue
import numpy as np
These imports pull standard queue models and NumPy array structures for managing path coordinates.
Lines 5 - 12
Define Manhattan distance Heuristic
Write calculations estimating coordinate paths to the target goal node.
def heuristic(a, b):
# Manhattan distance on 2D grid systems
return abs(a[0] - b[0]) + abs(a[1] - b[1])
This calculates Manhattan distance, giving the A* optimizer search cost estimations to guide pathfinding.
Lines 13 - 35
Implement Breadth-First Search (BFS)
Write standard BFS routing logic using FIFO queues to expand nodes in waves.
frontier = Queue()
frontier.put(start)
came_from = {start: None}
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next_node in get_neighbors(current):
if next_node not in came_from:
frontier.put(next_node)
came_from[next_node] = current
This uses a FIFO queue to check neighboring cells level-by-level, returning the shortest path by checking all options equally.
Lines 36 - 55
Implement A* Search
Write A* routing logic using priority queues to evaluate nodes by cost and heuristic score.
frontier = PriorityQueue()
frontier.put((0, start))
came_from = {start: None}
cost_so_far = {start: 0}
while not frontier.empty():
_, current = frontier.get()
if current == goal:
break
for next_node in get_neighbors(current):
new_cost = cost_so_far[current] + 1
if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
cost_so_far[next_node] = new_cost
priority = new_cost + heuristic(next_node, goal)
frontier.put((priority, next_node))
came_from[next_node] = current
This uses a priority queue to sort expanded paths by actual path cost plus heuristic estimate, optimizing the search path.
Combined Classical AI Diagnostic Script
Save the consolidated blocks above as ~/Projects/classical_ai/warehouse_agent.py and execute it inside the active ds_ai_ml environment:
# warehouse_agent.py - BFS and A* Search comparisons on warehouse gridsfrom queue import Queue, PriorityQueue
classWarehouseGrid:
def__init__(self, width, height, obstacles):
self.width = width
self.height = height
self.obstacles = obstacles
defin_bounds(self, id):
(x, y) = id
return 0 <= x < self.width and 0 <= y < self.height
defpassable(self, id):
return id not in self.obstacles
defneighbors(self, id):
(x, y) = id
results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1)]
results = filter(self.in_bounds, results)
results = filter(self.passable, results)
return list(results)
defheuristic(a, b):
(x1, y1) = a
(x2, y2) = b
return abs(x1 - x2) + abs(y1 - y2)
defbfs_search(grid, start, goal):
frontier = Queue()
frontier.put(start)
came_from = {start: None}
nodes_expanded = 0
while not frontier.empty():
current = frontier.get()
nodes_expanded += 1
if current == goal:
breakfor next_node in grid.neighbors(current):
if next_node not in came_from:
frontier.put(next_node)
came_from[next_node] = current
return came_from, nodes_expanded
defa_star_search(grid, start, goal):
frontier = PriorityQueue()
frontier.put((0, start))
came_from = {start: None}
cost_so_far = {start: 0}
nodes_expanded = 0
while not frontier.empty():
_, current = frontier.get()
nodes_expanded += 1
if current == goal:
breakfor next_node in grid.neighbors(current):
new_cost = cost_so_far[current] + 1
if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
cost_so_far[next_node] = new_cost
priority = new_cost + heuristic(next_node, goal)
frontier.put((priority, next_node))
came_from[next_node] = current
return came_from, nodes_expanded, cost_so_far
defreconstruct_path(came_from, start, goal):
current = goal
path = []
while current != start:
path.append(current)
current = came_from.get(current)
if current is None:
return []
path.append(start)
path.reverse()
return path
defdraw_grid(grid, path, start, goal):
for y in range(grid.height):
row_str = ""for x in range(grid.width):
cell = (x, y)
if cell == start:
row_str += " S "elif cell == goal:
row_str += " G "elif cell in grid.obstacles:
row_str += "###"elif cell in path:
row_str += " * "else:
row_str += " . "
print(row_str)
defmain():
print("=== Classical AI Pathfinding Simulation ===")
# Define 10x10 grid with custom obstacle locations
obstacles = [(3, 2), (3, 3), (3, 4), (4, 4), (5, 4), (6, 4), (6, 5), (6, 6)]
grid = WarehouseGrid(10, 10, obstacles)
start = (1, 1)
goal = (8, 8)
# 1. Run BFS
came_from_bfs, expanded_bfs = bfs_search(grid, start, goal)
path_bfs = reconstruct_path(came_from_bfs, start, goal)
# 2. Run A*
came_from_astar, expanded_astar, _ = a_star_search(grid, start, goal)
path_astar = reconstruct_path(came_from_astar, start, goal)
# Outputs comparison logs
print("\n[BFS Search Results]")
print(f" - Path Length: {len(path_bfs) - 1} steps")
print(f" - Expanded Nodes: {expanded_bfs} states")
draw_grid(grid, path_bfs, start, goal)
print("\n[A* Search Results]")
print(f" - Path Length: {len(path_astar) - 1} steps")
print(f" - Expanded Nodes: {expanded_astar} states")
draw_grid(grid, path_astar, start, goal)
print("\n=== AI Agent Search Benchmarks Completed! ===")
if __name__ == "__main__":
main()
5. Deliverables Summary
Verify that the following configurations and outputs exist inside your project workspace.