CSCE476/876: Homework 2 (HW2)

Getting to know the technical environment Given:          Wednesday, Jan 19, 2000.
Due dates:   Wednesday, Feb 2, 2000 at the beginning of the class.
Note:            To be turned in to the instructor. As much as possible, please indicate how much time you spend on each problem. The last two problems, Problem 5 and Problem 6, are a primer to the LISP environment. Just indicate whether or not you have run all the steps.

The goal of the homework is to familiarize you with the resources at the Love Library and the developing environment of Common Lisp.

(30 points) Problem 1: AI topics and subfields by a library search. (Library search.)
(10 points) Problem 2: What is AI about. (Your opinion.)
(10 points) Problem 3: AI in the media. (Library search.)
(20 points) Problem 4: Intelligent Agents. (Exercise from AIMA.)
(20 points) Problem 5: Problem solving. (Exercise from AIMA.)
(05 points) Problem 6: Tutorial to debugging tools. (Courtesy of B.V. Faltings, AILab, Swiss Federal Institute of Technology in Lausanne.)
(05 points) Problem 7: Getting help with the command fi:clman. (Courtesy of B.V. Faltings, AILab, Swiss Federal Institute of Technology in Lausanne.)

Advice: Problems 6 and 7 are straightforward, do them quickly. Problems 4 and 5 should be very easy, do them as soon as you have read the relevant sections. Problems 1, 2 and 3 require some library search: do not delay until the last moment as books may be missing from the library.

Problem I: AI topics and subfields by a library search (Please do not check the proceedings out of the library as your colleagues need to access them too. )

The following conferences are general AI conferences:

The European Conference on Artificial Intelligence, ECAI (biennial, even years)
The International Joint Conference on Artificial Intelligence, IJCAI (biennial, odd years)
The National Conference on Artificial Intelligence NCAI, also called AAAI (almost annual).

In these conferences, almost all AI subfields are discussed. Specialized conferences focusing on specific subfields also exist.

Task 1: Major general-purpose AI Conferences.

Go to the Love Library and look for the proceedings of ECAI, IJCAI, AAAI for any year, selected randomly (years need not be different).
Report all subfields listed in the table of contents of the proceedings.
Is there a particular subfield you are interested in learning about? Explain your choice in 2 or 3 sentences. Consult the MIT Encyclopedia of the Cognitive Sciences (call number BF311 .M556 1999, LIB USE ONLY) or other reference book (provide exact reference) to write a little paragraph about the subfield you selected (e.g., definition, focus, methods, history, successes/failures, most significant advances).

Task 2: Evolution of a major AI Conference.

Choose one conference among the three listed above. Check the earliest and the latest available proceedings of this conference.
Report the subfields listed in each venue.
Identify the intersection of, and difference between, the two lists of subfields. Note if any evolution of the field is visible.

Task 3: Other AI Conferences.

Find the proceedings of one AI conference other than the one listed above.
Is it a general conference or does it address a subfield of AI?
If the conference you selected is restricted to a subfield, check out whether or not the topic of the conference is included in each of the proceedings of the general conferences you chose in Task 1. Otherwise (i.e., you selected a general AI conference), compare the list of topics with that of one of the conferences selected in Task 1 (identify the intersection of and the differences between the two lists). Can you say something about the audiences targeted by either conference.

Task 4: Books

Find one general AI textbook, report the reference (Title, Author(s), Editor(s), Publisher, Year, ISBN, etc.).
Find one specialized AI book, report the reference.

Task 5: Books on reserve at LL

Look up the books put on reserve at LL for the course. Report the list of references.
Skim each book on reserve and write two or three sentences about its content and scope.
Choose two books, and write a paragraph (3--5 sentences) on how they overlap and how they differ.

Note:

Please do not check the proceedings out of the library as your colleagues need to access them too.
You can browse the catalogue of the UNL libraries via the URL: iris.unl.edu

Problem 2: What is AI about.

Consider the 8 definitions of AI cited in AIMA, page 5, Figure 1.1. When applicable:

indicate which one you most agree with (i.e., a definition that correctly states what AI is about in your opinion), justify (1 sentence)
indicate which one you most disagree with (i.e., a definition of what AI should not be concerned with in your opinion), justify (1 sentence)
indicate which ones appear to you as a reasonably feasible task, justify (1 sentence)
indicate which ones in your opinion is not realizable, justify (1 sentence)

Justify in 1 sentence in case, for any of the above categories, you cannot identify a fitting definition among the 8 definitions cited in AIMA.

