A* in the presence of bottlenecks
Author
Consider a map divided into two or more regions, such that there is a single bottleneck node you must pass through to get from one region to another. If that bottleneck node is blocked, the A* algorithm will eventually return "not possible" when you ask for a path from one region to the other. However, that will take time. Is there an obvious way to optimise the search when you have a map with blockable bottlenecks?
For definiteness, we might consider a world map and look at the oceans. To get to the Black Sea, for example, you are going to have to pass through the Dardanelles, which are eminently blockable. Similarly, to get to the Med in the first place, you must pass either Gibraltar or Suez; which opens up a whole new can of worms, since it means you can block access to the Black Sea by blocking those two straits, instead of the Dardanelles.
Now, A* will solve these problems eventually, but I am looking for optimisations. If necessary I can add extra information to the nodes, such as what region the node belongs to. Suggestions?
Considering the scale at which you are applying this problem, I would probably point out that a ship crew would not be able to tell whether or not an area is blocked until they got there.
Author
A cogent point, but I am only using the world-map as a concrete example that everybody can visualise. Plus, the ship crew would know whether or not they were at war with Turkey.
You could have a graph of 'connected components' which define your different regions. Lets say you have two rooms with a narrow/bottlenecking connector between.
You have connected components regions; one of which can be blocked. When your AI is looking for a path, first search the 'connected components graph' to see if there is a path at all. The main idea is that this graph should be vastly simpler than your low level graph.
You may want to spend a bit of time on google looking at hierarchical search algorithms. Much of the info there is heavier weight than you are looking for (as it is used for searching huge GIS databases).
Take a look at:
http://www.cs.ualberta.ca/~jonathan/Papers/Papers/jogd.pdf
...if nothing else, it may have a few useful references.
You have connected components regions; one of which can be blocked. When your AI is looking for a path, first search the 'connected components graph' to see if there is a path at all. The main idea is that this graph should be vastly simpler than your low level graph.
You may want to spend a bit of time on google looking at hierarchical search algorithms. Much of the info there is heavier weight than you are looking for (as it is used for searching huge GIS databases).
Take a look at:
http://www.cs.ualberta.ca/~jonathan/Papers/Papers/jogd.pdf
...if nothing else, it may have a few useful references.
Mmm, the fires have settled down a fair bit around here... maybe it's time I started posting again...
KoM: This is a common problem dealt with in the planning literature. Essentially you don't know a priori whether the bottleneck is passable or not. This is an identical problem in its description to the more commonly studied 'locked door' problem. Unless you have other information, then a priori you would assign a uniform probability distribution over the possible states of the bottleneck; so these would be 'blocked' and 'not blocked'.
The expected cost of a path from start to goal passing through a bottleneck is given by:
Cost to get to bottleneck +
Pr(not blocked)*cost of path through bottleneck to goal +
Pr(blocked)* cost of shortest path from bottleneck to goal not going through bottleneck
You can see that this last term will also depend on the probability of other bottlenecks being blocked.
Now, as Brian pointed out, many researches deal with this problem by first abstracting the movement between regions segragated by bottlenecks. That is, they approximate the cost to cross a region (e.g. room) from one bottleneck (doorway) to another and work out the planning problem at this level. At the more detailed level they compute the actual cost to cross a region from each bottleneck to each other bottleneck and adjust the approximations accordingly, usually dependent on how much computation time is available.
You can also solve this problem without resorting to probabilities... but using the expected costs method gives your agents rationality (according to the Principle of Maximum Expected Utility).
Cheers,
Timkin
KoM: This is a common problem dealt with in the planning literature. Essentially you don't know a priori whether the bottleneck is passable or not. This is an identical problem in its description to the more commonly studied 'locked door' problem. Unless you have other information, then a priori you would assign a uniform probability distribution over the possible states of the bottleneck; so these would be 'blocked' and 'not blocked'.
The expected cost of a path from start to goal passing through a bottleneck is given by:
Cost to get to bottleneck +
Pr(not blocked)*cost of path through bottleneck to goal +
Pr(blocked)* cost of shortest path from bottleneck to goal not going through bottleneck
You can see that this last term will also depend on the probability of other bottlenecks being blocked.
Now, as Brian pointed out, many researches deal with this problem by first abstracting the movement between regions segragated by bottlenecks. That is, they approximate the cost to cross a region (e.g. room) from one bottleneck (doorway) to another and work out the planning problem at this level. At the more detailed level they compute the actual cost to cross a region from each bottleneck to each other bottleneck and adjust the approximations accordingly, usually dependent on how much computation time is available.
You can also solve this problem without resorting to probabilities... but using the expected costs method gives your agents rationality (according to the Principle of Maximum Expected Utility).
Cheers,
Timkin
You could keep a variable for each unit for instance, that would dictate in wich of those regions the unit would be.
Also keep a table of regions and the connections between each other, if some passage gets obstructed, you go to that region's table entry and remove that particular passage.
When moving the unit, instead of jumping right to A* algo, first check if there is a passage from the region the unit is in to the region it is trying to get to.
There are a lot of ways this little trick won't work though, for instance if the passage for each region is too wide, checking if some relatively large number of spaces are obstructing the passage can become time consuming. Another, if some regions are connected to a relatively high number of regions, checking the table might become time consuming as well.
Well, just think about it.
Also keep a table of regions and the connections between each other, if some passage gets obstructed, you go to that region's table entry and remove that particular passage.
When moving the unit, instead of jumping right to A* algo, first check if there is a passage from the region the unit is in to the region it is trying to get to.
There are a lot of ways this little trick won't work though, for instance if the passage for each region is too wide, checking if some relatively large number of spaces are obstructing the passage can become time consuming. Another, if some regions are connected to a relatively high number of regions, checking the table might become time consuming as well.
Well, just think about it.
Quote:Original post by fup
Timkin! Welcome back! :)
I've always been here... I was still reading the forums every day... I still moderated the occasional thread in this forum... and I still helped people privately... I just wasn't posting publicly after the last debacle... hopefully things will be a little friendlier around here for a while. 8)
Timkin
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
