Tácticas mixtas para la negociación automática de múltiples servicios con información incompleta en entornos multiagente. Aplicación a problemas de gestión de tráfico.

Abstract

La creciente importancia del fenómeno de la interacción entre sistemas informáticos ha modificado la forma tradicional de analizarlos y programarlos, puesto que éstos han pasado de ser considerados como sistemas aislados a ser fundamentalmente concebidos como sistemas distribuidos. La necesidad de interaccionar entre los componentes del sistema es cada vez más importante para poder realizar o resolver tareas conjuntas que de forma individual serían muy costosas o incluso imposibles de desarrollar (por ejemplo, porque los recursos necesarios para resolver una tarea estén distribuidos entre distintos componentes del sistema). No obstante, los sistemas informáticos, que deben alcanzar sus propios objetivos operacionales, no siempre se encuentran dispuestos a compartir o ceder los recursos necesarios para desarrollar las acciones que otros sistemas informáticos solicitan, puesto que pueden surgir conflictos de interés.<br/><br/>Uno de los mecanismos para la resolución de conflictos de interés es la negociación automática. Esta se centra en proveer un marco de negociación que permita la interacción de los participantes. Este marco de negociación, que debe ser conocido y aceptado por todos los participantes, define las normas que describen la negociación: cuál es el tiempo máximo que puede durar la negociación, cuál es el contenido de las ofertas y que ocurre si no se alcanza un acuerdo. La utilización de protocolos como mecanismo de negociación automáticos permite definir y especificar completamente todos los componentes necesarios. Sin embargo, esta definición presenta problemas a la hora de definir formalmente las características específicas del protocolo y del dominio donde se vaya a aplicar.<br/><br/>El trabajo que se presenta en esta tesis ha consistido en el desarrollo de un protocolo de negociación que permita a los participantes alcanzar acuerdos óptimos para la prestación de servicios coordinados en una única negociación. El protocolo presentado aborda los siguientes aspectos: <br/>· El resultado de la negociación puede ser una combinación de elementos que aporten una solución a un problema dado.<br/>· La relación existente entre los elementos que forman parte de la negociación.<br/>· Cómo afecta a la negociación la implementación secuencial, es decir, el acuerdo sobre un elemento implica que éste pasa a desarrollarse, lo que afecta al escenario de negociación y consecuentemente a las estrategias de negociación sobre el resto de elementos.<br/>· La implementación de tácticas mixtas que eviten que el acuerdo sobre un elemento, que en un instante t podría ser considerado como óptimo, pueda no serlo cuando se alcance un acuerdo sobre otro elemento en un instante t' posterior.<br/>· La utilización de creencias, ya que el entorno donde se desarrolla el protocolo es un entorno con información incompleta, es decir, un participante no conoce los rangos de acuerdos del otro participante. <br/><br/>Este problema, negociación sobre múltiples elementos relacionados, se encuentra presente en multitud de dominios de aplicación. Por ejemplo, en la provisión de servicios: provisión de ancho de banda, logística de recursos distribuida, o como en el caso en el que el protocolo se ha adaptado: la gestión del tráfico interurbano.<br/><br/>El protocolo presentado se ha adaptado a un entorno real, en concreto, a la determinación automática de itinerarios alternativos como solución cuando se producen incidentes en la circulación en una red viaria. Por último, se ha diseñado e implementado un sistema multiagente para la gestión del tráfico interurbano que implementa el protocolo de negociación propuesto.

The interaction between system components has become an important requirement to develop or solve common tasks which individual components are unable to reach. However, computer systems, that have to reach their operational objectives, are not usually disposed to share or yield the resources that other system request. Thus conflict of interest appears.<br/><br/>One of the mechanisms to solve conflict of interest is automatic negotiation. It is focused on providing a negotiation framework. This framework allows the interaction between participants (or players). Nevertheless, this framework presents problems when we have to define formally the specific characteristic of the protocol and the application domain.<br/><br/>The work developed in this thesis is focused on the development of a new negotiation protocol. This protocol allows players to reach optimal agreements to share and use services co-ordinately. The protocol has the next characteristics: a) it is played in a incomplete information environment; b) there are several elements involved in the negotiation and they are related; c) the result negotiation could be a combination of elements providing a solution; d) the implementation of elements, once they are agreed, is sequential and e) the generation of offers and counter offers are developed using mixed tactics.<br/><br/>The protocol developed has been adapted to be used in a real environment: the non urban road traffic domain. The protocol has been developed to automatically define alternative itineraries as solution to a road incident. A multiagent system has been designed and implemented to traffic management. This MAS prototype allows to monitors weather problems and to negotiate, using the proposed protocol, alternatives itineraries when weather problems (snow, ice, etc) appear in the road network.