COMP3411 Artificial Intelligence
Session 1, 2011

Tutorial - Week 10 - Planning

  role(you)

  succ(1,2)
  succ(2,3)
  succ(3,4)
  succ(4,5)
  succ(5,6)
  succ(6,7)
  succ(7,8)

  init(row(1,one_coin))
  init(row(Y,one_coin)) <= succ(X,Y)
  init(step(1))

  legal(you,jump(X,Y)) <= true(row(X,one_coin)) ∧ true(row(Y,one_coin)) ∧
                          ( kate(X,Y) ∨ kate(Y,X) )

  harry(X,Y) <= succ(X,Y)
  harry(X,Y) <= succ(X,Z) ∧ true(row(Z,empty)) ∧ harry(Z,Y)

  will(X,Y) <= succ(X,Z) ∧ true(row(Z,empty)) ∧ will(Z,Y)
  will(X,Y) <= succ(X,Z) ∧ true(row(Z,one_coin)) ∧ harry(Z,Y)

  kate(X,Y) <= succ(X,Z) ∧ true(row(Z,empty)) ∧ kate(Z,Y)
  kate(X,Y) <= succ(X,Z) ∧ true(row(Z,one_coin)) ∧ will(Z,Y)
  kate(X,Y) <= succ(X,Z) ∧ true(row(Z,two_coins)) ∧ harry(Z,Y)

  next(row(X,empty))     <= does(you,jump(X,Y))
  next(row(Y,two_coins)) <= does(you,jump(X,Y))
  next(row(X,C))         <= true(row(X,C)) ∧
                            does(you,jump(Y,Z)) ∧ distinct(X,Y) ∧ distinct(X,Z)
  next(step(Y))          <= true(step(X)) ∧ succ(X,Y)

  terminal <= ¬open
  open     <= legal(you,M)
  
  goal(you,100) <= true(step(5))
  goal(you,  0) <= ¬true(step(5))

1. Logic Programming -- Answer Substitutions

   Compute all answer substitutions to the query  ?- init(F).

   Hint: You should obtain 9 different answers for variable  F. These 9 features compose the initial game state. Can you draw a simple diagram to visualise this position?

2. Logic Programming -- Derivations

   The key to unlocking the mystery is to understand the meaning of the three recursive relations,  kate, will, harry. To get the idea, suppose given the following facts:

     true(row(1,one_coin))
     true(row(2,empty))
     true(row(3,empty))
     true(row(4,one_coin))
     true(row(5,one_coin))
     true(row(6,one_coin))
     true(row(7,two_coins))
     true(row(8,one_coin))
   

   Which of the following queries have a successful derivation?

   1. ?- harry(1,4)
   2. ?- harry(1,5)
   3. ?- will(1,5)
   4. ?- kate(1,5)
   5. ?- kate(1,6)
   6. ?- kate(1,7)
   7. ?- kate(6,8)

   Can you now guess what  kate(m,n) "counts"?

3. Planning -- Action Preconditions and Effects
   1. Next, have a look at the definition for  legal(you,jump(X,Y)). In words, what are the preconditions for jumping from row X to row Y? How many actions are possible in the initial state of the game (cf. exercise 1)?
   2. Pick any one of the actions  jump(m,n)  that are possible in the initial state and, with the help of the rules for  next(F), compute the new state after  does(you,jump(m,n)). In words, what are the effects of jumping from X to Y?

4. Planning

   The definitions for  terminal  and  goal(you,100)  respectively imply that the game ends when you are stuck (i.e. there are no more legal moves) and that you win the game when you can make the maximum of 4 moves before getting stuck. Find a plan (i.e. a sequence of 4 actions) that solves this problem! (Hint: there is more than one solution.)

5. Planning

   Bonus Challenge: We humans are often better than computers when it comes to generalising a solution. How would you solve the game if initially there were 1,000 coins in a row and the goal is to make 500 moves?