Writing Tablet Screenshare:
10.107.75.162:8080

Announcements/Logistics


Campuswire does NOT
send email notifications!

RECAP


What is an intelligent agent?

Consider a Roomba (a robot vacuum)


  • Percepts
  • Interactions
  • Learning/Inference
  • Rationality

How about Netflix/Youtube/Amazon Recommendations?


  • Percepts
  • Interactions
  • Learning/Inference
  • Rationality

Categorizing AI Environments


  • Fully Observable v/s Partially Observable
  • Single Agent v/s Multi Agent
  • Deterministic v/s Non-Deterministic
  • Episodic v/s Sequential
  • Static v/s Dynamic
  • Discrete v/s Continuous
  • Known v/s Unknown

SEARCH


Assume a Fully Observable, Static, Deterministic, Known environment (for now)


Let us try and formalize the following problems.

Route Planning


  • Start & End State
  • Successor/Transition Function (Action & Cost)
    • When riding the T?
    • When driving?
  • State Space

Maze Solving


  • Start & End State
  • Successor/Transition Function (Action & Cost)
  • State Space

8 Puzzle


  • Start & End State
  • Successor/Transition Function (Action & Cost)
  • State Space
    • How many possible states?

State Space Graph


Nodes: States or World Configurations

Edges: Actions

Edge Weights: Cost of Action

Path: Sequence of Actions

Solution: A Path leading from Start to Goal

Depth First Search


From start state, explore leftmost branch until end.

If goal not found, backtrack and continue.


Let's try this on an example!

Depth First Search


Is DFS complete?

Is DFS optimal?


How would you implement it?


Hint: Stacks or Recursion!

Depth First Search


Let's check out how stupid DFS can be.

Breadth First Search


From start state, explore all neighbors.

If goal not found, explore all neighbors of neighbors.


Let's try this on an example!

Breadth First Search


Is BFS complete?

Is BFS optimal?


How would you implement it?


Hint: Queues!

Breadth First Search


Let's check out how expensive BFS can be.

A Hybrid Approach - Iterative Deepening


Run DFS limited to depth of 1.

Run DFS limited to depth of 2.

...

Run DFS limited to depth of n.


A Hybrid Approach - Iterative Deepening


Is Iterative Deepening complete?

Is Iterative Deepening optimal?


What do BFS, DFS & IDS have in common?


Not Cost Sensitive!

Uninformed Searches - no clue if getting closer to goal

Unnecessary Search Tree Expansion


What can we do?

Next Class


Uniform Cost Search

Hill Climbing

Intro to Heuristics