Option B
Microsoft Word - COS30019-2019 S1-A1.doc COS30019 - Introduction to AI Assignment 1 Page 1 of 7 Assignment 1 – Tree Based Search Due 4:30pm Friday 26th April 2019 (Week 7) Contributes 20% to your final subject result, subject to moderation if required. Individual. For this assignment, you can choose either Option A or Option B: 1. For Option A, we would like to solve the NxM-Puzzle problem. You will be given a Java code base allowing you to search for solutions of the NxN problem and your job is to understand how it works and possibly extend this given program. You can only achieve a maximum of 80% if you choose this option. Note that you can also re-implement the Java code in a language of your choice for this option. 2. For Option B, we would like to solve the Robot Navigation problem. You will write the whole program from scratch. You can achieve up to a maximum of 110% if you choose this option. This assignment requires you to work individually to get working tree based search algorithms. OPTION A - Summary We would like to implement tree-based search algorithms in software to search for solutions to the NxM- Puzzle problem. Both informed and uninformed methods will be implemented to allow you to understand how these methods work. You will be given a Java code base that implements several search algorithms (BFS and GBFS) to search for solutions of the NxN-Puzzle problem. Your tasks are to: 1. Gain a good understanding of how search methods work in this particular problem by generating many different tests cases to see how these problems can be solved; 2. Extend the given code base to allow other search algorithms to be implemented, such as DFS and A*; 3. Further extensions are possible: a. Can you extend the given code base to implement other search methods such as iterative deepening depth-first search or IDA*? b. The provided code base is not very efficient (especially the BFS search method), can you find a way to improve its performance? How much does your improved version gain in terms of performance? c. The given code base only works for the NxN-Puzzles, can you extend it to work with any NxM- Puzzles? Note that if N≠M, the given code base will not work; Note that, eventually your implementation will be tested on a standard Microsoft Windows 7 system. The NxM-Puzzle Problem In the lectures you have seen the 8-puzzle problem. The N-Puzzle problem (or, sliding puzzle, sliding tile puzzle) is a generalisation of the 8-puzzle problem where N=3, 8, 15, … You are referred to http://en.wikipedia.org/wiki/Sliding_puzzle and http://en.wikipedia.org/wiki/Fifteen_puzzle for informal descriptions of the problem. The 8-puzzle can also be viewed as a 3x3-puzzle as each side of the puzzle grid has 3 cells. As a generalisation of the 3x3-puzzle problem, we can have NxM-puzzle problems where N and M are positive integers and N is not necessarily equal to M and there is one blank cell. For instance, the following 5x3 puzzle consists of cells labelled by numbers 1..14 on a 5x3 grid and the blank cells labelled by number 0. 1 2 3 5 11 6 12 10 13 4 9 8 7 14 COS30019 - Introduction to AI Assignment 1 Page 2 of 7 The above configuration will be represented by the following sequence (with the number 0 representing the empty cell): 1 2 3 5 11 6 4 13 9 8 0 12 7 10 14 File Format: The problems are stored in simple text files with the following format: First line contains a string NxM: N representing the number of rows of the puzzle and M represents the number of columns of the puzzle. For example, if the first line is 5x3 then the puzzle has 5 rows and 3 columns. The next two lines represent the start-configuration and the end-configuration, respectively, of the puzzle your program is supposed to solve. We will only be interested in search algorithms. Therefore, you can assume that the problem files will contain valid configurations. For instance, if NxM=3x4 then you don’t have to worry that the problem file will contain a cell labelled by number 12. Search Algorithms The following are standard tree-based search algorithms (covered in the lectures): Search Type Description Method Uninformed depth-first search Select one option, try it, go back when there are no more options DFS breadth-first search Expand all options one level at a time BFS Informed greedy best-first Use only the cost to reach the goal from the current node to evaluate the node GBFS A* (“A Star”) Use both the cost to reach the goal from the current node and the cost to reach this node to evaluate the node AS Note1: When all else is equal, nodes should be expanded according to the following order: the agent should try to move the empty cell UP before attempting LEFT, before attempting DOWN, before attempting RIGHT, in that order. You are given a Java code base implementing BFS and GBFS for the NxN-Puzzle. You can start learning about search algorithms by playing with this code base. Try to create many test cases to gain an understanding of how search algorithms work. You will find that this code base is NOT perfect. It is quite slow. It does NOT follow the instruction in Note1 above (see the TODO in the code). Part of your job is to improve this code base. Command Line Operation The given program operates DOS command-line interface which can be brought up in Windows 7 by typing cmd into the search box at the Start button. Below is how to run the given program from DOS command line: > nPuzzler
You can try the program with the given file N-puzzle-test.txt and the two provided search methods BFS and GBFS. If you test it with a NxM-puzzle (e.g., the given file NM-puzzle-test.txt), it won’t work. Report You must include a single Report (between 5 and 10 pages, either in Microsoft Word or in PDF) with your work with the following details: Student Details: Your full student name and student ID. Features/Bugs/Missing: Include a list of the features you have implemented. Clearly state if a required feature has not been implemented. Failure to do this will result in penalties. Include a list of any known bugs. COS30019 - Introduction to AI Assignment 1 Page 3 of 7 Acknowledgements/Resources: Include in your report a list of the resources you have used to create your work. A simple list of URL's is not enough. Include with each entry a basic description of how the person or website assisted you in your work. Discussion: A full description of the problem, the solution and other findings you may want to include about your research ideas and results. In particular, you have to include a section on your understanding of how the given program solves the problem using tree search. In this section, you need to provide at least one example (based on a data file you created) so that you can draw the search trees that the given program traverses when finding a solution of the problem. If you write extra code to extend the given program, please describe them as well. Notes: Anything else you want to tell the marker, such as how to use the GUI version of your program, and something particular about your implementation. Marking Scheme & Submission You must submit your work via the online assignment collection system ESP https://esp.swin.edu.au/ Create a single zip file with your code and a working version of your program. Do not use deep folder hierarchies. The upload limit to ESP will be 10 MB. Please consult early if you have a large binary/package for some. You must also include your report in your submission. If you have generated some data files to gain your understanding of these search algorithms AND your report refers to these data files, please include these data files as well. Standard late penalties apply - 10% for each day late, more than 5 days late is 0%. Marking Scheme Requirements (or equivalent sections) Mark If you can extend the program and get DFS work well 10 If you can extend the program and get A* work well 10 If you can extend the program and get some other informed search method work well 10 If you can extend the program and get it work with NxM-Puzzles OR you can find a way to improve the performance of the program (you only need to do one of them). 15 Report: Clear and provide sufficient information (e.g., providing a clear example) about your understanding of how tree-based search works. Clear explanation of the algorithms you implement and how you implement them. 35 Total 80 You need to follow good programming practice (e.g., well-designed, well-structure codes with clear and helpful comments). Failure to do so get penalty. Up to -20 You need to demonstrate the progress you make every week to your tutor. That is, if your tutor approach you and ask for the progress, you have to be able to show the tutor the progress you have made in comparison to the previous week. Failure to do so get penalty. Up to -50 COS30019 - Introduction to AI Assignment 1 Page 4 of 7 OPTION B - Summary You need to implement tree-based search algorithms in software (from scratch) to search for solutions to the Robot Navigation problem. Both informed and uninformed methods will be required. You will also need to do some self-learning to learn several search methods (not covered in the lectures). Implementation You are welcome to implement your software using any of the following languages; Java or C++/C#. You must gain permission before using anything else. Assignment work will be tested