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. Tesis (Master), E.T.S. de Ingenieros Informáticos (UPM).

Descripción

Título: Clustering task assignment: an algorithm for time critical task assignment problems
Autor/es:
  • Meireles Valadares, Henrique
Director/es:
  • Swoboda, Nik
Tipo de Documento: Tesis (Master)
Título del máster: Inteligencia Artificial
Fecha: Julio 2017
Materias:
Escuela: E.T.S. de Ingenieros Informáticos (UPM)
Departamento: Inteligencia Artificial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (762kB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 47933
Identificador DC: http://oa.upm.es/47933/
Identificador OAI: oai:oa.upm.es:47933
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 02 Oct 2017 06:35
Ultima Modificación: 02 Oct 2017 06:35
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM