Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

13.8 Exercises

Exercise 13.1:
The aim of this exercise is to explore multiple representations for the same domain.

Tic-tac-toe is a game played on a 3×3 grid. Two players, X and O, alternately place their marks in an unoccupied position. X wins if, during its turn, it can place an X in an unoccupied position to make three X's in a row. For example, from the state of the game

X O O
X
X O

X can win by moving into the left middle position.

Fred, Jane, Harold, and Jennifer have all written programs to determine if, given a state of the game, X is able to win in the next move. Each of them has decided on a different representation of the state of the game. The aim of this question is to compare their representations.

Fred decides to represent a state of the game as a list of three rows, where each row is a list containing three elements, either x, o, or b (for blank). Fred represents the above state as the list

[[x,o,o],[b,x,b],[x,b,o]].

Jane decides that each position on the square could be described by two numbers, the position across and the position up. The top left X is in position pos(1,3), the bottom left X is in position pos(1,1), and so forth. She represents the state of the game as a pair ttt(XPs,OPs) where XPs is the list of X's positions and OPs is the list of O's positions. Thus, Jane represents the above state as

ttt([pos(1,3), pos(2,2), pos(1,1)], [pos(2,3), pos(3,3), pos(3,1)]).

Harold and Jennifer both realize that the positions on the tic-tac-toe board could be represented in terms of a so-called magic square:

6 7 2
1 5 9
8 3 4

The game is transformed into one where the two players alternately select a digit. No digit can be selected twice, and the player who first selects three digits summing to 15 wins.

Harold decides to represent a state of game as a list of nine elements, each of which is x, o, or b, depending on whether the corresponding position in the magic square is controlled by X, controlled by O, or is blank. Thus, Harold represents the game state above as the list

[b, o, b, o, x, x, o, x, b].

Jennifer decides to represent the game as a pair consisting of the list of digits selected by X and the list of digits selected by O. She represents the state of the game above as

magic([6, 5, 8], [7,2, 4]).
  1. For each of the four representations, write the relation to determine whether X has won based on that representation, such as x_won_fred(State), with the intended interpretation that X has won the game in state State based on Fred's representation (and similarly for the other three representations).
  2. Which representation is easier to use? Explain why.
  3. Which representation is more efficient to determine a win?
  4. Which representation would result in the simplest algorithm to make sure a player does not lose on the next move, if such a move exists?
  5. Which do you think is the best representation? Explain why. Suggest a better representation.
Exercise 13.2:
Sam has proposed that any n-ary relation P(X1, X2, X3, ... , Xn) can be reexpressed as n-1 binary relations, namely,
P1(X1, X2).
P2(X2, X3).
P3(X3, X4).
     ...
Pn - 1(Xn -1, Xn ).

Explain to Sam why this may not be such a good idea. What problems would arise if Sam tried to do this?

Exercise 13.3:
Write an ontology for the objects that often appear on your desk that may be useful for a robot that is meant to tidy your desk. Think of the categories that (a) the robot can perceive and (b) should be distinguished for the task.
Exercise 13.4:
Suppose a "beach resort" is a resort that is near a beach that the resort guests can use. The beach has to be near the sea or a lake, where swimming is permitted. A resort must have places to sleep and places to eat. Write a definition of beach resort on OWL.
Exercise 13.5:
A luxury hotel has multiple rooms to rent, each of which is comfortable and has a view. The hotel must also have more than one restaurant. There must be menu items for vegetarians and for meat eaters to eat in the restaurants.
  1. Define a luxury hotel in OWL, based on this description. Make reasonable assumptions where the specification is ambiguous.
  2. Suggest three other properties you would expect of a luxury hotel. For each, give the natural language definition and the OWL specification.
Exercise 13.6:
For the following, explain how each is categorized by BFO:
  1. your skin
  2. the period at the end of the previous sentence
  3. the excitement a child has before a vacation
  4. the trip home from a vacation
  5. a computer program
  6. summer holidays
  7. the ring of a telephone
  8. the dust on your desk
  9. the task of cleaning your office
  10. the diagnosis of flu in a person

Based on this experience, suggest and justify a modification of BFO. Think about what distinctions in BFO either don't cover the cases you need or are not exclusive.

Exercise 13.7:
Modify the depth-bound meta-interpreter of Figure 13.12 so that
  1. the bound is on the total length of the proof, where the length is the total number of instances of base-level atoms that appear in the proof.
  2. different base-level atoms can incur different costs on the bound. For example, most atoms could have zero cost, and some atoms could incur a positive cost.

Discuss why either of these may be better or worse than using the depth of the tree.

What conditions on the atom costs would guarantee that, when a positive bound is given, the proof procedure does not go into an infinite loop?

