State Space Search

Question 1

state space search

Answer 1

represented using a search tree or search graph it is about finding a sequence of actions to lead from an initial state/position to a goal state without knowing how to get there

Question 2

state

Answer 2

representation of the problem at a given point in time

Question 3

actions

Answer 3

set of all possible moves

Question 4

transition model

Answer 4

describes result of applying action to a sate given the environment (rules)

Question 5

state-space

Answer 5

math representation of all possible states that a system can be in with actions to go from one to another

Question 6

completeness

Answer 6

always finding a solution if one exists

Question 7

optimality

Answer 7

finding the least costly solution

Question 8

time complexity in terms of big 0

Answer 8

nodes generated/expanded
how run time grows as a function of input

Question 9

space complexity in terms of big 0

Answer 9

max nodes in memory

how much memory required grows as function of input

Question 10

uninformed search

Answer 10

single agent
systematically exploring state space without use of knowledge to guide the agent until finds goal state
inefficient unintelligent

Question 11

uninformed search has the following features

Answer 11

initial state
transition model (rules)
set of possible actions
goal test

Question 12

node in state space search has

Answer 12

represents a state in the search tree incl extra info like action that led to i, parent node, depth, costs)

Question 13

path vs step cost

Answer 13

path is total cost of total cost associated with a particular sequence of actions
step cost is cost incurred moving from one state to another or taking a single action

Question 14

how is search strategy determined?

Answer 14

dependant on order of nodes in fringe are expanded

Question 15

if search algorithm picks first node determined by

Answer 15

how new nodes are added

Question 16

if search algorithm picks last node determined by

Answer 16

which node picked to expand

Question 17

4 types of tree searches

Answer 17

Breadth first
depth first
death limited
iterative depth

Question 18

BFS, what, complete, optimal and space/time

Answer 18

expand nodes in order of adding them to the fringe
work across all in one depth before going down
yes will complete if there is a solution
not optimal in general
space and time expo

Question 19

DFS, what, complete, optimal and space/time

Answer 19

explores nodes as far as possible along a branch before backtracking via stack
complete if finite depth not complete if in inf depth
not optimal
space linear
time expo

Question 20

DLS what, complete, optimal and space/time

Answer 20

DFS with limited depth
prevents inf loop
complete if depth is enough to find solution
not optimal
space linear
time expo

Question 21

IDS, what, complete, optimal

Answer 21

combines space efficiency of DFS with completeness of BFS
complete
not optimal in general
space linear
time expo

Question 22

tree vs graph search

Answer 22

tree explores hirearchical structures with single root, simple but doesn’t;t check for repeated states so wastes time and space
graph searches explore connections accounting for cycles, keeps closed list of repeated states expanded so far so only adds new node is state is not found on list but takes additional memory to track visited states

Question 23

informed search

Answer 23

single agent
systematically exploring state space with use of knowledge to prioritise node expansion on those that are more likely to lead it to the goal state

Question 24

informed search features

Answer 24

initial state
set of possible actions
transition model (rules)
goal test (evaluation function to evaluate with respect to reaching goal)

Question 25

informed search picks the node to expand with the

Answer 25

best evaluation function

Question 26

3 types of uninformed search

Answer 26

uniform cost search greedy search A*

Question 27

uniform cost search, what, how, optimal, complete

Answer 27

variant of BFS prioritising nodes based on their path cost expands nodes in increasing order (lowest first) and only looks back to cost of getting so far finds optimal route complete if action cost >0 but not in terms of space and time complexity explores lots of possibilities and gives the optimal route

Question 28

greedy search, what, how, optimal, complete

Answer 28

only looks forward to goal state chooses node to expand with lowest heuristic won't give optimal route like last time but finds the goal state a lot quicker not optimal as might prioritise nodes that lead to dead ends

Question 29

heuristic, what and how used

Answer 29

evaluate how promising a prticular state or action is in reaching the goal aim to reduce the search space by prioritizing certain paths.

Question 30

A*, what complete, optimal

Answer 30

uses actual accumulated cost so far and heuristic to estimate cost to reach the goal node complete unless inf nodes optimal if TS admissible heuristic and GS consistent heuristic

Question 31

adversial search

Answer 31

multi-agent finds optimal strategy for one player while anticipating opponents move models consequences of an action by modelling what action the other play may take essential in 0 sum games (when one player gains the other loses resulting in 0 utility)

Question 32

adversial search features

Answer 32

