COM316: Programming Assignments

Programs are due at the start of class. Programs delivered late will get partial credit, half credit will be given if it is turned in before the following class. No credit will be given after that. Programming assignments can be done in teams of no more than two students. Questions: email parker@conncoll.edu

Scheme #1a is due on Wednesday, 5 Sept.

Scheme #1b is due on Monday, 10 Sept.

Scheme #2 is due on Wednesday, 12 Sept.

Scheme #3 is due on Monday, 17 Sept.
grid-main.ss
grid-class.ss
grid-draw.ss
grid-make.ss
grid-search.ss

AI #1: Implement DFS and BFS. Your programs are due at the start of class on Wednesday, 24 Sept. Hand in a printout of the search code. You will have an opportunity to demo your program during class. Don't forget that your assigned reading and the answers to the standard questions are also due on 24 Sept.
grid-main.ss
grid-class.ss
grid-draw.ss
grid-make.ss
grid-new.ss
grid-queue.ss
grid-stack.ss

AI #2: Implement Branch and Bound with distance to goal estimates. Your program is due in class on Monday, 5 Oct 2009. You may use the DFS and/or BFS code available below. Hand in a printout of the changed code. You will have an opportunity to demo your program during class. It is your option to implement Best-First search or Hill Climbing with backtracking for a max score of 90. Don't forget that your assigned reading and the answers to the standard questions are also due on 5 Oct.
grid-DFS.ss
grid-BFS.ss

AI #3: Implement a real-time search strategy such as RTA*. Your program is due during class on Monday, 12 Oct 2009, although it will be accepted for full credit if complete before class on Wednesday, 14 Oct 2009. Hand in a printout of the changed code. You will have an opportunity to demo your program during class. Don't forget that your answers to the standard questions are due before class on Monday and that the assigned reading (Genetic Algorithms for the Development of Real-Time Multi-Heuristic Search Strategies) is also due for class on 12 Oct. Make sure your program counts the number of steps taken so we can compare it to other methods.

AI #4: Implement a Game Playing program with you being the goal or the robot (as assigned in class), with the robot chasing the goal. Your program is due before class on Monday, 19 Oct 2009. Hand in a printout of the changed code. You will have an opportunity to demo your program during class. Don't forget that the reading (A Chess Playing Program) and your answers to the standard questions are also due on 19 Oct.
Start out with the program below:
grid-chase.ss
grid-class.ss
grid-draw.ss
grid-get-next-goal.ss
grid-get-next-robot.ss
grid-main.ss
grid-make.ss
grid-new.ss
grid-priority-queue.ss
You may only modify one file (either grid-get-next-robot.ss or grid-get-next-goal.ss as assigned). The program should currently be so that each turn the robot moves to the best spot toward the goal and the goal moves to the best spot away from the robot. You are no longer required to keep track of paths or update the grid or anything. Just have each move one step. Use a 100x100 grid with an obstacle density from 5 to 25. The goal should stop when the robot is within one move from it. What you need to do now is modify your get-next file to include mini-max and a really good static evaluator. The program should work well in a variety of different obstacle densities. Make sure that all of your functions are unique. If you are the robot, put robot- at the front of each function name. If you are the goal, put goal- at the front of each function name.

AI #5: Create facts and rules that will allow you to reason about the search problem discussed in HW 5. Conceptualize a small grid (3x3) with a few obstacles and the robot and goal. Add facts and rules as required to search for the goal. Write a program that will return "finished" if there is a way from the robot to the goal. If you look at facts after this is run, you will find the nodes that were visited. Hand in a printout of the code. You will have an opportunity to demo your program during class. Don't forget that your answers to the standard questions are also due on 22 October.
My facts are:
(define facts '(goal22 visited00 obstacle11 obstacle21))
One of my rules list looks like this:
(define rules '(((visited00 goal00) (finished)) ... ))
... being one of several other rules.
You need to finish defining the rules and write two functions:
ModusPonens, which takes in a rule and checks to see if each of the symbols in the antecedent are in the facts list. If they are, you return the consequent. If not, return '(). BTW, my ModusPonens breaks each rule into its antecedent and consequent (which are both lists) and calls a helper function ModusPonens2 that calls itself recursively going through all of the symbols of the antecedent seeing if they are all facts. Remember that to check to see if -P is true you need to make sure P is not a fact. Check that ModusPonens works before going on. One more help: try (member 4 '(1 3 4 7 8)) and (member 4 '(1 3 7 8)) in your repl to see how member works. Now try (if (member 4 '(1 3 4 6 7)) 'x 'y)
Write search, which takes in an integer (call it count). It should continually go through the list of rules checking each with ModusPonens. If ModusPonens returns '() it knows that there is no new fact. If it returns the consequent, add the symbol (visited01, etc) in it to the list of facts. Sine the consequent (what-is-returned) is in the form of a list, the way I did this was to set! facts to (append what-is-returned facts). This puts the new facts up front. The way I go through the rules is to try the car of rules (first rule) and then set! it to the end of the rules so that the next rule will be the next one in line. So I continually rotate through the rules. You can use count to keep track of how many rules you've gone through without making a new fact, or do the simple thing and count how many times search is called and stopping after 1000 or so (enough to make sure you've exhausted all possibilities). Return "not found" if the goal can't be reached. Return "goal found" if it can be reached. This should work on any possible 3x3 terrain, not just my example. You do not need to show the path although you could find possible paths by looking at your facts.
This is to simulate a robot thinking using the facts and rules. The use of the grid is not necessary. The program only returns text: "not found" or "goal found". It only takes one file to program. I've included one to help you get started. No other files or even functions are required; just complete the define and the functions not completed.
propSearch.ss
OK, that should be more than enough hints. Have fun, you're programming a reasoning machine.
For an extra credit point (for example, receive an 11 instead of a 10), add the rules needed to consider high and stable as factors.

AI #6 is due on Monday, 2 Nov. See FirstOrderLogic by Dr. Jonathan Hodgson for optional reading.
My propSearch.ss.

AI #7 is due on Monday, 9 Nov.
grid-class.ss
grid-draw.ss
grid-main.ss
grid-make.ss
grid-new.ss
grid-ProductionSystem.ss
Don't forget to do the reading and your answers to the standard questions.

AI #8 is due on Monday, 16 Nov. Ensure that your work is complete and printed before class starts.

AI #9 is due on Wednesday, 18 Nov. Ensure that your work is complete and printed before class starts.

AI #10 is due on Monday, 23 Nov. Ensure that your work is complete and printed before class starts.
See Frames and Concept Learning for assistance.

Return to the COM316 Home Page