COMPSCI  367

Assignment  3

due Wednesday  19  October  2022

Due: by 11:59pm on the due date.  This is a hard due date. Late assignments will not be marked.

Total marks: 10.

Weighting: This assignment counts toward 10% of your final mark.

1.  [2.5  marks]  This  question  asks you to formulate the following problem as a  CSP.

Edmund Hillary and Tenzing Norgay play ten games of Rock-Paper-Scissors. Here are the given facts:

-     Norgay uses Rock once, Paper six times, and Scissors three times.

-     Hillary uses Rock five times, Paper four times, and Scissors once.

-     There are no ties in all 10 games.

-     The order of the games is unknown (and unimportant).

(a) Formulate this problem as a CSP. State clearly the variables, the domains of the variables and the constraints.

Note: We are given a limited vocabulary for how we can formulate our CSP constraints. We may use standard mathematical operators, including equality (=), inequality (≠), addition (+), multiplication (*), and exponentiation (^), where “2^3” is 2-to-the-power-of-3, as well as any other symbols that have been used for CSP constraints in our lectures (e.g., <, >, ≤, ≥).

(Give this a go. If you get stuck, I have put a hint on how to solve this on the last page of this assignment.)

(b) Let’s say that we have a partial assignment of game results as follows:

Given this partial assignment, perform. the Backtracking algorithm and use your results to answer the following questions:

(i)        If Norgay plays Paper in Game 6, what must Hillary play in Game 6? Which of your constraint(s), given the current variable assignments, entails this?

(ii)       Given your answer to (i), what must Hillary then play in game 7. Which of your constraint(s), given the new variable assignments, entails this?

(iii)      After completing the search, who wins the greatest number of games? And how many do they win?

2.  [2.5  marks]  This  question  asks  you to  solve a  CSP problem. We are searching for the correct assignment of numbers to variables.

Here are the given facts:

-     The variables are: A, B, C, D, E, F, G, H.

-     The Domain for each variable is: {1, 4, 5, 7, 9, 14, 16, 21}.

-     None of the variables have the same value (i.e., each value is used only once).

-     The following constraints must be satisfied:

(i)        C + F = G

(ii)       A + C = F

(iii)      B + G = D

(iv)      B + E = H

(v)       D + F = H

(a) Draw the constraint hypergraph for this CSP problem. (For the purposes of drawing the constraint hypergraph, you may ignore the constraint that no two variables have the same value).

(b) Begin with the partial assignment A=1. Apply the AC3 algorithm. At each step, if you have a single variable value assignment, you can delete that value from the other temporary domains. This has been done for you in the first row of the table below. None of the edge consistency checks have been completed, so you will need to do this.

For each row, write the edge that you are testing for consistency in the first column and fill in the rest ofthe row with the resulting temporary domains for each variable.

(Note: the edge may be written as (A,ii) for the edge between variable A and the constraint “A + C = F”)

What are the resulting temporary domains for each variable after the application of the AC3 algorithm?

Question 3 [5 marks]

For this question, you are asked to resolve the Seven Trick Candles logic problem using PDDL.

There are seven trick candles in a circle. Initially, every Candle is Lit. When you blow on a candle, your blow changes the state not just of the candle you blow on, but also both candles either side of it. So, you can think of any blowing action affecting a Trio of candles. The trick is that when a trio of candles is blown on, any candles in that trio that are currently lit will no longer be lit, and candles in the trio that are unlit will become lit! The goal of this puzzle is to blow out all of the candles.

Given what has been said, you can assume at the outset that every candle is a member of exactly three different trios of candles. For example, if you give each candle a number, you can assume that Candle3 will be in the trios: {Candle3, Candle4, Candle5}, {Candle2, Candle3, Candle4} and {Candle1, Candle2, Candle3} and likewise for the other candles. Further, you will note that there are only seven possible distinct trios of candles.

Also, note that every time you select a trio of candles to blow on (an action), there are only eight possible combinations ofthe current states of the candles—lit or unlit—in your selected trio (and eight corresponding effects as a result of the trio being blown on). See the table here:

(a) Write a PDDL domain file candles_domain.pddl that specifies the eight action schemas:

BlowTrioType1, BlowTrioType2, BlowTrioType3, BlowTrioType4, BlowTrioType5,

BlowTrioType6, BlowTrioType7, and BlowTrioType8.

You need to use the PDDL syntax starting from the following:

(define (domain candles)

(:requirements :strips :equality)

(:predicates (candle ?c) (lit ?c) (trio ?t) (intrio ?t ?c))

…//fill in the description here//

)

Note 1: the “equality” requirement in the code above allows you to check whether two objects are different, which will be useful for checks in your action schemas. For example, it allows the following type of check:  (not (= ?c1 ?c2)), which will return True if the variables ?c1 and ?c2 refer to different objects.

Note 2: The  (intrio ?t ?c) relation can be used to check whether a Candle is in a particular Trio of candles or not. For example, if Trio3 contains {Candle2, Candle3, Candle4} then a precondition in an action that checks  (intrio Trio3 Candle3) will return True. Likewise, the same code could be used elsewhere in part (b) of this question to assign Candle3 to Trio3.

(b) Write a PDDL problem file candles_task.pddl that specifies the initial state and the goal state.

Submit the two files candles_domain.pddl and candles_task.pddl.

You may use the PDDL Editor to test your code:http://editor.planning.domains/

Hint for Question 1(a): One way we might specify constraints for sentences like “Norgay played Rock five times, Paper four times, and Scissors once” is to utilise the properties of prime factorisation. Instead of the Domain for each game using letters—say, “R”=Rock, “P”=Paper and “S”=Scissors—the domain could instead use a different prime number, pi, to stand in for each of the options (p1=Rock, p2=Paper, p3=Scissors).

So, for example, if we knew that for a series of games, G1, G2, G3, that a player used Rock twice and Scissors only once, and we use prime numbers 2=Rock and 3=Scissors (so that the domain for each outcome is {2,3}), then we can specify the constraint that: G1 * G2 * G3 = 2^2 * 3^1.

Also note that formulating the constraint this way means that a partial assignment of two-Scissors (i.e., two-3s) to G1 and G2 in this case would be illegal, as the value of 2^2 * 3^1 (=12) cannot be divided by 3^2 (=9). Thank goodness for prime numbers!