Exam 2

Question 1

What does a reflex agent do?

Answer 1

It chooses an action based on it’s current percept (memory), and doesn’t consider the consequences (which may make it irrational)

Question 2

What does a planning agent do?

Answer 2

It makes a decision based on an evaluation of future action sequences

Question 3

What does a search algorithm assume?

Answer 3

A known deterministic transition model, discrete states and actions, full observability, and atomic representation

Question 4

What is goal formulation?

Answer 4

Based on the current situation and the agent’s performance measure, first step in problem solving, meant to limit objectives and hence the actions to be considered

Question 5

What is problem formulation?

Answer 5

The process of deciding what actions and states to consider, given a goal

Question 6

What’s the difference between a search and an execution?

Answer 6

The search simply looks for a sequence of actions that reaches the goal until it’s found, while the execution is the actual doing of the actions in the solution, typically one at a time

Question 7

What does a search problem consist of?

Answer 7

A state space (S), initial state (S0), Actions (A(S)), transition model (Result(s,a)), goal test (G(S)), and action cost (c(s,a,s’))

Question 8

What makes a solution optimal?

Answer 8

It has the lowest cost among all possible solutions

Question 9

What makes an open-loop system?

Answer 9

The agent ignores percepts which breaks the loop between the agent and environment

Question 10

What makes a closed-loop system?

Answer 10

The agent monitors its percepts, since the environment may be nondeterministic

Question 11

What is a state space graph?

Answer 11

A mathematical representation of a search problem with nodes being abstracted configurations and arcs representing transitions; Each state occurs only once

Question 12

What does a search algorithm do?

Answer 12

It takes a search problem as an input and returns a solution (or indication of failure)

Question 13

What is a search tree?

Answer 13

Essentially a “what-if” tree of plans and outcomes with the root node being the start state and the rest of the nodes showing states (but correspond to plans that achieve these states)

Question 14

Do we usually construct the entire state space graph or search tree?

Answer 14

No, it would take up too much memory

Question 15

What is the frontier of a search?

Answer 15

Set of all current leaf nodes

Question 16

What separation does the frontier create in a state-space graph?

Answer 16

An interior region where every state has been expanded and an exterior region of states that have not yet been reached

Question 17

Are search trees and state-space graphs the same?

Answer 17

No, they are two different structures

Question 18

How does a priority queue work in search algorithms?

Answer 18

It first pops the node with the minimum cost according to some evaluation function, f(n)

Question 19

What is a cycle/loopy path?

Answer 19

A path that visits the same state/node

Question 20

How does a redundant path differ from a loopy path?

Answer 20

A redundant path has the same initial and final state in it’s path but with unnecessary states that increase the total path cost

Question 21

What are the 4 components of a node?

Answer 21

node.State, node.Parent, node.Action, node.Path-Cost

Question 22

What are the 4 ways that performance is evaluated?

Answer 22

Completeness, optimality, time complexity, and space complexity

Question 23

How is complexity measured?

Answer 23

Depth/number of actions in an optimal solution (d), maximum number of actions in any path (m), and branching factor/number of successors of a node that need to be considered (b)

Question 24

What makes a search algorithm uninformed?

Answer 24

It only uses information provided in problem formulation and only distinguishes goal states from non-goal states

Question 25

Describe breadth-first search (BFS)

Answer 25

Expands the shallowest node first, uses a FIFO queue frontier, goal test is performed when a node is generated (before the node is added to the frontier)

Question 26

What is the BFS performance?

Answer 26

Complete (d must be finite), optimal (if costs are equal, usually not), TC = O(b^d), SC = O(b^d)

Question 27

Describe uniform cost search (UCS)

Answer 27

Expands the node with the lowest path cost g(n), uses a priority queue with the priority being cost, goal test is performed when the node is popped

Question 28

What is the UCS performance?

Answer 28

Complete (assuming C, optimal solution cost, is finite and epsilon, minimum arc/action cost, > 0), optimal, TC = O(b^(C/epsilon)), SC = O(b^(C*/epsilon))

Question 29

