Pathfinding efficientie algorithmes

[HawVer]

Ik ben bezig met een implementatie van pathfinding om verkeer te simuleren. Ik heb inmiddels a* geimplementeerd in een graph. Het is de bedoeling dat mijn agents langs de wegen gaan bewegen. So far so good. Alleen tussendoor kan de graph wijzigen. Sommige wegen krijgen hogere kosten vanwege verkeersdrukte of sommige segmenten verdwijnen. Hoe kan ik daar het beste mee om gaan? Ik heb inmiddels ook al d* lite gevonden. Alleen daar heb ik ook kritische reacties op gelezen, omdat a* opnieuw uitvoeren sneller bleek te zijn dan d*. Iemand hier die met specifieke probleem ervaring heeft en mij verder zou kunnen helpen. De vraag is wat is de beste manier om hier mee om te gaan als er veel agents zijn?

[pedorus]

Veel agents, weinig wegen? Al eens naar iets als Wikipedia: Johnson's algorithm gekeken anders? (Edit: bedenk me dat je waarschijnlijk alleen positieve edges hebt, dus effectief is dat Dijkstra, of A* met nul-heuristiek, vanaf alle punten..) Is het wel echt zo dat de agents de kortste routes gaan/moeten volgen na wijzigingen? Voor echt verkeer lijkt me dat een onjuiste assumptie. Is er een gewenste uitvoersnelheid?

[ Voor 17% gewijzigd door pedorus op 29-03-2013 23:29 ]

[Verwijderd]

Als je verkeer wilt simuleren lijkt het mij dat je juist geen A*/dijkstra/... wilt hebben. Dat soort algoritmes zijn bedacht om het kortste pad te vinden. Een auto in het verkeer neemt bijvoorbeeld niet het kortste pad.

[Zoijar]

Jur van den Berg heeft veel gepubliceerd over dit soort dingen; misschien kan je daar wat papers van opzoeken voor inspiratie. Zoals dit bv http://arl.cs.utah.edu/pubs/VR2009.pdf

[Aloys]

Verwijderd schreef op vrijdag 29 maart 2013 @ 23:57:
Als je verkeer wilt simuleren lijkt het mij dat je juist geen A*/dijkstra/... wilt hebben. Dat soort algoritmes zijn bedacht om het kortste pad te vinden. Een auto in het verkeer neemt bijvoorbeeld niet het kortste pad.

Je kan natuurlijk makkelijk implementeren dat je niet de lengte van de weg, maar de benodigde tijd om de weg af te leggen gebruikt. Zo heb ik ook een routeplanner gemaakt die de snelste, morste of goedkoopste route kon nemen. Simpelweg ee kwestie van andere gewichten gebruiken voor je edges.

[Verwijderd]

Ik doelde meer op het feit dat een auto niet noodzakelijk het kortste, snelste of 'beste' pad hoeft te nemen. De mens mist ook nog wel eens een afslag.

[HawVer]

pedorus schreef op vrijdag 29 maart 2013 @ 23:17:
Veel agents, weinig wegen? Al eens naar iets als Wikipedia: Johnson's algorithm gekeken anders? (Edit: bedenk me dat je waarschijnlijk alleen positieve edges hebt, dus effectief is dat Dijkstra, of A* met nul-heuristiek, vanaf alle punten..) Is het wel echt zo dat de agents de kortste routes gaan/moeten volgen na wijzigingen? Voor echt verkeer lijkt me dat een onjuiste assumptie. Is er een gewenste uitvoersnelheid?

Bedankt voor je link. Ik ga die even bekijken. Ik heb inderdaad alleen positieve edges en ze zijn allemaal directed.

Aloys schreef op zaterdag 30 maart 2013 @ 11:46:
[...]

Je kan natuurlijk makkelijk implementeren dat je niet de lengte van de weg, maar de benodigde tijd om de weg af te leggen gebruikt. Zo heb ik ook een routeplanner gemaakt die de snelste, morste of goedkoopste route kon nemen. Simpelweg ee kwestie van andere gewichten gebruiken voor je edges.

Ja ik ga niet voor de kortste route, ik wil dat het verkeer eerst de wegen neemt met de meeste capaciteit. Dat doe ik nu door de routes met een lagere capaciteit duurder te maken.

Verwijderd schreef op zaterdag 30 maart 2013 @ 14:13:
Ik doelde meer op het feit dat een auto niet noodzakelijk het kortste, snelste of 'beste' pad hoeft te nemen. De mens mist ook nog wel eens een afslag.

Het wordt niet een heel realistische simulatie. Het idee wat ik wil simuleren is als volgt:

Een agent plant zijn route van punt a naar punt b.
De agent heeft voorkeur voor wegen met een grote capaciteit.
Zodra hij gaat rijden kan de weg duurder worden door:
1. Extra drukte op de weg
2. Deel van de weg wordt weggehaald.
Als het deel van de weg wordt weggehaald waar de agent op dat moment op rijdt wordt hij gereset naar punt a.,
Wanneer het wegdeel duurder wordt, wordt berekend of de route nog wel de meest optimale route is.
D* lite wordt ook in Sim City gebruikt en het voordeel van D* lite is dat het algoritme de route niet opnieuw hoeft te berekenen. Maar ik kan er ook voor kiezen om a* te berekenen vanaf het laatste kruispunt zodra een route duurder wordt.

Zoijar schreef op zaterdag 30 maart 2013 @ 11:19:
Jur van den Berg heeft veel gepubliceerd over dit soort dingen; misschien kan je daar wat papers van opzoeken voor inspiratie. Zoals dit bv http://arl.cs.utah.edu/pubs/VR2009.pdf

Top, ik ga de link bekijken!

[ Voor 6% gewijzigd door HawVer op 30-03-2013 16:10 ]