Abstract
This paper considers the problem of optimal task allocation for heterogeneous teams, e.g., teams of heterogeneous robots or human-robot teams. It is well known that this problem is NP hard and hence computationally feasible approaches must develop an approximate solution. This paper proposes a solution via a Stochastic Clustering Auction (SCA) that uses a Markov chain search process along with simulated annealing. The original developments are for a centralized auction, which may be feasible at the beginning of a mission. The problem of developing a distributed auction is also considered. It can be shown that if the distributed auction is such that the auctioneer allocates tasks to optimize the regional cost, then the distributed auction will always decrease the global cost or have it remain constant, which provides the theoretical basis for distributed SCA. Both centralized SCA and distributed SCA are demonstrated via simulations. In addition, simulation results show that by appropriate choice of the parameter in SCA representing the rate of “temperature” decrease, the number of iterations (i.e., auction rounds) in SCA can be dramatically reduced while still achieving reasonable performance. It is also shown via simulation that in relatively few iterations (8 to 35), SCA can improve the performance of sequential or parallel auctions, which are relatively computationally inexpensive, by 6%-12%. Hence, it is complimentary to these existing auction approaches.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Gerkey, B.P., Mataric, M.J.: Sold!: auction methods for multirobot coordination. IEEE Transactions on Robotics and Automation 18(5), 758–768 (2002)
Simmons, R., Singh, S., Heger, F., Hiatt, L.M., Koterba, S.C., Melchior, N., Sellner, B.P.: Human-robot teams for large-scale assembly. In: Proceedings of the NASA Science Technology Conference 2007 (NSTC 2007) (May 2007)
Dias, M.B., Zlot, R.M., Kalra, N., Stentz, A.: Market-based multirobot coordination: a survey and analysis. Proceedings of the IEEE 94(7), 1257–1270 (2006)
Koes, M., Sycara, K., Nourbakhsh, I.: A constraint optimization framework for fractured robot teams. In: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 491–493 (May 2006)
Koenig, S., Tovey, C.A., Zheng, X., Sungur, I.: Sequential bundle-bid single-sale auction algorithms for decentralized control. In: IJCAI, pp. 1359–1365 (2007)
Zlot, R.M., Stentz, A.: Market-based multirobot coordination for complex tasks. Int. J. of Robot. Res., Special Issue on the 4th International Conference on Field and Service Robotics 25(1), 73–101 (2006)
Parker, L.E.: Alliance: An architecture for fault tolerant multi-robot cooperation. IEEE Transactions on Robotics and Automation 14(2) (1998)
Wagner, A., Arkin, R.C.: Multi-robot communication-sensitive reconnaissance. In: Proceedings of the IEEE International Conference on Robotics and Automation, New Orleans, LA, April 26 - May 1, pp. 4674–4681 (2004)
Sandholm, T.: An algorithm for optimal winner determination in combinatorial auctions. In: IJCAI 1999, pp. 542–547 (1999)
Srivastava, A., Joshi, S.H., Mio, W., Liu, X.: Statistical shape analysis: Clustering, learning, and testing. IEEE T. on Pattern Anal. 27(4), 590–602 (2005)
Robert, C.P., Casella, G.: Monte Carlo Statistical Methods (Springer Texts in Statistics). Springer, New York (2005)
Prim, R.C.: Shortest connection networks and some generalisations. Bell System Technical Journal 36, 1389–1401 (1957)
Kirkpatrick Jr., S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Zhang, K., Collins, E.G., Shi, D., Liu, X., Chuy, O. (2009). A Stochastic Clustering Auction (SCA) for Centralized and Distributed Task Allocation in Multi-agent Teams. In: Asama, H., Kurokawa, H., Ota, J., Sekiyama, K. (eds) Distributed Autonomous Robotic Systems 8. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00644-9_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-00644-9_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00643-2
Online ISBN: 978-3-642-00644-9
eBook Packages: EngineeringEngineering (R0)