The communication efficient multi-robot (CEMR) task scheduling algorithm for heterogeneous MRS is given in [17]. CEMR assumes direct communication between each robot and a central unit, and direct communication among some robot pairs. Each robot reports its status and detected tasks to a central unit, which allocates tasks, using an auction-based method with a fitness function (including capability, distance from task, and availability). Robots receive status (including positions) of all of the other robots from the central unit, and can also ask directly other nearby robots for help. The article does not discuss any multi-hop communication protocol. Simulation is made with six robots, and the alternative approach is ‘broadcasting’, which is direct request to all of the
other robots instead to few of them who might be available based on a priori knowledge. Three decentralized task allocation schemes among the unmanned
aerial vehicles (UAVs) in destroy targets scenario using negotiation concepts from the team theory and game theory are given in [18]. It is acknowledged that full communication between all UAVs poses high communication costs and idea of localized communication (communication among neighbors only) is given as well as the necessity for the multi-hop communication, if the agents are out of the communication range. However, only the case with the complete graph is simulated. The multi-hop communication was stated in some scenarios, but there is no discussion of any communication protocol actually applied. In summary, finding solutions to concrete task assignment scenarios in the presence of mobility, when the communication cost is not negligible, and communication protocols need to be specified, still remains a research challenge.