AI Search Algorithms: Techniques and Properties

• Search techniques are commonly applied in AI
• Search algorithms in AI are important for solving AI-related problems
• These algorithms help AI agents find the best solutions
• AI agents often use search algorithms behind the scenes

Search Problem Elements

• Search Space is the set of possible solutions
• Start State defines where an agent begins its search
• Goal State checks whether the goal is achieved

Algorithm Properties

• Completeness: An algorithm is complete if it reaches a particular solution for any random input and guarantees a solution
• Optimality: A solution is optimal if guaranteed to be the best one
• Time Complexity: Measures the time it takes for an algorithm to find a solution
• Space Complexity: Measures the storage space an algorithm requires during execution

Importance of Search Algorithms

• Used for solving problems and improve problem-solving
• Applied in real-world applications like route planning in Google Maps, to find the quickest or shortest paths
• Many AI activities can be coded in terms of searching
• Improve the efficiency of goal-based agents
• Used in production systems to find rules leading to the required action
• Utilized in neural networks

Tree Data Structure

• This is a non-linear data structure that follows a hierarchical model
• Elements are arranged in levels
• Contains one unique node, referred to as the parent/root node
• Does not create any loops or cycles
• Has directed edges
• Supports insert and delete operations, other than search

Graph Data Structure

• This is a non-linear data structure that follows a network model
• It does not have a unique node
• Can have loops or cycles
• Can have directed or undirected edges
• Used for finding the shortest path in a network

Types of Search Algorithms

• Uninformed Search:
  • Breadth First Search
  • Uniform Cost Search
  • Depth First Search
  • Depth Limited Search
  • Iterative Deepening Depth First Search
• Informed / Heuristic search:
  • Best First
  • A* Search

Breadth First Search (BFS)

• An uninformed search technique using a Queue (FIFO) data structure
• Explores nodes at the same level before moving to the next level, also known as level order searching
• It is complete as it always searches
• Time Complexity: O(V+E) or O(b^d), where b is the branch factor, d is the depth, V is vertices, and E is edges
• It needs more memory than DFS, space complexity of O(V)
• The starting nodes are entered on a Queue
• The algorithm stops if the Queue is empty
• If the first element on Queue is the Goal node return success and stop
• Otherwise, the first element from Queue is removed and expanded, and children are placed at the end of queue
• Traversal starts from root node level by level
• Visited nodes are added to and removed from queue, adding next level nodes

Depth First Search (DFS)

• An uninformed search technique that uses a Stack (LIFO) data structure
• Explores nodes in depth before moving to the next path
• May be incomplete in infinite states
• Time Complexity: O(V+E) or O(b^d)
• Space complexity is O(d), where d is the depth level of the tree

Depth Limited Search (DLS)

• A depth-first search with a predetermined depth limit
• Assumes no successors exist after the limit value
• Solves infinite problems
• The algorithm ends with two conditions:
  • Standard failure indicating no solution
  • Cutoff value indicates no solution within depth limit
• Is more efficient than DFS, using less time and memory
• Guarantees a solution in a finite amount of time
• If target node doesn't exist inside the chosen depth limit, iterative deepening search is used

Iterative Deepening Search

• This algorithm gradually increases the limit, starting from 0, then 1, 2, and so on, until a goal is found

Uniform Cost Search (UCS)

• Used for traversing weighted trees and graphs
• The objective is to find the path with the lowest cumulative cost from start to goal node
• The edge with the minimum cost receives high priority
• Node expansion is based on path cost
• Implementation uses priority queue

Informed Search Algorithms

• These contain knowledge to reach the goal node, decreasing search spaces
• Also known as Heuristic search
• A heuristic function takes the current state as input and estimates the distance to the goal and has a positive value
• It expands nodes based on the heuristic value, h(n)
• It maintains two lists, OPEN(Queue/Pq) and CLOSED/Visited
• Nodes are expanded and put on the closed list until a goal state is found

Best First Search

• A greedy search that selects the best path using a heuristic function to search for the best path
• Combination of DFS and BFS
• Implemented using a Priority Queue
• It is not optimal or complete but gives the best path result
• The starting node is placed into the OPEN/QUEUE list
• Stop and return failure occurs if the OPEN/QUEUE list is empty
• The node n with the lowest value of h(n) is removed from the OPEN list and placed into the CLOSED/VISITED list
• Node n is expanded, and successors are generated
• For each successor node, the algorithm checks the evaluation function f(n) and if the node has been in either OPEN or CLOSED list, and if not adds it to the OPEN list

A* Search

• Another form of Best First Search that is optimal and complete, however, has a high memory requirement
• Combination of Uniform Cost Search and Best First Search
• Selects the best path by using heuristic and cost functions
• Similar to UCS except that it uses g(n)+h(n) instead of g(n)
• Combine both costs as a fitness number
• F(n) = G(n) + H(n)
  • F(n) is the actual cost path from the start node to the goal node
  • G(n) is the actual cost path from the start node to the current node
  • H(n) is the actual cost/heuristic path from the current node to goal node
• The algorithm
  • Add the starting node in the open list
  • If the open list is empty return fail
  • Select node drom open list with the smallest value
  • If node is goal return success
  • Expand the Node N and generate all sucessors and compute (g+h)
  • If code N is in Open/Close attach to backpointer
  • Goto step 3
  • Exit

Dijkstra's Algorithm Vs A* Search Algorithm

• Heuristic: A* uses a heuristic function h(n) versus no heuristic
• Prioritization: A* is based on f(n) = g(n) + h(n), where djikstra is based on actual cost g(n)
• Guarantees: A* finds shortest path to the goal node if heuristic is admissible versus finding sortest paths to all nodes
• Efficiency: A* is potenially more efficient than Djikstra's due to heuristics

Game Search (Mini-Max Algorithm)

• A type of Adversarial/Game Search, where one candidate plans against the strategy of other
• For multiagent environments, the agents work in the same environment to find the best solution
• A recursive/backtracking algorithm that is complete and optimal if opponents play optimally
• Used in decision making and game theory
• Uses recursion to search through the game tree for two player games like Chess, Tic-Tac-Toe
• One player is Min and the other is Max, where one player tries to maximize the value for win, and the other minimizes the value for opponent
• Max selects the maximum value and Min selects the minimum value
• Uses Depth-First-Search to explore the complete game tree
• The Minimax algorithm is optimal and complete
• The time complexity is O(b^d)