Tech Reports

ULCS-10-002

Efficient Storage and Retrieval in Protocol Libraries using Subsumption Hierarchies

Tim Miller and Peter McBurney

Abstract

For an agent to intelligently use specifications of executable protocols, it is necessary that the agent can quickly and correctly locate a protocol that achieves its goals. Techniques such as model checking or theorem proving can be used to assess whether a protocol achieves a goal; however, for resource-bounded agents, this approach may be inefficient. Building on previous work on characterising and matching protocols, we present a method for structuring and searching protocol libraries using subsumption hierarchies. These hierarchies are directed graphs, in which the vertices are characterisations of protocols, and edges record a relation between two characterisations if one characterisation subsumes the other; that is, the characterised protocol achieves all of the same outcomes. An experimental analysis demonstrates that this approach is more efficient for anything other than the smallest of protocol libraries.

[Full Paper]