# A* (A-star) search algorithm including closest distance from a node to an obstacle in heuristic and step cost

I want to include the distance of a node to the closest obstacle in the cost function, so that the path length is not only minimal, but also not near obstacles.

We know that: Dijkstra's algorithm uses cost function $$f(n) = g(n)$$ whereas A* uses cost function $$f(n) = g(n) + h(n)$$, with $$g(n)$$ being the cost of the path from the start node to node $$n$$, and $$h(n)$$ is a heuristic function that estimates the cost of the cheapest path from node $$n$$ to the goal.

More specifically, for a successor $$n'$$ of the current node $$n$$, the cost function is $$f(n') = g(n') + h(n')$$, with $$g(n')=g(n)+c(n,n')$$, with $$c(n,n')$$ the step cost function, i.e. the Euclidean distance between two nodes and $$h(n') = d(n',\text{goal})$$ with the heuristic function equal to the Euclidean distance between n' and the goal.

However, I want to add the distance to closest obstacle in the step cost function and I have two in mind, namely:

1. $$c(n,n') = d(n,n')/\text{dis2obs}(n')$$
2. $$c(n,n') = d(n,n')/\min\{\text{dis2obs}(n),\text{dis2obs}(n')\}$$. with $$d(n,n')$$ the Euclidean distance between two nodes, and, $$\text{dis2obs}(n)$$ and $$\text{dis2obs}(n')$$ the distance to the closest obstacle for respectively node $$n$$ and $$n'$$. Which step cost function would you suggest and why? I thought the first one, but second takes also $$n$$ into account.

Secondly, I want to find a heuristic for this new step cost function, that's admissible and consistent. I thought about the following heuristic for the second version of the edge cost: $$h(n') = d(n',\text{goal})/\min\{\text{dis2obs}(n),\text{dis2obs}(n')\}$$

However, when I use Dijkstra and A* with this new edge cost and heuristic, they don't give the same paths and I don't understand why. I thought that my heuristic is admissible and consistent, because I think it fulfills the condition:

$$h(n) \leq c(n,n') + h(n')$$

• don't give the same paths is their length any different? Oct 19 at 6:26
• @greybeard yes, indeed, I meant with that their length is different. They are roughly similar, but still not exactly the same. Oct 21 at 16:14