Hybrid Multiagent Collaboration for Time-Critical Tasks: A Mathematical Model and Heuristic Approach

Principal–assistant agent teams are often employed to solve tasks in multiagent collaboration systems. Assistant agents attached to the principal agents are more flexible for task execution and can assist them to complete tasks with complex constraints. However, how to employ principal–assistant age...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Yifeng Zhou, Kai Di, Haokun Xing
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	multi-agent collaboration time-critical tasks heuristic approach Industrial engineering. Management engineering T55.4-60.8 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/8de1950bc9be4520a9aeccca78b30f2b
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:8de1950bc9be4520a9aeccca78b30f2b
record_format	dspace
spelling	oai:doaj.org-article:8de1950bc9be4520a9aeccca78b30f2b2021-11-25T16:13:14ZHybrid Multiagent Collaboration for Time-Critical Tasks: A Mathematical Model and Heuristic Approach10.3390/a141103271999-4893https://doaj.org/article/8de1950bc9be4520a9aeccca78b30f2b2021-11-01T00:00:00Zhttps://www.mdpi.com/1999-4893/14/11/327https://doaj.org/toc/1999-4893Principal–assistant agent teams are often employed to solve tasks in multiagent collaboration systems. Assistant agents attached to the principal agents are more flexible for task execution and can assist them to complete tasks with complex constraints. However, how to employ principal–assistant agent teams to execute time-critical tasks considering the dependency between agents and the constraints among tasks is still a challenge so far. In this paper, we investigate the principal–assistant collaboration problem with deadlines, which is to allocate tasks to suitable principal–assistant teams and construct routes satisfying the temporal constraints. Two cases are considered in this paper, including single principal–assistant teams and multiple principal–assistant teams. The former is formally formulated in an arc-based integer linear programming model. We develop a hybrid combination algorithm for adapting larger scales, the idea of which is to find an optimal combination of partial routes generated by heuristic methods. The latter is defined in a path-based integer linear programming model, and a branch-and-price-based (BP-based) algorithm is proposed that introduces the number of assistant-accessible tasks surrounding a task to guide the route construction. Experimental results validate that the hybrid combination algorithm and the BP-based algorithm are superior to the benchmarks in terms of the number of served tasks and the running time.Yifeng ZhouKai DiHaokun XingMDPI AGarticlemulti-agent collaborationtime-critical tasksheuristic approachIndustrial engineering. Management engineeringT55.4-60.8Electronic computers. Computer scienceQA75.5-76.95ENAlgorithms, Vol 14, Iss 327, p 327 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	multi-agent collaboration time-critical tasks heuristic approach Industrial engineering. Management engineering T55.4-60.8 Electronic computers. Computer science QA75.5-76.95
spellingShingle	multi-agent collaboration time-critical tasks heuristic approach Industrial engineering. Management engineering T55.4-60.8 Electronic computers. Computer science QA75.5-76.95 Yifeng Zhou Kai Di Haokun Xing Hybrid Multiagent Collaboration for Time-Critical Tasks: A Mathematical Model and Heuristic Approach
description	Principal–assistant agent teams are often employed to solve tasks in multiagent collaboration systems. Assistant agents attached to the principal agents are more flexible for task execution and can assist them to complete tasks with complex constraints. However, how to employ principal–assistant agent teams to execute time-critical tasks considering the dependency between agents and the constraints among tasks is still a challenge so far. In this paper, we investigate the principal–assistant collaboration problem with deadlines, which is to allocate tasks to suitable principal–assistant teams and construct routes satisfying the temporal constraints. Two cases are considered in this paper, including single principal–assistant teams and multiple principal–assistant teams. The former is formally formulated in an arc-based integer linear programming model. We develop a hybrid combination algorithm for adapting larger scales, the idea of which is to find an optimal combination of partial routes generated by heuristic methods. The latter is defined in a path-based integer linear programming model, and a branch-and-price-based (BP-based) algorithm is proposed that introduces the number of assistant-accessible tasks surrounding a task to guide the route construction. Experimental results validate that the hybrid combination algorithm and the BP-based algorithm are superior to the benchmarks in terms of the number of served tasks and the running time.
format	article
author	Yifeng Zhou Kai Di Haokun Xing
author_facet	Yifeng Zhou Kai Di Haokun Xing
author_sort	Yifeng Zhou
title	Hybrid Multiagent Collaboration for Time-Critical Tasks: A Mathematical Model and Heuristic Approach
title_short	Hybrid Multiagent Collaboration for Time-Critical Tasks: A Mathematical Model and Heuristic Approach
title_full	Hybrid Multiagent Collaboration for Time-Critical Tasks: A Mathematical Model and Heuristic Approach
title_fullStr	Hybrid Multiagent Collaboration for Time-Critical Tasks: A Mathematical Model and Heuristic Approach
title_full_unstemmed	Hybrid Multiagent Collaboration for Time-Critical Tasks: A Mathematical Model and Heuristic Approach
title_sort	hybrid multiagent collaboration for time-critical tasks: a mathematical model and heuristic approach
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/8de1950bc9be4520a9aeccca78b30f2b
work_keys_str_mv	AT yifengzhou hybridmultiagentcollaborationfortimecriticaltasksamathematicalmodelandheuristicapproach AT kaidi hybridmultiagentcollaborationfortimecriticaltasksamathematicalmodelandheuristicapproach AT haokunxing hybridmultiagentcollaborationfortimecriticaltasksamathematicalmodelandheuristicapproach
_version_	1718413269268430848

Hybrid Multiagent Collaboration for Time-Critical Tasks: A Mathematical Model and Heuristic Approach

Ejemplares similares