FIT5047 Semester 1, 2020 Assignment 1(100 marks =20%) Due Date: May 8,10:00pm Submission: You have to submit two things i) your report (in pdf format) which answers all questions (except programming) in this assignment in both Moodle link and Turnitin; ii) your program file (one single .py file) for Question 1 in Moodle link. Note 1: Please follow the University and Faculty policies and regulations regarding Academic Integrity. Details please find from https://www.monash.edu/__data/assets/pdf_file/0004/801841/Student-Academic- Integrity-Policy.pdf Note 2: You will be required to present your work during tutorial in week 8 individually. Please be prepared. This is compulsory in this assessment. Please be aware that the time of interview might be subject to change. The time will be determined by your lecturer and tutor. Question-1: Problem Solving as Search (total marks 40) The Problem: Consider a grid of size N x N that represents a topographic map. Each tile describes the characteristics of its terrain, which could be of two types: normal or mountainous. ROBBIE the robot must navigate from a starting position (xs,ys) to a goal position (xg,yg) using a learned algorithms (there can only be one start and one goal). Note: In the explanations below, we assume that tile (1,1) is the top-left tile in the map. Transition rules: ROBBIE is allowed to go to one of the (at most) eight surrounding tiles, as shown in Figure 1(a). However, it cannot move to a mountainous tile, and it cannot move diagonally if one of the directions composing the diagonal contains a mountainous tile. For instance, the black tile in Figure 1(b) represents a mountain, hence ROBBIE can move only to the five white tiles indicated by the arrows. In contrast, ROBBIE can move to seven tiles in Figure 1(c). Path cost: ROBBIE’s wheels are built so that a diagonal move is the easiest. Hence, the cost of such a move is 1. Any other move has a cost of 2. The Task: Your task is to write a Python 3 program called planpath that plans a path from a given starting tile to a goal tile. • You should implement either Graph or Treesearch procedure to perform A*. • Propose and implement a heuristic function for solving this problem. • Determine whether this function is admissible or monotonic, and explain why. Is the resulting algorithm A or A*? • You will need to implement tie-breaking rules when all options have equal merit. Specify clearly in your documentation what are your tie-breaking rules. Calling your program: Your program will have two command line arguments as follows: python planpath.py INPUT/inputi.txt OUTPUT/outputi.txt Flag Flag where the folders INPUT and OUTPUT should reside in the same folder as your program. • inputi.txt – the name of the input file, where i is the number of the input file; • outputi.txt – the name of the output file, where i is the number of the output file; • Flag – indicates how many node expansions require a diagnostic output (if it is 0, no diagnostic output is required) – see the example later on in the assignment. Input: • The first line will contain one number that specifies the number of rows and columns in the map. • Subsequent lines will contain the map, one line per row. The following values will be accepted for each tile: The following illustrates a procedure call and sample input for applying A/A* to a 3×3 map and printing diagnostic output for 5 iterations: python planpath.py INPUT/input1.txt OUTPUT/output1.txt 5 where input1.txt is 3 SXR RRR XXG Output: Your program should produce a sequence of moves that ROBBIE should perform to get from the start node to the goal, and the accumulated cost and ROBBIE’s position after each move. Output format: • The sequence of moves should be formatted as a list of actions separated by dashes followed by a blank space and the cost of the path according to the algorithm. If no path was found, the output should state NO-PATH. • The actions (in UPPER CASE) are: R (Right), RD (Diagonal Right-Down), D (Down), LD (Diagonal Left-Down), L (Left), LU (Diagonal Left-Up), U (Up), RU (Diagonal Right-Up). • For example, a path that goes Start, Right, Right-Down, Down, Down, Left- Down and Goal, with a total cost of 8, is represented as follows: S-R-RD-D-D- LD-G 8 Programming Requirements: • Your program should be written in Python 3. • Your program can only utilize Panads and Numpy package instead of any other advanced level packages. • Your program should create a unique identifier for every generated node. The identifier of the start node should be N0, and other nodes should be identified as N1, N2, . . . according to the order in which they are generated. If you wish, you can include the actions used to reach a node in its identifier, e.g., N0-R-D. If you implement Graphsearch (as opposed to Treesearch), you need to identify when a repeated instance of a node is reached, and use only the first identifier created for this node. • Your program should work on different maps, including those provided in moodle. • The Graph/Treesearch procedure should build a search graph/tree respectively. Each node in the search graph/tree should have the following components: 1. an identifier; 2. the operator that generated it; 3. order of expansion (if in CLOSED) otherwise 0; 4. the cost g of reaching that node; 5. a heuristic value h (0 for DLS); 6. a value f, where f=g+h; 7. a pointer to its children; and 8. a pointer to its parent (if you implement Treesearch, and your action sequence is included in a node identifier, then this pointer is not necessary). • In diagnostic mode (Flag ≥ 1), each time a node is expanded, your program should output the following components: 1. node identifier; 2. order of expansion; 3. the cost g of reaching that node; 4. a heuristic value h; 5. a value f, where f=g+h; 6. the resolution of pointer to its children, i.e., the identifier of each child of the expanded node and the action that generated it; 7. the lists OPEN (sorted in descending order of merit) and CLOSED. The value of Flag will be small, so don’t worry about OPEN and CLOSED being too long. Failure to print OPEN and CLOSED will result in loss of marks. Output example: Say node N0:S at position (1, 1) is the first node to be expanded by some search algorithm not A*. The output for this step should be something like the following: • N0:S 1 0 0 0 # ID expansion-order g, h, f • Children: {N1:S-R, N2:S-RD, N3:S-D } • OPEN: {(N1:S-R 2 0 2), (N2:S-RD 1 0 1), (N3:S-D 2 0 2) } • CLOSED: {(N0:S 1 0 0 0)} Question 2: First order logic, representation (2× 4 = 8) Use the following vocabulary to express the assertions in the following sentences: – MALE(x) means that the object denoted by x is male. – FEMALE(x) means that x is female. – VEGETARIAN(x) means that x is a vegetarian. – BUTCHER(x) means that x is a butcher. – LIKES(x, y) means that x likes y. a. No man is both a butcher and a vegetarian. b. All men except butchers like vegetarians. c. The only vegetarian butchers are women. d. No man likes a woman who is a vegetarian. Question 3: Unification (2 × 2 = 4) In the following pairs of expressions, w, x and y are variables, A and B are constants, and f and g are functions. Do these pairs of expressions unify? If they do, give the substitution that unifies them. If they don’t, then indicate where the unification fails. a. P(x,f(x),A,A) and P(y,f(A),y) b. P(x,f(x,y),g(x,w)) and P(A,f(w,B),g(w,x)) Question 4: Resolution refutation ((4 × 2 + 2 × 0.5) + (4 × 1) + 11 = 24) Consider the following statements: 1. A student is successful if s/he has high grades. 2. Students who are bright and work hard have high grades. 3. Students who are not bright fail CSEXXX. 4. Students who do not work hard have lots of fun. 5. James is not having any fun. 6. James passed CSEXXX a. Use the predicates SUCCESSFUL, HIGH-GRADES,
BRIGHT, WORK-HARD, HAS-FUN and PASS (the opposite of FAIL) to represent these statements as predicate calculus formulas. DO NOT include STUDENT as a predicate, as it complicates the solution. b. Convert these statements to clauses. c. Use resolution refutation to prove that James is a successful student. Question 5: Resolution refutation ((2 × 2 + (4 × 1) + (6 + 10) = 24) Consider the following statements: 1. Every boy or girl is a child. 2. Every child gets a doll or a train or a lump of coal. 3. No boy gets a doll. 4. No child who is good gets a lump of coal. a. Use the predicates BOY, GIRL, CHILD, GET-DOLL, GET-TRAIN, GET- COAL and GOOD to represent these statements as predicate calculus formulas. b. Convert these statements to clauses. c. Use resolution refutation to prove that if no child gets a train, then no boy is good. Also note: • Students should submit a file called FIT5047_StudentId_1stSem2020_Asst1.pdf to the relevant place on Moodle. • Students using a .py program in Question 1 should also submit a second file is: FIT5047_StudentId_1stSem2020_Asst1.py • Please note that StudentID refers to your Student ID number. So, as an example, if your StudentId is 12345678 and you submit a Python file, then you should submit two files, respectively called FIT5047_12345678_1stSem2020_Asst1.pdf and FIT5047_12345678_1stSem2020_Asst1.py . • Recall notes on page 1 about Academic Integrity and about the requirement for your attending an interview as a compulsory part of your assessment. —- END OF FIT5047 1st Semester 2020 Assignment 1 —-
