In this paper, we present a negotiation protocol for simultaneous task subdivision and allocation for heterogeneous multi-robot systems. An abstraction of the concept of task is presented that allows to apply the protocol on a variety of tasks. The negotiation adopts Rubinstein's alternate offers protocol, where offers are evaluated and generated using a heuristic search step. The protocol has been tested on computer simulations.

In this paper, we present an application to Search and Rescue of a task negotiation protocol for teams of heterogeneous robots. Self-organization through autonomous negotiations allow the robots to assign themselves a number of target observation points decided by the operator, who is relieved from deciding the optimal assignment. The operator can then focus on monitoring the mission and deciding next actions. The protocol has been tested on both computer simulations and real robots.