CS188 lecture2

Today, we focus on searching methods, especially uninformed search methods.

Abstraction

• Agents that Plan Ahead
• Search Problems
• Uninformed Search Methods(dfs, bfs, uniform-cost search)

Planning Agents & Reflex Agents

Reflex agents:

• Choose action based on current percept (and maybe memory)
• May have memory or a model of the world’s current state
• Do not consider the future consequences of their actions
• Consider how the world IS

Reflex agents CAN be rational

Planning agents:

• Ask "what if"
• Decisions based on (hypothesized) consequences of actions
• Must have a model of how the world evolves in response to actions
• Must formulate a goal (test: eg "do you have an apple or not")
• Consider how the world WOULD BE

Search Problems

A search problem consists of:

• a state space
• a successor function (with actions, costs)
• a start state and a goal test

A solution is a sequence of actions (a plan) which

transforms the start state to a goal state

State Space Graphs

State space graph: A mathematical representation of a search problem:

• Nodes are (abstracted) world configurations
• Arcs represent successors (action results)
• The goal test is a set of goal nodes (maybe only one)

In a state space graph, each state occurs only once!

We can rarely build this full graph in memory (it’s too big), but it’s a useful idea

Search Trees

root node: start state

Every possible futures will become a vertex

A search tree:

• A “what if” tree of plans and their outcomes
• The start state is the root node
• Children correspond to successors
• Nodes show states, but correspond to PLANS that achieve those states
• For most problems, we can never actually build the whole tree

Every node occurs only once in state space graphs but not necessarily occurs only once in search trees.

Important: Lots of repeated structure in the search tree!

Searching with a Search Tree

Search:

• Expand out potential plans (tree nodes)
• Maintain a fringe of partial plans under consideration
• Try to expand as few tree nodes as possible

lec2-1

important ideas:

• Fringe
• Expansion
• Exploration strategy

Main question: which fringe nodes to explore

Depth-First Search(DFS)

Strategy: Expand a deepest node first.

Implementation: Fringe is a LIFO stack

Depth-First Search Properties

What nodes DFS expand?

• Some left perfix of the tree
• Could process the whole tree
• if m is finite, takes time \(O(bm)\)

DFS is NOT optimal, because it find the "left-most" solution.

Breadth-First Search(BFS)

Strategy: Expand a shallowest node first.

Implementation: Fringe is a FIFO queue.

Breadth-First Search(BFS) Properties

What nodes BFS expand?

• Processes all nodes above shallowest solution.
• Let depth of shallowest solution be s
• Search takes time \(O(n^s)\)

Takes time \(O(b^s)\)

It is optimal ONLY IF costs are all 1

DFS vs BFS

DFS will be better when you don't have enough space costs. In other words, when you have so many situations or you want to save time, DFS is better.

BFS will be better when all your costs are 1, it can give an optimal solution based on its strategy.

Iterative Deepening

Idea: get DFS's space advantage with BFS's time / shallow-solution advantages

Run a DFS with a depth limit, find all paths with depth limit. if no solution, update depth limit and do the search again.

Uniform Cost Search

Strategy: Expand a cheapest node first.(Greedy)

Fringe is a priority queue.

When we find a path costs n, we ensure that we have searched all the paths that costs smaller than n.

Uniform Cost Search (UCS) Properties

What nodes does UCS expand?

• Processes all nodes with cost less than cheapest solution
• If that solution costs \(C^*\) and arcs cost at least \(\epsilon\), then the "effective depth" is roughly \(\frac{C^*}{\epsilon}\)
• Takes time \(O(b^{\frac{C^*}{\epsilon}})\) (exponential in effective depth)

It is completely optimal

Uniform Cost Issues

UCS explores increasing cost contours.

disadvantages:

• Explores options in every "direction"
• No information about goal location

The One Queue

All these search algorithms are the same except for fringe strategies.

• Conceptually, all fringes are priority queues (i.e. collections of nodes with attached priorities)
• Practically, for DFS and BFS, you can avoid the log(n) overhead from an actual priority queue, by using stacks and queues
• Can even code one implementation that takes a variable queuing object