This paper studies multi-robot task allocation in settings where tasks are revealed sequentially for an infinite or indefinite time horizon, and where robots may execute bundles of tasks. The tasks are assumed to be synergistic so efficiency gains accrue from performing more tasks together. Since there is a tension between the performance cost (e.g., fuel per task) and the task completion time, a robot needs to decide when to stop collecting tasks and to begin executing its whole bundle. This paper explores the problem of optimizing bundle size with respect to the two objectives and their trade-off. Based on qualitative properties of any multi-robot system that bundles sequential stochastic tasks, we introduce and explore an assortment of simple bundling policies. Our experiments examine how these policies perform in a warehouse automation scenario, showing that they are efficient compared to baseline policies where robots do not bundle tasks strategically.
展开▼