Intelligent Systems

Front 1

A single state problem is... the agent... the solution is...

Back 1

Deterministic and fully observable. The agent knows exactly what state it will be in and the solution is a sequence

Front 2

A sensor less problem is... the agent... the solution...

Back 2

Non-observable. Agent may have no idea where it is, solution is a sequence.

Front 3

Contingency problem is...

Back 3

Non deterministic and/ot partially observable. Percepts provide NEW information about current state. Often interleave search and execute.

Front 4

An exploration problem is...

Back 4

An unknown state space

Front 5

What 4 things are needed to define a problem?

Back 5

Initial state

Actions

Goal state

Path cost

Front 6

Give an example of an implicit goal state and an explicit goal state.

Back 6

Implicit = checkmate

Explicit = a particular node on a graph

Front 7

What information do basic tree nodes contain?

Back 7

State

Parent node

Action

Path cost g(x)

Depth

Front 8

What 4 things are strategies evaluated on?

Back 8

Completeness

Time complexity

Space complexity

Optimality

Front 9

What is completeness

Back 9

Does it find A solution, if one exists

Front 10

What is time complexity

Back 10

Number of nodes GENERATED (not expaned)

Front 11

What is space complexity

Back 11

Maximum number of nodes in memory

Front 12

What is optimality

Back 12

Does it always find the least cost/ Best solution

Front 13

What is the variable for max branching factor

Back 13

B

Front 14

What is the variable for depth of the least cost solution

Back 14

D

Front 15

What is the variable for maximum depth of the state space

Back 15

M

Front 16

Define an uninformed search strategy and give examples

Back 16

Only uses the information available in the problem defenition. E.g. breadth first, depth first, depth limited, iterative deepening.

Front 17

Is breadth first complete

Back 17

Yes, if b is finite

Front 18

What is the time complexity of breadth first

Back 18

O(b^(d+1))

Think: number of nodes expanded max will be the branching factor to the power of the lowest level expanded which will be one bellow the solution.

Front 19

Is breadth first optimal

Back 19

Yes (if cost is the same for all steps)

Front 20

What is the space complexity of breadth first

Back 20

O(b^(d+1))

Think: it keeps every node in memory therefore is the same as time complexity

Front 21

Is depth first complete

Back 21

Yes in finite space. No in infinite space (which is quite common) or spaces with loops

Front 22

What is the time complexity of depth first

Back 22

O(b^(m))

This is terrible is m is much larger than d but can bd faster than breadth if solutions are dense.

Think: imagine it's the last path checked.

Front 23

What is depth first space complexity

Back 23

O(bm) linear! Good!

Think: only one branch is stored in memory as once the bottom is reached it can be removed.

Front 24

Is depth first optimal

Back 24

No (optimal solution may be lower that first found one)

Front 25

What is the main advantage of depth limited

Back 25

Solves the issues around infinite m

Front 26

What's a disadvantage of depth limited

Back 26

May miss the solution

Front 27

What's the main advantages of iterative deepening

Back 27

Fixes issues around infinite m AND is complete

Front 28

What's an issue with iterative deepening

Back 28

Have to restart each time. However actually not that big of an issue.

Front 29

Is iterative deepening complete

Back 29

Yes

Front 30

Is iterative deepening optimal

Back 30

Yes (if step cost is constant)

Front 31

What is the time complexity of iterative deepening

Back 31

O(b^d)

Think: same as depth first but with d instead of m therefore better

Front 32

What is the space complexity of iterative deepening

Back 32

O(bd) same as depth first

Front 33

What issue does graph search ignore/ fix

Back 33

Repeated states

Front 34

What is the space complexity of graph search

Back 34

Linear

Front 35

Why do bi directional search?

Back 35

The time complexity is lower:

b^(d/2) + b^(d/2) is less than b^d

Front 36

How do you know a solution has been found using bi directional search?

Back 36

Before expanding a node check if it is in the fringe/open in the other search. If yes a solution has been found

Front 37

How do you do bi directional search if there are many goal states to work back from?

Back 37

Add a dummy node that all goal states lead to and start from there

Front 38

Describe best first search

Back 38

Use an evaluation function f(n) for each node and order the fringe based on that.

Front 39

Describe greedy best first search

Back 39

Let h(n) be the estimated cost from node to goal based on straight line distance. Therefore gbfs expands the node that seems closest to the goal

Front 40

Is gbfs complete

Back 40

No. (Can get stuck in loops like depth first if the heuristic is bad)

Front 41

What is gbfs time complexity

Back 41

O(b^m) but a good heurist can improve it a lot.

Front 42

What is gbfs space complexity

Back 42

O(b^m) keeps all nodes therefore same as time complexity

Front 43

Is gbfs optimal

Back 43

Mo

Front 44

Describe A* search

Back 44

Avoids paths that are already expensive. Uses evaluation function f(n) = g(n) + h(n)

Where g is cost so far

And h is estimated cost n to goal

So f us estimated cost of the total path through n

Front 45

What makes a heuristic admissible

Back 45

For every node n h(n) <= h*(n) where h*(n) is the TRUE COST.

