An interesting tidbit quote on the optimal assignment problem (aka ST–SR–IA:Single-Task Robots, Single-RobotTasks, Instantaneous Assignment, the multirobot task allocation problem):

“Thus, for small-scale to medium-scale systems, say n< 200, a broadcast-based centralized assignment solution is likely the better choice” [1].

Note that n is the number of robots.  This is an interesting assertion and is backed up by their experiments.  They had 300 robots and 300 tasks and they used the Hungarian method to do the task distribution it ran in under 1 second and that was on a Pentium III 700 MHz machine!

[1]  Gerkey, B. P. (2004). A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems. The International Journal of Robotics Research, 23(9), 939–954. doi:10.1177/0278364904045564

 

Brian Gerkey is pretty cool http://www.ai.sri.com/~gerkey/index.php?src=pubs http://robotics.stanford.edu/~gerkey/