Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-24T17:11:37.876Z Has data issue: false hasContentIssue false
  • English
  • Français

Game theory-based negotiation for multiple robots task allocation

Published online by Cambridge University Press:  07 March 2013

Rongxin Cui ,
Ji Guo  and
Bo Gao
Rongxin Cui*
Affiliation:
College of Marine Engineering, Northwestern Polytechnical University, Xi'an 710072, P. R. China
Ji Guo
Affiliation:
College of Physics and Electrical Engineering, Anyang Normal University, Anyang 455000, P. R. China
Bo Gao
Affiliation:
College of Marine Engineering, Northwestern Polytechnical University, Xi'an 710072, P. R. China
*
*Corresponding author. E-mail: [email protected].
Get access Rights & Permissions [Opens in a new window]

Summary

This paper investigates task allocation for multiple robots by applying the game theory-based negotiation approach. Based on the initial task allocation using a contract net-based approach, a new method to select the negotiation robots and construct the negotiation set is proposed by employing the utility functions. A negotiation mechanism suitable for the decentralized task allocation is also presented. Then, a game theory-based negotiation strategy is proposed to achieve the Pareto-optimal solution for the task reallocation. Extensive simulation results are provided to show that the task allocation solutions after the negotiation are better than the initial contract net-based allocation. In addition, experimental results are further presented to show the effectiveness of the approach presented.

Keywords

