Artificial Intelligence
nishamal
Assignment03-Informedsearch-1.pdf
Informed search
2
• We can consider a 2D Grid having several obstacles and we start from a source cell
(colored red below) to reach towards a goal cell (colored green below).
9/17/2021 AK Chanda
End
Start
Informed search
3
• Here, we plan to use A* search algorithm to solve this problem.
• The algorithm picks a node according to a lowest value-‘f’ which is a parameter equal to
the sum of two other parameters – ‘g’ and ‘h’.
• g = the cost to move from the starting point to a given square on the grid.
• h = the estimated movement cost to move from that given square on the grid to the
destination.
• There can be many ways to calculate this ‘h’.
9/17/2021 AK Chanda
Informed search
4
• One way to calculate the distance is Manhattan distance.
• Manhattan distance:
• It is the sum of absolute values of differences in the goal’s x and y coordinates and the current cell’s x and y coordinates respectively, i.e.,
h =abs(current_cell.x – goal.x)+abs(current_cell.y – goal.y)
9/17/2021 AK Chanda
Informed search
5 9/17/2021 AK Chanda
Informed search
6
• For this assignment, you can assume you have a 2D board of 20 by 20 size, where the start state is (1,1) and goal state is (19,19).
o Write a program that will show the path from start to goal using A* search algorithm. You will show two solutions for Manhattan and Euclidean distance.
9/17/2021 AK Chanda
Informed search
7 9/17/2021 AK Chanda
Input Output
(the agent can move to up, down, left and right)
Output (the agent can move to up,
down, left and right, as well as in diagonal)
Informed search
8
Python input:
board = [ [ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#’ ],
[ '#', 'A', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#’ ],
[ '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', '#’ ],
[ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#’ ] ]
start_x = 1
start_y = 1
goal_x = 19
goal_y = 19
9/17/2021 AK Chanda
