-1
$\begingroup$

I have the following game board below, and we're using A* search to find the optimal path from the agent to the key. There are 8 directions. Up, down, left, right have a cost of 1, and diagonal directions have cost 3. We will be using a priority queue with function $f(v) = g(v) + h(v)$ where $g(v)$ is the backwards cost from the goal through the given edges and up to the vertex v while $h(v)$ is the optimal least cost distance from v to the goal node.

enter image description here

So I calculated the f(s) for the different states, assuming no prior edges specified: enter image description here

And then I started the search and these are the steps I took: expand C: (CD,3), (CE,3), (CF,3), (CA,5), (CB,5)

expand CD: (CDF,3),(CE,3), (CF,3), (CA,5), (CB,5), (CDB,5)

expand CDF: (CDFH,3), (CE,3), (CF,3), (CA,5), (CB,5), (CDB,5), (CDFG,6)

expand CDFH: (CE,3), (CF,3), (CA,5), (CB,5), (CDB,5), (CDFG,6)

So I only expanded, C,D,F,H. I got the correct answer for the optimal path, but not the correct answer for nodes expanded, which is supposed to be C, D, E, F, G, H. What am I doing wrong?

Improve this question
$\endgroup$
4
  • $\begingroup$ In the first iteration of $A*$ (and basically many other state-space search algorithms), you will only add to the frontier the nodes reachable from your current node, but $H$ and $G$ are not reachable with a single action from $C$ (if I interpret correctly your state-space), so I'm not sure how you calculated $f(n)$ for those (in the table). So, you should probably try to think about this issue before proceeding. I would also suggest that you draw your state space as a graph, so that to avoid this type of confusion again. $\endgroup$
    – nbro
    Commented Feb 11, 2021 at 0:49
  • $\begingroup$ those f(s) values are just there for the question, I dont use those exact values for the queue. are my expansion steps right? $\endgroup$
    – Manny
    Commented Feb 11, 2021 at 2:49
  • 1
    $\begingroup$ If I understand correctly, diagonal moves cost 3. So the first expand: CF=3+1, CB=3+3 $\endgroup$
    – Cohensius
    Commented Feb 11, 2021 at 6:22
  • $\begingroup$ @Manaal As I said above, it looks like you didn't really understand how A* (or any other state-space search algorithm) expands the nodes or adds them to the frontier, so I would suggest that you do what I said. Draw your state space as a graph, where only reachable nodes are connected by an edge (so no edge between C and H, e.g.). Moreover, someone also pointed out above that you didn't calculate correctly f(n) for several nodes. I would suggest that you delete this post, do what I suggested, try to solve the problem again, then ask another question, if you still have a question. $\endgroup$
    – nbro
    Commented Feb 11, 2021 at 12:27

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .