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

#### PROF. CAROLINA RUIZ

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

• Instructions for Homework 3:
• This is an INDIVIDUAL homework.
• The homework is due Friday, February 18, 2000 at 5 pm.
Please turn in Problems 1 and G of the homework using the turnin system. Problems 2 and 3 must be turned in on paper.

• Homework Problems: This homework consists of three (plus an additional problem for students who are taking this course for graduate credit) problems:

### 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:

• Tasks: The n tasks will be denoted by t1, t2, t3, ..., tn.
• The "lenght" of each task is given. The lenght corresponds to the number of seconds that it takes a processor to run the task. The lenght of task i will be denoted by li.

• Processors: The m processors will be denoted by p1, p2, p3, ..., pm. Each of the processors runs the tasks assigned to it in a sequencial manner. Processors are independent from each other.

• Constraints: The constraints are of the following sort:

• Deadline: A deadline d, given in seconds, is specified by the user. All tasks must be executed before the deadline. That is, each of the processors must be able to sequentially execute all tasks assigned to it before the deadline. All processors start executing the processes assigned to them at time t=0.

• Unary constraints (involving one variable):
• A task can only be assigned to one of a subgroup of processors. For instance, the user may specify that task t10 can be run only on one of the following processors: p2, p7, p10.
• A task cannot be assigned to any in a given group of procesors. Example: task t9 cannot be assigned to p3 nor p2

• Binary constraints (involving two variables):
• Two given tasks need to be run on the same processor
• Two given tasks cannot be assigned to the same processor
• Two given tasks cannot be simultaneously assigned to a given pair of processors. For instance, the user can specify that task t1 cannot be assigned to processor p7 if task t4 is assigned to processor t3.

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:
• n: the number of tasks,
• m: the number of processors,
• li: the lenght (in seconds) of task i, for each task.
• d: the deadline (in seconds).
• the unary and binary constraints.

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:
• An assignment of processors to tasks such that all constraints are satisfied (including the deadline constraint). OR
• A message stating that NO such assignment is possible, IF that's the case.

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

### Problem 2: Logic-based Systems (25 points)

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:
• !gets(Jack,train) -> !good(Jack)

if Jack doesn't get a train, then Jack is not a good boy.

following the steps below (Show your work on each of the steps):
• (2 points) Negate the conclusion.
• (13 points) Translate all statements to clausal form.
• (10 points) Apply resolution to the clauses until you obtain the empty clause.

### 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.
• Initial Situation:  at(monkey,a) at(bananas,b) at(box,C) height(monkey,low) height(banana,high) height(box,low) !grasp(monkey,bananas) path(a,b) path(b,a) path(a,c) path(c,a) path(b,c) path(c,b)

• Final Situation: has(monkey,bananas).

• Four Actions (or operators):

1. GO monkey from location x to location y
 IF at(monkey,x) path(x,y) ADD go(monkey,y) at(monkey,y) DELETE at(monkey,x)

2. GRASP monkey bananas
 IF at(monkey,x) at(bananas,x) height(monkey,y) height(bananas,y) ADD grasp(monkey,bananas) has(monkey,bananas)

3. CLIMB monkey on top of box
 IF at(monkey,x) at(box,x) height(monkey,low) height(box,low) ADD climb(monkey,box) height(monkey,high) DELETE height(monkey,low)

4. PUSH monkey box from location x to location y
 IF at(monkey,x) at(box,x) height(monkey,low) height(box,low) path(x,y) ADD push(monkey,box,y) at(monkey,y) at(box,y) DELETE at(monkey,x) at(box,x)
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.