cmsc421 ch3

Tradeoffs for search algorithms

amount of time search takes vs amount of memory available vs quality of solution

Heuristic function

provides domain dependent knowledge via estimating how far a given state is from the goal or by precomputing partial solutions involving patterns or landmarks

What must be formulated before agent can start searching

well-defined problem

What does a well-defined problem consist of

initial state, set of actions, transition model describing results of actions, a set of goal states, and action cost function

How is the environment of a problem represented

via state space graph

How to arrive at solutions in state space graph

take path through state space, which is a sequence of actions, from initial state to goal state

How do search algorithms treat states and actions

states and actions are treated as atomic, without any internal structure

How are search algorithms judged

by completeness, cost optimality, time complexity, and space complexity

How do uninformed search methods work

by having access to only problem definition, algorithms build search tree in an attempt to find a solution.

How do uninformed search algorithms differ

differences arise based upon which node algorithm expands upon first

What type of search is best-first search

uninformed

What type of search is breadth-first search

uninformed

What type of search is uniform-cost search

uninformed

What type of search is depth-first search

uninformed

What type of search is iterative deepening search

uninformed

What type of search is bidiretional search

uninformed

Best-First search

selects nodes for expansion using an evaluation function

Breadth-First search

expands the shallowest nodes first; it is complete, optimal for unit action costs, but has exponential space complexity

Unit action cost

every action in state space (aka environment) has identical cost

How does uniform-cost search work

expands the node with lowest path cost, g(n), and is optimal for general action costs

Depth-first search

expands deepest unexpanded node first. Neither complete not optimal but has linear space complexity. Depth limited search adds a depth bound

Iterative Deepening Search

calls depth-first search with increasing depth limits until a goal is found. Complete when full cycle checking is done, optimal for unit action costs, has time complexity similar to bfs and has linear space complexity

Bidirectional Search

Greedy best-first search

expands nodes with minimal h(n) aka solution cost. Not optimal but often efficient

Cost-Optimal

algorithm is guaranteed to find the absolute lowest-cost path/solution among all possible solutions. Cares entirely about quality of final output

Efficient

algorithm judged based on amount of resources (time and memory) it consumes to find a solution. In AI search, this is measured by number of nodes it expands or states it explores before reaching goal

Optimal but not efficient

algorithm can be guaranteed to find perfect, lowest-cost solution, but might take long time or expand immense number of unnecessary states to get to solution

Efficient but not optimal

algorithm can be incredibly fast, pinpointing solution almost immediately while expanding very few nodes, path it finds may be highly suboptimal

Optimal and Efficient

algorithm can find absolute cheapest path while simultaneously expanding the absolute minimum number of states necessary to prove the path’s optimality

A* search

Bidirectional A* search

is sometimes more efficient than A* itself

IDA*

iterative deepening version of A*, and thus addresses the space complexity issue

RBFS and SMA*

Recursive Best-First Search and Simplified Memory Bounded A* are robust, optimal search algorithms that use limited amounts of memory; given enough time, they can solve problems for which A* runs out of memory for.

Beam Search

puts a limit on the size of the frontier (leaf nodes of current tree, aka unexplored nodes). Makes it incomplete and suboptimal, but finds reasonably good solutions and runs faster than complete searches

Weighted A*

focuses search towards a goal, expanding fewer nodes, but sacrificing optimality

What type of search is greedy best-first search

What type of search is A* search

informed

What type of search is bidirectional A* search

informed

What type of search is IDA* (iterative deepening A*) search

informed

What type of search is RBFS (recursive best-first search)

informed

What type of search is SMA* (simplified memory bounded A*)

informed

What type of search is beam search

informed

What type of search is weighted A* search

informed

What do heuristic search algorithms depend on

quality of heuristic function aka function that estimates how far off given state is off goal

How to construct good heuristics

relax problem definition, store precomputed solution costs for subproblems in a pattern database, defining landmarks, or learning from experience with the problem class

Landmark

a specific vertex in the graph where optimal path costs to and from every other vertex are precomputed and stored in memory. During active search, these precomputed costs are used to instantly estimate distance between current state and goal.

Environments that are episodic, single-agent, fully observable, deterministic, static, discrete, and completely known

An environment that is completely predictable, fully visible, changes only when the single agent takes an isolated, step-by-step action, and has completely known rules. All chapter 3 search algorithms operates in such environment