Abstract：In order to achieve complex task allocation dynamically and effectively in multi-robot systems,a general formal description method is presented.The proposed method defines both robot and task capability vectors from the viewpoint of capability classification,and formally describes the multi-robot task allocation problem.Task accomplishment conditions are discussed for both single and multiple robots.Based on this formal description method,a novel market-based wholly distri-buted multi-robot task allocation method is proposed.Simulation results show that this method can achieve complex task(allocation) effectively and dynamically in multi-robot systems in a wholly distributed way.
 Arai T,Pagello E,Parker L E.Advances in multirobot systems[J].IEEE Transactions on Robotics and Automation,2002,18 (5):655-661.  Cao Y U,Fukunaga A S,Kahng A B.Cooperative mobile robotics:antecedents and directions[J].Autonomous Robots,1997,4(1):1-23.  Gerkey B P,Mataric M J.A formal analysis and taxonomy of task allocation in multi-robot systems[J].The International Journal of Robotics Research,2004,23 (9):939-954.  Parker L E.ALLIANCE:an architecture for fault tolerant multirobot cooperation[J].IEEE Transactions on Robotics and Automation,1998,14(2):220 -240.  Gerkey B P,Mataric M J.Sold!:auction methods for multirobot coordination[J].IEEE Transactions on Robotics and Automation,2002,18(5):758 -768.  Ygge F,Akkermans H.Decentralized market versus central control:a comparative study[J].Journal of Artificial Intelligence Research,1999,11:301 -333.  Robert Z,Tony S A,Bernardine D M,et al.Multi-robot exploration controlled by a market economy[A].Proceedings of the IEEE International Conference on Robotics and Automation[C].Piscataway,USA:IEEE,2002.3016-3023.  Liu L,Wang L,Zheng Z Q,et al.A learning market based layered multi-robot architecture[A].Proceedings of the IEEE International Conference on Robotics and Automation[C].Piscataway,USA:IEEE,2004.3417-3422.  Smith R G.The contract net protocol:high level communication and control in a distributed problem solver[J].IEEE Transactions on Computers,1980,C -29(12):1104-1113.