CS4341 Introduction to Artificial Intelligence
SOLUTIONS  HOMEWORK 3  C 2000
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:
 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.
 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}.
 Binary constraints should be represented using constraint matrices.
Each constraint matrix is an mbym matrix.
 The problem solving strategy should be an implementation of the one
discussed in class:
 Arc consistency checking,
 Depthfirst search with backtracking, and
 a sound heuristic to select the first variable and the order in which
other variables are expanded.
 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.
 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: Logicbased Systems (25 points)
(Adapted from Novak's notes.)
Consider the following axioms:
 forall x ((boy(x) or girl(x)) > child(x))
every boy or girl is a child
 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
 forall w (boy(w) > !gets(w,doll))
no boy gets any doll
 forall z ((child(z) and good(z)) > !gets(z,coal))
no child who is good gets any lump of coal
 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):
 (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.
Solution: By Weiyang Lin
 Transform axioms into clause form:
 forall x ((boy(x) or girl(x)) > child(x))
!(boy(x) or girl(x)) or child(x)
(!boy(x) and !girl(x)) or child(x)
(!boy(x) or child(x)) and (!girl(x) or child(x))
 forall y (child(y) > (gets(y,doll) or gets(y,train) or gets(y,coal)))
!child(y) or gets(y,doll) or gets(y,train) or gets(y,coal)
 forall w (boy(w) > !gets(w,doll))
!boy(w) or !gets(w,doll)
 forall z ((child(z) and good(z)) > !gets(z,coal))
!(child(z) and good(z)) or !gets(z,coal)
!child(z) or !good(z) or !gets(z,coal)
 boy(Jack)
 !(!gets(Jack,train) > !good(Jack)) negated conclusion
!(gets(Jack,train) or !good(Jack))
!gets(Jack,train) and good(Jack)
 The set of CNF clauses:
 (a) !boy(x) or child(x)
(b) !girl(x) or child(x)
 !child(y) or gets(y,doll) or gets(y,train) or gets(y,coal)
 !boy(w) or !gets(w,doll)
 !child(z) or !good(z) or !gets(z,coal)
 boy(Jack)
 (a) !gets(Jack,train)
(b) good(Jack)
 Resolution:
 4. !child(z) or !good(z) or !gets(z,coal)
6.(b). good(Jack)

7. !child(Jack) or !gets(Jack,coal) (substituting z by Jack)
 1.(a). !boy(x) or child(x)
5. boy(Jack)

8. child(Jack) (substituting x by Jack)
 7. !child(Jack) or !gets(Jack,coal)
8. child(Jack)

9. !gets(Jack,coal)
 2. !child(y) or gets(y,doll) or gets(y,train) or gets(y,coal)
8. child(Jack)

10. gets(Jack,doll) or gets(Jack,train) or gets(Jack,coal)
(substituting y by Jack)
 9. !gets(Jack,coal)
10. gets(Jack,doll) or gets(Jack,train) or gets(Jack,coal)

11. gets(Jack,doll) or gets(Jack,train)
 3. !boy(w) or !gets(w,doll)
5. boy(Jack)

12. !gets(Jack,doll) (substituting w by Jack)
 11. gets(Jack,doll) or gets(Jack,train)
12. !gets(Jack,doll)

13. gets(Jack,train)
 6.(a). !gets(Jack,train)
13. gets(Jack,train)

14. empty clause
Problem 3: Planning (25 points)
Consider the monkeyandbananas 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):
 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)

 GRASP monkey bananas
IF  at(monkey,x)

 at(bananas,x)

 height(monkey,y)

 height(bananas,y)

ADD  grasp(monkey,bananas)

 has(monkey,bananas)

 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)

 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.
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.