A few more notes about the project

1. Although I’ve given you a very specific chunk of code, don’t feel that there is an absolute right answer for each question, or that we’ll be using an autograder or anything like that (we don’t plan to). In general I expect that we’ll be depending a lot more on your reports (where you explain your implementation and show some of the output) than on the code itself. The code is just there to back up your claims.

2. Be sure to check out the comments (see the recent comments listing to the right). Lots of good information.

3. When you run into problems, post your questions. We’ll answer them as best we can.

Read Full Post »

Modifications to Project 2

UPDATE: Download the sample code here.

I’m having some problems updating the homework page right now, so I’ll add this as a blog entry and update the page later. Here are the changes to Project 2:

Due: Friday, September 21 by midnight.

Exercise 3.19, p.93. with the following changes:

a. Describe the algorithm that would be best for this domain, and justify your answer. For example, if you were to claim that depth-first search would be best, why would it be better than the alternatives?

b. Apply the search algorithm you’ve chosen (which can either one that is predefined in the AIMA code or one you’ve rolled yourself) and apply it to the described 3×3 world. Name this function problem3.19b (see code)

c. Here apply your algorithm to a set of 10 3×3 worlds with an 0.2 chance of dirt on any square. Summarize the results in terms of the average number of nodes expanded and the average length of the path. Write this as function problem3.19c (see code).

d. Here, instead of a random agent, compare your search algorithm with a simple breadth-first algorithm (see code).

e. Here, show how the algorithm performs, on average, on worlds from size 3×3 to 7×7. Explain why you get the result that you do in terms of the search algorithm itself.

The code to use is given after the break:

Read Full Post »

Lots of questions on Project 2…

I’m getting lots of questions on Project 2 right now and I also found a couple of problems with the textbook code, so I’m putting together a more general FAQ that I hope will be helpful. I may postpone the deadline again if I feel that the project was too hard. I probably won’t be posting the FAQ before Sunday, so here are a few useful items until then:

• To do this assignment, you’ll need to extend the vacuum problem in the search module, not the agent module. This version of the vacuum problem has some syntactic problems that are easy to spot but need to be fixed (and I plan to release a fix for them soon).
• The search algorithm you’ll need must check for repeated states, otherwise you’ll be hosed (if you’ve been reading the text, it’s pretty clear why). Not surprisingly, you should be looking at the search algorithms that check for repeated states. You can still use some of the agent code by using the problem->environment function to make your problem into an environment (although it still won’t print the pretty grids without some work, and you may want to roll your own grid printer for that reason 😦 ).
• One question that came up earlier was if it was a problem checking for repeated states if you sometimes had to cross the square multiple times. It turns out that this is not really a problem, and it depends critically on how you define a state. The default definition given in the AIMA code works fine, however. Here’s one way to think of it: you may cross a particular square many times, but will you always cross it in the same direction? 😉
• I may change the problem so that instead of comparing to a reactive agent, you compare to a simple agent that does breadth-first search without checking for repeated states. This is a more useful comparison, I think, and is easier to implement (as you’ll hopefully see).
• The vacuum agent only knows about the square underneath it. It does not know what is in the squares nearby. The goal test, however, does check to see that there is no dirt left. Looking at the vacuum-state structure in the search module makes it easy to see how this is done.
• This project will be worth a significant amount of your grade — I’ll try to get a more exact figure later.
• The agent must sweep up all the dirt in the grid, but it doesn’t have to explore the entire grid to do this. The reason is found in the goal test, which knows how many spots of dirt are left. So, while the agent doesn’t know the locations of the spots of dirt, it is stored in the state and used by the goal test to determine if the area has been swept clean.

Rest assured we’ll cover this material on Monday as well.

Read Full Post »

Displaying N-Queens solutions

Hopefully some of you have tried out the AIMA code for constraint satisfaction problems. If you are looking at the N-Queens problem, here is some code that will display the solution for you. To use it, just pass it the result value of the CSP search. For example:

CL-USER 49 > (csp-forward-checking-search (make-nqueens-problem :n 8))

#<NODE f(8) = g(8) + h(0) state:#<CSP ((7 (4) 4 NIL) (6 (6) 6 NIL) (5 (1) 1 NIL) (4 (4 5) 5 NIL) (3 (2 6) 2 NIL) (2 (0 1 6) 0 NIL) (1 (0 1 2 3 4 5) 3 NIL) (0 (0 1 2 3 4 5 6 7) 7 NIL))>>

CL-USER 50 > (display-nqueens-solution *)

 - - - - Q - - -

 - - - - - - Q -

 - Q - - - - - -

 - - - - - Q - -

 - - Q - - - - -

 Q - - - - - - -

 - - - Q - - - -

 - - - - - - - Q

NIL

Code after the jump:

Read Full Post »

Don’t forget to check out the blog comments

If you’re struggling with the homework, don’t forget to check out the comments on the Homework page, where several issues have already been addressed.

And if your issue isn’t addressed, please add a comment 😉

Read Full Post »

What do you need to solve Project 1?

Here are all the Lisp commands and constants that I needed to solve Project 1. As you can see, it doesn’t take much:

Constants: T and nil

Tests: null, equal, =, <, not, numberp, listp, and atom.

Conditionals and control structures: cond, unless, dolist, when

