Dept. Colloquiua

CS 470   Artificial Intelligence,  Instructor:  Jeffrey Horn

COURSE ANNOUNCEMENTS (Monday, April 30, 2012)

What's REALLY New:

• Final Project.   I have details below.   Click here.

Not so New (Older Announcements):

• A5
• A3
• First quiz moved to Wed., Feb. 8.   Will be similar to the Practice Quiz, which we will discuss in class Monday, Feb. 6.   So try to do it before class!
• A3 is planned for Wed. (to be assigned, and up on the web by then)
• Reminder:  A2 due tomorrow, Monday, Feb. 6.
• Assignment 2 is now assigned, and is due next Monday, Feb. 6.   That's less than a week but it is a short assignment.
• We'll have our first quiz on Monday as well.   More info to follow...
• FYI:  We have an Educat account for this class!   I will use this primarily for posting grades.   (Nothing to post just yet!)
Please bring your notebook PC to class everyday, for interactive learning!
• Snow day today (NMU closed), Monday, Jan. 23, 2012
• Welcome to class!
• Please bring your laptop to class Monday, for interactive learning.
• This is where old announcements will go, so that you won't miss any news!

• Syllabus

• Lecture Notes

• Assignments

• Programming
• Tests and Quizzes

• Assignment 1:   Introduction to State Space Search (FWGC and Uninformed Search)
  • Assigned:   Monday, January 23, 2012
  • Due:  Monday, January 30, 2012
  • Code for A1 is here (cabbage.scm has the Scheme code and plt-301-bin-i386-win32.exe installs the older version of Dr. Scheme that has been confirmed to work with the source code in cabbage.scm. )
  • TASKS:
    1. Graph the entire State Space for the FWGC problem, as defined in class.
       • Each vertex represents a unique state.   Label each vertex with the state descriptor using Scheme syntax.
       • Use directed edges (i.e, single-head arrows as arcs) between states, labeling each edge to indicate the type of move (i.e., "F" for farmer only, "W" for farmer and wolf, "G" for farmer and goat, etc.)
       • Draw all states, including "illegal" states that violate one or more contraints of the problem, above.   Draw an "X" through all illegal states.
       • DO draw all edges going INTO illegal states.   DO NOT draw edges FROM illegal states.
       • Indicate the original problem by circling the initial and goal states and highlighting the path from initial to goal (i.e., "(w w w w)" to "(e e e e)" ).
    2. Answer the following questions:
       1. What is the longest plan that you can generate using the FWGC Scheme code provided in class?  Give me the length of the plan, the plan itself, and the problem (i.e., pair of initial and goal states).
       2. What can you say about the symmetry of the state space for FWGC?
       3. Give another problem (i.e., pair of initial and goal states) in the FWGC state space that yields a plan of at least length four.   (Give me the problem and a plan that solves it!)
• Assignment 2:   Introduction to Heuristic Search (Blocks World and Informed Search)
  • Assigned:   Wednesday, Feb. 1, 2012
  • Due:  Monday, Feb. 6, 2012
  • Submission:  Hardcopy or email is fine.    Just write it up CLEARLY!   And use the notation introduced below.
  • Code for A2 is here (block.scm. )
  • TASKS:   ( For all of the tasks below, assume the single goal state G = " ( (A) (B C) (D) ) "   )
    • Design your own heuristic for OUR Blocks World (the one in Scheme; see link above)
      • Your heuristic should be a function from blocks world states to a scalar value (actually, non-negative integers).  
      • Use the notation "h*(s)", where s is a state of the blocks world.  
      • The cost of a path or plan should be measured as the number of move operations (function calls) in the plan.
      • Your h*(s) should be an estimate of the cost of minimal cost path (plan) to get from s to the goal state G.
      • Your h*(s) should be admissible, which means it should be an underestimate of the actual cost
      • Your h*(s) should be as informed as you can make it!  (Well, that is your challenge.)
      • Be as specific and precise as possible in describing your function.   Feel free to use natural language, mathematical notation, and computer code (pseudocode or real code) to make clear what your function computes.   I will try to implement some of the heuristics (in Scheme!) for class on Wednesday (or perhaps the following Monday) so that we can test and compare each other's functions!  
    • Evaluate your heuristic on the following states (i.e., give me  h*(s₁ ),  h*(s₂ ),  and h*(s₃ )   ):
      1.   s₁ = ( ( A B C D) ( ) ( ) )
      2.   s₂ = ( (A) (B) (C D) )
      3.   s₃ = ( (B C) ( ) (D A) )
