Recent Changes - Search:
AIfall10 /

LectureBlog

Home Assignments Lecture Blog Resources Project Discussion Group

Note: Right-click on any image to open it in hi-res.

Final Exam Review Session: Wed Dec 15

Meeting 41: Fri Dec 10

  • This was the final project expo! Here is a link to the Projects.

Meeting 40: Wed Dec 8

Meeting 39: Mon Dec 6

  • more on HMMs from earlier handout
  • sometimes-fair-casino HMM

Meeting 38: Fri Dec 3

  • Discuss SoM Ch 20
  • Went over Template Project
  • Brainstormed questions for MM (see newsgroup)

Meeting 37: Wed Dec 1

  • Debriefed project plans

Meeting 36: Mon Nov 29

  • Discuss SoM Ch 19
  • intro HMMs
  • Minsky will join for Skype chat on Wed Dec 8

Meeting 35: Wed Nov 24

  • Discuss SoM Ch 18

Meeting 34: Mon Nov 22

  • final project proposals returned with feedback
  • FP Deliverable One Guidelines
  • Discuss SoM Ch 17
  • Work through AIMA Ch 14 problems 14.1, 14.6, and 14.14

Meeting 33: Fri Nov 19

  • Discuss literacy and the brain article
  • Derive P(Alarm|Earthquake) using Bayes Net theory since we don't have JPD

Meeting 32: Wed Nov 17

  • Discuss SoM Ch 16
  • Intro to Bayes nets

Meeting 31: Mon Nov 15

Meeting 30: Fri Nov 12 

       November 2010
    Su Mo Tu We Th Fr Sa
     7  8  9 10 11(12)13   we are here
    14 15 16 17 18 19 20
    21 22 23 24 xx xx 27   Thanksgiving 
    28 29 30  1  2  3  4   December 2010
     5  6  7  8  9 xx 11   last day of class->FPs due
    12 13 14 15 16 xx 18   12/17 8am: final & proj papers due
Summary: There is one month left (minus Thanksgiving) + 1 week before final
Plan: work on FPs in parallel with last problem set
FP Schedule:
  • Fri 11/19: FP proposal due (real one)
  • Wed 11/24: 1st deliverable
  • Fri 12/03: 2nd deliverable
  • Fri 12/10: project presentations (working code + 1-pg writeup)
  • Fri 12/17: project papers due
PS4 schedule TBA

Meeting 29: Mon Nov 8

Meeting 28: Fri Nov 5

Meeting 27: Wed Nov 3

  • discussed bridge question again (q6 from ps)
  • feature functions & linear combinations
  • look at feature code in Pac-Man
  • upside down flying helicopters (ponies)

Meeting 26: Mon Nov 1

  • discussed SoM 13
  • final project proposal 1 handed back & example proposal & discussion
  • final project proposal 2 assigned
  • discuss PS3 question 6 -- where is the goal; what is the optimal policy; how do you learn it
  • problem with strict Q-learning of states

Meeting 25: Fri Oct 29

  • reinforcement learning notes handed out
  • discussed SoM 12.7-12.12

Meeting 24: Wed Oct 27

Meeting 23: Mon Oct 25

  • discuss mouse science NPR story
  • go over final project pitch 1 assignment
  • policy iteration
  • reinforcement learning
  • Attach:91420_543_rl.pdf

Meeting 22: Fri Oct 22

  • quiz

Meeting 21: Wed Oct 20

  • quiz review
  • see repository of Berkeley quizzes here: http://inst.eecs.berkeley.edu/~cs188/sp09/exams/
  • don't worry about stuff we didn't do (e.g., CSPs) or stuff that will be tested later (e.g., MDPs)
  • everything else is fair game -- these are good questions

Meeting 20: Mon Oct 18

  • SoM 11.1 - 11.4 discussed
  • alternation between q-values being computed and state values being updated in Bellman value iteration algorithm
  • discussed how varying noise, discount, and reward parameters can lead to different paths, per question 3
  • looked at the code for PS3a

Meeting 19: Fri Oct 15

  • assignments update: PS3a assigned; Quiz 1 Oct 22
  • SoM 10.5-10.9 discussed
  • Bellman equations and value iteration
  • policy iteration

Meeting 18: Wed Oct 13

Meeting 17: Tue Oct 12

  • Bytes and Brains discussion
  • What is a Markov process? Each chance is independent of previous events
  • Additive vs. discounted methods for calculating utility (γ as discount factor)
  • Policy: pre-determined series of choices for actions given state
  • Expected utility: sum over states given policy choices, probabilities, and discounting
  • Attach:91420_543_MDPs.pdf

Meeting 16: Fri Oct 8

  • PS1c returned
  • NYT “NELL” article
  • Attach:91420_543_meu_utilities.pdf
  • more about Expectimax
  • utility functions and maximum expected utility
  • cash example
  • Gridworld and Markov Decision Processes

Meeting 15: Wed Oct 6

  • demo won't eat one-dot problem
  • SoM 10.1 - 10.4
  • alpha-beta
  • expectimax & demo

Meeting 14: Mon Oct 4

  • Fred's SoM example (walk through the woods)
  • SoM 9.x
  • talked through what's required to deal with multiple ghosts in minimax
  • tried to figure out why Pac-Mac doesn't food when it can (turns out that this only occurs when there's exactly one nearby dot; he doesn't care if he eats it now or later)

