Artificial Intelligence and Expert Systems 1 Assignment 3

Computer Science 456: Artificial Intelligence and Expert Systems 1
Assignment 3
Weight: 15% of your final grade
Due: after Unit 6
Important!
Please note that, for the sake of fairness to all students, your tutor is not supposed to provide help
with your program coding (e.g., pick up compiler errors, send a working code for part of the
program, correct your wrong code and convert it to a working one). S/he may, however, give
advice about your steps and/or your techniques. If you need help with your coding in order to
complete your assignment or to keep you going with it, then you may lose marks on your
assignment.
Question 1 (20 marks)
Briefly define the three main components of production systems.
Question 2 (20 marks)
Contrast the use of a data-driven strategy versus a goal-driven strategy for the control of search in
production systems.
Question 3 (20 marks)
Briefly describe the blackboard architecture for problem solving.
Question 4 (40 marks)
For this question, you will write a short report that explains how your program works, and give some
execution examples.
The Farmer Problem
Consider the famous problem of a farmer having a goat, a wolf, and a cabbage. The farmer wants to
cross the river from the east shore to the west shore, but his boat is small. The boat has space for only
the farmer with one of the items: cabbage, wolf, or goat. The farmer cannot leave the wolf alone with
the goat or the goat alone with the cabbage.
The state space for this problem can be represented by the different situations of the four subjects that
can be at any time either on the east or the west shore, but when moving from one state to another the
items are subject to the conditions specified in the previous paragraph.
Computer Science 456: Artificial Intelligence and Expert Systems 2
We can represent a state space by the relation s(X, Y), which is true only if there is a legal move from
state X to state Y within the specified conditions.
Each state can be represented by the tuple (FP, GP, WP, CP), where the variables FP, GP, WP, CP can
have only two values (e, w), which indicate the position east or west of the farmer, goat, wolf, and
cabbage.
The initial state of the system can be represented by (e, e, e, e), where all subjects are on the east side.
The goal state of the system can be represented by (w, w, w, w), where all subjects have been moved to
the west side.
Other intermediate states will be represented using combinations of these positions (e,w).
1. Write a depth-first search program with cycle detection to find and display different solution paths
for the farmer problem. (20 marks)
2. Write a breadth-first search program with cycle detection to find and display different solution
paths for the farmer problem. (20 marks)
Note: all data about the state space and the initial state of the system should be defined in the
program as facts.
Your program should list for each path the possible steps the farmer may take to move his items
across the river safely. You should explain how your predicate works and give some execution
examples.