School of Computer Science The University of Adelaide
Artificial Intelligence Assignment 1
Semester 1, 2019
due 23:59, Thursday 11th April 2019
Note that this project specification is not yet complete. It is provided now so that if you want to you can start work. Details of the marking scheme and how to submit will be released a.s.a.p.
Introduction
With suitable abstractions planning a path for a mobile robot can be converted into a search problem. Begin by abstracting the environment into a 2D grid of square ¡°cells¡±. The robot state can be represented by a [x,y] pair, with [0,0] being the top-left cell of the grid. Movements of the robot are possible at any time either UP, DOWN, LEFT RIGHT (denoted U, D, L, R) unless the neighbouring cell is occupied. The UP action moves to the cell immediately above (if possible) by changing [x,y] to [x,y-1]. Likewise RIGHT changes the current state from [x,y] to [x+1,y], and so on. Given a start state, the goal of the robot is to reach a new (user specified) state [X*, Y*], where this must be an unoccupied cell in the grid. An action that would take the robot outside the grid or into an occupied cell results in no change to the current state.
Your task is to write a program that will read in an environment, a start state and a goal state, and conduct a search to find a path between start and goal. You may implement any of the search algorithms discussed in lectures. Your output should be in the form of a space-separated list of actions, such as U R R D D L L (more specific detail is given below).
Test data will be provided on the course pages along with this Assignment description. Different data will be present in the submission system and your search program will be evaluated against these unseen data for its completeness and optimality.
You must write the program yourself in either C, C++, Java or Python. You may freely use libarries or packages for data structures (e.g. for queues or trees or other structures you deem necessary), but if you use a library package or language function call for doing the search itself, you will be limited to 50% of the available marks. If there is evidence you have simply copied code from the web, you will be awarded no marks and referred for plagiarism.
The program must accept 5 arguments from the command-line: a file (which contains the environment); and 4 integers specifying start state and goal state, eg:
1
./robotplanner env.txt 0 2 4 1
would read the environment specification from the file env.txt and should plan a path from
[0 2] to goal state [4 1]
Submission and Assessment
The search algorithm you use is deliberately not specified. You can use any search algorithm that you believe will produce a solution.
Undergraduates will be assessed on whether they produce a valid solution. Postgraduates must produce an optimal solution.
Submit your program on the Computer Science Web Submission System. This means you
must create the assignment under your own SVN repository to store the submission files. The SVN key for this submission is XXXXX for undergraduates and XXXXX for postgraduates.
There will a number of test examples and your code will be assessed against each with the marks equally divided.
This assignment is due 11.59pm on Thursday 11th April, 2019. If your submission is late, the maximum mark you can obtain will be reduced by 25% per day (or part thereof) past the due date or any extension you are granted.
File format
The environment will be stored as text file in the following format: the first line contains the width and height as two (space or tab separated) integers. Each subsequent line contains a set of space-or-tab-separated 0s and 1s, with 0 representing that a cell is free-space (and therefore navigable) and 1 indicating it is occupied, and therefore cannot be entered or passed through by the robot.
For example
53 00100 10100 00001
If we suppose that the start state is [0,0] (i.e. at the top left) and the goal state is [4,0] (i.e. top right), then a valid solutions is
RDDRRUUR
2
Note that this solution is optimal but not unique.
Your program must produce output in the format of a line with two numbers representing
respectively, the number of nodes explored, the path length to the goal, followed by a line with the set of robot actions. For example:
100 8 RDDRRUUR
For the case that 100 nodes have been explored, finding a path of length 8.
Prof. Ian Reid, 18 March 2019
3