5COM2003 Practical Assignment: Report on a paper (Variant A – Graph measures) 5COM2003 Artificial Intelligence Semester B 2022/2023 In this assignment, you will apply some of the notions, principles, methods and algorithms we touched on in the Artificial Intelligence lectures and prac- ticals to design, program, test, explain and demonstrate an agent based on a given paper. There are 25 marks to achieve, each

5COM2003 Practical Assignment: Report on a paper (Variant A – Graph measures) 5COM2003 Artificial Intelligence Semester B 2022/2023 In this assignment, you will apply some of the notions, principles, methods and algorithms we touched on in the Artificial Intelligence lectures and prac- ticals to design, program, test, explain and demonstrate an agent based on a given paper. There are 25 marks to achieve, each translating to 1% of your overall module grade. This assignment requires you to: 1. read (parts of) a paper 2. program parts of it (with some alterations) 3. explain your design choices 4. run a simulation and collate results 5. evaluate your simulation’s results Submission requirements The work must be your own. You may of course collaborate but the work handed in must be distinctly yours. The following two sets of documents must be submitted on StudyNet/Canvas: (a) A .zip archive containing your commented code. 1 (b) A report in PDF format providing the explanations and figures re- quested in the tasks given below. You do not specifically get marks for comments, but where code is required and not readable marks might be deducted based on unreadability. Assume the reader of your code is one of the better programmers in your cohort. On some task you will see a word count. This is not a specific requirement, but a guidance about expectations. Do make sure you are using the words effectively to describe key aspects and choices. Reading: Empowerment and Relevant Goal Information as Alternatives to Graph-Theoretic Centrality for Navigational Decision Making Your paper can be found here: Empowerment and Relevant Goal Information as Alternatives to Graph- Theoretic Centrality for Navigational Decision Making by Marcus Clements. It is the work of a former (research) MSc student here at UH, Marcus Clements. And sits in the triangle between established graph theoretical metrics, information theoretical measures such as empowerment and rele- vant goal information(RGI), and human decision making. All of this on the example of a street network in Soho. You are asked to read these parts of it in particular: • The abstract to learn about the general goal. (page 2) • Chapter 1 until including 1.2, for a general motivation and idea. (page 6-10) • Chapter 2.5 explaining some graph measurement you will be asked to implement. (page 23) ● The conclusion 5.1 for some of the results of the research. (page 55) You may of course – read more of the paper and it will help in your under- standing, but these are the required parts the later test will be based on. You 2 will find a lot of parallels to our lectures in the module, feel free to compare 🙂 World design [5 total marks] The basis for this world can be found on page 33 of the reading material. It is a undirected graph with seven vertices and seven edges. You have three tasks based on this: 1. Implement the graph using a node, an edge, and a graph class. [1 mark] 2. Draw an UML Class diagram containing the variables and functions of each class as well the relations between them. [2 marks] 3. Write a paragraph explaining your design choices. (20-50 words) [2 marks] World metrics [8 total marks] In chapter 2.5, three graph metrics are given. Your task is to implement these measure in your program. 1. Write a class GraphMetrics and implement all three metrics as func- tions in it. [1/2/3 marks] 2. Write a text explaining your overall design choice. Mention how you computed the shortest paths(geodesics) for your implementation for the Betweenness Centrality function. (40-55 words) [2 marks] Agent design and simulation [12 total marks] Agent Design [5 total marks] Write an agent capable of walking from a given start node to another given target node through the graph. The agent should posses two modes of movement: 1. Random Walk [1 marks] 3 2. Shortest Path [1 marks] In order to help your shortest path walking. Compute the shortest paths between each pair of nodes once and store them in a suitable data structure to avoid constant recomputation. [1 mark] To enable future analyses the agent should also posses some memory for each episode (each navigation from start to target). And the ability to return this information at the end of the navigation task. Give your agent the ability to sense its current state (including start and target) and store each visited node during one episode. [1 mark] To round the task out, update the UML Class Diagram from earlier to include the agent and its capabilities. [1 mark] Simulation [2 total marks] Use both Agent and World you can now run one simulation – and episode – as given below [1 mark]: 1. Randomly select a start and (different) target node from the seven possible choices. 2. Count all nodes visited. 3. Store the results. Run 1000 simulations each Random Walk and the shortest path movement, for a total of 2000. Keep the result separated. [1 mark] Evaluation [5 total marks] Compare your results for both movement modes in a table. [0.5 marks] Write an analyses of your obtained results along the lines of these questions: [30-60 words] [2 marks] • What are the differences between the two movement modes? • Why are we seeing these results? • Do the results surprise you? 4 ст Create a second table comparing the outputs of the graph metrics with the simulation results.[0.5 marks] (You may also do this in one big table.) Compare your results to the metrics. In how far do the results align with the metrics? Compare the different numbers along the same lines as above. [30-60 words] [2 marks]