## Description

## 1 Introduction

A* is an optimisation (search) algorithm that is used to find the optimum path

between a start state and one of the goal states (if there are multiple-goal

states) with minimum cost. The term state may refer to two cities when the

optimum (shortest) path between two cities is of interest to be found, or may

refer to two different states of a 15 or 8 puzzle when going from state 1 to state

2 is of interest.

Normally there are a large number of paths between two points and testing

all possible paths in order to find the optimum path is nearly impossible or it

is hugely time-consuming, therefore some smart solutions have to be employed.

In order to illustrate the problem more graphically, we can consider the trip

from city S to the city E in Figure 1. To have the map of all cities, one can

create the Tree structure of the map in order to illustrate the complexity of the

problem (See Figure 2).

As you can see there are 12 paths

{1, 5, 13}, {1, 6, 13}, {1, 7, 14}, {1, 8, 14}, {1, 8}, {2, 8, 14}, {2, 9, 15}, {3, 10, 15},

{4, 11, 16}, {4, 12, 16}, {1, 13}, {2, 8}.

The question is which path is the best to choose?

## 2 A*

A* has two functions called g and h. The input of these two functions is the

next node on the path. Function g(n) simply calculates the cost of the path

from the start point, therefore the value for g(n) is 0 at the beginning. h(n) is a

function that estimates the cost from point n the destination. The sum of these

two functions indicates the total cost of the current path f(n) = g(n) + h(n).

1

Figure 1: Travelling from S to E

Figure 2: All possible paths from S to E

2

## 2.1 Algorithm

In this section, the A* algorithm is presented. This algorithm can be then

generalised for any type of problems from different contexts.

1. Declare three parameters, the source, the destination and the current

point, S, E, C.

2. Declare a function called mem(n) for each single point n.

3. C := S

4. Initiate two lists call them closed and open.

5. Identify all the points (m points) that are directly/simply (without any

intermediate point) reachable from C: X = {X1, X2, …, Xm}.

6. Those members of X that are not in closed are added into the open list.

7. Add C into closed.

8. Calculate g(n) for all the members of open.

9. Estimate h(n) for all the members of open.

10. Estimate the value of f(n) for all the members of open.

11. Select a point from open, Oi

, where Oi 6∈ closed and f(Oi) is minimum;

then assign Oi to C; C := Oi

.

12. mem(Oi) = C

13. Add Oi

into closed and remove Oi from open.

14. If C = E, terminate the algorithm otherwise go back to step 4.

Following the aforementioned algorithm above, one can find the shortest

path in Figure 1 as follows:

1. C = S

2. X = {1, 2, 3, 4}

3. open = {1, 2, 3, 4}

4. closed = {S}

5. f(1) = 3, f(2) = 3, f(3) = 4, f(4) = 4

6. Either f(1) or f(2) is selected to be assigned into Oi

. (we choose Oi = f(1)

7. C = 1

3

8. mem(C) = S; mem(1) = S

9. open = {2, 3, 4}: Current members of open.

10. closed = {S, 1}

11. X = {5, 6, 7, 8, 13, S}

12. open = {2, 3, 4, 5, 6, 7, 8, 13}: Updating open

13. f(2) = 3, f(3) = 4, f(4) = 4,f(5) = 4, f(6) = 4, f(7) = 4, f(8) = 4,

f(13) = 3: Either 2 or 13 is chosen, we choose 13.

14. C = 13

15. mem(C) = 1; mem(13) = 1

16. open = {2, 3, 4, 5, 6, 7, 8}: Current members of open.

17. closed = {S, 1, 13}

18. open = {2, 3, 4, 5, 6, 7, 8, E}: Updating open

19. f(2) = 3, f(3) = 4, f(4) = 4,f(5) = 4, f(6) = 4, f(7) = 4, f(8) = 4,

f(E) = 2: E is chosen.

## 3 Project

3.1 The shortest path problem

In this project, we are going to use the A* algorithm 1

to solve a problem of

finding a path between two vertices or nodes in a graph such that the sum of

the weights of its constituent edges is minimised. This problem is known as

the shortest path problem 2 and can be defined for undirected, directed, or

mixed graphs. For this project, we are going to consider the undirected graph

definition expressed on grid maps.

The grid map used in this project should be an 8 × 8 matrix that allows 4

directions of movement (e.g., left, right, up, and down). Diagonal movements

are not allowed. In addition to the grid map, an obstacle needs to be generated

randomly, including its position on the map and its shape. For generating

the obstacle, a minimum of 3 or a maximum of 5 connected blocks should be

considered and in the shape of a letter (e.g., T, L, or I). Figure 3 illustrates an

example of a grid map with an obstacle.

The generated grid map with an obstacle must be displayed using a console

or graphical interface. Subsequently, the end-user must be asked for the start

and goal positions. User input must be validated. If the input provided by the

user is invalid (e.g., start or goal positions are outside of the grid map), new

1https://en.wikipedia.org/wiki/A*_search_algorithm

2https://en.wikipedia.org/wiki/Shortest_path_problem

4

Figure 3: A grid map with obstacle

input needs to be provided. If the input is valid, an updated version of the grid

map with the start and goal positions should be shown, as illustrated in Figure

4.

## 3.2 Manhattan distance

In the A* algorithm, h(n) is a heuristic function that estimates the cost of the

cheapest path from n to the goal. To this end, we are going to use Manhattan

distance 3 as a heuristic function. The Manhattan distance is calculated by

d(i, j) = |x1 − x2| + |y1 − y2|. For more information regarding how to calculate

the Manhattan distance, use the following resource 4

. Finally, after finding the

shortest path, you must print it out on the grid map.

## 4 Submission

You are required to write a Java program in order to solve the shortest path

problem using the A* algorithm.

1. The deadline of the submission is (Saturday) 25th of April 2020 (end of

week 12).

2. Only one .java file has to be submitted by one of the members of the

group.

3https://en.wikipedia.org/wiki/Taxicab_geometry

4http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

5

Figure 4: A grid map with obstacle and start and goal positions

3. The name of the .java file has to be is12345678.java where 12345678 is

the student ID of the person who submits the project.

4. The first few lines of the .java file has to contain the full name and the

student ID of all the member in the group.

5. The submission must be made by email to davi.monteiro@ul.ie and the

full name and student ID of all members have to be listed in the email.

Please CC all the members of the group in the submission email as well.

6. Any submission that fails to run and/or compile will be graded 0.

7. Submissions after the deadline will not be evaluated.

8. The submission is marked out of 20 marks.

6