Problem 3: AI in the media.

AIMA, Exercise 1.6, Page 30.

Problem 4: Intelligent Agents

AIMA, Exercise 2.4, Page 50.

Problem 5: Problem solving

AIMA, Exercise 3.2, Page 87.

Problem 6: tutorial to debugging tools

The n-Queens Problem consists of putting n queens on a n x n chess board such that no two queens can attack each other (we will say conflict). Two queens conflict if they are on the same row, the same column or the same diagonal. The following LISP program has two functions, and allows to test a new position for a new queen conflicts with other queens already on the board. The board is a list of a pair of numbers representing the positions on the chess board of the already placed queens. For instance: ((0 1) (1 3)) means that two queens have be positioned on the chess board; the first queen is on line 0 and column 1 and the second on line 1 and column 3.

(defun threatens (line-1 column-1 line-2 column-2)
  (or (= line-1 line-2)
      (= column-1 column-2)
      (= (- line-1 column-1)(+ line-2 column-2))
      (= (+ line-1 column-1)(+ line-2 column-2))))

(defun conflict (line column board)
  (cond 
    ((endp board) nil)
    ((threatens line column 
             (first (first board))(second (first board)))
     t)
    (t (conflict line column board))))

This code has two rather simple errors that we will try to detect using the LISP functions trace and step.

Wrong call
Write the program above in a file, then load the file in the LISP environment. Type the expression: (conflict 'a 2 '((0 1))). You will be prompted with the following error:

Error: EXCL::=_2OP: `A' is not of the expected type `NUMBER'
  [condition type: TYPE-ERROR]
[1] USER(xx):

[1] at the head of the prompt means that we are at level 1 of the execution stack. Use the command :zoom to check the whole execution stack. You will then see:

Evaluation stack:

   (ERROR TYPE-ERROR :DATUM ...)
 ->(= A 0)
   (OR OR (= LINE-1 LINE-2) ...)
   (THREATENS A 2 ...)
   (COND COND (# NIL) ...)
   (CONFLICT A 2 ...)
   ..

The arrow indicates the current level in the execution stack. You can use :up <n> and :dn <n> to move around this stack. At each level, you can examine the content of the parameters and local variables using the command :loc. Further, the command :eval :context T entered once and for all, make the local environment accessible. This means that the local variables are read and write accessible with their names.
This is particularly useful when a variable is a complex data structure such that defstructure or a hashing table. We can examine and modify their content. This can be done using the functions describe and inspect. Above, we can see that the parameter 'a given to the function conflict is not correct.

Infinite loop
Evaluate the expression : (conflict 1 2 '((0 1))). Nothing happens, and the LISP interpreter does not seem to stop. In order to stop it, you have to type C-c C-c (you may have to do so several times before the interpreter reacts). Clearly, the program is entering an infinite loop. Since conflict is a recursive function, it may be the case that the condition to end the recursive call is never verified.
In such cases, we may choose to "trace" the function to check the calls as well as the values returned by the function. Type (trace conflict) then re-execute the function. To stop the interpreter, use C-c C-c. The ending condition (board = NIL) is not verifiable because board has always the same value. We must thus change the recursive call so that we give only the rest of board at each call. The function traceis used to verify that the value of arguments are really what we want them to be. To exit from the trace mode, we have to call the function (untrace <function name>). If we do not put the name of the function, all functions being trace will no longer be. Modify the function conflict and exit the trace mode.

Step execution
After making the correction above, make the call again (conflict 1 2 '((0 1))). The result of this call is not correct since the result is NIL while the queens are obviously in conflict. The function that test whether two queens can attack each other is buggy. In this situation, we can use the stepper to run the execution of the code step by step. Warning: the stepper works only on interpreted code and not on compile code. Type (step threatens), then make the following call again (conflict 1 2 '((0 1))). In the stepping mode, three commands are important:

The Return: key allows to go one step further
The command :so (step-over) allows us to pass the stepping of a block (a function)
The command :res stops execution.

To exit the stop mode, type the command :step.

Use the stepper to localize and correct the error. In general, the step function is a last-chance tool when we really do not see what is happening in the code and that trace is not providing enough information.

Problem 7: getting help with the command fi:clman
M-x fi:clman is an on-line LISP manual. Check it out for the function member (type the command then the name of the function). What is member useful for? What is the result of the following:

(member 'a '(d e a f g))
(member 'g '(d e a f g))
(member 'x '(d e a f g))

Verify in the LISP interpreter.

Berthe Y. Choueiry
Last modified: