Multi-Agent Pathfinding

Recommended Posts

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.

Share on other sites

You should be searching for algorithms related to the windy postman problem.

Share on other sites
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.

Share on other sites
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 by fiveworlds
Share on other sites
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.

Share on other sites
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.

Share on other sites

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 ?

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 account