Improving Performance of Agents by Activity Partitioning

Abstract

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