Exercise 13.8:
The program of Figure 13.16 allows duplicate delayed goals. Write a version of dprove that returns minimal sets of delayed goals, in their simplest forms.
Exercise 13.9:
Write a meta-interpreter that can ask multiple sources for information. Suppose that each source is identified by a universal resource identifier (URI). Suppose you have the predicates
  • can_answer(Q,URI) is true if the source given by URI can answer questions that unify with Q.
  • reliability(URI,R) is true if R is some numerical measure of reliability of URI. You can assume that R is in the range [-100,100], in which the higher number means that it is more reliable.
  • askSite(URI,Q,Answer) is true when you ask the source URI a question Q, it gives the Answer that is one of {yes,no,unknown}. Note that although can_answer and reliability can be simple databases, askSite is a sophisticated program that accesses the web or asks a human a question.

Write a meta-interpreter that can utilize multiple information sources and returns a reliability of the answer, where the reliability of an answer is the minimum of the reliabilities of the information sources used. You must have some convention for when no external sources were used (e.g., a reliability of 200). You can only ask an information source a question that you have recorded that it can answer.

Exercise 13.10:
Write a meta-interpreter that allows for asking the users yes-or-no questions. Make sure it does not ask questions to which it already knows the answer.
Exercise 13.11:
Extend the ask-the-user meta-interpreter to have questions that ask for instances. You should be able to interpret declarations that say that a predicate is functional and respond accordingly.
Exercise 13.12:
Write a program that takes in a tree produced from the meta-interpreter that builds proof trees as shown in Figure 13.13 and lets someone traverse the tree using how questions.
Exercise 13.13:
Write a meta-interpreter that allows both how and why questions. In particular, it should allow the user to ask how questions about a goal that has been proved after a why question. Explain how such a program may be useful.
Exercise 13.14:
Write a meta-interpreter for definite clauses that does iterative deepening search. Make sure that it only returns one answer for each proof and that the system says no whenever the depth-first searcher says no. This should be based on the depth-bounded meta-interpreter and the iterative-deepening search algorithm.
Exercise 13.15:
Build an iterative deepening abductive reasoning system to find minimal consistent sets of assumables to imply a goal. This can be based on the depth-bounded meta-interpreter of Figure 13.12, and the delaying meta-interpreter of Figure 13.16 to collect assumptions. The depth bound should be based on the number of assumables used in the proof. Assume that the assumables are all ground.

This should be done in two parts:

  1. Find the minimal sets of assumables that imply some g using iterative deepening on the number of assumables. When g is false, this program finds the minimal conflicts.
  2. Based on part (a), find the minimal explanations of g by interleaving finding conflicts and finding minimal sets of assumables that imply g.
Exercise 13.16:
In this question, you will write a meta-interpreter for parametrized logic programs. These are logic programs that can use constants in arithmetic expressions. The values for the constants are given as part of the input to the meta-interpreter.

Assume that an environment is a list of terms of the form val(Parm,Val), where Val is the value associated with parameter Parm. Assume that each parameter only appears once in an environment. An example environment is [val(a,7),val(b,5)].

In AILog, you can use <= as the base-level implication and & as the base-level conjunction. AILog has <= defined as an infix operator and number is a built-in predicate.

  1. Write a predicate lookup(Parm,Val,Env) that is true if parameter Parm has value Val in environment Env.
  2. Write a predicate eval(Exp,Val,Env) that is true if parametrized arithmetic expression Exp evaluates to number Val in environment Env. An expression is either
    • of the form (E1+E2), (E1*E2), (E1/E2), (E1-E2), where E1 and E2 are parameterized arithmetic expressions;
    • a number; or
    • a parameter.

    Assume that the operators have their usual meaning, that numbers evaluate to themselves, and that parameters evaluate to their value in the environment. You can use the AILog predicates is, use infix as N is E, which is true if (unparametrized) expression E evaluates to number N, and number(E), which is true if E is a number.

  3. Write a predicate pprove(G,Env) that is true if goal G is a logical consequence of the base-level KB, where parameters are interpreted in environment Env. An example interaction with AILog is 
    ailog: tell f(X,Y) <= Y is 2*a+b*X.
ailog: ask pprove(f(3,Z),[val(a,7),val(b,5)]).
Answer: pprove(f(3,29),[val(a,7),val(b,5)]).
  [ok,more,how,help]: ok.
ailog:  ask pprove(f(3,Z),[val(a,5),val(b,7)]).
Answer: pprove(f(3,31),[val(a,5),val(b,7)]).
  [ok,more,how,help]: ok.
ailog: tell dsp(X,Y) <= Z is X*X*a & Y is Z*Z*b.
ailog: ask pprove(dsp(3,Z),[val(a,7),val(b,5)]).
Answer: pprove(dsp(3,19845),[val(a,7),val(b,5)]).
  [ok,more,how,help]: ok.
ailog: ask pprove(dsp(3,Z),[val(a,5),val(b,7)]). 
Answer: pprove(dsp(3,14175),[val(a,5),val(b,7)]).
  [ok,more,how,help]: ok.