3D Motion Planning Lesson 3.1 Cost Exercise solution

[davinderc]

The solution to the uniform cost search and A search exercises both ignore potential paths with lower costs that could be found at a later point. This means that if a cheaper route to a node is found, it is not considered. However, A search only ignores nodes that have been explored or have a higher cost.

[a6a3uh]

Maybe this my solution will explain situation better https://gist.github.com/a6a3uh/55188cce0876379cbc1040126ec45180

[jchernus]

A* and Uniform Cost Search use priority queues as their data structures. Such queues order their items by cost. As a result, when you pop an item off the queue, it is going to be the item with the lowest cost.

Therefore, in Uniform Cost Search, this means that any paths found at a later time will either have the same path cost, or a greater one.

In A it's a bit trickier, the heuristic must be admissible for the following to hold true. If it is not, then you are right - there may be undiscovered paths that are shorter, and the implementation of A would not be optimal.

[a6a3uh]

You are in a grid world with diagonal motions acceptable. But you have cost of diagonal motion more then twice the cost for other (perpendicular) motions. So you are going through all 8 valid actions placing them in queue in whatether order you like (including ordering them by cost) and also you are putting those 8 valid new positions in the set of visited. Now you marked all of diagonal positions as visited. And you visited them by moving diagonally. But more optimal solution would be to make 2 steps because diagonal motion has cost much bigger (in my example) than perpendicular. That mean you have to revisit already visited positions as shown in my gist example.

Am I still getting something wrong?

In the graph world with arbitrary costs for edges the situation is more common with necessity to revisit already visited nodes. As sometimes one-step motion could cost much more then several-step motions. Even in greed world you can have moving backwards to cost you much more than making a turn and move forward.