# Algorithm to solve gridlock (traffic jam)

Is there an algorithm for solving a gridlock (traffic jam)? Given a gridlock situation, this algorithm should tell which moves each car should make, and in which order the cars should move, so that the congestion is eliminated and the cars can go in the direction they intended to.

I have googled 'traffic jam solve algorithm', but I've found results about preventing jams (not solving jams once they occurred), or results about mathematical modelling of the traffic jams (or mining other kind of data from a traffic jam) - which is not what I'm looking for.

So far, the 'sliding blocks' game/puzzle seems to me to be a simpler version of the traffic jam problem (some variants of the game are even called Rush Hour), but it seems that this kind of problem is PSPACE-complete (which is even harder than NP-complete), according to http://groups.csail.mit.edu/mac/users/bob/sliding-blocks.pdf

So, is there at least some approximate algorithm to do this?

By traffic jam I do not mean a situation where the traffic is going on very slowly, but otherwise is still going on, but a situation where cars are actually blocked by other cars, and cannot move forward, or backwords. actually, only a few cars can move at a time - just like in the block sliding problem. See this picture for example.

• Could you specify the traffic jam situation more precisely? For instance, are the variables for how many lanes and how many vehicles there are in each lane? – J W May 4 '15 at 11:41
• well, for the sake of simplicity, let's not bother yet about the number of lanes, nor the number of cars coming from behind on each lane. The picture that i had in mind was an aerial overview of an intersection crowded with cars, and i would expect the algorithm to tell which car to move first, and how, and so on. Basically, if you regard cars as rectangles, what I'm asking is a solution ( or at least some research) to the sliding blocks game – Petre Luca May 4 '15 at 12:22
• Are you thinking more of a gridlock situation? – J W May 4 '15 at 13:57
• you are right!! gridlock describes perfectly what i mean. i didn't knew this term, that's why i used the term 'traffic jam'. i will edit the post right now – Petre Luca May 4 '15 at 14:41
• traffic lights and/or roundabouts? – JMP Jun 23 '15 at 1:14