Question 2. Given the following environment represented as a grid (black cells:

Question

Question 2. Given the following environment represented as a grid (black cells: obstacles, white cells: free space; each cell denoted with coordinates x.y), where a robot, able to move up/down/left/right with cost 1, starting from (0,0) wants to reach (3,3) Apply A* algorithm (tree-search), where the heuristic is perfect, drawing the expanded tree, marking the related cell, cost, and heuristic for each node, and explicitly showing the order in which nodes are expanded in the first five iterations.

Explanation / Answer

Algorithm
We create two lists – Open List and Closed List
// A* Search Algorithm
1. Initialize the open list
2. Initialize the closed list
put the starting node on the open
list (you can leave its f at zero)
3. while the open list is not empty
a) find the node with the least f on
the open list, call it "q"
b) pop q off the open list
  
c) generate q's 8 successors and set their
parents to q

d) for each successor
i) if successor is the goal, stop search
successor.g = q.g + distance between
successor and q
successor.h = distance from goal to
successor (This can be done using many
ways, we will discuss three heuristics-
Manhattan, Diagonal and Euclidean
Heuristics)
  
successor.f = successor.g + successor.h
ii) if a node with the same position as
successor is in the OPEN list which has a
lower f than successor, skip this successor
iii) if a node with the same position as
successor is in the CLOSED list which has
a lower f than successor, skip this successor
otherwise, add the node to the open list
end (for loop)
  
e) push q on the closed list
end (while loop)

Approximation Heuristics –
Using Euclidean Distance-
As it is clear from its name, it is nothing but the distance between the current cell and the goal cell using the distance formula
h = sqrt ( (current_cell.x – goal.x)2 +
(current_cell.y – goal.y)2 )




Algorithm
We create two lists – Open List and Closed List
// A* Search Algorithm
1. Initialize the open list
2. Initialize the closed list
put the starting node on the open
list (you can leave its f at zero)
3. while the open list is not empty
a) find the node with the least f on
the open list, call it "q"
b) pop q off the open list
  
c) generate q's 8 successors and set their
parents to q

d) for each successor
i) if successor is the goal, stop search
successor.g = q.g + distance between
successor and q
successor.h = distance from goal to
successor (This can be done using many
ways, we will discuss three heuristics-
Manhattan, Diagonal and Euclidean
Heuristics)
  
successor.f = successor.g + successor.h
ii) if a node with the same position as
successor is in the OPEN list which has a
lower f than successor, skip this successor
iii) if a node with the same position as
successor is in the CLOSED list which has
a lower f than successor, skip this successor
otherwise, add the node to the open list
end (for loop)
  
e) push q on the closed list
end (while loop)

Approximation Heuristics –
Using Euclidean Distance-
As it is clear from its name, it is nothing but the distance between the current cell and the goal cell using the distance formula
h = sqrt ( (current_cell.x – goal.x)2 +
(current_cell.y – goal.y)2 )

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.