Others: defun, first (or car), rest (or cdr), cons, 1- (or -), +, let , push, and funcall.

Note that some functions used other functions. For example, my implementation of my-remove-dups used my-member.

Read Full Post »

Testing Project 1

Some of you who are still working on Project 1 may want to find a way to test your code. One of the joys of Lisp is that it is very easy to set up a testing system. In Java this requires a module such as JUnit. In Lisp you can roll your own in a few lines.

The following code is a testing system for Project 1. Load the code into your version of Lisp, and then call (project1). This module will then test your code against all the examples given in the homework, as follows:

CL-USER 40 > (project1)

CORRECT: The result of (MY-MEMBER (QUOTE A) (QUOTE (B C J A))) is (A)

CORRECT: The result of (MY-MEMBER (QUOTE (C D)) (QUOTE (A B C (A B) (C D) J K))) is ((C D) J K)

CORRECT: The result of (MY-MEMBER (QUOTE A) (QUOTE (B C (A D) E))) is NIL

CORRECT: The result of (MY-INSERT (QUOTE A) (QUOTE (B C D E)) 0) is (A B C D E)

CORRECT: The result of (MY-INSERT (QUOTE A) (QUOTE (B C D E)) 3) is (B C D A E)

CORRECT: The result of (MY-INSERT (QUOTE A) (QUOTE (B C D E)) 14) is (B C D E A)

CORRECT: The result of (MY-REMOVE-DUPS (QUOTE (A B A C A D))) is (D C B A)

CORRECT: The result of (MY-REMOVE-DUPS (QUOTE (A B (A C) A D))) is (D (A C) B A)

CORRECT: The result of (MY-REMOVE-DUPS (QUOTE (A B (B C) A (B C) D))) is (D (B C) B A)

CORRECT: The result of (MY-INTERSECTION (QUOTE (A B C)) (QUOTE (C A E))) is (C A)

CORRECT: The result of (MY-INTERSECTION (QUOTE (A B (A C) C)) (QUOTE (A C B))) is (C B A)

CORRECT: The result of (MY-INTERSECTION (QUOTE (A B (A C) C)) (QUOTE ((A C) B))) is ((A C) B)

CORRECT: The result of (DYADIC-APPLY (FUNCTION +) (QUOTE (1 2 3)) (QUOTE (6 5 4))) is (7 7 7)

CORRECT: The result of (DYADIC-APPLY (FUNCTION LIST) (QUOTE (A B C)) (QUOTE (1 2 3 4))) is ((A 1) (B 2) (C 3))

CORRECT: The result of (TREE-SUM (QUOTE (1 2 3 4 5))) is 15

CORRECT: The result of (TREE-SUM (QUOTE (A 1 B 2))) is 3

CORRECT: The result of (TREE-SUM (QUOTE (A (1 (2 (3 B) C) D E) F 4))) is 10

CORRECT: The result of (MY-FLATTEN (QUOTE (A B (C D)))) is (A B C D)

CORRECT: The result of (MY-FLATTEN (QUOTE (A (B (C (D (E F))) G (H I (J K)) L (M)) (((N)))))) is (A B C D E F G H I J K L M N)

CORRECT: The result of (FULL-REVERSE (QUOTE (A B C D))) is (D C B A)

CORRECT: The result of (FULL-REVERSE (QUOTE (A (B C) D))) is (D (C B) A)

CORRECT: The result of (FULL-REVERSE (QUOTE ((A B) (C (D E) F G (H I) J K) L M))) is (M L (K J (I H) G F (E D) C) (B A))

CORRECT: The result of (MY-SUBST (QUOTE A) (QUOTE B) (QUOTE (T H B D S T B R N E R))) is (T H A D S T A R N E R)

CORRECT: The result of (MY-SUBST (QUOTE A) (QUOTE B) (QUOTE (A B (A B (A B)) (A B)))) is (A A (A A (A A)) (A A))

NIL

Here’s the code (after the jump):

Read Full Post »

Downloading the textbook code

Although you don’t need the textbook code quite yet, now is a good time to download it and begin to use it with your system.

The code is available at the AIMA Lisp Code website.  If you’re using Franz Allegro Common Lisp, I recommend that you download this version of the code, which has some fixes for that implementation.

I’ve added the textbook code page to the Lisp blogroll as well.

Read Full Post »

Getting up to speed on Lisp, part 2

Project 1 is now up on the homework page, and is due Aug 31.  The goal for project 1 is to let you dig into Lisp. As you’ll notice as you look through the assignment, Lisp uses lists and symbols as basic data structures, so this project focuses on list processing. This capability will be quite useful when we need to manipulate representations of the world (among other things).

Read Full Post »

Getting up to speed on Lisp, part 1

As I mentioned in class today, although you can run Lisp on the CoC machines, there are also free and reasonable (for homework) Lisps available.

Both Lispworks and Franz Allegro Common Lisp are available as free systems with good IDEs. If you need to choose between them, choose Franz because the IDE is a bit better (in my opinion) and you may find that it is used in other classes (since Tech has a site license).

Many of my students who use Macs and Linux really like SBCL, which is a full-powered ANSI-compliant open-source Lisp. Alas, it really isn’t available for Windows.

Read Full Post »