Aka an admissible heuristic NEVER overestimates, it is optimistic

Front 46

Go look at the proof for A* heuristic being admissible

Back 46

Do you get it?!??

Front 47

What makes a heuristic consistent/ monotonic

Back 47

If for every node n, every successor n' of n generated by any action a :

h(n) <= c(n,a,n') + h(n)

I.e f(n) is non decreasing along any path

Front 48

Is A* complete

Back 48

Yes unless there are infinity nodes with lower cost than the solution

Front 49

Is A* optimal

Back 49

Yes (if heuristic is admissible in tree search or consistent for graph search)

Front 50

What is the time complexity of A*

Back 50

Exponential in length of optimal solution

Front 51

What is the space complexity of A*

Back 51

Keeps all expanded nodes in memory

(So I think also exponential ??)

Front 52

Describe how one heuristic dominates another

Back 52

If for every node a heuristic has a larger estimate than another while still being admissible it dominates the other

Front 53

Describe what a local search algorithm is

Back 53

Keeps a single current state and tries to improve it. Where the state space is a set of complete configurations and the goal is to satisfy some constraint. E.g. n queens

Only the goal is necessary not the steps to get there.

Front 54

Describe hill climbing search

Back 54

Moves in one direction while that direction is better. When it is no longer better stops and returns the current solution

Front 55

What is the issue with hill climbing

Back 55

Gets stuck in local maxima

Front 56

Describe simulates annealing search

Back 56

Hill climbing but allows some bad moves. Gradually decreases the likelihood of making bad moves.

Front 57

Is simulates annealing optimal

Back 57

Almost. If T decreases slowly enough then the probability of finding optimal solution approaches 1.

Front 58

Describe local beam search

Back 58

Keeps track of K states

Starr with K randomly generated states

At each iteration all successors of k are generated

If any one is a goal state stop. Else select the k best successors and repeat.

Front 59

Disadvantage of local beam search

Back 59

Can become focused in a small region of the state space

Front 60

Describe genetic algorithms

Back 60

A sucsessor is generated by combining 2 parent states

Population is k randomly gen states

Produce a new generation by selection, crossover, and mutation.

Front 61

What is a constraint satisfaction problem

Back 61

A problem where state is defined by variables with values from a domain.

The goal is a set of constraints specifying allowed combinations of values for subsets of variables

Front 62

What type of problem is map colouring

Back 62

CSP constraint satisfaction

Front 63

Varieties of CSP includes

Back 63

Discrete variables:

Finite domains e.g. SAT

Infinite domains e.g. job scheduling

Continuous variables:

E.g. start/end times for telescope observations????

Front 64

What are unary constraints

Back 64

Unary constraints involve a single variable e.g. SA= green

Front 65

What are binary constraints

Back 65

Binary constraints involve pairs of variables e.g. SA /= WA

Front 66

What are higher order constraints

Back 66

Higher order constraints involve 3 or more variables e.g. cryptarithmetic column constraints

Front 67

4 examples of real world CSP

Back 67

Assignment problems (who teaches what class)

Timetabling problems (which class is offered where and when)

Transportation scheduling

Factory scheduling

Front 68

Describe backtracking search

Back 68

Depth first search for CSP with single variable assignments

Front 69

How does backtracking search work

Back 69

Works down assigning randomly until reaching an impossibility, then goes up one step and goes down a different branch. Continues this until finding a solution. (Hopefully that makes sense later)

Front 70

Explain the difference between backtracking and depth first search

Back 70

backtracking applies one action to produce one successor node and continues down then only later if it has to revisit that node will it check if there were other successors.

Dfs contrastingly expands all successors each time and keeps them in the fringe.

Front 71

Name the general purpose methods that help chose what variable to assign next

Back 71

Most constrained variable

Most constraining variable

Least constraining value

Front 72

Describe most constrained variable

Back 72

The varibale with the fewest legal values. This is The minimum remaining values MRV heuristic

Front 73

Describe the most constraining variable

Back 73

The variable that constrains the most other variables.

Front 74

Describe the least constraining value

Back 74

The value that constrains other variables the least

Front 75

Describe the concept of forward checking

Back 75

Forward checking keeps track of remaining legal values for unassigned variables and terminates the search where any variable has no legal values left.

Front 76

Describe how you would apply local searches e.g. Hill climbing or simulated annealing to a CSP

Back 76

You would need to allow states to violate constraints

And have operators reassign variable values

Therefore randomly select any conflicted variable then select a value by using the min conflict heuristic (the value the violates the fewest constraints)

Front 77

Describe iterative min conflicts

Back 77

While not at a solution:

Pick a conflicted variable and change its value to the min conflicting value

Works well for n queens!

Front 78

What problems use local search

Back 78

Problems where only the solution matters.

The state space is a set of complete configurations.

Front 79

Alpha beta best possible complexity

Back 79

O(b^ d/2) if ordered from best to worst

Front 80

Minimax complexity

Back 80

O(b^d)

Front 81

Suggest a heuristic for planning problem

Back 81

Sub goal independence assumption. Assume the cost of a set of sub goals is equal to their combined sum