Improving Performance of Agents by Activity Partitioning
Publication or External Link
There is growing interest in software agents that provide a variety of
services to humans, other agents, and third party software applications.
Some of these agents are engaged in hundreds of activities
at any given time point. In such cases, agents may try
to examine a set A of activities and leverage commonalities between them
in order to reduce their load. We call this activity merging.
Unfortunately, in most application domains, activity merging turns out to
be NP-complete. Thus, for each application domain, there is an integer
k (which varies from domain to domain) such that activity merging can
merge up to k activities while satisfying the application's performance
expectations. In this paper, we consider the problem of what to do
when the set of activities exceeds k. Our approach partitions A into disjoint sets A1 union A2 union ... union An such that each Ai contains at most k activities in it (thus the activities in each Ai can be merged using a merging algorithm). When creating such partitions, we would like to ensure that the activities inside each Ai share a lot of commonality, so that merging yields a lot of savings. In this paper, we propose two optimal algorithms (based on the A* algorithm and the branch and bound paradigm), as well as numerous greedy algorithms to solve the problem. We have implemented these algorithms and conducted detailed experiments. The results point out which algorithms are most appropriate for scaling agent performance. UMIACS-TR-2002-96