HW2 : Adversarial Search, Learning, and Evolutionary Programming

Submission Guidelines

DUE Saturday March 24th 11:59 PM

Send the homework to: chipp@sci.brooklyn.cuny.edu as PLAIN TEXT or PDF.

Please DO NOT SEND WORD DOCUMENTS!!!

(Total Points 8)

Questions

1. Adversarial Search: Alpha-Beta Pruning (2 points)

Consider the Minimax Search Tree Expanded 2-ply, the square nodes are MAX nodes and the circular nodes are MIN nodes.

Conduct a Minimax Search (with Alpha-Beta Pruning) on this tree (in a depth-first manner searching from left to right like the examples in class). The values that the leaf-nodes will evaluate to are given in the bottom most MAX layer.

Show where alpha-beta pruning occurs, along with the final alpha-beta range values for each node that is searched (again in the same manner done in class).

2. Learning: Training a Single TLU (2 points)

Remember our Boudary Following Agent described in Lecture 3 (Simple Agents) and then revisited in our lectures on Neural Networks. The functions for it's production system are linearly seperable. Given this training set (composed of sensor readings mapped to the go-east action):

Show the Training of a Single TLU using:

   a. The Error-Correction method

   b. The Generalized Delta method

I suggest using a spreadsheet program (either Microsoft Excell or Google Spreadsheets) to conduct the training . Alternatively you may be more comfortable to write a small program to conduct the TLU training.

Compare the convergence of both techniques and discuss how you arrived at the learning rate utilized in your training for either case.

3. Evolutionary Agent: Traffic Signal Control System (2 points)

The New York City Department of Transportation's Traffic Management Center, maintains the Traffice Signal Control System (TSCS) for the 6000 traffic lights for the 5 bouroughs of New York City. An TSCS is an advanced system that adjust the amount of "green" time for each street and and coordinates operation between signals to maximize traffic flow and minimize delay based on real-time changes in demand. (They estimate that $10 billion a year is lost in local revenue due to traffic flow disruptions!)

Currently they are prototyping and deploying "intelligent" Intersection Traffic Signal System - which will not only be outfitted with communication capabilities to the Traffic Management Center in Queens, but also be able to run autonomously via it's own own board embedded computer (for stand-alone operation /and/ for autonomous reactions to local conditions). Since Traffic Flow Maintenance is such a complex system, one solution is to evolve an evolutionary agent to run the traffic signal for an intersection.

Pick a traffic intersection near where you live and observe the number of signal "actions" (outputs) and the conditions that an "intelligent" Intersection Traffic Signal agent might face with.

   1. Describe the genotype for a traffic signal program for your intersection. Describe it to a level that it could be implemented and evolved in tournament selection. Use Occam's Razor and keep your solution simple.

   2. Now specify the fitness function for use in evolving your intersection agent. Pseudo-code /or/ a simple mathematical description is sufficient. If you are having trouble and need some inspiration, spend more time observing the intersection and take a peek at this chapter on Traffic Control Signal Systems.

4. Genetic Programs: Crossover (2 points)

From our lecture on Genetic Programs, the crossover operation selects a random subtree in both parents. Comment on what you think the effects would be of biasing the random selection according to:

   1. Preferring those subtrees that were highly active during the fitness trials.

   2. Preferring larger subtrees to smaller ones, and vice versa.

  Source: Nils J. Nilsson (1998), "Artificial Intelligence: A New Synthesis", Morgan Kaufmann Publishers, Inc. p 69.

Last Updated 3/10/2007