COMP3702 Artificial Intelligence (Semester 2, 2023) Assignment 2

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP3702 Artiicial lntelligence (semester 2, 2023)

Assignment 2: DRAGONGAME MDP

key information:

. Due:  3pm， wednesday 20 september

.  This assignment assesses your skills in developing algorithms for solving MDPs.

.  Assignment 2 contributes 20% to your inal grade.

.  This assignment consists of two parts:  (1) programming and (2) a report.

.  This is an individual assignment.

. Both the code and report are to be submitted via Gradescope (https://www.gradescope.com/). you can ind a link to the COMP3702 Gradescope site on Blackboard.

. your program (Part 1, 50/100) will be graded using the Gradescope code autograder, using testcases similar to those in the support code provided at https://gitlab.com/3702-2023/a2-support.

. your report (Part 2, 50/100) should it the template provided, be in .pdf format and named according to the format a2-COMP3702-[sⅠD].pdf, where slD is your student lD. Reports will be graded by the teaching team.

The DRAGONGAME AI Environment

“untitled Dragon Game”1 or simply DRAGONGAME, is a 2.5D Platformer game in which the player must collect all of the gems in each level and reach the exit portal,  making  use of a jump-and-glide movement mechanic, and avoiding landing on lava tiles.  DRAGONGAME is inspired by the  “spyro the  Dragon” game series from the original Playstation.  For this assignment, there are some changes to the game environment indicated in pink font.  ln Assignment 2, actions may have non-deterministic outcomes!

To optimally solve a level, your Al agent must ind a policy (mapping from states to actions) which collects all gems and reaches the exit while incurring the minimum possible expected action cost.

Levels in DRAGONGAME are composed of a 2D grid of tiles, where each tile contains a character representing the tile type. An example game level is shown in Figure 1.

Figure 1:  Example game level of DRAGONGAME, showing character-based and Gul visualiser representations

Game state representation

Each game state is represented as a character array, representing the tiles and their position on the board. ln the visualizer and interactive sessions, the tile descriptions are graphical assets, whereas in the input ile these are single characters.

Levels can contain the tile types described in Table 1.

Table 1: Table of tiles in DRAGONGAME, their corresponding symbol and efect

An example of performing the walk Right action on a super charge tile is shown in Table 2:

Table 2:  Example walk  Right action on a super charge tile

The ‘, on the green tile represents the current player position, ‘>>>, represents tiles which are skipped over, and each (P) represents a possible new position of the player.

Actions

At each time step, the player is prompted to select an action. Each action has an associated cost, representing the amount of energy  used  by  performing that action.   Each  action  also  has  requirements which  must  be satisied  by the current state  in order for the action to  be valid.   The  set  of available actions, costs and requirements for each action are shown in Table 3.

Table 3: Table of available actions, costs and requirements



Example of glide action validity requirements for GLⅠDE RⅠGHT 2 (‘gr2,):

Interactive mode

A good way to gain an understanding of the game is to play it. You can play the game to get a feel for how it works by launching an interactive game session from the terminal with the following command:

$ python play-game.py  .txt

where .txt is a valid testcase ile from the support code with path relative to the current directory, e.g. testcases/L1.txt

ln interactive mode, type the symbol for your chosen action and press enter to perform the action.  Type‘q, and press enter to quit the game.

DRAGONGAME as an MDP

ln this assignment, you will write the components of a program to play DRAGONGAME, with the objective of inding a high-quality solution to the problem using various sequential decision-making algorithms based on the Markov decision process (MDP) framework.  This assignment will test your skills  in deining a MDP for a practical problem and developing efective algorithms for large MDPs.

what is provided to you

we provide supporting code in Python, in the form of:

1.  A class representing the DRAGONGAME environment and a number of helper functions (in game  env.py)

一 The constructor takes an input ile (testcase) and converts it into a DRAGONGAME map

2.  A class representing the DRAGONGAME game state (in game state.py)

3.  A graphical user interface for visualising the game state (in gui.py)

4. A solution ile template (solution.py)

5. A tester (in tester.py)

6.  Testcases to test and evaluate your solution (in  ./testcases)

The  support  code  can  be  found  at: https://gitlab.com/3702-2023/a2-support. Please  read  the README.md  ile  which  provides  a  description  of  the  provided  iles.    Autograding  of  code  will  be  done through Gradescope, so that you can test your submission and continue to improve it based on this feedback — you are strongly encouraged to make use of this feedback.

your assignment task

Your task  is  to  develop  planning  algorithms  for  determining  the  optimal  policy  (mapping  from  states  to actions) for the agent (i.e. the Dragon), and to write a report on your algorithms, performance. You will be graded on both your submitted program (part 1，50%) and the report (part 2，50%).  These percentages will be scaled to the 20% course weighting for this assessment item.

The provided support code formulates DRAGONGAME as an MDP, and your task is to submit code imple- menting the following MDP algorithms:

1. value lteration (vl)

2.  Policy lteration (Pl)

Once you have implemented and tested the algorithms above, you are to complete the questions listed in the section  “Part 2 - The Report” and submit the report to Gradescope.

More detail of what is required for the programming and report parts are given below.

part 1 — The programming task

Your program will be graded using the Gradescope autograder, using testcases similar to those in the support code provided at https://gitlab.com/3702-2023/a2-support.

Interaction with the testcases and autograder

we  now  provide you with some details explaining  how your  code will  interact with the testcases and the autograder (with special thanks to Nick Collins for his eforts making this work seamlessly).

lmplement your solution  using  the  supplied  solution.py  template  ile.   You  are  required  to  ill  in  the constructor and the following method stubs of the solver class:

. vi initialise()

. vi is converged()

. vi iteration()

. vi get state value()

. vi select action()

. pi initialise()

. pi is converged()

. pi iteration()

. pi select action()

You can add additional helper methods and classes (either in solution.py or in iles you create) if you wish. To ensure your code is handled correctly by the autograder, you should avoid using any try-except blocks in your implementation of the above methods (as this can interfere with our time-out handling).  Refer to the documentation in solution.py for more details.

lf you are unable to solve certain testcases, you may specify which testcases to attempt in testcases to attempt.

Grading rubric for the programming component (totaI marks:  50/100)

For marking, we will use 5 diferent testcases to evaluate your solution.  Each test case is scored out of 10.0 marks in the following categories:

a)  completion/reaching goal (0.5 pts pass/fail)

