Efficient storage and retrieval in agent protocol libraries using subsumption hierarchies

Abstract

To be truly adaptive in dynamic environments, agents must be able to interact in ways that were not conceived at design time. One way to achieve this is to use executable protocol specifications, in which participants can share a protocol specification at runtime, and interact using the specified rules. In such a model, it is necessary that an agent can quickly and correctly locate a protocol that achieves its goals. Building on previous work, we present a method for characterising, storing, structuring, and searching protocol libraries. Libraries are represented using subsumption hierarchies, in which the vertices represent characterisations of protocols, and edges record a relation between two characterisations if one characterisation subsumes the other. This structure can be used to prevent searching of irrelevant parts of the library. An experimental analysis demonstrates that searching the library has an average-case time complexity of $\mathit{O}\mathrm{(}\mathit{n}\mathrm{)}$ , which is the same as a standard linear search, however, the measured time is significantly lower. Despite this, the cost of structuring the library has an average-case time complexity $\mathit{O}\mathrm{(}{\mathit{n}}^2\mathrm{)}$ , so the ratio of searches to insertions must be high to gain a benefit.