COS30019 Introduction to Artificial Intelligence Assignment 1 Semester 1, 2025 | SUT

COS30019 Introduction to AI Assignment

This assignment requires you to work individually to implement tree-based search algorithms. 

You need to write a program to implement tree-based search algorithms (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 code in the following languages: Python (recommended), Java, C++ or C#. Under special circumstances, we may allow other languages, but you must obtain permission from the convenor. Assignment work will be tested on a standard Microsoft Windows 11 system. 

The Robot Navigation Problem

In the lectures, you have seen the Robot Navigation problem: The environment is an NxM grid (where N> 1 and M> 1) with walls occupying some cells (marked as grey cells). The robot is initially located in one of the empty cells (marked as a red cell) and is required to find a path to visit one of the designated cells of the grid (marked as green cells). For instance, the following is one possible environment:

Assume that the cells of the grid can be located by their coordinates with the leftmost top cell being considered to be at the coordinate (0,0). The input file format is explained below: 

• The first line contains a pair of numbers NxM, where Nrepresenting the width (number of columns) and M represents the height (number of rows) of the grid. 
• The second line is a pair of numbers x,y which represents the coordinate (column#, row#) of the starting point 
• The third line is a sequence of number pairs separated by ";" i.e. x1,y1; x2,y2 ...which represents the coordinates of the goals to reach
• The subsequent lines consist of the coordinates of the walls 

One line for each wall position

For instance, the above environment can be expressed by the following specification: 

11x5 // The grid has 11 columns and 5 rows 
0,1// initial state of the agent - coordinates of the red cell 
7,0; 10,3// goal states for the agent - coordinates of the green cells 
2,0// all of the following are coordinates of wall cells 
3,0 
8,0 
10,0 
2,1 
3,1 
8,1 
2,3 
2,9 
2,4 
3,4 
4,4 
5,4 
8,4 
9,4 

We will only be interested in search algorithms. Therefore, you can assume that the problem files will always contain valid configurations. For instance, if N=11 and M=5, then you don't have to worry that the agent is initially located at coordinates (15, 3). 

Search Algorithms

The following are the tree-based search algorithms you need to implement. DFS, BFS, GBFSand AShave been covered in the lectures and the tutorials. CUS1 and CUS2 are two algorithms you may learn by yourself (from the textbook, from the Internet or any other sources). 

The objective is to reach one of the green cells. 

NOTE2:When all else is equal, nodes should be expanded according to the following order: the agent should try to move RIGHT before attempting DOWN, then LEFT, and eventually UP, in that order. Furthermore, when all else is equal, the two nodes N1and N2 on two different branches of the search tree should be expanded according to the chronological order: if node N1is added BEFORE node N2then N1 is expanded BEFORE node N2.

Command Line Operation

Your program needs to operate from a Windows command-line (terminal) interface to support batch testing. A Windows command-line interface can be brought up in Windows 11 by typing cmd into the search box at the Start button. You can create a Windows .bat(batch) file if needed to make it easy to execute your code. Below are the three different argument formats you need to support. Note the unique argument count for each

Report File

You must also include a report, which has to be either in Microsoft Word or in PDF, whose name is your student ID (for example, 1234567.pdf), containing your report. The aim of this report is for you to summarise your understanding of the problem, to introduce the search algorithms used in your assignment (including the standard ones), and to discuss how you implemented them. You'll also need to compare and discuss your strategies, in particular the custom strategies developed, using data obtained by running your program. 

Report Details: The report must be between 10 to 14 pages (excluding cover page and TOC). 

• Student Details: Your full name and student ID.
• Table of contents (TOC).
• Instructions: Basic instructions on how to use your program. You can also include a note containing 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.
• Introduction: Introduce the Robot navigation Problem, basic graph and tree concepts and other related terminology that may be needed later in your report. (Hint: using a glossary)
• Search Algorithms: Present and discuss the qualities of the search algorithms used in your assignment. Which algorithms are better and why? Use data collected to support your points.
• Implementation: Briefly present how each search program was implemented. Class diagrams and flow charts (pseudo code) are all suitable. Point out and briefly discuss differences in implementation or approach. Note important references.
• 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. Also, 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.
• Research: If you managed to do some additional research to improve the program in some ways (see several ideas for research initiatives), please report it here.
• Conclusion: Conclude with a discussion about the best type of search algorithm you would use for this type of problem. Include thoughts about how you could improve performance.
• Acknowledgements/Resources: Include in your report a list of the resources you have used to create your work. A simple list of URLs is not enough. Include with each entry a basic description of how the person or website assisted you in your work.
• References: Cite the sources you referred to in your Assignment (implementation, report, etc.) 

Tips: 

• All figures and tables need to be properly captioned with sensible descriptions.
• Report presentation should include header/footer information (page numbers, etc.) 

Marking Scheme & Submission

You must submit your work via Canvas. 

Create a single zip file that contains the source code and the executable of your program. Do not use deep folder hierarchies. Do not include the data files (we have them). Beware of any upload limit to Canvas - ensure that your file is not too large for download and assessment. Please consult early if you have a large binary/package for submission. 

Standard late penalties apply - 10% for each day late, more than 5 days late is 0%

Marking Scheme

Ideas for Research Initiatives

• Can you modify your program so that the robot will visit ALL the green cells with the SHORTEST path? Please include in your report the challenges you have to overcome to address this requirement and how you solved them.
• Can you extend your program to allow the robot to have four additional actions jump_up(n), jump_down(n), jump_left(n), and jump_right(n); where n is the number of squares the robot jumps to (i.e., when n = 1 then jump_x(1) is the same as moving to the direction x). The action jump_x(n) allows the robot to jump over the obstacles with the exponential cost: The cost of jump_x(n) should be: 2(n-1). For example, the cost of jump_x(4) is 8. Can you compare the optimal solutions when the robot is allowed to use the actions jump_x() and when it is not allowed to? If you choose this option, please make sure that this extension comes with a command-line argument so that the default option of your program is still for the original problem files we will use to test your program.
• In addition to the mandatory command-line-based user interface, can you build a GUI to display the environment and how the algorithm is trying to find the solution? This option should also include a visualizer to show the changes happening to the search tree.
• Can you produce comprehensive test suites to ensure that as many bugs as possible can be caught? Can you automate the test case generation? Your test automation technique should also include data collection and report generation. 

Note: You don't have to realise too many ideas. Choose one idea and execute it very well, and you can get the 20 marks awarded for doing a research initiative.