b)  Number of lterations vs target (up to 1 pt with partial marks)

c)  Average time per iteration vs target (up to 1 pt with partial marks) [disqualiied if max time per iteration

is much greater than the mean]

d)  convergence of values/policy (1pt pass/fail)

e)  values - distance from reference solution values (up to 1 pt with partial marks) [assessed for vl only]

f)  Reward vs target (up to 1 pt with partial marks)

This totals to 5.5 marks per testcase for vl, 4.5 marks per testcase for pl, resulting in 10 marks per testcase, and 50 marks total over 5 testcases.

Part 2 — The report

The report tests your understanding of MDp algorithms and the methods you have used in your code, and contributes 50/100 of your assignment mark.

Question 1.   MDP probIem deinition (18 marks)

a)  Deine  the state space,  Action space,  Transition function, and  Reward function components of the DRAGONGAME MDp planning agent as well as where these are represented in your code.  (10  marks)

b)  Describe the purpose of a discount factor in  MDps.                                                                   (3 marks)

c)  state and briely justify what the following dimensions of complexity are of your agent  in the DRAG-

ONGAME MDp. (see https://artint.info/3e/html/ArtⅠnt3e.ch1.S5.html for deinitions) (5 marks)

.  planning Horizon

.  sensing uncertainty

.  Efect uncertainty

.  computational Limits

.  Learning

Question 2. comparison of aIgorithms (17 marks)

This question requires comparison of your implementation of value iteration (vl) and policy iteration (pl). lf you did not implement pl, you may receive partial marks for this question by providing insightful relevant comments on your implementation of vl. For example, if you tried standard vl and asynchronous vl, you may compare these two approaches for partial marks.

a)  Describe your  implementations of value  lteration and  policy  lteration  in one sentence each.   lnclude details such as whether you used asynchronous updates, and how you handled policy evaluation in pl. (2 marks)

b)  pick three  representative testcases to compare the performance of vl and pl, reporting the numerical values for the following performance measures:                         (6 marks)

.  Time to converge to the solution.

.  Number of iterations to converge to the solution.

c)  Discuss the diference  between the numbers you found for vl and pl. Explain and provide reasons for why the diferences either make sense, or do not make sense.                                                     (9  marks)

Question 3. Investigating optimaI poIicy variation (15 marks)

One consideration in the solution of a Markov Decision process (i.e.  the optimal policy) is the trade of between a risky higher reward vs a lower risk lower reward, which depends on the probabilities of non-deterministic dynamics of the environment and the rewards associated with certain states and actions.

Consider testcase  L4.txt,  and  explore  how  the  policy  of  the  agent  changes  with  ladder  fall prob  and game over penaltg . The agent must cross from the bottom left (to collect a gem) to the bottom right (to reach the exit).  There are 3 possible paths from left to right (bottom,  middle and top).   Because  of the chance to fall when performing a walk action while on top of a ladder, there is a risk of falling into the lava in the centre.

Figure 2: Testcase L4.txt

