Practical Implementations of BFS in Pathfinding of Robots
Consider the below example, depicting the scenario where a robot seeks to navigate to its goal. Initially, the robot expands its successors that evaluate the possible moves to progress towards its destination. It is essential to note the presence of obstacles that may impede the robot’s path as it traverses through the nodes. Let’s now understand the concept of pathfinding stepwise.
Step 1: Create a Node a class for the search tree
The Node class represents a node in a search tree that contains the states or grid coordinates of the robots.
class Node:
def __init__(self, state, parent=None, action=None):
self.state = state
self.parent = parent
self.action = action
Step 2: Create a class for GridProblem and Node
The GridProblem class represents the problem of pathfinding on a grid. It contains attributes for the initial state, goal state, and obstacles on the grid. The three typical methods are fitted in the code such as
- is_goal – This method checks if the given state is the goal state.
- is_valid_cell – This functions checks that a cell is valid to move or obstacles
- expand – This method is in charge of generating child nodes (states) from the given parent node by considering obstacles and grid boundaries.
from collections import deque
class GridProblem:
def __init__(self, initial_state, goal_state, grid):
self.initial_state = initial_state
self.goal_state = goal_state
self.grid = grid
def is_goal(self, state):
return state == self.goal_state
def is_valid_cell(self, row, col):
return 0 <= row < len(self.grid) and 0 <= col < len(self.grid[0]) and self.grid[col][row] == 0
def expand(self, node):
row, col = node.state
children = []
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
new_row, new_col = row + dr, col + dc
if self.is_valid_cell(new_row, new_col):
child_state = (new_row, new_col)
child_node = Node(child_state, parent=node)
children.append(child_node)
return children
Step 3: Function to reconstruct the Solutions path
Define the function to reconstruct the solution path and print the path
def reconstruct_path(node):
path = []
while node:
path.append(node.state)
node = node.parent
return list(reversed(path))
# Function to print the complete path
def print_complete_path(path):
for step, point in enumerate(path):
print("Step {}: {}".format(step, point))
Step 4: Define the Traversal Algorithms
This the most important parts of the solutions. We we use the same breadth_first_search algorithm function which is defined above.
Complete Implementations of BFS in Pathfinding of Robots
In this example, we initialize the initial state such as (0,0) and goal state as (0,6) and obstacles on the grid. It creates a GridProblem instance with these parameters and when it calls the BREATH_FIRST_SEARCH function it finds the solution for the problem instance. If it can’t find the solution for the problem instance it returns No solution found.
Grid with Obstacles
Robot (0,0) | Block | (2,0) | (3,0) | Block | (5,0) | Goal |
(0,1) | Block | (2,1) | (3,1) | Block | (5,1) | (6,1) |
(0,2) | (1,2) | (2,2) | (3,2) | Block | (5,2) | (6,2) |
(0,3) | (1,3) | Block | (3,4) | Block | (5,3) | (6,3) |
(0,4) | (1,4) | Block | (3,5) | (4,4) | (5,4) | (6,4) |
(0,5) | (1,5) | Block | (3,6) | (4,5) | (5,5) | (6,5) |
(0,6) | (1,6) | Block | (3,6) | (4,6) | (5,6) | (6,6) |
Complete code
from collections import deque
class GridProblem:
def __init__(self, initial_state, goal_state, grid):
# Initializes a grid problem instance with initial and goal states, and the grid layout
self.initial_state = initial_state
self.goal_state = goal_state
self.grid = grid
def is_goal(self, state):
# Checks if the given state is the goal state
return state == self.goal_state
def is_valid_cell(self, row, col):
# Checks if the given cell coordinates are within the grid boundaries and not blocked
return 0 <= row < len(self.grid) and 0 <= col < len(self.grid[0]) and self.grid[col][row] == 0
def expand(self, node):
# Expands the given node by generating child nodes for valid adjacent cells
row, col = node.state
children = []
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
new_row, new_col = row + dr, col + dc
if self.is_valid_cell(new_row, new_col):
child_state = (new_row, new_col)
child_node = Node(child_state, parent=node)
children.append(child_node)
return children
class Node:
def __init__(self, state, parent=None, action=None):
# Initializes a node with a state, parent node (optional), and action (optional)
self.state = state
self.parent = parent
self.action = action
def breadth_first_search(problem):
# Performs breadth-first search algorithm to find a solution for the given problem
node = Node(problem.initial_state)
if problem.is_goal(node.state):
return node
frontier = deque([node])
reached = {problem.initial_state}
while frontier:
node = frontier.popleft()
for child in problem.expand(node):
state = child.state
if problem.is_goal(state):
return child
if state not in reached:
reached.add(state)
frontier.append(child)
return None
def reconstruct_path(node):
# Reconstructs the path from the goal node back to the initial node
path = []
while node:
path.append(node.state)
node = node.parent
return list(reversed(path))
def print_complete_path(path):
# Prints the complete path from start to goal
if path:
for step, point in enumerate(path):
print("Step {}: {}".format(step, point))
else:
print("No solution found")
# Example usage and grid definition
"""
1 : Denotes the obstacles
0 : Empty space or a non-obstacle cell in the grid
"""
grid = [
[0, 1, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0]
]
# Define initial and goal states
initial_state = (0, 0)
goal_state = (6, 0)
# Define the problem instance
problem = GridProblem(initial_state, goal_state, grid)
# Perform breadth-first search to find a solution
solution_node = breadth_first_search(problem)
# Print solution if found
print('!! Reached the Goal!!' if solution_node else None)
if solution_node:
print("Solution found!")
solution_path = reconstruct_path(solution_node)
print("Complete Path:")
print_complete_path(solution_path)
else:
print("No solution found")
Output:
!! Reached the Goal!!
Solution found!
Complete Path:
Step 0: (0, 0)
Step 1: (0, 1)
Step 2: (0, 2)
Step 3: (1, 2)
Step 4: (2, 2)
Step 5: (3, 2)
Step 6: (3, 3)
Step 7: (3, 4)
Step 8: (4, 4)
Step 9: (5, 4)
Step 10: (6, 4)
Step 11: (6, 3)
Step 12: (6, 2)
Step 13: (6, 1)
Step 14: (6, 0)
Output explanation
- We first start at the initial position (0,0), it is where the robot begins its exploration.
- The robot moves south along below row such as (0,1), and (0,2).
- Now, the robot moves east along the column to the position of (1,2).
- The robot follows a path to the east (2,2), and (3,2), then south (3,3), and again (3,4).
- Again, the robot moves east to towards (4,4), (5,4) and (6,4).
- Now the robot moves towards the North along row from (6,4) to (6,3),(6,2),(6,1) and (6,0).
- Finally, the robot reaches the goal node i.e (6,0).
The output indicates that the Breadth_First_Search algorithm successfully found a solution to the pathfinding problem. In this case, the goal state is (6,0) that represents the destination that the robot needs to reachPractical use cases in AI.
Breadth First Search (BFS) for Artificial Intelligence
In artificial intelligence, the Breadth-First Search (BFS) algorithm is an essential tool for exploring and navigating various problem spaces. By systematically traversing graph or tree structures, BFS solves tasks such as pathfinding, network routing, and puzzle solving. This article probes into the core concepts of BFS, its algorithms, and practical applications in AI.
Table of Content
- What is Breadth-First Search?
- Key characteristics of BFS
- Breadth First Search (BFS) Algorithms
- How Breadth-First Search can help in Robot Pathfinding
- Practical Implementations of BFS in Pathfinding of Robots
- Conclusion
- FAQs on Breadth First Search (BFS) for Artificial Intelligence