Task Coordination Organization Model and the Task Allocation Algorithm for Resource Contention of the Syncretic System

Danfeng Wu; Guangping Zeng; Di He; Zhaopeng Qian; Qingchuan Zhang

doi:10.1109/TST.2016.7536724

Tsinghua Science and Technology 2016, 21(4): 459-470 https://doi.org/10.1109/TST.2016.7536724

Open Access | Issue | Published: 11 August 2016

Task Coordination Organization Model and the Task Allocation Algorithm for Resource Contention of the Syncretic System

Show Author's Information Hide Author's Information Danfeng Wu, Guangping Zeng(

), Di He, Zhaopeng Qian, Qingchuan Zhang

School of Computer & Communication Engineering, University of Science & Technology Beijing, Beijing 100083, China

School of Software, Liaoning Technical University, Huludao 125105, China

Beijing Key Laboratory of Knowledge Engineering for Materials Science, Beijing 100083, China.

Graduate Center, City University of New York, New York, NY 10016, USA.

Keywords:

game theory, SoftMan, robot, syncretic system, organization model, task allocation

Cite this article:

Wu D, Zeng G, He D, et al. Task Coordination Organization Model and the Task Allocation Algorithm for Resource Contention of the Syncretic System. Tsinghua Science and Technology, 2016, 21(4): 459-470. https://doi.org/10.1109/TST.2016.7536724

Download citation

EndNote(RIS)

BibTeX

403

Views

Downloads

Citations

Crossref

N/A

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

At present, robot embedded systems have some common problems such as closure and poor dynamic evolution. Aiming at resolving this situation, our paper focuses on improvements to the robot embedded system and sets up a new robot system architecture, and we propose a syncretic mechanism of a robot and SoftMan (SM). In the syncretic system, the structural organization of the SoftMan group and its modes are particularly important in establishing the task coordination mechanism. This paper, therefore, proposes a coordination organization model based on the SoftMan group, and studies in detail the process of task allocation for resource contention, which facilitates a rational allocation of system resources. During our research, we introduced Resource Requirement Length Algorithm (RRLA) to calculate the resource requirements of the task and a resource conformity degree allocation algorithm of Resource Conformity Degree Algorithm (RCDA) for resource contention. Finally, a comparative evaluation of RCDA with five other frequently used task allocation algorithms shows that RCDA has higher success and accuracy rates with good stability and reliability.

Full text

Abstract

Full text

Outline

About this article

Task Coordination Organization Model and the Task Allocation Algorithm for Resource Contention of the Syncretic System

Show Author's information Hide Author's Information Danfeng Wu, Guangping Zeng(

), Di He, Zhaopeng Qian, Qingchuan Zhang

School of Computer & Communication Engineering, University of Science & Technology Beijing, Beijing 100083, China

School of Software, Liaoning Technical University, Huludao 125105, China

Beijing Key Laboratory of Knowledge Engineering for Materials Science, Beijing 100083, China.

Graduate Center, City University of New York, New York, NY 10016, USA.

Abstract

Keywords: game theory, SoftMan, robot, syncretic system, organization model, task allocation

References(30)

[1]

Zeng G. P., Tu X. Y., and Wang H. B., SoftMan Research and Applications (in Chinese), Beijing, China: Science Press, 2007, pp. 10–19.

[2]

Zeng G. P. and Tu X. Y., The concept model and construction frame of the SoftMan, Computer Science, vol. 32, no. 25, pp. 135–143, 2005.

Google Scholar

[3]

Liu Q., Zeng G. P., Zhang W., and Tu X. Y., Research on SoftManindividual model, Computer Engineering and Applications, vol. 30, pp. 49–51, 2005.

Google Scholar

[4]

Karagiannis P., Vouros G., Stergiou K., and Samaras N., Overlay networks for task allocation and coordination in large-scale networks of cooperative agents, Autonomous Agents and MultiAgent Systems, vol. 24, no. 1, pp. 26–68, 2012.

DOI Google Scholar

[5]

Wang W. Y. and Jiang Y. C., Community-aware task allocation for social networked multiagent systems, IEEE Transactions on Cybernetics, vol. 44, no. 9, pp. 1529–1543, 2014.

DOI Google Scholar

[6]

Sarker M. O. F., Dahl T. S., and Arcaute E., Local interactions over global broadcasts for improved task allocation in self-organized multi-robot systems, Robotics & Autonomous Systems, vol. 62, no. 10, pp. 1453–1462, 2014.

DOI Google Scholar

[7]

Capdepuy P., Polani D., and Nehaniv C. L., Perceptionaction loops of multiple agents: Informational aspects and the impact of coordination, Theory in Biosciences, vol. 131, no. 3, pp. 149–159, 2012.

DOI Google Scholar

[8]

Arsenyan J., Büyükzkan G., and Feyziolu O., Modeling coordination formation with a game theory approach, Expert Systems with Applications, vol. 42, no. 4, pp. 2073–2085, 2015.

DOI Google Scholar

[9]

Hermoso R., Billhardt H., and Ossowski S., Trust-based role coordination in task-oriented multi-agent systems, Knowledge-Based Systems, vol. 52, pp. 78–90, 2013.

DOI Google Scholar

[10]