.  The bottom path has the lowest cost (fewest jumps  needed) and highest risk, as the lava tiles above prevent using jump+glide (which is more expensive than walking but has no fall risk).

.  The middIe path also  has lava tiles above preventing jump+glide, but if the agent falls once it can glide and land in a safe part of the bottom path for a second chance at making it across.

.  The top path has enough headroom to allow jump+glide (which eliminates the risk of falling),  but requires a large number of jumps to reach, so is expensive.

The  level  of  risk  presented  by  the  lower  paths  can  be  tuned  by  adjusting  the  ladder  fall prob and  the game over penaltg .

lf you did not implement pl, you may change the solver type to vl in order to answer this question.

a)  Describe how you expect the optimal path to change as the ladder  fall prob and game over penaltg

values change.  use facts about the algorithms or Bellman optimality equation to justify why you expect these changes to have such efects.                                                                                        (7.5 marks)

b)  picking three suitable values for ladder  fall prob, and three suitable values for the game over penaltg , explore how the optimal policy changes over the 9 combinations of these factors.  You should present the results in a table, indicating whether the agent,s optimal policy is to traverse the top, middle or bottom path, or something else, using colours to denote the optimal behaviour for each combination. Do the experimental results align with what you thought should happen?  lf not, why? (7.5 marks)

Academic Misconduct

The university deines Academic Misconduct as involving  “a range of unethical behaviours that are designed to give a student an unfair and unearned advantage over their peers.”  uQ takes Academic  Misconduct very seriously and any suspected cases will be investigated through the university,s standard policy (https:// ppl.app.uq.edu.au/content/3.60.04-student-integrity-and-misconduct).  lf you are found guilty, you may be expelled from the university with no award.

lt is the responsibility of the student to ensure that you understand what constitutes Academic Misconduct and to ensure that you do not break the rules.  lf you are  unclear about what is required, please ask.

lt is also the responsibility of the student to take reasonable precautions to guard against unauthorised access by others to his/her work, however stored in whatever format, both before and after assessment.

ln the coding part of cOMP3702 assignments, you are allowed to draw on publicly-accessible resources and provided tutorial solutions, but you must make reference or attribution to its source, by doing the following:

.  All blocks of code that you take from public sources must be referenced in adjacent comments in your code or at the top of your code.

.  Please also include a list of references indicating code you have drawn on in your solution.py docstring.

lf you have utilised Generative Al tools such as chatGPT, you must cite the tool and version in your code as well as describe in the report. A failure to reference generative Al use may constitute student misconduct under the student code of conduct.

However, you must not show your code to, or share your code with, any other student under any circumstances.  You must not post your code to pubIic discussion forums (incIuding Ed Discussion) or save your code in pubIicIy accessibIe repositories  (checK your security settings). You must not IooK at or copy code from any other student.

All submitted iles (code and report) will be subject to electronic plagiarism detection and misconduct proceed- ings will be instituted against students where plagiarism or collusion is suspected.  The electronic plagiarism detection can detect similarities  in code structure even  if comments, variable  names,  formatting etc.   are modiied.  lf you collude to develop your code or answer your report questions, you will be caught.

For more information, please consult the following university web pages:

.  lnformation regarding Academic lntegrity and Misconduct:

一 https://my.uq.edu.au/information-and-services/manage-my-program/student-integrity-and-

conduct/academic-integrity-and-student-conduct

一 http://ppl.app.uq.edu.au/content/3.60.04-student-integrity-and-misconduct

.  lnformation on student services:

一 https://www.uq.edu.au/student-services/

Late submission

students should not leave assignment preparation until the last minute and must plan their workloads to meet advertised or notiied deadlines.  lt is your responsibility to manage your time efectively.

lt may take the autograder up to an hour to grade your submission.  lt is your responsibility to ensure you are uploading your code early enough and often enough that you are able to resolve any issues that may be revealed by the autograder before the deadline. submitting non-functional code just before the deadline, and not allowing enough time to update your code in response to autograder feedback is not considered a valid reason to submit late without penalty.

Assessment submissions received after the due time (or any approved extended deadline) will be subject to a 100% late penalty.  A one-hour grace period will be applied to the due time after which time the 100% late

penalty will be imposed. This grace period is designed to deal with issues that might arise during submission (e.g.  delays with Blackboard or Turnitin) and should not be considered a shift of the due time.  Please  keep a record of your submission time.

ln the event of exceptional circumstances, you may submit a request for an extension.  You can ind guide- lines on acceptable reasons for an extension here https://my.uq.edu.au/information-and-services/manage-my- program/exams-and-assessment/applying-extension. All requests for extension must be submitted on the UQ Application for Extension of Assessment form at least 48 hours prior to the submission deadline.


2023-09-27