DFS Implementation in Robotics Pathfinding
DFS can be used to find a path from a start node to a goal node in a maze or grid-based environment. The DFS algorithm systematically explores all possible paths from the start node, one branch at a time until it finds a path that leads to the goal. The below figures show the maze which contains the initial state of the robot, the obstacles, and the goal state. Here, the goal node is in the position of (0,5) where the robot needs to traverse through the maze to find the path to reach the goal.
Step 1: Define Maze dimensions and obstacles
We define a maze_size representing the dimension of the maze, in our case, it’s a 6×6 grid. A list of coordinates that represents the positions of obstacles within a maze is also specified. The robot is positioned at the initial state (0,0) and aims to reach the goal state (0,5).
Maze dimensions and obstacles
# Maze dimensions and obstacles
maze_size = 6
obstacles = [(0,1),(1,1),(3,2),(3,3),(3,4),(3,5),(0,4),(4,1),(4,2),(4,3)]
start = (0,0)
goal = (0,5)
Step 2: Define a is_valid function
The is_valid function checks whether a given position of (x,y) is valid such that it inspects that it’s within the bounds of the maze and not obstructed by any obstacles.
def is_valid(x,y):
return 0 <= x < maze_size and 0 <= y < maze_size and (x,y) not in obstacles
Step 3: Define dfs function (Depth-first search):
In the below code, we define the dfs function to implement the DFS algorithm. It uses a stack to keep a record of the nodes it visits, and it iterates through each node that helps in exploring its neighbors recursively until it finds the goal node or it exhausts all possibilities.
- The empty stack stores nodes to be explored, and the empty set is used to keep track of nodes that have been already visited to avoid revisiting them.
- If the current node is found to be the goal node, it reverses the path so that the robot can follow and it finally returns “Path found”.
- If no path is found, it returns “No path found”. This is an exhaustive search approach, it ensures that all the potential paths are explored and provides a comprehensive solution to the maze-navigating problem.
def dfs (current, visited, path):
x, y = current
if current == goal:
path.append(current)
return True
visited.add(current)
moves = [(x-1,y), (x+1, y), (x, y-1), (x, y+1)]
for move in moves:
if is_valid(*move) and move not in visited:
if dfs(move, visited, path):
path.append(current)
return True
return False
Step 4: Call DFS function to find the path
#Call DFS function to find the path
visited = set()
path = []
if dfs(start, visited, path):
path.reverse()
print("Path found:")
for position in path:
print(position)
else:
print("No path found!")
Complete Code of Robots Pathfinding
# Maze dimensions and obstacles
maze_size = 6
obstacles = [(0,1),(1,1),(3,2),(3,3),(3,4),(3,5),(0,4),(4,1),(4,2),(4,3)]
start = (0,0)
goal = (0,5)
# checks whether a given position of (x,y) is valid to move or not
def is_valid(x,y):
return 0 <= x < maze_size and 0 <= y < maze_size and (x,y) not in obstacles
#Dfs function (Depth-first search)
def dfs (current, visited, path):
x, y = current
if current == goal:
path.append(current)
return True
visited.add(current)
moves = [(x-1,y), (x+1, y), (x, y-1), (x, y+1)]
for move in moves:
if is_valid(*move) and move not in visited:
if dfs(move, visited, path):
path.append(current)
return True
return False
#Call DFS function to find the path
visited = set()
path = []
if dfs(start, visited, path):
path.reverse()
print("Path found:")
for position in path:
print(position)
else:
print("No path found!")
Output:
Path found:
(0, 0)
(1, 0)
(2, 0)
(3, 0)
(3, 1)
(2, 1)
(2, 2)
(1, 2)
(0, 2)
(0, 3)
(1, 3)
(2, 3)
(2, 4)
(1, 4)
(1, 5)
(0, 5)
Output explanation
Step 1: We first start at the initial position (0,0), it is where the robot begins its exploration.
Step 2: The robot moves right along the top row of the maze such as (1,0), (2,0),(3,0).
Step 3: Now, the robot moves down to the second row to the position of (3,1).
Step 4: The robot follows a path to the left (2,1), then down (2,2), then right (1,2), and then down again (0,2).
Step 5: Now, the robot moves right to reach the third row to the position (0,3).
Step 6: The robot moves right along the third row such as passing the positions of (1,3) and (2,3).
Step 7: The robot moves down to the fourth row (2,4) and then it moves left (1,4).
Step 8: The robot moves right to the last column (1,5).
Step 9: Finally, the robot reaches the goal node at the bottom-left corner(0,5) of the maze.
Depth First Search (DFS) for Artificial Intelligence
Depth-first search contributes to its effectiveness and optimization in artificial intelligence. From algorithmic insights to real-world implementations, DFS plays a huge role in optimizing AI systems. Let’s dive into the fundamentals of DFS, its significance in artificial intelligence, and its practical applications.
Table of Content
- What is a Depth-First Search in AI?
- Edge classes in a Depth-first search tree based on a spanning tree:
- Depth First Search(DFS) Algorithm
- DFS Behavior Across Different State Space Structures
- DFS Implementation in Robotics Pathfinding
- Applications of DFS in AI
- Conclusion
- FAQs on Depth First Search(DFS) for Artificial Intelligence