• Assignment 3:   A* Path Finding on 3D Terrain
  • Assigned:   Wednesday, Feb. 15, 2012
  • Due:  Wednesday, Feb. 29, 2012
  • Details here.
• Assignment 4:   The Perceptron (a linear classifier that learns)
• Assignment 5:  Genetic Algorithms for Intelligent Design (optimization)
  • Goal:  Become familiar with the GA and its application and behavior through optimization of a known, hard, and open problem (NYC Tunnels)
  • Tasks:
    1. Use the GA code in the folder "NYCtunnelsGA".  Run it on the NYC Tunnels problem with the following 10 random seeds:
       • 000xy, 111xy, 222xy, 333xy, 444xy, 555xy, 666xy, 777xy, 888xy, 999xy
       • where "xy" is your individual two digit number in the class (obtain from me).
    2. Experiment with the GA parameters until you get "good" performance using maximum 1,000,000 cost (that is, total number of fitness function evaluations, which you may upper bound as #gens * #popsize, unless you want to add the code to cache your function evaluations; that would give you more evolution!).  This means that you find the $38.79 million solution on at least one of your random seeds, and you find the second best known solution ($39.062 million on at least half of your random seeds).  
    3. Send me a text message or file with a list of the GA parameters that you used to complete Task 2 above, sufficient for me to REPRODUCE your results.
    4. Show me a plot of convergence for one of the runs.   You may print this or send me a screenshot, etc.   Label your plot (i.e., parameters, including random seed).   I want to see plots of on-line WORST, BEST, and AVERAGE fitnesses over time.  See example.

TESTS AND QUIZZES

Quizzes

• Q1: 

• Q2: 

• Q3: 

• Q4: 

• Q5:  Evolutionary Computation

Final

• Final Project:  Empirical Study of Rule Length vs. Number of Rules, in a Pittsburgh-style Learning Classifier System
  • Here is the code.  (There are two files there:  the java source code file and the BTSP data file.  Get both!)
  • Everyone needs to do XX runs, varying certain parameters.  The parameters that you need to change are all in the "main" function, lines 86-89:
    • Popsize:   Do all the runs below twice, once with popsize=1000, and once with popsize=2000.
    • RandomSeeds:   Everyone uses the same set of 10 seeds:  {0,1,2,3,4,5,6,7,8,9}.   So we are all doing 10 diff. runs at each setting of the other parameters.  
    • That's it!  Don't change crossover rate, mutation rate, maxNumGens, etc.   We all keep these the same.
    • For each of the two popsizes, I want you to do ten runs with the ten random seeds above, and calculate an average BestOfPop solutions from the final generations (gen 199) over the 10 runs.   This BestOfPop solution will be a number from 5000 to 10000, because it is the number of bits correctly predicted/classified by the rule set (individual) from the 10K bits in the training set.
    • Yes, you will have to recompile and run (as a Java application) for each of the twenty runs, changing the randomseed, and sometimes the popsize.   Feel free to write your own loops to do all the runs at once; then you can just let it run in the background while it saves the results to a file, perhaps.   But if you don't want to code you don't have to; you'll just have to babysit your experiments by changing parameters and re-compiling for each run, writing down your results somewhere.   Up to you!
    • Here are the parameter assignments: