Dmitri Kaznachey, Ph.D.
Manager, Portfolio Analytics and Research
Fannie Mae, Washington, DC
e-mail: dkaznachey@cox.rr.com; dkaznachey@yahoo.com
(202) 752-3344 work; (703) 278-2849 home

CS 480 Introduction to Artificial Intelligence,  Spring 2002
002 Thursday 4:30 p.m. – 7:10 p.m. ENT 176
Office hours: by appointment (SITE II, Room 435)

Artificial Intelligence: Theory and Practice by T. Dean, J. Allen, Y. Aloimonos, Addison-Wesley, 1995.

ANSI Common Lisp by P. Graham, Prentice Hall, 1996.

This course covers basic to intermediate knowledge on fundamental theoretical and computational concepts of Artificial Intelligence (AI). The emphasis is on algorithms implemented in Lisp for building and analyzing AI systems. The main topics include symbolic programming, representation, search, and learning. Students will practice on projects involving design and implementation of AI systems in Lisp.

Bonus points worth 10% credit will be awarded for doing some extra work on assignments. Answering challenging questions during the class will result in bonus points (up to 3) for class participation. The maximum possible total score to receive in class is 110.

No make-ups will be offered for exams and home works. Once the grade for a home work or a midterm exam is announced, a one-week grace period is allowed to discuss the grade with the instructor. No grade  adjustments will be made after the grace period.

Teaching Assistant

Shen-Shyang Ho

sho@gmu.edu

Office hours: Monday: 8-10 PM, Tuesday: 2-4 PM, Room 435 ST2

Tentative Schedule

LISP Information

    See Sean Luke's Page from CS480: http://cs.gmu.edu/~sean/cs480/Lisp.html

Home Work #1

Due by: February 14, 2002

1. (10 points) Design and implement a recursive Lisp function that simplifies arithmetic expressions that use the 4 following basic operation: +, -, *, /. The following examples demonstrate what the program should do.

