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:
- $c(n,n') = d(n,n')/\text{dis2obs}(n')$
- $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 pathsis their length any different? $\endgroup$