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
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.
-  B. Yamauchi, “Decentralized coordination for multirobot exploration,” Robot. Auton. Syst., Vol.29, No.2-3, pp. 111-118, 1999.
-  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.
-  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.
-  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.
-  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.
-  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.
-  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.
-  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.
-  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.
-  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.
-  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.
-  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.
-  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.
-  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.