Clustering task assignment: an algorithm for time critical task assignment problems

Meireles Valadares, Henrique (2017). Clustering task assignment: an algorithm for time critical task assignment problems. Thesis (Master thesis), E.T.S. de Ingenieros Informáticos (UPM).

Description

Title: Clustering task assignment: an algorithm for time critical task assignment problems
Author/s:
  • Meireles Valadares, Henrique
Contributor/s:
  • Swoboda, Nik
Item Type: Thesis (Master thesis)
Masters title: Inteligencia Artificial
Date: July 2017
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (762kB) | Preview

Abstract

Time critical task assignment problems are frequently found in operating systems and flight control applications. Tasks have to be assigned in less than one second, otherwise operating systems don’t work properly or catastrophes could happen. For instance, in a flight control real time application, one wrong task assignment decision could result in an airplane accident. To make things worse, these crucial decisions have to be taken in milliseconds, therefore, the efficiency of these kind of algorithm has to be optimized. In order to address time critical task assignment problems, the Clustering Task Assignment Approach CTA is proposed. The idea is to cluster the groups into tasks with the best candidates(free agents) according to a heuristic. In other words, the place where agents needs to reach(task facility) is designed as a cluster centroid and the agents inside each cluster are the candidates to execute each task. Agents compete with each other by means of an objective function in order to define the assigned task. This heuristic is capable of dramatically reduce the number of calls to the score function, thus assigning groups of agents efficiently to groups of tasks. The algorithm is compared against the well known Contract Net Protocol(CNET) and outperform it in terms of speed reducing the number of calls to the score function in 400%, the solution quality is 28% better as well. This algorithm was designed to work with time critical applications in which agents have to move from one place to another and when the score function is very costly. However results show that it can also be applied to time non critical applications because the solution quality found are outstanding in comparison to other approaches.

More information

Item ID: 47933
DC Identifier: http://oa.upm.es/47933/
OAI Identifier: oai:oa.upm.es:47933
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 02 Oct 2017 06:35
Last Modified: 02 Oct 2017 06:35
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM