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.

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: