Abstract: With the continued development of robotics, robots can perform more and more complex multi-robot tasks. The subtasks decomposed by multi-robot task may be different significantly and member robots in system may be varying on capability models. It is a challenge to most of task allocation algorithms in this context. This paper studied ST-MR-IA task allocation algorithm under heterogeneous capabilities condition. We give the concept of capability heterogeneity; provide a multi-robot task allocation algorithm, whose complexity being simplified by distributed computing and pruning strategy. The effectiveness of this new algorithm is verified in practice.