> (simplify '(+ x 0 y 0))
> (+ x y)
> (simplify '(- x (+ 0 0))
> x
> (simplify '(* (+ x 0) 1 (- y 0))
> (* x y)
> (simplify '(/ (+ x 0 0) (* 1 1))
> x

2. (Bonus 1 point) Submit your solution by February 7, 2002.

Submit the following (by e-mail to sho@gmu.edu) :

• A short (no more than 1 page) description of the program design.
• Source code.
• An example of program run with at least 10 examples.

Solution:

The following Lisp program covers addition only. Other operations can be added in a similar fashion.

;; Main function (interface)
(defun simplify (expr)
    (cond
        ((eql (first expr) '+) (finalize-expr '+ (simplify-terms (rest expr) 0) 0))
        (t nil)))

;; Remove redundant terms (specified by parameter num) from
;; the list of terms
(defun simplify-terms (terms num)
    (cond
        ((null terms) nil)
        ((atom (first terms))
            (if (eql (first terms) num)
                (simplify-terms (rest terms) num)
                (cons (first terms) (simplify-terms (rest terms) num))))
        (t
            (let ((term (simplify (first terms))))
                (if (eql term num)
                    (simplify-terms (rest terms) num)
                    (cons term (simplify-terms (rest terms) num)))))))

;; Finalize the resulting expression based on the operation (op), a list
;; of terms (terms) and the default term when no terms are present (default)
(defun finalize-expr (op terms default)
    (cond
        ((null terms) default)
        ((eql (length terms) 1) (first terms))
        (t (cons op terms))))

Back to Top

Home Work #2

Due by: February 28, 2002

1. (5 points) Modify the theorem function for automated theorem proving (DAA, p.86; class notes) to be applicable for predicate calculus. Use the match function (DAA, p. 101) to test rules.

2. (5 points) Consider the following knowledge base for a robot environment:

 " x, y ( (robot(x) Ù (person(x, near, y) Ú " z (obstacle(x, near, z))) É stop(x) )

• Interpret this rule in English
• Prove stop(Fred) using rules of inference assuming the following facts:

robot(Fred)
person(Fred, far, right)
" x (obstacle(Fred, near, x))

3. (Bonus 1 point) Implement and debug the theorem function in Lisp and demonstrate its running on example in question 2.

Solution:

1.

;; Keep track of
;;      conjuncts to prove,
;;    rules to apply for the first conjunct
;;    set of all rules
(defun check-theorem (conjuncts untried rules)
      (cond
            ((null conjuncts) T)
            ((null untried) NIL)
            ; if the first conjunct is the goal of the first rule
            ; and we can prove it for conditions of this rule
            ; and all other conjuncts, we are done
            ( (let ((m (match (first conjuncts) (get-consequent (first untried))))
                                (and m
                        (check-theorem
                              (make-subst
                                    (append (get-conditions (first untried)) (rest conjuncts))
                                    m
                              )
                              rules
                              rules
                  )
            ) T)
            (t (check-theorem conjuncts (rest untried) rules)))

;; Making substitutions according to the list of bindings
(defun make-subst (lst bindings)
      (cond
            ((null bindings) lst)
            ( t (make-subst
                  (subst
                        (second (first bindings))
                        (first (first bindings))
                        lst
                        :test #'equal)
                  (rest bindings)))))

2.

A robot stops if it sees a person in some near location or an obstacle in all near locations.

First convert the rule as follows:
" x, y ( (robot(x) Ù person(x, near, y)) É stop(x) )
" x ( (robot(x) Ù " z (obstacle(x, near, z))) É stop(x) )

1. " x ( (robot(x) Ù " z (obstacle(x, near, z))) É stop(x) )        AXIOM
2. robot(Fred) Ù " z (obstacle(Fred, near, z)) É stop(Fred)     UI: x->Fred, 1
3. robot(Fred)                                                                          AXIOM
4. " z (obstacle(Fred, near, z))                                                 AXIOM
5. robot(Fred) Ù " z (obstacle(Fred, near, z))                          CONJ: 3,4
6. stop(Fred)                                                                            MP: 2,5

Back to Top

Midterm

Selected problems from the midterm exam:

3. (5 points) Represent the following English sentences using predicate calculus

• There are exactly two robots that have the same person near them.

Solution:

The expression below ensures that only one pair of robots exists that have some person near both of them:

$ x, y, z (robot(x) Ù robot(y) Ù person(z) Ù Ø equal (x,y) Ù person-near(x,z) Ù person-near(y,z) Ù
            "v, w, p ((robot(v) Ù robot(w) Ù person(p) Ù Ø equal (v,w) Ù person-near(v,p) Ù 
                                person-near(w,p)) É 
                        ((equal(v, x) Ú equal(v, y)) Ù (equal(w, x) Ú equal(w, y))))

Back to Top

Home Work #3

Due by: April 11, 2002

1. (10 points) Consider the following expressions where all variables (a1-a5) are integers from [0, 15]:

 a1 – 2*a2*a3*a4 + a5

Design and implement a genetic algorithm that searches for a combination of values that maximizes the above expression. Note that, variable values require 4 bits for representation. Make sure your algorithm tests significantly fewer than all possible (16^5) combinations of values. The output of the algorithm should contain the maximum found value of the expression and the corresponding values of variables.

2. (Bonus 1 point) Submit your solution by April 4, 2002.

Back to Top

Home Work #4

Due by: April 25, 2002

Consider the navigating robot trying to determine if an obstacle is movable (class = "yes") or not (class = "no") with the following dimensions and training examples:

(height (tall short))
(width (wide narrow))
(shape (circle star)) 

(1 ((height tall) (width wide) (shape circle)) no)
(2 ((height short) (width narrow) (shape circle)) yes)
(3 ((height short) (width wide) (shape star)) yes)

1. (10 points) Specify the general and specific boundaries at each step of the version space-learning algorithm.

 2. (Bonus 1 point) Implement the version space learning algorithm in Lisp and test it on the above example.

Back to Top

Home Work #5

Due by: May 2, 2002

Consider the following list of dimensions and training examples for a navigating robot trying to determine if an obstacle is movable (class = "yes") or not (class = "no"):

(height (tall short))
(shape (star rectangle circle)) 

(1 ((height short) (shape star)) yes)
(2 ((height tall) (shape rectangle)) no)
(3 ((height tall) (shape star)) no)

1. (10 points) Build a decision tree according to the algorithm on page 199 of the textbook. When choosing an attribute at each step, calculate disorder values by filling out a partition table such as the one on page 201.

2. (Bonus 1 point) Implement and test the disorder value calculation in Lisp.

Back to Top