Gerkey’s paper addresses the issue faced with multi-robot task allocation (MRTA). The complexity of multi-robot systems has two primary sources: larger team sizes and greater heterogeneity of robots and tasks. Today we reasonably expect to see increasingly larger robot teams engaged in concurrent and diverse tasks over extended periods of time. This paper seeks to address this complexity not via characterization of architectures but instead seeks to categorize the underlying problems.
One method used to determine how the task allocation will be prioritized is to use utility (also called fitness, valuation and cost). The essence of a task allocation problem is comparison and selection among a set of available alternatives. Therefore, calculating utility is one nice method of comparing the different tasks and their given priorities. Regardless of the method used for calculation, the robots’ utility estimates will be inexact due to sensor noise, general uncertainty, and environmental change. Since many of the robots are interchangeable, it is often advantageous to allow any player to take on any role within the team, according to the current situation in the game. One technique used for solving the optimization problem with task allocation is to use the optimal auction algorithm. This technique allows a robot (when it discovers a new target) to insert its new target into its schedule, but retains the option of later auctioning the target off to another, closer robot. Another possible solution to this issue with task allocation is using a learning approach in which the robots learn both their utility estimates and their scheduling algorithms from experience. When trained for a particular task domain, this system has the potential to outperform the approximation algorithm.
One issue with the proposed solutions is that the communication requirements are not totally realistic given a real-world environment. The architecture assumes that a perfect shared broadcast communication medium is used and that messages are always broadcast, rather than unicast. This is the issue because as described in Stone’s “Task decomposition, dynamic role assignment, and low -bandwidth communication for real-time strategic teamwork”, the environment for communication can be a single-channel, low-bandwidth, unreliable communication. This issue should have been addressed more in depth since communication amongst the agents is critical for keeping synchronization and the soccer robots represent a great example of this being utilized in real-time.
In conclusion, we can see how the research efforts are useful, as they demonstrate that successful multi-robot coordination is possible, even in complex environments. The MRTA problems are fundamentally organizational in nature, in that the goal is to allocate limited resources in such a way as to efficiently achieve some tasks. This paper demonstrated the problems faced with addressing these issues.
Reference:
- Gerkey, Brian P. “A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems.” <http://robotics.stanford.edu/~gerkey/research/final_papers/mrta-taxonomy.pdf>
