Somehow this topic keeps on haunting me. While doing some home improvements over the weekend, I remembered a paper from few years ago:
Theta*: Any-Angle Path Planning on Grids
http://idm-lab.org/bib/abstracts/papers/aaai07a.pdf
It looks like there is more recent paper on topic too:
Incremental Phi*: Incremental Any-Angle Path Planning on Grids
http://ijcai.org/papers09/Papers/IJCAI09-303.pdf
The rough takeaway from both papers is that they incorporate line of sight tests to the cost calculation. So instead of accumulating the movement cost as you follow wiggly edge midpoints or polygon centroids you actually use the shortest path to most distant parent to calculate the cost.
It looks like the string pulling method used in Detour could be used in similar way. That is, it should be possible to create partial result of the shortest path up to the current polygon in open list and use that to make better guess of the cost up to a certain edge. The down side is that the state takes too much memory per node (around 28 bytes) so I don't think the trade off is good. I might give it a spin at some point just to see if it is indeed possible.
No comments:
Post a Comment