Meeting 13: Fri Oct 1

  • went over reflexAgent code
  • “When Pac-Man believes that his death is unavoidable, he will try to end the game as soon as possible because of the constant penalty for living.”

Meeting 12: Wed Sep 29

  • Adversarial search! Multi-Agent project
  • ⚠ (:html:) <a href="http://inst.eecs.berkeley.edu/~cs188/fa09/slides/FA09%20cs188%20lecture%206%20%2d%2d%20adversarial%20search%20(2PP).pdf">Berkeley minimax slides</a> (:htmlend:) ... starting at Slide 19 / Page 10 of PDF
  • Attach:adversarial.txt
  • tic-tac-toe game tree
  • min-max example
  • alpha-beta example
  • ⚠ (:html:) <a href="http://inst.eecs.berkeley.edu/~cs188/fa09/slides/FA09%20cs188%20lecture%207%20--%20expectimax%20search%20(2PP).pdf">Berkeley alpha-beta pruning slides</a> (:htmlend:)

Meeting 11: Mon Sep 27

  • PS1c due Wed; grad student papers due Fri
  • relaxed problems Attach:relaxed.txt slides 31+ showing 8-puzzle & heuristics
  • comparing performance of IDS, heuristic h1 (# of misplaced tiles), & heuristic h2 (sum of Manhattan distances over all tiles)
  • another intuitive way of understanding admissible: never leads you astray by telling you things are worse than they are. This would cause you to prune a subbranch that would otherwise be explored, if the heuristic weren't telling you things were bad this way.
  • Berkeley food search problem

Meeting 10: Fri Sep 24

  • handed out solution code for aStarSearch, Node, and graphSearch (do not redistribute)
  • handed out starterCornersHeuristic.py
  • tried large constant heuristic on CornersHeuristic -> same as using zero as the heuristic
  • tried using a random number as the heuristic -> expanded fewer nodes, but found worse solutions
  • used distance to nearest corner as heuristic (idea we had previously, as implemented in starterCornersHeuristic) and it was better than UCS: found optimal solution with fewer nodes expanded
  • had long conversation about what is the impact of the heuristic value going down as a food dot gets eaten (does it get eaten as the search expands? yes.) in the context of talking about a consistent vs. a merely admissible heuristic
  • yes, the “distance to nearest corner” heuristic is lame (and we knew that) because it is not consistent, but (a) it's an admissible heuristic and (b) it does improve things over UCS
  • what are better heuristics? something that's also consistent, involving TSP search over remaining dots? Distance to nearest + distance from that dot to another (if there are more than one left)?

Meeting 9: Wed Sep 22

  • PS1a graded & handed back
  • how did PS1b go?
  • CornersProblem solution handed out in hard-copy form – please do not redistribute electronically in any fashion
  • recap:
    • complete == will always find solution if there is one (DFS is not if search space is infinite)
    • optimal == will always find best solution if there are more than one
    • heuristic: if admissible, never overestimates, then, can provably avoid expanding nodes that are demonstrably bad while expanding nodes that may still be better, thereby guiding complete & optimal search to be more (optimally) efficient
  • read through CornersProblem code, and figured out the evil line of code that simultaneously determines if a given action will take us to a corner, and then rebuilds the visited-array:
newVisited = tuple([v or (nextx,nexty) == corner for v, corner in zip(visited, self.corners)])
  • then realized that the state representation for the CornerSearch problem is a two-element array [pos, visited], where pos is an x,y coordinate and visited is a 4-element list of true/false values, indicating whether the corresponding corner has been visited.

Meeting 8: Mon Sep 20

  • Attach:lec8-notes.txt
  • started the CornersProblem with heuristics problem
  • proposed distance to nearest corner as a heuristic
  • discovered properties of heuristics: (a) must be fcn of state, so they tell you where to go, (b) must be easily calculable

Meeting 7: Fri Sep 17

Meeting 6: Wed Sep 15

  • Informed (heuristic) search: A* search
  • solving the IGVC Nav Challenge with A*

Meeting 5: Mon Sep 13

Meeting 4: Fri Sep 10

  • recap again def'n of search problem
  • walk thru a breadth-first and depth-first search
  • python intro
  • Attach:util.py.pdf Attach:search.py.pdf
  • running the tinyMazeSearch -- it just outputs a fixed list of directions
  • delving to depthFirstSearch

Meeting 3: Wed Sep 8

Meeting 2: Fri Sep 3

  • sign up for Google Group at the class home page
  • tweet using @fgmart
  • Attach:lec2-notes.txt
  • adjacent fields to AI
  • Computational Sustainability AI
  • properties that make it search: observable environment, discrete states, deterministic actions
  • definition of search problem: an initial state, a set of actions (as a fcn of state), transition model (aka, successor fcn of state and action), goal test, and path cost.
  • analyzed Arad-Bucharest map, with and without path costs noted
  • straight-line distances will be useful in heuristic search (which we will do later) – now, we're doing uninformed search.

Meeting 1: Wed Sep 1

  • how to get textbooks (buy them used w/link on course home page)
  • course policies and syllabus
  • approach for working with Minsky SOM text (daily readings and daily "tweet"-style writeups)
  • what is AI? see discussion on whiteboard
  • Russell and Norvig's agent model of AI (Chap 2 stuff)
  • Berkeley AI class's quick history of AI