initial state possible actions transition model terminal test utility function (agent's subjective value of terminal state) agent chooses move to max its utility

Question 33

what is the algorithm used in adversial search and how does it work?

Answer 33

minimax search tree until reaches terminal state note utility of each term state (+1,1,0) back up values of nodes to parents selecting max value on MAX's move and min value on MIN's move continue backwards until get values for children of root node

Question 34

admissible vs consistent heuristic

Answer 34

admissible never over estimates cost of path from current to goal state (can underestimate but never overestimate) consistent estimate is always less than or equal to the estimated distance from any neighbouring vertex to the goal, plus the cost of reaching that neighbour

Question 35

every consistent h is ____ but

Answer 35

admissible but not all admissible are consistent

Question 36

optimality of A* using heuristics TS vs GS

Answer 36

TS: when uses AD h it will find least cost path to goal GS: when uses consistent h avoids redundant explorations

Question 37

2 common heuristics

Answer 37

1) straight line distance which is both ad and consistent 2) Manhattan distance in tile game is # of moves needed to get from one pt to to the other without diagonal moves

Question 38

depth limited minimax

Answer 38

same but just search until depth limit is reached, applying heuristic evaluation funcition to state of each leaf

Question 39

alpha beta pruning

Answer 39

optimisation technique used in minimax algorithm for eliminating branches that don't need to be explored

Question 40

what values ab pruning holds?

Answer 40

alpha (α): The best score that the maximizing player (Max) can guarantee so far. Initially, it’s set to a very low value (negative infinity). Beta (β): The best score that the minimizing player (Min) can guarantee so far. Initially, it’s set to a very high value (positive infinity).

Question 41

how ab pruning works

Answer 41

start with initialised a=- inf and b= +inf DFS of game tree for each maximiser node update a with max among children for each minimiser node update a with min among children pruning during traversal if at any point a>=b prune remaining branches of tree as won't be looked at

Question 42

why is ab pruning helpful?

Answer 42

increases efficiency of algorithm as prunes redundant branches and increases as depth increases

Question 43

stochastic search

Answer 43

search algorithm that uses randomness/probability for decision making and doesn't care about going from A-B just wants to find the best state according to some criteria inspired by genetics and natural selection

Question 44

features of stochastic search

Answer 44

state space fitness function

Question 45

stochastic search pros and cons

Answer 45

searches large search space not guaranteed to find global optimum

Question 46

genetic algorithm

Answer 46

stochastic search of biological evolution over a state space

Question 47

GA state space

Answer 47

space of genetic variation in population

Question 48

GA fitness function

Answer 48

evaluates how close solution is to optimal solution

Question 49

GA chromosome

Answer 49

representation of a state in GA, encoded as #s often (DNA sequences) relates characteristic of individuals

Question 50

GA crossover

Answer 50

genetic operation combining 2 parent chromosome to crehtaeone new one

Question 51

mutation

Answer 51

randomly modify child's chromosomes

Question 52

population

Answer 52

set of chromosomes at a given iteration of the algorithm

Question 53

diversity

Answer 53

variety of solutions within the population high diversity avoids premature convergence to local optima

Question 54

elitism

Answer 54

retaining fittest individuals for next generation

Question 55

7 steps for GA

Answer 55

create pop of soutions evaluate how fit each solution is randomly select 2 parents but in a way fitter states are more likely to be picked combine parents into offspring mutuatiion, randomly modifying offspring to maintain diversity replace old population w new repeat process until stop criteria is met

Question 56

epoch

Answer 56

the one entire passing of training data through the algorithm

Question 57

2 parent selection options

Answer 57

roulette wheel selection tournament selection

Question 58

roulette wheel selection

Answer 58

stochastic selection each individual is given slice of wheel proportional to its fitness and wheel is spun

Question 59

tournament selection

Answer 59

select a sub group of individuals for a tournament and fitness there is selected

Question 60

RW vs TS pros/cons

Answer 60

RW which lech prefers may lead to rapid convergence if one individual is significantly fitter than most but good for preserving diversity TS promotes fittest while still trying to give others a chance more greedy

Question 61

3 types of point crossovers

Answer 61

single point, everything before point is from one parent and second half from other k point has multiple of those points uniform is all individual gene picked from each parent

Question 62

when would each of these types of state space searches be viable?

Answer 62

state space is not too large transition model (rules known) for (un/in/adv) fitness function can be formed that ranks attest and sensible cross over point (GA)