COEN 166 / 266

Project 1: Exploring a Search Space

We are given a set of points, some of which are connected by a direct path and the length of the paths. Given two points, we want to find the minimum distance path between them.

You are to implement this search using the various strategies on various problem sets. For each set and strategy, select randomly 100 different start and end points. Calculate the average number of nodes visited and their standard deviation. Then decide whether any strategy is better.

The strategies are

Try this out on the following sample files by calculating the distance between two arbitrary points. Repeat this 1000 times. Calculate the average number and the standard derivation of the number of points visited for each method and each file. The files are labeled by the total number of points. Each file contains the distance matrix of a graph in a tab separated format. The first line gives the first row of the distance matrix, etc. If there is no edge between the vertices, then the distance is set to UINT_MAX on an INT32 machine.

The files in the second column contais the same distance matrix, but with the location of the points in parentheses at the beginning of each line. The data file with 1000 nodes should stress your system and you cannot expect it to finish within seconds. The files in the third column contains the matrix and the points separately.

It is part of the project to verify the accuracy of your implementation of the algorithm.

Project 2: Autonomously Moving Agents in a Game

Games need to provide AI players with AI, but the processing cost of the AI needs be very limited. As a result, many of the more sophisticated AI algorithms cannot be deployed on current consoles and game programmers need to come up with simple solutions that are realistic. For this project, we will try to emulate the behavior of a flock of birds (in 2D) or grazing animals on a prairie (as they react to predators and obstacles).

Use the boid algorithm to create a flock of entities that move around in a 2D plane. If you want more of a challenge, have a predator wander around (or even chase when boids get too close,) or put in some simplistic obstacles (circles) that the boids will want to avoid.

Output: Coolest output results from using a 2d GUI that updates with a reasonable frame rate. You can do this relatively painless if you use C# on Visual Studio, Python with a graphics library installed or if you write a Java Applet. In this case, indicate the position of the boids with a simple marker (such as a small circle).

If you use something else, you might have to resort to ASCII art and view it in a text viewer consecutively. Do NOT spend all of your time getting really good output. That's the topic of a different course.

Project 3: CSP or More Difficult Alternatives

Alternative 1: Evaluate three different algorithms for the n-queens problem by measuring run-times. For example, you could use simple backtracking and backtracking with one or two heuristics.

Alternative 2: Implement group movement through a plane with obstacles. Basically, assume that I want to move groups of 5 tanks in wedge formation through a plain with muddy sinkholes. (This is quite a bit of work and assumes that you already dealt successfully with animation in project 2.

Alternative 3: Implement a "robots" like game. Robots is a game that you can find on many linux / unix machines that is designed to teach how to use the vi commands to move the cursor into any of the 8 directions. Each round of robots starts with random placement of robots and the player character on a rectangular playing field. The "robots" always move one step towards the character. The movement is predetermined. A good player can cause robots to crash into each other which creates a heap. Robots that run into the heap also crash and become part of the heap. When a or some robots are about to reach the player, the player has no moves left other than a random transport that places the player randomly on the map. If the player lands on a heap, a robot, or next to a robot, the player dies. The player receives points for each robot destructed and for finishing a round.

Your task is to create a robots game with AI control of the player and graphics that allow to watch the development of the game.

First challenge: Develop a heuristics with limited look-ahead that minimizes the number of random transports made by the player.

Second challenge: Change the behavior of the robots so that they randomly choose among the steps that gets them closer to the player.

Alternative 4: Write a program that presents and plays the "fox and hares" game on an 8 by 8 board. (Just getting the graphics reasonable is a challenge!)

Alternative 5: Expand on project 2 (if you are using a good GUI). Implement obstacle avoidance, predator wandering, and predator fleeing. Populate your game with a predator and obstacles.

Project 4: Neural Net Training

Train the 5 node three-layer ANN to calculate the XOR of the two inputs.

Extra credit: Train a three layer ANN to distinguish between a drawn X and a drawn O on a 4 by 4 grid.

Hand-In Procedures

You need to demonstrate the running of your project in person. Be ready to explain the code.

© 2009 Thomas Schwarz, S.J., COEN, SCU SCU COEN T. Schwarz COEN 166