PDA

View Full Version : AI Resource Allocation Problem: Max Flow/ Max Matching



gregchant
28-08-2007, 04:10 AM
I’d love to get some input on the best algorithm type to use for solving a specific resource allocation problem which I expect the AI to use quite a bit in a game I am designing. I’ve read up on and been experimenting with using matching algorithms for weighted bipartite graphs and maximum network flow algorithms, but so far have not found something that seems to fit exactly. If not obvious from my post, please note that I am a self-taught amateur and my day job is in another profession.

The game I am working on is a WWII turn-based division-level game. The particular problem I am trying to solve is as follows: given a set of divisions and a set of front line hexes, how best to distribute the divisions so that that the troop density is evenly distributed across the front line hexes. The front width of each hex may vary (for example, due to the number of hexsides bordering enemy troops) . Further, the ideal front width of each division will vary based on division type as well as its current strength. Each division may only be assigned to one hex, but each hex may have multiple or no divisions assigned to it. (I’d also like to minimize the march time it takes to get each division to a hex on the front by trying to assign divisions to the hexes to which they are closer when possible, but that is step two.)

For example, if there were two hexes, one with a 5km front width and one with a 7km front width, and there were three divisions with ideal front widths of 5km, 4km, and 3km, then the algorithm should put the 4km and 3km divisions in the 7km hex and the 5km division in the 5 km hex.

Obviously, I could solve by brute force, but given that the number of hexes may often exceed 10 and the number of divisions exceed 20 and that this algorithm will be heavily used, it is worthwhile to find a more efficient/quicker approach (10 hexes with 20 divisions results in a number of combinations equal to 10 to the power of 20).

This problem can be represented by a bipartite graph and I have experimented with using a max flow algorithm where (1) the nodes in set A are the divisions and the nodes in set B are the hexes, (2) the capacity of the edges between each division node and each hex node to which the division may move equals the front width of the division, (3) the capacity of the edges between each hex and the super sink equals the front width of the hex, and (4) the capacity of each edge from the super source equals the front width of the division to which node it is connecting. The problem with this approach is that the flow of one division can be split among more than one hex (yet I need to restrict each division to one hex only).

So far the best solution I can think of is as follows: (1) step one, use the max flow algorithm, but not allow any paths that do not take the full flow from the divisional node (2) for each unmatched division node, search for alternating paths along the residual network and implement any alternating paths that would be augmenting (i.e., increase the flow). While using alternate paths may normally be an efficient algorithm, in this case I am concerned it will be almost as bad as the brute force approach in that, unless step 1 results in a perfect matching, I will need to review every possible path to determine that there is not one that is augmenting (which is probably equivalent to examining each possible combination).
Any suggestions? Is the max flow or matching weighted bipartite the right approach, and if so how can I better model/solve this problem? Or am I barking up the wrong algorithm tree?

wodzu
29-08-2007, 07:44 AM
Hello :) Nice first post :) I can't give you the "best" algorithm to solve your problem, but I would try a Genetic Algorithm approach. You will find solution quickly, however it won't be optimal. But if you can live with an error ~5% than give it a try.

gregchant
30-08-2007, 05:06 PM
Thanks, I will look at using a Genetic Algorithm approach. Since I posted my original post I found some articles on line that describe this as a "separable assignment problem" (or SAP), a subset of a "general assignment problem," and evidently it is proven to be NP hard to solve, which I think means any maximum (best) solution is going to be computational expensive.

Here are some links to some articles in case anyone is looking to solve a similar problem (warning, heavy on math):

http://www.zib.de/Publications/Reports/SC-94-14.pdf

http://www-math.mit.edu/~goemans/ga-soda06.pdf

wodzu
14-09-2007, 09:32 AM
Keep working hard, if you find an algorithm that will solve this problem in polynomial time you will earn a lot of money ;-)