WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS4341 Introduction to Artificial Intelligence 
SOLUTIONS - HOMEWORK 3 - C 2000

PROF. CAROLINA RUIZ 

DUE DATE: Friday, Feb. 18 at 5 pm. 
------------------------------------------

Problem 1: Constraint Satisfaction (50 points)

 Consider the following scheduling problem. We need to execute n tasks (or processes) using m processors under certain constraints. For simplicity, we'll use the following notation:

Design and implement a constraint satisfaction system that produces an assignment of processors to tasks which satisfies all constraints (including the deadline constraint), if such an assignment exists. Your system must satisfy the following requirements:

  1. The input to the system consists of:

  2. The internal representation of the problem should use a constraint net.
    Note that the variables in this problem are the tasks t1, ..., tn and the domain of each of the variables is the set of all processors {p1,...,pm}.

  3. Binary constraints should be represented using constraint matrices. Each constraint matrix is an m-by-m matrix.

  4. The problem solving strategy should be an implementation of the one discussed in class:
    1. Arc consistency checking,
    2. Depth-first search with backtracking, and
    3. a sound heuristic to select the first variable and the order in which other variables are expanded.

  5. The output of the system should be either:

  6. You MUST write YOUR OWN code in any high level programming language. You MUST include a short user's manual with your submission so that we know how to run you system. For simplicity, your system interface should look like the one below: 
    number of tasks: 10
 lenght of task 1 (in sec.): 6
 lenght of task 2 (in sec.): 3
 lenght of task 3 (in sec.): 5
 lenght of task 4 (in sec.): 8
 lenght of task 5 (in sec.): 15
 lenght of task 6 (in sec.): 12
 lenght of task 7 (in sec.): 7
 lenght of task 8 (in sec.): 19
 lenght of task 9 (in sec.): 4
 lenght of task 10 (in sec.): 9

number of processors: 6

dealine (in sec.): 22

unary constraints:
  t1: none
  t2: p2, p3
  t3: !p6
  t4: none
  ...
  t10: !p5, !p1

binary constraints:
  t1: t3: same 
  t1: t5: !same
  t1: none
  t2: none
  t3: t4: same
  t3: t5: !(p1,p7)
  t3: none
  t4: none
  t5: none
  t6: none
  t7: none
  t8: none
  t9: none
  t10: none
    where your system is expected to print on the screen the messages to the left of the first ":" of each line.

    In this example, the unary constraints specify that task t2 can be executed only on p2 or on p3; task t3 cannot be executed on p6; and task t10 cannot be executed on p5 nor on p1. The binary constraints specify that t1 and t3 must be executed on the same processor; t1 and t5 cannot be executed on the same processor; and that the assignment t3 to p1 AND t5 to p7 is invalid.

FYI: See a nice extension of this problem to an optimization problem in the the description of Problem G: Additional Graduate Credit Problem

Solution: By James Abbatiello

(Thanks James for letting us post your solution. Good job!)

Constraint Satisfaction Code (solutions to Prob. 1 and Prob. G) by James Abbatiello
Includes sample runs.

Problem 2: Logic-based Systems (25 points)

(Adapted from Novak's notes.)

Consider the following axioms:

  1. forall x ((boy(x) or girl(x)) -> child(x))

    every boy or girl is a child

  2. forall y (child(y) -> (gets(y,doll) or gets(y,train) or gets(y,coal)))

    every child gets a doll or a train or a lump of coal

  3. forall w (boy(w) -> !gets(w,doll))

    no boy gets any doll

  4. forall z ((child(z) and good(z)) -> !gets(z,coal))

    no child who is good gets any lump of coal

  5. boy(Jack)

    Jack is a boy

Construct a proof by refutation using resolution of the statement: following the steps below (Show your work on each of the steps):

Solution: By Weiyang Lin

Problem 3: Planning (25 points)

Consider the monkey--and--bananas problem (this is a classic planning problem), in which there is a monkey in a room with some bananas hanging out from the ceiling out of the monkey's reach, but a box is available that will enable the monkey to reach the bananas if he climbs on it. Initially, the monkey is at A, the bananas at B, and the box at C. The monkey and box have height Low, but if the monkey climbs onto the box he will have height High, the same as the bananas. The actions available to the monkey include Go from one place to another, Push an object from one place to another, Climb onto an object, and Grasp an object. Grasping results in holding the object if the monkey and object are in the same place at the same height. The purpose of this problem is to construct a plan so that the monkey can get the bananas. Using backward chaining, construct a plan to go from the initial situation to the goal situation described below. Show your work. In particular, show establishes, threatens, and before links.

Solution: By Gleb Ralka

(Thanks Gleb for letting us post your solution. Good job!)

Problem G: Additional Graduate Credit Problem (20 points)

 Let's extend the specification of the constraint satisfaction problem in Exercise 1 of this homework. There is now a cost associated to each of the processors. The cost ci will represent the amount of dollars charged for using the processor pi during one second. That is, if a task tj uses the processor pi for say 12 seconds and ci = $10 then the total charge to task tj will be $120.

Extend the constraint satisfaction system that you constructed on Problem 1 of the homework to output an optimal assignment of processors to tasks, that is an assignment that satisfies all constrains and that minimizes the total cost of executing tasks t1,...,tn.

Solution: By James Abbatiello

(Thanks James for letting us post your solution. Good job!)

Included in the solution to Problem 1 of this homework.