Skip to main content

辅导案例-COMP4450/COMP6445-Assignment 3

By May 15, 2020No Comments

Assignment 3: Theoretical Methods April 15, 2020 COMP2550/COMP4450/COMP6445 – Advanced Computing R&D Methods Assignment 3: Theoretical Methods Maximum marks 100 points + 5 bonus points Submission deadline May 12, 11:59pm No late submission unless permission is obtained from the convener. Submission mode One PDF file via Wattle This assignment contains questions to both Theoretical Methods I and Theoretical Methods II. The first part gets 65 points the second gets 40 points. The maximum will be 105 of 100, meaning that you can earn up to 5 bonus points (and you can lose 5 points without actually losing them). Theoretical Methods I Although the main purpose on this lecture was to study and prove properties of algorithms (illustrated with the classical planning search algorithm and heuristics), we start with some general planning and search exercises before focusing on analyzing and proving theoretical properties of algorithms and, most importantly, heuristics. Thus, by first doing the exercises within the block 1. Foundational Planning and Search Exercises you can familiarize yourself with the topic and get a more intuitive understanding, before you move on to the more challenging – and more theoretical – questions. Do no leave out any exercises! When you need to prove something, check the required definition and try prove or argue (as formal as possible) why it is fulfilled or why not. — Pascal 1. Foundational Planning and Search Exercises A. Checking (Proving) Plan Executability (5 points) a) Let P1 = (V,A, sI , g1) and P2 = (V,A, sI , g2) be two classical planning problems, which base upon the same state variables, actions, and initial state. Only their goal descriptions are different. Let a¯1 = a11, a 1 2, . . . , a 1 n be a plan (i.e., a solution action sequence) for P1 and a¯2 = a21, a22, . . . , a2n be a plan for P2. Answer the following questions (1.5+1pts). If a statement is wrong provide a counter example and briefly explain why it is a counter-example. If a statement is correct provide a proof sketch or make a reasonable argument that shows that you understood why the respective property is true (we do not demand anything overly formal here). • If a¯1 ◦ a¯2 is executable in sI , then it is also a solution for P2. (Like in the lecture, the sign ◦ represents the concatenation of actions.) • If P1 (and thus P2) is delete-free, then a11, a21, a12, a22, . . . , a1n, a2n a solution for P3 = (V,A, sI , g1∪g2). b) Answer the following questions (1+1.5pts). If a statement is wrong provide a counter example and briefly explain why it is a counter-example. If a statement is correct provide a proof sketch or make a reasonable argument that shows that you understood why the respective property is true (we do not demand anything overly formal here). • Let a be an action and s be a state. If a is applicable in s once, then it is also applicable twice. Formally: If τ(a, s) = true, then τ(a, s′) = true for s′ = γ(a, s). • Let a be an action and s be a state. If a is applicable in s twice in a row, then it is also applicable thrice. Formally: If τ(aa, s) = true, then τ(aaa, s) = true. 1 B. Modeling a Planning Problem (5 points) (Re-)Consider the sliding tile puzzle from the lecture: 2 1 4 8 9 7 11 10 6 5 15 3 13 14 12 Initial State 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Goal State As the lecture explained, the left side shows the initial configuration of the puzzle (meant to represent a shuffled picture), and the right side shows the goal configuration. The numbers are provided so we can give individual tiles individual names – i.e., their number. The position without a number does not have a tile in it, this is the only empty position into which neighboring tiles could be moved in. We also assume that every “grid position” has a name that starts from 1 and ends at 16, in the same way as the goal configuration is shown. Thus, for example: • In the initial state, the tile with name 9 is located at position 5. • In both the initial state and the goal state, the empty position without any tile in it is number 16. • In the goal state, any tile with name i is also at position i. In this exercise you should model that problem as a classical planning problem (V,A, sI , g). To make things easier for you, we already provide you with a partial domain model. You can (i.e., have to!) assume that we are given the following problem components: • V = {posi-is-free|1 ≤ i ≤ 16} ∪ {tilei-at-posj |1 ≤ i ≤ 15 and 1 ≤ j ≤ 16} • sI = {tile2-at-pos1, tile1-at-pos2, tile4-at-pos3, tile8-at-pos4 tile9-at-pos5, tile7-at-pos6, tile11-at-pos7, tile10-at-pos8 tile6-at-pos9, tile5-at-pos10, tile15-at-pos11, tile3-at-pos12 tile13-at-pos13, tile14-at-pos14, tile12-at-pos15, pos16-is-free} Exercises (1.5+3.5pts): a) Specify the goal description. b) We are also still missing the action set A. However, because there are too many special cases to consider, we do not demand that you model the entire set. Instead, we only ask you to: • Model all (four) actions for moving tile number 6 from position 11 to all possible, directly neigh- boring positions. → Please provide names for your actions, e.g., move-tilei-from-posj-to-posk = (pre, add, del) with … Make sure that you covered all required preconditions and effects. C. Proving Simple Heuristic Properties (8 points) We will again take a look at the Sliding Tile puzzle. This time, however, we do not assume it to be modeled as a planning problem. It is simply the sliding tile puzzle! Its formal representation is not important for this exercise. Instead, we only look at the three heuristics that we already took a look at in the lecture: • The “number of misplaced tiles” heuristic. This heuristic counts the number of misplaced tiles. Please note that it counts tiles! Not positions! In other words, if the position (i, j) is empty in the current puzzle state, but it’s supposed to be occupied by some tile in the goal state, then the “wrong position” (i, j) does not contribute towards the heuristic value (as there is no tile on it). • The “Manhatten distance” heuristic. For each tile (again, tile!, not positions), add the horizontal plus vertical distance to its goal position. 2 • The “ignore some tiles” heuristic. This heuristic ignores a certain number of tiles, both in the current puzzle and the goal configuration. The resulting problem is solved optimally and the resulting solution cost is used as heuristic. For a fully defined heuristic, we had of course to define which tiles had to be ignored given some puzzle. This, however, is not important for the sake of this exercise. Just assume that for each puzzle state you are provided with a set of tiles that’s being ignored. Prove or disprove the following propositions. We do not expect anything formal here, but your arguments should be convincing enough to allow for your conclusion (i.e., using only natural language is sufficient, but don’t be too abstract). If a proposition is wrong, a proof would consist of a counter-example and an explanation why it is a counter-example. a) (2pts) The number of misplaced tiles heuristic h#MT is: • goal-aware. • safe. • admissible. • perfect. b) (3 pts) The Manhatten distance heuristic hMD is: • goal-aware. • safe. • admissible. • perfect. c) (3 pts) The ignore some tiles heuristic hIT is: • goal-aware. • safe. • admissible. • perfect. It is meant that the heuristic is perfect for any pattern. So if it is indeed perfect, show this for any possible pattern. It is not perfect if there exists a pattern for which it is not perfect. (So you can pick a pattern to construct a counter-example.) D. Executing A∗ (7 points) In this exercise you are supposed to experience the influence of heuristics’ guiding power. For this, you will execute the classical planning progression algorithm on the simple Cranes in the Harbor domain. You will not have to compute heuristics. Since the entire reachable state space consist of only six states we provide the heuristic values for you. (They are not computed by an actual heuristi
c but just chosen more-or-less arbitrarily.) This is the transition system: move move put take put take move move unload load move move Title: Lecture Slides for Automated Planning Source: nau/planning/slides/chapter01.pdf Licence: Attribution-NonCommercial-ShareAlike 2.0 Generic legalcode Copyright: Dana S. Nau Note that the transition system only mentions the action name “move”, but we differentiate between moveLeft and moveRight to differentiate between moving to the left location and the right location. Please be meticulous when writing down the move actions, because it is tempting to write down the “wrong 3 direction” (e.g., when moving from s2 to s0, the truck moves to the right, although the node s2 is on the left of s0, so don’t get that wrong). Assume that every action has a cost of 1. Assume that the initial state is s2 and the goal state is s5. Below, given the heuristic provided, you are supposed to execute the progression planning algorithm from the lecture. You do not have to show action applicability, instead you can simply use the transition system to identify which actions that are applicable in the respective states. You also do not have to write down the encoding of the planning states, it suffices to use the states’ names s0 to s5 (given in the graphic). You have to follow the annotation of the lecture! I.e., you have to draw one single search tree, just like in slide 19, which shows the A* search example of section AI search. Write to each node of the tree: • The content of the respective search node n. For example, the root node of the next exercise a) has to be labeled with “n = (s2, ε)”. • The f equation for n. E.g., you have to write “f(n) = g(n) + h(n) = 0 + 2 = 2” for the root note as mentioned above. • A number to indicate when you expanded the search node n (“expansion” meaning when you selected n from the search fringe to create its successors or to return the solution). The root note would obviously be annotated by “(1)”. Then, its successor with the smallest f value would get the “(2)”, and so on, until the solution node gets the highest number. a) (4 pts) Assume our heuristic, h1, has the following heuristic values: h1(s0) = 1, h1(s2) = 2, h1(s3) = 2, h1(s1) = 0, h1(s4) = 1, h1(s5) = 0. Execute the algorithm as described above. Hints: • The algorithm from the lecture does not check for duplicates. Since the transition system contains cycles it is likely that you will explore some states multiple times. • There is only one correct solution. The respective search tree will have 14 search nodes. • Again: Do not confuse moveLeft and moveRight ! b) (1.5 pts) Assume that instead of using h1 we would have used the heuristic h2, which has the same heuristic values for s3, s4, s5 as h1, but for the others it uses h2(s0) = 4, h2(s1) = 3, h2(s2) = 3. Can you make at least two observations about the resulting search tree (and, ideally, how it relates to the one from the previous exercise)? (Just one sentence each, this exercise is meant to make you think about the impact of using different heuristics, rather than testing your capabilities of proving properties.) c) (1.5 pts) Answer and prove (do not just say “yes” or “no”) the following questions: • Is h1 admissible? • Is h1 goal-aware? • Is h1 perfect? • (Remark: We do not ask whether h1 is safe because that would not make much sense as there are no states for which we defined h1 to be ∞.) 2. Relaxed Planning Heuristics. A. Algorithm to solve Delete-Relaxed Planning Problems (10 points) In the lecture we introduced delete-relaxation as a basis for heuristics. They were motivated as a domain- independent problem relaxation that makes a problem “easier” because all facts made true once will always remain true. It was claimed that solving a delete-relaxed problem can be done in polynomial time (which is a significant improvement because solving “normal” planning problems (where delete lists are not empty) takes exponential time). You have to prove that deciding whether a delete-relaxed problem has a solution can be done in polynomial time. To do so, • (6 pts) provide a decision procedure (i.e. an algorithm in pseudo code similar to the classical planning algorithm) that takes a delete-relaxed planning problem P+ = (V,A, sI , g) as input and that returns true if there is a solution and false if there is none. • (2 pts) Prove that your algorithm runs in polynomial time. • (2 pts) Prove (or explain) why the returned result (i.e., yes or no) is correct. 4 Hints: • Exploit the fact that executing an action (to progress some state to another) can never be a disad- vantage for the purpose of solving a (delete-free) planning problem, • exploit that there is no reason to ever execute an action more than once (i.e., once an action is executed it can be ignored). (By exploiting this the right way you can show that the algorithm runs in quadratic time (which is polynomial).) Recap In the lecture (recordings) we saw the proofs for: • hmax is not perfect. • hmax is safe. • hmax is goal-aware. • h+ dominates hmax Two of these proofs are based on the following fact: Let a¯ a solution plan for a planning problem P. Then, the delete-relaxed variant of a¯, a¯′ is a solution for the delete-relaxed variant of P, P+. You can assume the correctness of this property if you need it in the following. We will introduce two further heuristics, hadd (the add heuristic), and hPDB (the Pattern Database Heuris- tic). For these, you are supposed to prove these properties as well. B. Add Heuristic hadd (15 points) The hmax heuristic from the lecture can be interpreted as making the hardest fact in a goal condition true – the same applies to all the preconditions of all actions. Thus the preconditions of actions are taken into account by only a very limited extent, as only their hardest precondition contributes to the heuristic value, which is the reason why this heuristic is not very well informed. The add heuristic hadd tries to compensate that. Just like hmax we define hadd based on the relaxed planning graph. In contrast to hmax, rather than estimating an action’s cost based on it’s hardest precondition, we do this by adding over the cost of all preconditions. Based on the relaxed planning graph, hadd can be calculated as follows: • Action vertex: The cost of an action vertex a ∈ Ai is c(a) plus the sum of the predecessor vertex costs. Mathematically, this can be expressed as follows: hadd(a; s) = c(a) + hadd(pre(a); s) • Variable vertex: – The cost of a variable vertex v is 0 if v ∈ V 0. – For all v ∈ V i, i > 0, the cost of v equals the minimum cost of all predecessor vertices (these might be either action or variable vertices). Mathematically, this can be expressed as follows: hadd(v; s) = { 0 if v ∈ V 0 mina∈pred(v)hadd(a; s) otherwise Here, pred(v) stands for “predecessors”, which is the set of all actions that occur in an action layer before the vertex layer of v and add v. • Vertex set: For a set of state variables v¯ ⊆ V , the cost equals the sum of costs of the variables in v¯. Mathematically, this can be expressed as follows: hadd(v¯; s) = ∑ v∈v¯ hadd(v; s) For a state s ∈ S, hadd(s) equals the cost of g in the rPG that we start constructing in s. Just like hmax, hadd returns ∞ if and only if there does not exist a delete-relaxed solution for g (which is equivalent to stating that the final vertex layer does not contain all goals). Hint: Before you answer the following questions We recommend to compute the heuristic at least once in a small example, for instance in the Cranes in the Harbor Domain (you do already have a correct planning graph available, so you can easily and quickly annotate the respective values). 5 Answer and prove the following questions. As always: If some proposition does not hold, you can prove it by providing a counter-example (and showing/explaining that/why it is a counter-example). a) (2 pts) Is hadd perfect? b) (3 pts) Is hadd safe? c) (2 pts) Is hadd g
oal-aware? d) (4 pts) Is hadd admissible? e) (4 pts) Does hadd dominate hmax? C. Pattern Database Heuristics hPDB (15 points) Patter database heuristics (PDB heuristics) are a type of heuristic obtained by dropping a a subset of variables from the planning problem. The main idea is closely related to ignoring tiles in the sliding tile puzzle: Just make a world easier by completely ignoring certain parts of it! Given a planning problem P = (V,A, sI , g) and a set of variables – called a pattern – X ⊆ V , we restrict the planning problem to the pattern, thereby effectively ignoring all other state variables. Formally, we can define the resulting planning problem as PX = (X,AX , sIX , gX) with: • AX = {aX |a ∈ A} with – aX = (pre(a) ∩X, add(a) ∩X, del(a) ∩X, c(a)) for a ∈ A • sIX = sI ∩X • gX = g ∩X It is easy to see that the resulting planning problem PX is just a normal planning problem again, without any further special properties, it’s just smaller! (This is in contrast to, for example, delete-relaxation heuristics, because there the resulting planning problem has no delete-effects; here, however, depending on how we choose the pattern, we might still have delete effects.) The resulting problem PX is also referred to as “abstraction of P”. We will ignore many details about this heuristic as they will not be important for the purpose of this exercise. You only have to know that each “original” state s from the original problem’s search corresponds to exactly one “relaxed” state in the abstraction. Provided the heuristic uses a pattern X ⊆ V , we obtain the abstract state sX that corresponds to s by simply restricting s to X, i.e., sX := s ∩X. So if, during search, we encounter a state s, say {a, c, e, f}, and our heuristic uses the pattern X = {d, e, f}, then the PDB heuristic uses the state {e, f} for its computation. Now, completely similar to “ignoring tiles heuristic” in the Sliding Tile Puzzle, the PDB heuristic simply uses the cost of a perfect solution to the abstract problem as heuristic for the original state. Formally: Given the heuristic uses the pattern X, hPDB(s) (for P) is defined as h∗(sX) = h∗(s ∩X) in the problem PX . So, back in our example, hPDB({a, c, e, f}) for the original problem P would be defined as h∗({e, f}) in the abstracted problem PX . Answer (try to prove/disprove) the following questions for PDB heuristics. a) (2 pts) Is it perfect? Hint: It is completely obvious that this is not the case, so there is no harm in revealing that it’s not. For proving that it is not you are allowed to choose any pattern you want (for the counter example that you construct). b) (2 pts) If P = (V,A, sI , g) is the planning problem you are facing, can you provide a pattern X ⊆ V for which hPDB will be perfect? c) (3 pts) Is it safe? d) (2 pts) Is it goal-aware? e) (3 pts) Is it admissible? f) (3 pts) Let P = (V,A, sI , g) be a planning problem and X ⊆ V and Y ⊆ V patterns. Let hPBDX and hPBDY be the respective PDB heuristics that use X and Y as patterns, respectively. Assume X ⊇ Y . Does hPBDX dominate hPBDY or the other way round? Or is there no dominance among these heuristics? Explain (prove) your answer. Theoretical Methods II (see next pages) 6 3 Classical Propositional Logic (8pts.). Answer questions 1.1 to 1.3 below using only rules of propositional logic below and the lecture content. Clearly formulate and justify every argument in your proof using proper English. If you use a property listed as one of the questions on this assignment or listed in the lecture slides, please clearly state which question is it and how do you use it in your argument. Let A and B be logical statements. Propositional Logic Rules (there are more, but these set of rules are sufficient for the purpose of writing proofs for problems in this assignment): 1. To show that A⇒ B holds, we assume that A holds, then we deduce B. 2. If we know that both A and A⇒ B hold, then we can deduce B. 3. If we know that A holds and ¬A holds, then we can deduce F . 4. If we assume A holds, then deduced F , therefore ¬A must hold. 5. (Proof by Contradiction) To show that A⇒ B holds, we assume that both A and ¬B hold and deduce F . 6. If we know that A∧B holds, then we can deduce A and B (or equivalently in English, B and A). 7. If we know that A holds and B holds, we can deduce A ∧B 8. If we know that at least one of the following: (1) A holds, (2) B holds, then, we can deduce A ∨B. Note: Logical operators precedence order is the following ¬, ∧, ∨, and ⇒. Question A Show that (A ∧B)⇒ (B ∧ A). (2pts.) Question B Show that (A ⇒ B) ⇒ (¬B ⇒ ¬A). Deduce ¬A from ¬B using proof by contradiction. (4pts.) Question C Show that ¬¬A⇒ A using proof by contradiction. (2pts.) 1 4 Natural Numbers (32pts.). Using only given definitions below and the lecture content, answer the questions below. Clearly formulate and justify every argument in your proof using proper English. If you use a property listed as one of the questions on this assignment or listed in the lecture slides, please clearly state which question is it and how do you use it in your argument. Definition 1 (Natural Numbers N). Let 0 be a term. For n = (S x), n is a term if and only if x is a term, and we say that n is a successor of x. Let the set of Natural Numbers N and for its element n, we write n ∈ N and we say that n is a natural number. We have n ∈ N if and only if either n = 0 or n = (S x) if x ∈ N, and nothing else is a natural number. Thus, the natural numbers N is the set N = {0, (S 0), (S (S 0)), . . . }, which we write as {0, 1, 2, . . . }. J As mentioned in the slides, we will also assume arithmetical operations ”+” and ”×” over n ∈ N which for natural numbers a, b ∈ N, have the properties: • closed: a + b and a× b are also natural numbers, and • commutative: a + b = b + a and a× b = b× a. • ”×” is distributive: (a + b)× c = (a× c) + (b× c) Definition 2 (odd and even). For unary functions Odd and Even that accepts a natural number n, we have: • Even(n) = T if and only if ∃m ∈ N such that n = m× 2, and • Odd(n) = T if and only if ∃m ∈ N such that n = (S (m× 2)). J Question A Show by a direct proof that Odd(n) ∧ ¬Even(S n)⇒ F . (2pts.) For questions 2.2 to 2.7, consider the definition below. Definition 3 (ordering). For functions Geq and Leq that take two natural numbers, we have: • Geq(n,m) = T if and only if ∃k ∈ N such that n = m + k, and • Leq(n,m) = T if and only if ∃k ∈ N such that n + k = m. J 2 Question B Show that for n,m ∈ N, Leq(n,m) if and only if Geq(m,n) (i.e: this is equivalent to showing Leq(n,m)⇒ Geq(m,n) and Leq(n,m)⇐ Geq(m,n). (2pts.) Question C Show that for n,m, j ∈ N such that n 6= m 6= j, if Leq(n,m) ∧ Leq(m, p), then Leq(n, p). (4pts.) Question D Show that Geq(n,m) ∧ Leq(n,m)⇒ n = m. (2pts.) Question E Show by induction that ∀n ∈ N, Geq(n, 0). (4pts.) Question F Show by a direct proof that ∀n ∈ N, ∃m ∈ N where m 6= n such that Leq(n,m). (2pts.) Question G Show that for all n ∈ N, there exist m ∈ N such that ((Odd(n)⇒ Even(m))∨ (Even(n)⇒ Odd(m)))∧Geq(m,n). Use a method of proof that you think is appropriate (i.e: induction, direct, by contradiction, etc.). Justify your choice in a few sentences. (6pts.) Hint: Consider the definition of ’+’, which is: a + b = c iff c = (S (S . . . S (a) . . . ) (i.e: we apply S b-times to a). Question H Show that for all natural numbers n and m, we have Geq(n,m) ∨ Leq(n,m). (4pts.) Hint: Again, consider the definition of ’+’, which is: a+ b = c iff c = (S (S . . . S (a) . . . ) (i.e: we apply S b-times to a). Also recall the definition of a natural number. Question I Show that ∀a, b ∈ N such that b 6= 0, there exist q, r ∈ N such that (a = (b × q) + r) ∧ (Leq(r, b)). (6pts.) 3


Author admin

More posts by admin