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]
