JRM Vol.26 No.3 pp. 369-376
doi: 10.20965/jrm.2014.p0369


A Discrete Adaptive Auction-Based Algorithm for Task Assignments of Multi-Robot Systems

Xuefeng Dai*, Zhifeng Yao**, and Yan Zhao***

*Center of Networks and Information, Qiqihar University

**School of Computer and Control Engineering, Qiqihar University

***School of Communication and Electronic Engineering, Qiqihar University, Wenhua Str.42, Qiqihar, Heilongjiang 161006, China

January 15, 2014
May 9, 2014
June 20, 2014
multi-robot systems (MRSs), discrete adaptive auction-based algorithms, market economy, task assignments

Teammates trajectories

For reasons of production cost and differences in manufacturing dates for mobile robots, individual robots on a robot team have different processing, movement, and detection abilities. To maximize the potential ability of individual robots and minimize overall exploration time in unknown environments, this paper proposes a novel discrete adaptive auction-based algorithm for coordinating multirobot systems (MRSs). A utility calculation scheme that takes into account the dispersion of teammates is presented, followed by an identical performance index formula that converges to a value for measuring differences in exploration efficiency. The performance measure is taken into account in calculating bids for exploration tasks. We compared our results to other exploration strategies by simulation and results show improved exploration time.

Cite this article as:
X. Dai, Z. Yao, and Y. Zhao, “A Discrete Adaptive Auction-Based Algorithm for Task Assignments of Multi-Robot Systems,” J. Robot. Mechatron., Vol.26, No.3, pp. 369-376, 2014.
Data files:
  1. [1] B. Yamauchi, “Decentralized coordination for multirobot exploration,” Robot. Auton. Syst., Vol.29, No.2-3, pp. 111-118, 1999.
  2. [2] W. Burgard, M. Moors, C. Stachniss, and F. E. Schneider, “Coordinated multi-robot exploration,” IEEE Trans. Robot, Vol.21, No.3, pp. 376-386, 2005.
  3. [3] M. B. Dias, R. Zlot, N. Kalra, and A. Stentz, “Market-based multirobot coordination: a survey and analysis,” Proc. IEEE, Vol.94, No.7, pp. 1257-1270, 2006.
  4. [4] M. Nanjanath and M. Gini, “Repeated auctions for robust task execution by a robot team,” Robot Auton Syst, Vol.58, No.7, pp. 900-909, 2010.
  5. [5] M. Elango, S. Nachiappan, and M. K. Tiwari, “Balancing task allocation in multi-robot systems using K-means clustering and auction based mechanisms,” Expert. Syst. Appl., Vol.38, No.6, pp. 6486-6491, 2011.
  6. [6] D. Puig, M. A. Garcia, and L. Wu, “A new global optimization strategy for coordinated multi-robot exploration: Development and comparative evaluation,” Robot. Auton. Syst., Vol.59, No.9, pp. 635-653, 2011.
  7. [7] A. Solanas and M. A. Garcia, “Coordinated multi-robot exploration through unsupervised clustering of unknown space,” Proc. of the 2004 IEEE/RSJ Int. Conf. on intelligent robots and systems, Vol.1, pp 717-721, 2004.
  8. [8] K. M. Wurm, C. Stachniss, and W. Burgard, “Coordinated multirobot exploration using a segmentation of the environment,” Proc. of the 2008 IEEE/RSJ Int. Conf. on intelligent robots and systems, pp 1160-1165, 2008.
  9. [9] E. G. Jones, M. B. Dias, and A. Stentz, “Time-extended multirobot coordination for domains with intra-path constraints,” Auton Robots, Vol.30, No.1, pp. 41-56, 2011.
  10. [10] K. Zhang, E. Collins, and D. Shi, “Centralized and distributed task allocation in multi-robot teams via a stochastic clustering auction,” ACM Trans. Auton. Adap. Sys., Vol.7, No.2, pp. 21:1-21:22, 2012.
  11. [11] P. Chand and D. A. Carnegie, “Mapping and exploration in a hierarchical heterogeneous multi-robot system using limited capability robots,” Robot Auton Syst, Vol.61, No.6, pp. 565-579, 2013.
  12. [12] H. L. Choi, L. Brunet, and J. P. How, “Consensus-based decentralized auctions for robust task allocation,” IEEE Trans Robot, Vol.25, No.4, pp. 912-926, 2009.
  13. [13] W. Sheng, Q. Yang, J. Tan, and N. Xi, “Distributed multi-robot coordination in area exploration,” Robot Auton Syst, Vol.54, No.12, pp. 945-955, 2006.
  14. [14] R. Simmons, D. Apfelbaum, W. Burgard, D. Fox, M. Moors, S. Thrun, and H. Younes, “Coordination for multi-robot exploration and mapping,” Proc. of the AAAI national conf. on artificial intelligence, Menlo Park, CA, 2000, pp. 852-858, 2000.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, IE9,10,11, Opera.

Last updated on Nov. 16, 2018