3806ICT Assignment 3 Objective Gain knowledge and insight on AI planning, model checking, and reinforcement learning (RL) through research and experiment. Task 1: Model the Grid World Maze in PAT A grid world of maze is a 2-D matrix of points. Each point is either • an 'O' for open space, or • an 'H' for wall/obstacles, or • an 'S' for the starting location, or • a 'G' for the goal location. You can choose integers in PAT to represent those types of points as long as you use them consistently. Model a 10x10 grid world maze in PAT using the communicating sequent processes (CSP) module. You can place the walls, the starting point, and the goal anywhere you wish. Model the assertion for reaching the goal. Use model checking to find the optimal path. Task 2: Model the Grid World Maze for RL See Workshop 10. Task 3: Parameterise the Grid World Automate the grid world modelling process by writing a piece of code to generate a grid world of arbitrary size. Place the walls, the starting point, and the goal at random locations as long as they do not overlap. Your code should take x and y as input parameters and generate a grid world of size x by y. Task 4: Translate the Grid World to a PAT Model and a Model for RL PAT recognises multi-dimension arrays in a specific syntax. See the details in Section 3.1.1.1 in the link below. https://pat.comp.nus.edu.sg/wp-source/resources/OnlineHelp/htm/index.htm You can model a 2-D array as a flattened 1-D array in PAT and access the elements using index arithmetic coded by yourself. For reinforcement learning, you only need to modify the grid.txt file accordingly. The goal of this task is to take a grid world matrix as input, and generate two files: • a .csp file of a PAT model, and • a .txt file for RL. Both files should contain the same grid world maze. Task 5: Experiment on PAT vs RL for Maze Runner Conduct an experiment on PAT vs RL using the maze case study. You should test randomly generated mazes of different sizes. For example, you can randomly generate mazes of size 5x5, 10x10, 20x20, 50x50, 100x100, 200x200, 500x500, 1000x1000 etc., and use PAT and RL (you must test the same maze on PAT and RL in each case, obviously) to find the optimal path, and compare the results in terms of computation time used and the length of paths. The computation time of PAT is the time used for verification, and the computation time of RL is the time of training and testing combined. Construct a table to show your results. Write a short analysis of the table and the results. Submission • It must not exceed 5 pages, including figures, tables, and references. • Any information taken from the literature must be cited. • The text must be in 12-point Times New Roman or the default font in LaTex, single spacing. • Page size must be A4 with 2cm margins on all sides. • The report must have a title. • The report must list all the members of the group under the title. • The report must start with an abstract which should be in one paragraph and should not exceed 200 words. • LaTex is the preferred word-processing software, but Word is ok, too. • The report must be submitted as a PDF file. The report must satisfy the following requirements: Regarding programming languages in the Group Assignment: The automatic generation (Task 3) and map transaction (Task 4) can be coded in your favourite language. You can also automate the experiment (Task 5) in whatever language you like. The only requirement on the language is that the PAT model has to be done in PAT (obviously). Task 2 will be done in Python in Workshop 10, but you can program it your own way if you wish.





















































































学霸联盟