A fast first-cut protocol for agent coordination

This paper presents a fast probabilistic method for coordination based on Markov processes, provided the agents' goals and preferences are sufficiently compatible, and develops a model for coordinating the agents.

Abstract

This paper presents a fast probabilistic method for coordination based on Markov processes, provided the agents' goals and preferences are sufficiently compatible. By using Markov chains as the agents' inference mechanism, we are able to analyze convergence properties of agent interactions and to determine bounds on the expected times of convergence. Should the agents' goals or preferences not be compatible, they can detect this situation since coordination has not been achieved within a probabilistic time bound and the agents can then resort to a higher-level protocol. The application, used for motivating the discussion, is the scheduling of tasks, though the methodology may be applied to other domains. Using this domain, we develop a model for coordinating the agents and demonstrate its use in two examples.