Single Agent Pathfinding in AI

• AI relies on its data pool to respond to different scenarios.
• AI assistants respond within their reach and provide web search results or say "don't know" if asked beyond their expertise.
• AI systems search their data pool for specific answers; so searching is a universal problem-solving technique in AI.
• Envision an AI system playing a single-player game, like a sliding puzzle.
• To respond, the AI solves the puzzle by knowing each piece's exact position.
• A person does this by searching and moving the piece to its correct place in a blank space.
• This problem-solving method in AI is called Single Agent Pathfinding.

Terminologies for Single Agent Pathfinding

• Problem Space: The environment where the search occurs, including states and operators to change states.
• Problem Instance: The initial state and goal state.
• Problem Space Graph: Represents the problem state, with states as nodes and operators as edges.
• Depth of a Problem: The length of the shortest path or operator sequence from initial to goal state.
• Space Complexity: The maximum number of nodes stored in memory.
• Time Complexity: The maximum number of nodes created.
• Admissibility: An algorithm's ability to consistently find an optimal solution.
• Branching Factor: The average number of child nodes in the problem space graph.
• Depth: Length of the shortest path from initial to goal state.

Search Algorithm Strategies

• Brute-Force Search Strategies
• Informed Search Strategies

Brute-Force Search Strategies

• Simple strategies that do not need domain-specific knowledge, and work well with small state numbers.
• It requires these elements
  • State description
  • Set of valid operators
  • Initial state
  • Goal state description

Breadth-First Search

• A brute-force search algorithm that starts from the root node, explores neighbors in one level, and then moves to the next.
• It creates one tree at a time until the solution is found.
• Implemented using a Queue data structure with FIFO method, providing the quickest solution path.
• It follows these rules:
  • Visit the adjacent unvisited vertex
  • Mark vertex as visited
  • Insert visited vertex in a queue
  • If there is no adjacent vertex is found, remove first vertex from queue
  • Repeat Rule 1 to Rule 4 until the queue is empty
• If:
  • b = branching factor
  • d = depth
• Then: number of nodes at level d = bd
• The total number of nodes created in a worst case scenario follows exponential form: b + b² + b³ + ... + bd
• Each level of nodes is also saved leading to high memory use.
• The space requirement to store nodes is exponential in the worst-case scenario
• Breadth-First Search complexity depends on the number of nodes
• Breadth-First Search has duplicate checking capabilities.

Depth-First Search

• Implemented in recursion with LIFO stack data structure.
• The same node set is created as the Breadth-First method, but in a different order.
• Nodes on a single path are stored in each iteration from root to leaf node, so the space requirement to store nodes is linear.
• This algorithm follows these rules:
  • Visit the adjacent unvisited vertex
  • Mark said vertex as visited
  • Push visited vertex in a stack
  • If no adjacent vertex is found, pop up a vertex from the stack (It will pop up all the vertices from the stack, which do not have adjacent vertices).
  • Repeat Rule 1 to Rule 4 until the stack is empty
• It can go infinitely on one path; solved by choosing a cut-off depth.
  • May fail if the chosen cut-off is shorter than the ideal cut-off d.
  • Execution time increases if the cut-off chosen is above d.
• The complexity depends on the paths number, and it has no duplicate checking.

Bidirectional Search

• A search algorithm with two Breadth-First Searches simultaneously to find the shortest distance between a start and goal vertex.
• The tree splits into two subtrees
  • One for BFS at the start vertex
  • The other for the goal vertex.
• Search algorithms stop when the two trees intersect at a vertex.
• Then shortest path is determined by this intersection.
• If:
  • b = branching factor
  • d = depth
• Then: number of nodes at level d = bd/2
• Bidirectional Search has significantly less complexity when compared to BFS

Informed Search Strategies

• Unlike brute-force strategies which do not need any domain-specific knowledge, Informed search algorithms contain array of knowledge such as:
  • How far from the goal
  • Path costs
  • How to reach the goal node
  • etc.
• Help agents explore less of the search space, and find the goal node more efficiently.
• More useful for large search spaces.
• It is also called Heuristic search, because it uses heuristic ideas.
• Heuristic = Proceeding to solution by trial and error or rules that are only loosely defined.
• The Heuristic Function of an Informed search algorithm takes the current state of the agent as its input and produces the estimation of how close agent is from the goal.
• The heuristic method not always gives the best solution, but it guaranteed to find a good solution in reasonable time

