[Routing] Routing algorithms
Jonathan Stott
jonathan at jstott.me.uk
Sat Sep 20 22:33:10 BST 2008
Stefan Pflumm wrote:
> Hello,
>
> I'm searching for an routing algorithm who can handle this two properties:
>
> 1. the edge weight function c(E) of the edge E depends on the costs of
> the predecessor edges. A* for example, can't handle this, because it
> connects existings paths without updating the successors. If the path
> previous to an edge changes and the edge is already expanded the costs
> of the edge and all successors will also change.
>
> 2. the edge weight function c(E) of the node N depends on the successor
> edge. For example: E_1 and E_2 are neighbour edges of E. c(E) to E_1
> must be not equal to c(E) to E_2
>
> I hope somebody can give me an advice, thanks
>
I don't know if this is exactly what you want, but it sounds to me like
you want some kind of dynamic variant of A*. Stentz wrote about such a
variant back in 1994, commonly called D*:
Stentz, A. "Optimal and efficient path planning for
partially-knownenvironments". Robotics and Automation, 1994.
Proceedings., 1994 IEEE International Conference on: 3310-3317.
While I have looked at A*, Dijkstra, etc. as part of my PhD, I haven't
looked at Stentz's D* algorithm before.
Jonathan Stott
More information about the Routing
mailing list