Task allocationGame theoryMultiple robotsNegotiationCooperative controlPareto-optimization
Type
Articles
Information
Robotica , Volume 31 , Issue 6 , September 2013 , pp. 923 - 934
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Yang, C., Li, Z. and Li, J., “Trajectory planning and optimized adaptive control for a class of wheeled inverted pendulum vehicle models,” IEEE Trans. Cybern. 43 (1), 24–36 (2013).CrossRefGoogle ScholarPubMed
2.Fua, C. H. and Ge, S. S., “COBOS: Cooperative backoff adaptive scheme for multirobot task allocation,” IEEE Trans. Robot. 21 (6), 1168–1178 (2005).Google Scholar
3.Dahl, T. S., Matarić, M. and Sukhatme, G. S., “Multi-robot task allocation through vacancy chain scheduling,” Robot. Auton. Syst. 57, 674–687 (2009).CrossRefGoogle Scholar
4.Li, Z., Tao, P. Y., Ge, S. S., Adams, M. and Wijesoma, W. S., “Robust adaptive control of cooperating mobile manipulators with relative motion,” IEEE Trans. Syst. Man Cybern. B 39 (1), 103–116 (2009).Google ScholarPubMed
5.Yang, C., Ganesh, G., Haddadin, S., Parusel, S., Albu-Schaeffer, A. and Burdet, E., “Human-like adaptation of force and impedance in stable and unstable interactions,” IEEE Trans. Robot. 27 (5), 918–930 (2011).CrossRefGoogle Scholar
6.Cui, R., Ge, S. S., How, V. E. B. and Choo, Y. S., “Leader–follower formation control of underactuated autonomous underwater vehicles,” Ocean Eng. 37 (17–18), 1491–1502 (2010).CrossRefGoogle Scholar
7.Li, Z., Cao, X. and Ding, N., “Adaptive fuzzy control for synchronization of nonlinear teleoperators with stochastic time-varying communication delays,” IEEE Trans. Fuzzy Syst. 19 (4), 745 (2011).CrossRefGoogle Scholar
8.Li, Z., Li, J. and Kang, Y., “Adaptive robust coordinated control of multiple mobile manipulators interacting with rigid environments,” Automatica 40 (12), 2028–2034 (2010).CrossRefGoogle Scholar
9.Matarić, M. J., Sukhatme, G. S. and Østergaard, E. H., “Multi-robot task allocation in uncertain environments,” Auton. Robots 14 (2), 255–263 (2003).CrossRefGoogle Scholar
10.Elango, M., Nachiappan, S. and Tiwari, M. K., “Balancing task allocation in multi-robot systems using k-means clustering and auction based mechanisms,” Expert Syst. Appl. 38, 6486–6491 (2011).CrossRefGoogle Scholar
11.Gerkey, B. and Matarić, M. J., “A formal framework for the study of task allocation in multi-robot systems,” Int. J. Robot. Res. 23 (9), 939–954 (2004).CrossRefGoogle Scholar
12.Sayyaadi, H. and Moarref, M., “A distributed algorithm for proportional task allocation in networks of mobile agents,” IEEE Trans. Autom. Control 56, 405–410 (2011).CrossRefGoogle Scholar
13.Service, T. C. and Adams, J. A., “Coalition formation for task allocation: Theory and algorithms,” Auton. Agent and Multi-Agent Syst. 22, 225–248 (2011).CrossRefGoogle Scholar
14.Chan, Z. S. H., Collins, L. and Kasabov, N., “An efficient greedy k-means algorithm for global gene trajectory clustering,” Expert Syst. Appl. 30, 137–141 (2006).CrossRefGoogle Scholar
15.Cheng, C. H., Cheng, G. W. and Wang, J. W., “Multi-attribute fuzzy time series method based on fuzzy clustering,” Expert Syst. Appl. 34, 1235–1242 (2008).CrossRefGoogle Scholar
16.Strens, M. and Windelinckx, N., “Combining planning with reinforcement learning for multi-robot task allocation,” In: Adaptive Agents and Multi-Agent Systems II (Kudenko, D., Kazakov, D. and Alonso, E., eds.), Springer, Berlin (2005) pp. 260–274.CrossRefGoogle Scholar
17.Abdallah, S. and Lesser, V., “Learning the Task Allocation Game,” Proceedings of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems, ACM (2006) pp. 850–857.CrossRefGoogle Scholar
18.Vamvoudakis, K. G. and Lewis, F. L., “Multi-player non-zero-sum games: Online adaptive learning solution of coupled Hamilton–Jacobi equations,” Automatica 47 (8), 1556–1569 (2011).CrossRefGoogle Scholar
19.Dias, M. B., Zlot, R., Kalra, N. and Stentz, A., “Market-based multirobot coordination: A survey and analysis,” Proc. IEEE 94 (7), 1257–1270 (2006).CrossRefGoogle Scholar
20.Khamis, A. M., Elmogy, A. M. and Karray, F. O., “Complex task allocation in mobile surveillance systems,” J. Intell. Robot. Syst. 64, 33–55 (2011).CrossRefGoogle Scholar
21.Choi, H.-L., Brunet, L. and How, J. P., “Consensus-based decentralized auctions for robust task allocation,” IEEE Trans. Robot. 25, 912–926 (2009).CrossRefGoogle Scholar
22.Rasmusen, E., Games and Information: An Introduction to Game Theory, Blackwell, Malden, MA (2007).Google Scholar
23.Adler, M. R., Davis, A. B., Wehmayer, R. and Worrest, R. W., “Conflict Resolution Strategies for Nonhierarchical Distributed Agents,” In: Distributed Artificial Intelligence (Huhns, M., ed.), Morgan Kaufmann, San Francisco, CA (1989) vol. 2, pp. 139–161.CrossRefGoogle Scholar
24.Botelho, S., Alami, R. and LAAS-CNRS, T., “M+: A Scheme for Multi-robot Cooperation Through Negotiated Taskallocation and Achievement,” IEEE International Conference on Robotics and Automation, Detroit, MI (1999) vol. 2, pp. 1234–1239.Google Scholar
25.Davis, R. and Smith, R. G., “Negotiation as a metaphor for distributed problem solving,” Artif. Intell. 20 (1), 63–109 (1983).CrossRefGoogle Scholar
26.Durfee, E. H., “Distributed Problem Solving and Planning,” In: Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence (Gerhard, W., ed.), MIT Press, Cambridge, Massachusetts, USA (1999) pp. 121–164.Google Scholar
27.Mullen, T. and Wellman, M., “Some issues in the design of market-oriented agents,” In: Intelligent Agents II Agent Theories, Architectures, and Languages (Michael, W., Jörg, M. and Milind, T., eds.), Springer, Berlin (1996) pp. 283–298.CrossRefGoogle Scholar
28.Wellman, M. P., “Market-oriented Programming: Some Early Lessons,” In: Market-based Control: A Paradigm for Distributed Resource Allocation (Clearwater, S., ed.), World Scientific, Singapore (1996) pp. 74–95.CrossRefGoogle Scholar
29.Zlotkin, G. and Rosenschein, J. S., “Cooperation and conflict resolution via negotiation among autonomous agents in noncooperative domains,” IEEE Trans. Syst. Man Cybern. 21 (6), 1317–1324 (1991).CrossRefGoogle Scholar
30.Basar, T. and Olsder, G. J., Dynamic Noncooperative Game Theory, SIAM Series in Classics in Applied Mathematics, SIAM, Philadelphia, PA (1999).Google Scholar
31.Sycara, K., Roth, S. F., Sadeh, N. and Fox, M. S., “Distributed constrained heuristic search,” IEEE Trans. Syst. Man Cybern. 21 (6), 1446–1461 (1991).CrossRefGoogle Scholar
32.Zlotkin, G. and Rosenschein, J. S., “Cooperation and conflict resolution via negotiation among autonomous agents in noncooperative domains,” IEEE Trans. Syst. Man Cybern. 21 (6), 1317–1324 (1994).CrossRefGoogle Scholar
33.Liu, G. P., Yang, J. B. and Whidborne, J. F., Multiobjective Optimisation and Control (Research Studies Press, Baldock, Hertfordshire, UK, 2004).Google Scholar
34.Das, I. and Dennis, J., “Boundary intersection: A new method for generating pareto optimal points in multicriteria optimization problems,” SIAM J. Optim. 8 (3), 631–657 (1998).CrossRefGoogle Scholar
35.Cui, R., Gao, B. and Guo, J., “Pareto-optimal coordination of multiple robots with safety guarantees,” Auton. Robots 32 (3), 189–205 (2012).CrossRefGoogle Scholar
36.Harsanyi, J. C., Rational Behavior and Bargaining Equilibrium in Games and Social Situations (Cambridge, Cambridge University Press, 1977).CrossRefGoogle Scholar
37.Sandholm, T. W., “An Implementation of the Contract Net Protocol Based on Marginal Cost Calculations,” Proceedings of the National Conference on Artificial Intelligence, Washington, DC (1993) pp. 256–256.Google Scholar
38.Sandholm, T. W., “Contract Types for Satisficing Task Allocation: I. Theoretical Results,” In: AAAI Spring Symposium Series: Satisficing Models, AAAI, California, USA (1998), pp. 68–75.Google Scholar
39.Ahuja, R. K., Magnanti, T. L., Orlin, J. B. and Weihe, K., Network Flows: Theory, Algorithms, and Applications (Prentice Hall, Englewood Cliffs, NJ, 1993).Google Scholar
40.Rosenschein, J. S. and Zlotkin, G., Rules of Encounter (MIT Press, Cambridge, MA, 1994).Google Scholar
41.Cormen, T., Leiserson, C., Rivest, R. and Stein, C., Introduction to Algorithms (MIT Press, Cambridge, MA, 2001).Google Scholar
42.Bramel, J. and Simchi-Levi, D., “A location based heuristic for general routing problems,” Oper. Res. 43 (4), 649–660 (1995).CrossRefGoogle Scholar
43.Guo, J., Gao, B., Cui, R. and Ge, S. S., “Estimating the Minimum Number of Robots to Finish Given Multi-objects Task,” IEEE 5th International Conference on Cybernetics and Intelligent Systems (CIS), Qingdao, P. R. China (2011) vol. 1, pp. 170–174.Google Scholar