Describe depth-first search (DFS)

Answer 29

Expands the deepest node in the current frontier, uses a LIFO queue frontier, goal test is done after popping a node from the frontier

Question 30

What is the DFS performance?

Answer 30

Complete (only with graph-searches), Not optimal (with either graphs or trees), TC = O(b^m), SC = O(bm)

Question 31

Describe depth-limited search (DLS)

Answer 31

Essentially DFS with a single predetermined depth limit l

Question 32

What is the DLS performance?

Answer 32

Incomplete (if l < d), not optimal (if l > d), TC = O(b^l), SC = O(bl)

Question 33

Describe iterative deepening search (IDS)

Answer 33

Essentially DLS but reiterates, starting with the lowest l and finishing to where l = d

Question 34

What is the IDS performance?

Answer 34

Complete (when b is finite), optimal (when path costs are identical), TC = O(b^d), SC = O(bd)

Question 35

Describe bidirectional search

Answer 35

Simultaneously searches forward from initial state and backwards from goal state, uses other preexisting search algorithm to do so. Solution is found when the two frontiers collide

Question 36

What is the bidirectional search performance?

Answer 36

Complete (if goal states are clear), optimal (if goal states are clear), TC = O(b^(d/2)), SC = O(b^(d/2))

Question 37

What is a heuristic?

Answer 37

A function that estimates how close a state, usually node n, is to a goal, h(n)

Question 38

What queue do heuristic searches usually use?

Answer 38

Priority queues where the priority is based on decreasing order of desirability

Question 39

Describe greedy search

Answer 39

f(n) = h(n), expands a node that seems to be closest to the goal

Question 40

What is the greedy search performance?

Answer 40

Incomplete (may get stuck in a loop, but is complete in finite state spaces), not optimal, TC = O(b^m), SC = O(b^m)

Question 41

Describe A* search

Answer 41

f(n) = g(n) + h(n), avoids expanding paths that are already expensive, combines UCS and greedy search advantages

Question 42

What is the A* search performance?

Answer 42

Complete, optimal, TC = O(b^m), SC = O(b^m)

Question 43

What does the explored set look like for informed algorithms?

Answer 43

Like hash tables, or Python’s dictionaries

Question 44

Describe IDA* search

Answer 44

Essentially A* with a reiterating aspect (such as how IDS belongs to DFS), doesn’t keep all reached states in memory, reiterates with the cutoff being the f-cost (g+h); each iteration, cutoff value is the smallest f-cost of any node (works as contours)

Question 45

Describe recursive best-first search (RBFS)

Answer 45

Uses only linear space, uses f-limit to keep track of the f-value of the best alternative path available from any ancestor of the current node; if current nude exceeds this limit, recursion unwinds back to the alternative path

Question 46

Describe simplified memory-bounded A* (SMA*)

Answer 46

Essentially A* with a memory limit; when/if the memory limit is reached, the oldest worst leaf node (highest f-value) is dropped and its f-value is backed up to its parent

Question 47

What makes a heuristic admissible?

Answer 47

If 0<=h(n)<=h(n), where h(n) is the true cost to the nearest goal and h(n) is just the estimated cost to the nearest goal

Question 48

What makes a heuristic consistent?

Answer 48

If h(n)<=c(n,a,n’)+h(n’), where n’ is the successor node of node n

Question 49

What’s the relation between consistency and admissibility of a heuristic?

Answer 49

All consistent heuristics are admissible but not vice versa

Question 50

How do search contours work?

Answer 50

Each contour is labeled with a value, in which every node has f(n) = g(n) + h(n) <= value

Question 51

Describe a graph search

Answer 51

Tree search with a set of expanded states, expand the search tree node-by-node but never expand a state twice

Question 52

What are the points of creating admissible heuristics?

Answer 52

Needed to solve hard search problems optimally, often are solutions to relaxed problems (the same problems with lesser constraints/assumptions)

Question 53

How can you tell if one heuristic is better than another?

Answer 53

If that one heuristic dominates the other: for example, h2(n) >= h1(n), h2(n) is the better/dominant heuristic