BUSS 925: Techniques in Knowledge-Based Systems Development

Assignment 2 (due June 9, 1999):

Question 1 (1 marks):

Solve Problem 10.6 from your textbook (page 472).

Question 2 (1 mark):

Develop a CLIPS implementation of a meeting scheduling system. The system accepts as input a series of facts about a set of 5 individuals describing their availability in terms of the day of the week and the time slot when they are available. Each time slot is one hour in duration, starting at the beginning of every hour. Each day thus has 8 slots, the first slot starting at 9am and the last slot ending at 5pm. Assume that these facts are included in the CLIPS file you develop. The program must query the user to determine which subset of these 5 people need to meet, and must output a time slot when all of them are available, based on the facts describing the availability of each of the individuals. Assume that program has information concerning the individual calendars for only one week, and must generate a meeting time within that week. Note that a meeting time is denoted by its corresponding time slot, so that meetings are assumed to last for only one hour.

Question 3 (1 mark):

Translate the following sentence, concerning the lexicographic ordering of words in the English language, into predicate logic:
Every word except the word `a' has one and only one immediate predecessor
using only the following:

• The function f(x), which stands for the immediate predecessor of the word x in the lexicographical ordering of words in the English language.
• The predicate word(x) which denotes that the object x is a word in the English language.
• The predicate equal(x, y) which denotes that the object x is identical to the object y.

Question 4 (1 mark):

Assume that the 8-puzzle board is encoded with the following scheme. A 9-digit string is used to denote the board, with the first 3 digits denoting the first row (read from left to right), the next 3 digits denoting the second row (read from left to right) and so on. Thus the string 13b824765 denotes a board where the first row consists of 1 and 3 followed by the blank tile, the second row consists of 8, 2 and 4, while the third row consists of 7, 6 and 5, in that order. Draw the search tree for the 8-puzzle up to a depth of 3, using this encoding scheme, using 13b824765 as the root node, and ensuring that 13482b765 is the leftmost child of this node. Show how each of the following algorithms would search this tree:

• Depth-first search
• Iterative deepening search
• A* search, using a heuristic which counts the number of tiles out of place to estimate a node's distance from the goal.

Comment of the heuristic adequacy of these algorithms if they were used to search the full tree generated by the 8-puzzle.

Question 5 (1 mark):