Exam 2 Flashcards
Chapter 3 - Uninformed and Informed Searches
What does a reflex agent do?
It chooses an action based on it’s current percept (memory), and doesn’t consider the consequences (which may make it irrational)
What does a planning agent do?
It makes a decision based on an evaluation of future action sequences
What does a search algorithm assume?
A known deterministic transition model, discrete states and actions, full observability, and atomic representation
What is goal formulation?
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
What is problem formulation?
The process of deciding what actions and states to consider, given a goal
What’s the difference between a search and an execution?
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
What does a search problem consist of?
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’))
What makes a solution optimal?
It has the lowest cost among all possible solutions
What makes an open-loop system?
The agent ignores percepts which breaks the loop between the agent and environment
What makes a closed-loop system?
The agent monitors its percepts, since the environment may be nondeterministic
What is a state space graph?
A mathematical representation of a search problem with nodes being abstracted configurations and arcs representing transitions; Each state occurs only once
What does a search algorithm do?
It takes a search problem as an input and returns a solution (or indication of failure)
What is a search tree?
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)
Do we usually construct the entire state space graph or search tree?
No, it would take up too much memory
What is the frontier of a search?
Set of all current leaf nodes
What separation does the frontier create in a state-space graph?
An interior region where every state has been expanded and an exterior region of states that have not yet been reached
Are search trees and state-space graphs the same?
No, they are two different structures
How does a priority queue work in search algorithms?
It first pops the node with the minimum cost according to some evaluation function, f(n)
What is a cycle/loopy path?
A path that visits the same state/node
How does a redundant path differ from a loopy path?
A redundant path has the same initial and final state in it’s path but with unnecessary states that increase the total path cost
What are the 4 components of a node?
node.State, node.Parent, node.Action, node.Path-Cost
What are the 4 ways that performance is evaluated?
Completeness, optimality, time complexity, and space complexity
How is complexity measured?
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)
What makes a search algorithm uninformed?
It only uses information provided in problem formulation and only distinguishes goal states from non-goal states
Describe breadth-first search (BFS)
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)
What is the BFS performance?
Complete (d must be finite), optimal (if costs are equal, usually not), TC = O(b^d), SC = O(b^d)
Describe uniform cost search (UCS)
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
What is the UCS performance?
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))
Describe depth-first search (DFS)
Expands the deepest node in the current frontier, uses a LIFO queue frontier, goal test is done after popping a node from the frontier
What is the DFS performance?
Complete (only with graph-searches), Not optimal (with either graphs or trees), TC = O(b^m), SC = O(bm)
Describe depth-limited search (DLS)
Essentially DFS with a single predetermined depth limit l
What is the DLS performance?
Incomplete (if l < d), not optimal (if l > d), TC = O(b^l), SC = O(bl)
Describe iterative deepening search (IDS)
Essentially DLS but reiterates, starting with the lowest l and finishing to where l = d
What is the IDS performance?
Complete (when b is finite), optimal (when path costs are identical), TC = O(b^d), SC = O(bd)
Describe bidirectional search
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
What is the bidirectional search performance?
Complete (if goal states are clear), optimal (if goal states are clear), TC = O(b^(d/2)), SC = O(b^(d/2))
What is a heuristic?
A function that estimates how close a state, usually node n, is to a goal, h(n)
What queue do heuristic searches usually use?
Priority queues where the priority is based on decreasing order of desirability
Describe greedy search
f(n) = h(n), expands a node that seems to be closest to the goal
What is the greedy search performance?
Incomplete (may get stuck in a loop, but is complete in finite state spaces), not optimal, TC = O(b^m), SC = O(b^m)
Describe A* search
f(n) = g(n) + h(n), avoids expanding paths that are already expensive, combines UCS and greedy search advantages
What is the A* search performance?
Complete, optimal, TC = O(b^m), SC = O(b^m)
What does the explored set look like for informed algorithms?
Like hash tables, or Python’s dictionaries
Describe IDA* search
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)
Describe recursive best-first search (RBFS)
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 node exceeds this limit, recursion unwinds back to the alternative path
Describe simplified memory-bounded A* (SMA*)
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
What makes a heuristic admissible?
If 0<=h(n)<=hstar(n), where hstar(n) is the true cost to the nearest goal and h(n) is just the estimated cost to the nearest goal
What makes a heuristic consistent?
If h(n)<=c(n,a,n’)+h(n’), where n’ is the successor node of node n
What’s the relation between consistency and admissibility of a heuristic?
All consistent heuristics are admissible but not vice versa
How do search contours work?
Each contour is labeled with a value, in which every node has f(n) = g(n) + h(n) <= value
Describe a graph search
Tree search with a set of expanded states, expand the search tree node-by-node but never expand a state twice
What are the points of creating admissible heuristics?
Needed to solve hard search problems optimally, often are solutions to relaxed problems (the same problems with lesser constraints/assumptions)
How can you tell if one heuristic is better than another?
If that one heuristic dominates the other: for example, h2(n) >= h1(n), h2(n) is the better/dominant heuristic