Heuristic Function

• Estimates how close a state is to the goal, represented by h(n), and calculates the cost of an optimal path between the pair of states.
• The value of the heuristic function is always positive.
• The admissibility of the heuristic function is given as: h(n) <= h*(n)
  • h(n) is the heuristic cost
  • h*(n) is the estimated cost

Pure Heuristic Search

• Pure heuristic search is the simplest form of heuristic search algorithms.
• It expands nodes based on their heuristic value h(n).
• It maintains two lists, OPEN and CLOSED list.
  • In the CLOSED list, it places those nodes which have already expanded
  • In the OPEN list, it places nodes which have yet not been expanded.
• On each iteration, each node n with the lowest heuristic value is expanded and generates all its successors and n is placed to the closed list.
• The algorithm continues unit a goal state is found.
• The two main algorithms of pure heuristic search are:
  • Greedy Search Algorithm
  • A* Search Algorithm

Greedy Search Algorithm

• This is the combination of depth-first and breadth-first search algorithms.
• It uses the heuristic function and search.
• Best-first search allows us to take advantages of both algorithms.
• With the help of best-first search, at each step, we can choose the most promising node.
• In the best first search algorithm, we expand the node which is closest to the goal node and the closest cost is estimated by heuristic function, i.e. f(n) = h(n)
  • Where h(n) is the estimated cost from node n to the goal
• Implemented by the priority queue.
• The algorithm follows these rules:
  • Place the starting node into the OPEN list.
  • If the OPEN list is empty, Stop and return failure.
  • Remove the node n, from the OPEN list which has the lowest value of h(n), and places it in the CLOSED list.
  • Expand the node n, and generate the successors of node n.
  • Check each successor of node n, and find whether any node is a goal node or not. If any successor node is goal node, then return success and terminate the search, else proceed to Step 6.
  • For each successor node, algorithm checks for evaluation function f(n), and then check if the node has been in either OPEN or CLOSED list. If the node has not been in both list, then add it to the OPEN list.
  • Return to Step 2.

Advantages of Greedy Search Algorithm

• Best first search can switch between BFS and DFS by gaining the advantages of both the algorithms.
• This algorithm is more efficient than BFS and DFS algorithms.

Disadvantages of Greedy Search Algorithm

• It can behave as an unguided depth-first search in the worst case scenario.
• It can get stuck in a loop as DFS
• This algorithm is not optimal

A* Search Algorithm

• This is the most commonly known form of best-first search.
• It uses heuristic function h(n), and cost to reach the node n from the start state g(n).
• It has combined features of UCS and greedy search, by which it solve the problem efficiently.
• This search algorithm finds the shortest path through the search space using the heuristic function
  • Expands less search tree
  • Provides optimal result faster.
• Similar to UCS except that it uses g(n)+h(n) instead of g(n).
• It is used search heuristic as well as the cost to reach the node.
• Both costs can be combined as following, and this sum is called as a fitness number: f(n) = g(n) + h(n)
  • f(n) estimated cost of the cheapest solution
  • g(n) cost to reach node n from start state
  • h(n) cost to reach from node n to goal node.

Algorithm Rules

• Place the starting node in the OPEN list.
• Check if the OPEN list is empty or not, if the list is empty then return failure and stops.
• Select the node from the OPEN list which has the smallest value of evaluation function (g+h), if node n is goal node then return success and stop, otherwise Expand node n and generate all of its successors, and put n into the closed list.
• For each successor n', check whether n' is already in the OPEN or CLOSED list, if not then compute evaluation function for n' and place into Open list.
• Else if node n' is already in OPEN and CLOSED, then it should be attached to the back pointer which reflects the lowest g(n') value.
• Return to Step 2.

Advantages for A* Search Algorithm

• A* search algorithm is the best algorithm than other search algorithms
• A* search algorithm is optimal and complete
• This algorithm can solve very complex problems.

Disadvantages for A* Search Algorithm

• The heuristic and approximation-based A* search method does not always produce the shortest path.
• There are some complexity issues with the A* search algorithm.
• The main drawback of A* is memory requirement as it keeps all generated nodes in the memory, so it is not practical for various large-scale problems.