M.Sc Thesis

M.Sc StudentGoldin Alexander
SubjectGeometric Message-Filtering Protocols for Distributed Multi-
Agent Environments
DepartmentDepartment of Computer Science
Supervisor PROF. Chaim Craig Gotsman


Message filtering is important for distributed multi-agent systems, where a large number of dynamic agents participate in the system activity, but a typical agent is interested in only a very small dynamic subset of the other agents. The agent must be constantly updated on the status of this subset, and this is achieved by message passing between relevant agents. Message filtering is required to reduce the communications load on the system, which may become prohibitive if each agent must communicate with all others in order to obtain the information it needs.

This paper deals with the case of multi-agent real and virtual environments, where each agent has a location in 2D space, and is interested in a small subset of the other agents, either those within a fixed range - as treated by previous authors, or k other agents nearest to it - treated here for the first time. Furthermore, we consider the case of a decentralized system, where no central server(s) are available to coordinate between the agents. The main challenge here is to design protocols which significantly filter all messages, yet enable each agent to maintain a consistent image of the other agents in which it is interested. These protocols are useful in multi-agent games, simulations and other virtual environments in which the geometric relationships between agents are important. They could also be useful for mobile-commerce cellular phone-based gaming applications, and military applications.