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.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.