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')$

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.