bsmart805 Posted August 18, 2018 Share Posted August 18, 2018 Hi everyone, I have been studying about Multi-agent pathfinding. My task is to implement a cooperative pathfinding in a city, the streets as a edges and intersections as a vertex. Now, i hope you can help me with documentation about that, all is usefull in order to research. Actually Im looking papers about multi-agent pathfinding IN cities ( no between cities ), for example A* for a simple agent with a city as a graph or LRTA* for single agent or directly for multi agent. regards ! and thanks for everyone. Link to comment Share on other sites More sharing options...
fiveworlds Posted August 18, 2018 Share Posted August 18, 2018 You should be searching for algorithms related to the windy postman problem. Link to comment Share on other sites More sharing options...
Strange Posted August 18, 2018 Share Posted August 18, 2018 10 minutes ago, fiveworlds said: You should be searching for algorithms related to the windy postman problem. Can you explain how that is relevant. The OP didn't mention anything about asymmetry in the costs of traversing edges. Link to comment Share on other sites More sharing options...
fiveworlds Posted August 18, 2018 Share Posted August 18, 2018 (edited) Quote Can you explain how that is relevant. The OP didn't mention anything about asymmetry in the costs of traversing edges. The windy postman problem concerns finding the best route along directed graphs (think one-way roads) with a cost of travelling a road (think traffic and speed limit). It could be faster to take the motorway in the city than to take side roads etc even if the motorway route is longer. Edited August 18, 2018 by fiveworlds Link to comment Share on other sites More sharing options...
Strange Posted August 18, 2018 Share Posted August 18, 2018 11 minutes ago, fiveworlds said: The windy postman problem concerns finding the best route along directed graphs (think one-way roads) with a cost of travelling a road (think traffic). But the specific thing about the windy postman problem is that the edges have a different cost depending which way you traverse them. The OP's question may be related to the generalisation of that (route inspection) or the the travelling salesman problem. But I somehow suspect that someone who is working on multi-agent pathfinding is well aware of those problems and possible solutions. Link to comment Share on other sites More sharing options...
fiveworlds Posted August 18, 2018 Share Posted August 18, 2018 Quote But the specific thing about the windy postman problem is that the edges have a different cost depending which way you traverse them. Yeah the motorway going into the city can have much worse traffic in the morning than the motorway leaving the city. Quote But I somehow suspect that someone who is working on multi-agent pathfinding is well aware of those problems and possible solutions. I would imagine so too. I am just pointing him in the direction of where he might find city pathfinding algorithms as opposed to A* which doesn't take traffic etc into account. Link to comment Share on other sites More sharing options...
bsmart805 Posted August 19, 2018 Author Share Posted August 19, 2018 11 hours ago, fiveworlds said: You should be searching for algorithms related to the windy postman problem. Thanks ! , i will read about it... Also I found some information about DIMACS problem, some people say that could be usefull, what do you think about it ? Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now