Hunt S., Meng Q. G., Hinde C., and Huang T. W., A consensus-based grouping algorithm for multi-agent cooperative task allocation with complex requirements, Cognitive Computation, vol. 6, no. 3, pp. 338–350, 2014.

DOI Google Scholar

[11]

Hyun L. D., Zaheer S. A., and Hwan K. J., Ad hoc network-based task allocation with resource-aware cost generation for multi-robot systems, IEEE Transactions on Industrial Electronics, vol. 61, no.12, pp. 6871–6881, 2014.

DOI Google Scholar

[12]

Lattuada M. and Ferrandi F., Modeling resolution of resources contention in synchronous data flow graphs, Journal of Signal Processing Systems, vol. 80, no. 1, 39–47, 2014.

DOI Google Scholar

[13]

de Blanche A. and Lundqvist T., Addressing characterization methods for memory contention aware co-scheduling, The Journal of Supercomputing, vol. 71, no. 4, pp. 1451–1483, 2015.

DOI Google Scholar

[14]

Sheikhalishahi M., Grandinetti L., Wallace R. M., and Vazquez-Poletti J. L., Autonomic resource contention-aware scheduling, Software: Practice and Experience, vol. 45, no. 2, pp. 161–175, 2015.

DOI Google Scholar

[15]

Tillenius M., Larsson E., Badia R. M., and Martorell X., Resource-aware task scheduling, ACM Transactions on Embedded Computing Systems (TECS), vol. 14, no. 1, p. 5, 2015.

DOI Google Scholar

[16]

Fink A. and Homberger J., An ant-based coordination mechanism for resource-constrained project scheduling with multiple agents and cash flow objectives, Flexible Services and Manufacturing Journal, vol. 25, nos. 1&2, pp. 94–121, 2013.

DOI Google Scholar

[17]

Tu X. Y., Wang Z., and Guo Y. H., Large Scale Systems Control Theory, (in Chinese). Beijing, China: Beijing University of Posts and Telecommunications Press, 2005.

[18]

Tu X. Y., Generalized model, intelligent simulation, soft-man, Computer Simulation, vol. 28, no. 7, pp. 224–228, 2011.

Google Scholar

[19]

Weerdt M. M. D., Zhang Y., and Klos T., Multiagent task allocation in social networks, Autonomous Agents and Multi-Agent Systems, vol. 25, no. 1, pp. 46–86, 2012.

DOI Google Scholar

[20]

Jiang Y. and Jiang J., Contextual resource negotiation-based task allocation and load balancing in complex software systems, IEEE Transactions on Parallel & Distributed Systems, vol. 20, no. 5, pp. 641–653, 2008.

DOI Google Scholar

[21]

Jiang Y., Zhou Y., and Wang W., Task allocation for undependable multiagent systems in social networks, IEEE Transactions on Parallel & Distributed Systems, vol. 24, no. 8, pp. 1671–1681, 2013.

DOI Google Scholar

[22]

Jiang Y. and Li Z., Locality-sensitive task allocation and load balancing in networked multiagent systems: Talent versus centrality, Journal of Parallel & Distributed Computing, vol. 71, no. 6, pp. 822–836, 2011.

DOI Google Scholar

[23]

Jiang Y. and Huang Z., The rich get richer: Preferential attachment in the task allocation of cooperative networked multiagent systems with resource caching, Systems Man & Cybernetics Part A Systems & Humans IEEE Transactions on, vol. 42, no. 5, pp. 1040–1052, 2012.

DOI Google Scholar

[24]

Wang L., Sofa: An expert-driven, self-organization peer-to-peer semantic communities for network resource management, Expert Systems with Applications, vol. 38, no. 1, pp. 94–105, 2011.

DOI Google Scholar

[25]

Fjuita S. and Lesser V. R., Centralized task distribution in the presence of uncertainty and time deadlines, in Proc. 2nd ICMAS, Kyoto, Japan, 1996, pp. 87-94.

[26]

Kose H., Tatldede U., MeriCli C. E., Kaplan K., and Ak H. L., Q-learning based market-driven multi-agent collaboration in robot soccer, in Proceedings of the Turkish Symposium on Artificial Intelligence & Neural Networks, 2004, pp. 219-228.

DOI

[27]

Wang W. and Jiang Y., Community-aware task allocation for social networked multiagent systems, IEEE Transactions on Cybernetics, vol. 44, no. 9, pp. 1529–1543, 2014.

DOI Google Scholar

[28]

Park M. and Park H., An efficient test method for rate monotonic schedulability, IEEE Transactions on Computers, vol. 63, no. 5, pp. 1309–1315, 2014.

DOI Google Scholar

[29]

Okuyan E. and Kayayurt B., Earliest deadline first scheduling algorithm and its use in ANKA UAV, Digital Avionics Systems Conference (DASC), 2012 IEEE/AIAA 31st IEEE, 2012, pp. 8B1-1-8B1-8.

[30]

Biletskiy Y., Ranganathan G. R., and Vorochek O., Identification and resolution of conflicts during ontological integration using rules, Expert Systems, vol. 27, no. 2, pp. 75–89, 2010.

DOI Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 29 September 2015

Accepted: 17 November 2015

Published: 11 August 2016

Issue date: August 2016

Copyright

Acknowledgements

This work was supported by the National Natural Science Foundation of China (No. 61404069) and the National High-Tech Research and Develpment (863) Program of China (No. 2015AA015403).