search problems

state spaces&search problems

state spaces: The set of all possible states that are possible in your given world
transition model: output the next state when the specific action is taken at current state
cost: Incurred when moving from one state to another after applying an action
start state -> goal test

state space graphs

A state space graph is constructed with states repre senting nodes, with directed edges existing from a state to its children.
These edges represent actions , and any associated weights represent the cost of performing the corresponding action.

The standard protocol for finding a plan to get from the start state to a goal state is to maintain an outer frontier of partial plans derived from the search tree.

We continually expand our frontier by removing a node (which is selected using our given strategy) corresponding to a partial plan from the frontier, and replacing it on the frontier with all its children.

some rudimentary properties of the strategy:

  • completness: is the strategy guaranteed to find it given infinite computational resources
  • optimality: guaranteed to find the lowest cost path to a goal state?
  • branching factor: The increase in the number of nodes on the frontier each time a frontier node is dequeued and replaced with its children is O(b)

DFS

always selects the deepest frontier node from the start node for expansion.
It is incomplete(might into circles!!!)

Removing the deepest node and replacing it on the frontier with its children necessarily means the children are now the new deepest nodes- their depth is one greater than the depth of the previous deepest node. This implies that to implement DFS, we require a structure that always gives the most recently added objects highest priority. A last-in, first-out (LIFO) stack does exactly this, and is what is traditionally used to represent the frontier when implementing DFS
![[Pasted image 20240730225547.png]]

BFS

always selects the shallowest fron tier node from the start node for expansion

If we want to visit shallower nodes before deeper nodes, we must visit nodes in their order of insertion. Hence, we desire a structure that outputs the oldest enqueued object to represent our frontier. For this, BFS uses a first-in, first-out (FIFO) queue, which does exactly this
![[Pasted image 20240730225607.png]]

UCS

a strategy for exploration that always selects the lowest cost frontier node from the start node for expansion

To represent the frontier for UCS, the choice is usually a heap-based priority queue, where the priority for a given enqueued node v is the path cost from the start node to v, or the backward cost of v. Intuitively, a priority queue constructed in this manner simply reshuffles itself to maintain the desired ordering by path cost as we remove the current minimum cost path and replace it with its children
![[Pasted image 20240730225730.png]]

If we have some notion of the direction in which we should focus our search, we can significantly improve performance and “hone in” on a goal much more quickly. This is exactly the focus of informed search.

Heuristics

driving force that allow estimation of distance to goal states

a strategy for exploration that always selects the frontier node with the lowest heuristic value for expansion, which corresponds to the state it believes is nearest to a goal

operates identically to UCS, with a priority queue Frontier Representation. The difference is that instead of using computed backward cost (the sum of edge weights in the path to the state) to assign priority, greedy search uses estimated forward cost in the form of heuristic values

a strategy for exploration that always selects the frontier node with the lowest estimated total cost for expansion, where total cost is the entire cost from the start node to the goal node

uses a priority queue to represent its frontier. A* combines the total backward cost (sum of edge weights in the path to the state) used by UCS with the estimated forward cost (heuristic value) used by greedy search by adding these two values, effectively yielding an estimated total cost from start to goal.

in some problems, we only care about finding the goal state — reconstructing the path can be trivial. For example, in Sudoku, the optimal configuration is the goal. Once you know it, you know to get there by filling in the squares one by one.

The hill-climbing search algorithm (or steepest-ascent) moves from the current state towards the neighbor ing state that increases the objective value the most.
![[Pasted image 20240731165514.png]]
Hill-climbing is incomplete. Random restart hill-climbing on the other hand, which conducts a number of hill-climbing searches from randomly chosen initial states, is trivially complete as at some point a randomly chosen initial state can converge to the global maximum.

Simulated annealing aims to combinerandomwalk(randomlymovestonearbystates)andhill-climbing to obtain a complete and efficient search algorithm. In simulated annealing we allow moves to states that can decrease the objective.

The algorithm chooses a random move at each timestep. If the move leads to higher objective value, it is always accepted. If it leads to a smaller objective value, then the move is accepted with some probability. This probability is determined by the temperature parameter, which initially is high (more “bad” moves allowed) and gets decreased according to some “schedule”.
![[Pasted image 20240731170524.png]]

local beam search keeps track of k states (threads) at each iteration. The algorithm starts with a random initialization of k states and at each iteration it takes on k new states as done in hill-climbing. These aren’t just k copies of the regular hill-climbing algorithm. Crucially, the algorithm selects the k best successor states from the complete list of successor states from all the threads. If any of the threads finds the optimal value the algorithm stops.

Genetic Algorithms

Genetic algorithms begin as beam search with k randomly initialized states called the population. States (called individuals ) are represented as a string over a finite alphabet.

Each individual is evaluated using an evaluation function (fitness function) and they are ranked according to the values of that function. For the 8-Queens problem this is the number of non-attacking (non-conflicted) pairs of queens.

![[Pasted image 20240803193425.png]]
pseudocode:
![[Pasted image 20240803194215.png]]