Exploring Search Algorithms in Simulated Environments: The TurtleBot Project

Artificial Intelligence

Overview

• Introduction
• Search Problems
• Uninformed and Informed Search
• Admissible and Consistent heuristics
• Implementation
• Results
• Conclusion

Introduction

This blog includes the project which I done as part of my Artificial Intelligence course. The methods are implemented in the simulated turtle bot environment.

Search Problems

what are search problems?

Link

This project involved implementing graph search algorithms on the Turtlebot environment to avoid obstacles and find the optimal path to the goal state.In search problems, can-world and cafe-world environment is used to navigate the turtlebot using efficient search algorithm.

There are various algorithms that can be used to solve this search problem, namely, Breadth-First search, Greedy Best-First search, Uniform Cost Search, and A. A simulated environment is used using TurtleBot to create a virtual version of the logistics problem. This environment is used to test the solutions developed for the search problem. The goal of this project is to implement graph search algorithms, similar to best-first search, including Breadth-First search, Greedy Best-First search, Uniform Cost Search, and A with Manhattan heuristic, on the Turtlebot environment. The algorithms will be implemented in two environments, the Can World and Cafe ́ World. The performance of each algorithm will be evaluated in terms of the time taken and nodes expanded for different grid dimensions.

Uninformed and Informed Search

Algorithms used: In this project, I implemented several search algorithms including Breadth-First Search, Greedy Best-First Search, Uniform Cost Search, and A Search.*

Uninformed search:

It generates the path to the goal without considering edge cost or estimated cost to the goal. It explores the search space without any domain-specific knowledge. It uses simple strategies such as breadth-first search, depth-first search, or uniform cost search to explore the search space and find the goal state.

Informed search:

on the other hand, Informed search considers edge cost and estimated cost to reach the goal. It is considered to be more efficient than the Uninformed search.

Breadth-First Search(Uniformed search):

It is efficiently used for unweighted graph where it explores all possible path from the start node to the end node.

Greedy Best-First Search (Informed search):

Unlike BFS, it expands the nodes based on the estimated cost to the goal. It will expand the node which has shortest distance to the goal.

Uniform Cost Search (Informed search):

It expands the node with the lowest path cost. It expands the nodes with shortest edge cost.

*A Search (Informed search):**

It expands the node by considering both edge cost and estimated cost to the goal. Since it considers both edge cost and estimated cost to goal, it is guaranteed to provide a optimal path to the goal.

Overall, I chose these algorithms to solve the problem in the project.

To implement efficient and optimal search , I used Manhattan distance heuristic to estimate distance to the goal from current state. By considering heuristics, states which are closer to the goal are estimated first compared to other states.

Admissible and Consistent heuristics

Admissible:

It never over estimates the cost to the goal. This guarantees to provide a optimal path.

Consistent:

A consistent heuristic makes sure that the estimate for parent node is always less than or equal to the successor node. It conveys that the successor node cannot be reached earlier than its parent node.

In my implementation, I ensured that the heuristics used in the A* algorithm and GBFS were both admissible and consistent.

Implementation

I have implemented graph search algorithms by initializing the initial and goal states and created the initial node of the search tree. Then, I computed the fscore of the initial node using the ‘compute g‘ and ‘compute h‘ functions which calculate the cost from the initial node to the current node and the heuristic cost from the current node to the goal node respectively.

To implement graph search, I used a priority queue data structure and added the initial node with its fscore to the priority queue. I used a dictionary ‘reached‘ to keep track of the nodes that have already been expanded and their fscore. I used a function ‘expand‘ to get the child nodes of the cur- rent node and computed the fscore of each child node using the ‘computeg‘ and ‘computeh‘ functions. I then checked if the child node is already in the ‘reached‘ dictionary and if its fscore is less than the existing fscore, then I added it to the priority queue and updated its fscore in the ‘reached‘ dictionary.

I kept expanding the nodes in the priority queue until I reached the goal node or the time limit exceeded. Finally, I extracted the sequence of actions to reach from the initial state to the goal state and the total number of nodes expanded during the search. If the time limit is exceeded, the function raises a ‘SearchTimeOutError‘.

Overall, this implementation uses priority queue and heuristic functions to efficiently explore the search space and find the optimal path from the initial state to the goal state.

Results

• Time taken for different dimensions estimated for all al- gorithms in the Figure1.
• It is clear that gbfs has optimal time across dimensions.
• Time taken for all the other algorithms are increasing when dimensions are increased.

• The results for nodes expanded in figure2 are similar to time taken graph.
• Nodes expanded for GBFS is less across dimensions.
• In both graph it is clear that GBFS outperforms all the other algorithms in terms of nodes expanded and time taken.

Conclusion

This blog illustrates how search algorithms work efficiently in simulated environment and demonstrated how correct heuristics will achieve optimal solutions.

In my other blogs I will explain about other Artificial Intelligence projects