Re: [glob2-devel] Optimal Unit Assignment

[Stéphane Magnenat]

> To be truly optimal:
> We then consider all buildings, all building unit combinations, and find
> the one that fills all possible slots that ends up with the lowest overall
> distance covered. This could be run as often as wanted to take care of
> changing circumstances.

This is a well known problem in multi-agent task allocation. In general, 
optimal allocation is NP-complete. For a scientific introduction to the 
subject, I suggest reading [1]. I can send the corresponding journal article 
with better layout and table to the ones who want.

The other problem is that we only want to reallocate units that are free, 
which opens the question of how long a unit should wait before reallocation. 
My feeling is that the optimal time, from a player point of view, depends on 
the average amount of job turn-taking. So maybe we should wait longer in the 
beginning of the game.

Anyway as the future is uncertain and game duration unbounded, the problem is 
a Markov Decision Process [2] over an unbounded space, and the overall 
optimum (i.e. the expectancy over all possible outcomes weighted by their 
probabilities ) is undecidable; if we take only a finite horizon and a finite 
state space, the problem is NC (proably worst than P-complete, but this is 
currently only a conjecture) [3].

So to be realistic and ensure scalability, we certainly should use smart 
heuristics instead of finding the optimal; of course, we can find heuristics 
that are optimal in common cases ;-)

Have a nice day,

Steph

[1]     http://www.cs.cmu.edu/~robz/publications/CMU-RI-TR-05-13.pdf
[2]     http://en.wikipedia.org/wiki/Markov_decision_process
[3]     http://dspace.mit.edu/bitstream/1721.1/2893/1/P-1479-13685602.pdf

-- 
http://stephane.magnenat.net