Multi-Agent Pathfinding

[bsmart805]

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.

 

[fiveworlds]

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

[Strange]

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.

[fiveworlds]

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

[Strange]

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.

[fiveworlds]

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.

[bsmart805]

 

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 ?