%B 2009 IEEE International Conference on Robotics and Automation, ICRA 2009 %L upm5425 %X 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. %I IEEE %A Claudio Rossi %A Leyre Aldama Perez %A Antonio Barrientos Cruz %C New Jersey, EEUU %D 2009 %T Simultaneous Task Subdivision and Allocation for Teams of Heterogeneous Robots