An asynchronous algorithm to improve scheduling quality in the multiagent simple temporal problem

Abstract

In order to schedule an activity that depends on other people, we very often end up wasting precious time trying to find compatible times and evaluating if they are accepted by all involved. Even though modeling and solving multiagent scheduling problems seem completely understood and several algorithms can be found in the literature, one limitation still stands up: How to find a compatible time slot for an activity shared by many users without requiring the users themselves to spend time going through their calendar and choosing time slots until everybody agrees. The main contribution of this work is an algorithm called Asynchronous Time Finder (ATF) based on the Asynchronous Backtracking (ABT) that enables applications to find compatible times when scheduling shared activities among several users while requiring minimal user interaction. This dissertation starts by revisiting the Simple Temporal Problem (STP) and its multiagent version (MaSTP), it then shows how they can be used to solve the problem of managing agendas and then finally it presents the ATF giving an experimental evaluation and the analysis of its complexity.

Ao tentar agendar uma atividade que dependa da presença de outras pessoas, geralmente acabamos desperdiçando tempo precioso avaliando os possíveis horários e verificando se os mesmos são aceitos por todos envolvidos. Embora a modelagem e a resolução do problema de agendamento multiagente pareçam estar completamente entendidas e ainda diversos algoritmos possam ser encontrados na literatura, uma questão ainda existe: Como definir horários compatíveis para uma atividade compartilhada sem que os usuários tenham que manualmente escolher horários livres de seus calendários até que todos envolvidos aceitem um horário. A principal contribuição é um algoritmo chamado Descobridor Asíncrono de Horários (ATF) baseado no Rastreamento Asíncrono (ABT) que permite que aplicações encontrem horários compatíveis para atividades compartilhadas requerendo mínima intervenção manual dos usuários. Esta dissertação revisita o Problema Temporal Simples (STP) e a sua versão multiagente (MaSTP), demonstra como eles podem ser utilizados para resolver o problema de agentamentos e ao final apresenta o ATF, a avaliação experimental e a análise de complexidade.