> 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 _______________________________________________ glob2-devel mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/glob2-devel
