Improving Performance of Agents by Activity Partitioning

dc.contributor.authorOzcan, Fatmaen_US
dc.contributor.authorSubrahmanian, V. S.en_US
dc.date.accessioned2004-05-31T23:22:55Z
dc.date.available2004-05-31T23:22:55Z
dc.date.created2002-10en_US
dc.date.issued2002-12-19en_US
dc.description.abstractThere 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-96en_US
dc.format.extent262226 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/1240
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-4416en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-2002-96en_US
dc.titleImproving Performance of Agents by Activity Partitioningen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
CS-TR-4416.pdf
Size:
256.08 KB
Format:
Adobe Portable Document Format