Week 4 Homework -- Nov 2, 2011 see images: 04week_HW_Q*.jpg 1. Logic Select whether the logical sentences are always true (T), always false (F), or sometimes true sometimes false depending on the values of the variables (?). -- I'm using these equivalents: ---------- A => B <=> ~A OR B A AND B <=> ~( ~A OR ~B) ------------------------------------------ A. Smoke => Fire <=> Smoke V ~Fire {t,f,?} -- ? (Smoke IMPLIES Fire IS EQUIVALENT TO Smoke OR NOT-Fire) { (S => F) <=> (S OR (NOT F)) } { ( (NOT S) OR F ) <=> ( S OR (NOT F) ) } -- true for values where S=F B. Smoke => Fire <=> ~Smoke => ~Fire {t,f,?} -- ? (Smoke IMPLIES Fire IS EQUIVALENT TO NOT-Smoke IMPLIES NOT-Fire) { (S => F) <=> ( (NOT S) => (NOT F) ) } { ( (NOT S) OR F ) <=> ( NOT( (NOT S) ) OR (NOT F) ) } { ( (NOT S) OR F ) <=> ( S OR (NOT F) ) } -- same as A. C. Smoke => Fire <=> ~Fire => ~Smoke {t,f,?} -- t (Smoke IMPLIES Fire IS EQUIVALENT TO NOT-Fire IMPLIES NOT-Smoke) { (S => F) <=> ((NOT) F => (NOT S)) } { ( (NOT S) OR F ) <=> ( NOT( (NOT F) ) OR (NOT S) ) } { ( (NOT S) OR F ) <=> ( (NOT S) OR F ) -- identical statements D. Big V Dumb V (Big => Dumb) {t,f,?} -- t (Big OR Dumb OR (Big IMPLIES Dumb) { B OR D OR (B => D) } { B OR D OR ( NOT(B) OR D ) } -- B OR ~B is always true E. Big /\ Dumb <=> ~(~Big V ~Dumb) {t,f,?} -- t (Big AND Dumb) IS EQUIVALENT TO NOT-( NOT-Big OR NOT-Dumb ) { B AND D <=> NOT( (NOT B) OR (NOT D) ) -- definition of AND 2. More Logic Select whether the logical sentences correctly encode the English sentence (check-mark), incorrectly encode the English sentence (X), or not a legitimate sentence in first-order logic (Err). English Sentences and the lines with the corresponding logical sentences: "Paris and Nice are both in France". A. In (Paris /\ Nice, France) {c,X,E} -- E AND in func arg not correct syntax (Paris AND Nice ARE IN France) B. In (Paris, France) /\ In (Nice, France) {c,X,E} -- c (Paris IS IN France) AND (Nice IS IN France) "There is a country that borders Iran and Syria". C. Ec C(c) /\ B(c,Iran) /\ B(c,Syria) {c,X,E} -- c (There exists a C [country] such that [we're going to use a capital C to mean 'c' in the argument is a country] AND [we're going to use the predicate B to mean two objects border each other] "There exists a Country such that C borders Iran AND C borders Syria" D. Ec C(c) => ( B(c,Iran) /\ B(c,Syria) ) {c,X,E} -- X right for wrong reason: t=>f "There exists a C, if C is a country THEN (C borders Iran) AND (C borders Syria)" { ~C(c) OR ( B(c,Iran) AND B(c,Syria) ) explanation: If c is not a country this is true... "No two bordering countries can have the same map color". [use the predicate MC for map-color... and I should say we are using Map Color here as a Function not as a Predicate] E. Ax,y C(x) /\ C(y) /\ B(x,y) => ~( MC(x) = MC(y) ) {c,X,E} -- c (For ALL (x and y) (x is a Country) AND (y is a Country) AND (x and y Border each other) IMPLIES NOT the case that (the map color of x) equals (the map color of y) { got it wrong: I thought X because of this: { Vid7.13, "the moral is for a definition you want an EQUIVALENT <=>" ...this _might_ explain why the statement is wrong.... } { ~( C(x) AND C(y) AND B(x,y) ) OR ~( MC(x) = MC(y) ) { false if x,y countries w/border OR false if border colors the same } { But in fact...this is the same as F. below after two logic transformations... } F. Ax,y ~C(x) V ~C(y) V ~B(x,y) V ~( MC(x) = MC(y) ) {c,X,E} -- c (For ALL (x and y) it is NOT the case that (x is a Country) OR it is NOT the case that (y is a Country) OR it is NOT the case that (x and y Border each other) OR it is NOT the case that (the map color of x) equals (the map color of y) { false if x and y are countries with a border and same color true if x and y are countries with a border and different colors true if x or y are not countries true if x and y don't have a border } 3. Vacuum World The image represents belief states of the two-room vacuum world. In this version there are no percepts/sensors, the actions are all deterministic, and the environment is static (dirt stays put). In the initial state you have no information about which state you are in. Your goal is to be in the leftmost of the two squares and have both squares cleaned up. A. Click on the -- added: shortest path -- sequence of actions (L, R, or S) that take you from the initial state to the goal state (determining the initial and goal states are part of the problem). B. Select yes if the sequence is guaranteed to always reach the goal or no if it is not. DON'T CLICK STATE BOX!!! (Start in 8 state box at top center, do: Right, Suck, Left, Suck, end in bottom mid-right state-7) ( Yes, always reaches the goal) 4. More Vacuum World This problem deals with a version of the two-room vacuum world where there is local sensing, dynamic dirt generation, and stochastic movement actions. Local sensing means after any action you get information about the room you are in (left or right) and whether there is dirt in that room, but no information about dirt in the other room. The world is dynamic, which means dirt can spontaneously appear in either room after an action is performed except <*** when the robot has performed a suck action, in which case the room where the suck action has been performed will have no dirt. Left and right moves are stochastic because they can sometimes fail, for example, the robot might not move right even if the move right action is chosen. The suck action is deterministic so it will always succeed in removing dirt. Given we start in the leftmost location and that location is clean (i.e. we start in either belief state 5 or 7), select the set of belief states we will PREDICT after performing a move right action. (ALL states 1-8 may not move right because moves don't always work and may end up with dirt because dirt appears after all actions but Suck) 5. More Vacuum World Assume we have the same belief states that we had at the end of problem 4. We now sense that we are in the right most square and the square is dirty. Click on all the belief states as we update due to this percept. (ALL states with Right and Dirty: 2,6 [Left can be dirty or clean]) 6. More Vacuum World (Now our belief states contain 2 and 6...did we give it away?) Assume we have belief states two and six. We perform a suck action. Select the belief states we have after performing the Suck action. ("after we make a PREDICTION for what's going to happen after the Suck action!?") (Does the PREDICTION of determinsitic Suck update belief state correctly? yes ALL states with Right and Clean: 4,8 <--I think based on 08class_predictUpdate.jpg 7. More Vacuum World Assume we have the same belief states that we had at the end of problem 6. We now sense that we are in the right most square and the square is clean. Select the belief states we have after sensing. (ALL states with Right and Clean: 4,8 -- same thing) 8. Monkey and Bananas Famous problem described in the language of classical planning. Six Actions: Monkey can go from location X to Y Can push object from X to Y Can climb up on an object Can grasp something Can climb down from an object Can un-grasp something Initial state: Monkey at location A Bananas at location B Box at location C Monkey at a low height Box at low height Bananas at high height Box is pushable Box is climbable Plan: Go from A to C Push box from C to B Climb up on the box Grasp the bananas Climb down from the box Clarifications to action descriptions: The effect on ClimbUp should be: On(Monkey, b) and !Height(Monkey, Low) and Height(Monkey, High) There should also be an additional precondition at Push action, add: At(b, x), where b = box "It is intentional for the bananas to remain high." Given the Plan written in red on the upper right piece of paper and the Initial State described at the very bottom of the screen, select the statements that will be true in the final state after performing the plan starting in the initial state. A. Have(Monkey, Bananas) -- X B. At (Box, C) -- no C. At (Monkey, B) -- X D. At (Bananas, B) -- X E. Height(Monkey, High) -- no E. Height(Bananas, High) -- X -- yes?! because no rule says bananas change height .... so A and E are contradictory... 9. Situation Calculus The domain for this problem is a combination lock with 4 digits. The correct combination that will open the lock is called X. { I am going to assume that a "correct representation" is also complete... } { also note that he mistakenly wrote Poss(s,a) and didn't correct that until an hour before the gdm homework was due, but I ignored it anyway } There are two actions 1) dial any four digit combination into the lock, where the result is the lock opening if the right combination (X) is dialed 2) push a lock button (L) which makes the lock, locked. "whether it was open before or not" Are the axioms correct for the domain or not? Select the axioms that correctly encode the situation. Notation: Poss(action, situation) - possible to perform action in a given situation X - the correct combination "assuming all variables are scoped so we say an implicit For All c and All s" "and X is a constant" "which, if any, or both, of these axioms you think correctly encode the situation?" A. (c=X) => Poss( Dial(c), s ) -- no...incomplete If (c=X) THEN it is POSSIBLE to Dial (c) in situation s B. (0000 <= c <= 9999) => Poss( Dial(c), s ) -- X For all c if c is >= 0000 and c <= 9999 THEN it is POSSIBLE to Dial (c) in any situation s for Lock action: "which if any of the following represents a correct representation of the problem?" C. Open(s) => Poss(Lock, s) -- no...incomplete If the safe is open in situation s THEN it is POSSIBLE to execute the Lock action in s "or maybe we should say:" D. ~Open(s) => Poss(Lock, s) -- no...incomplete If the safe is NOT open in situation s THEN it is POSSIBLE to execute the Lock in s "or maybe we should say:" E. True => Poss(Lock, s) -- X If TRUE THEN it is POSSIBLE to execute the Lock action in situation s "finally successor state axioms for all the fluents, only one fluent -- whether or not the safe is Open" "which if any or all of these are accurate representations of the problem?" F. Poss(s,a) => ( Open( Result(s,a)) <=> (a=Dial(X) V (Open(s) /\ a != Lock) ) ) For any situation and action, if it's possible to execute that action in the situation THEN the Open fluent is going to be true in (..the situation resulting from...) the result of executing that action IF and ONLY IF the action is Dial(X) OR the safe was already Open in situation s AND the action was not equal to Lock() -- X assuming OK to dial when open "that's one option, and the other option is:" G. Poss(s,a) => ( Open( Result(s,a)) <=> (a=Dial(X) /\ (a != Lock) ) ) The same thing on the left hand side (to the <=> EQUIV) and on the right hand side: ("it's open") IF and ONLY IF that action is Dial(X) "dialing the correct combination" AND the action is not equal to Lock -- no doesn't cover already unlocked and the a AND a this is redundant "Tell me if or all of the axioms are good as they stand alone, don't look at any combinations of axioms just go through and check the box if you think the axiom on that line _alone_ is a correct representation of the problem."