Partitioning Activities for Agents

1 Introduction

The number of software agents deployed on the Internet has grown dramatically over the last few years. Major corporations have agents that continuously track events - some corporations use such agents to identify and exclude IP addresses that "scrape" data from their sites. Other corporations use agents that track some phenomenon (e.g. stock quotes) and take different actions for different clients who have registered parameters to be tracked and actions to be taken when certain

 Parts of this research were supported by Army Research Lab contract DAAL0197K0135, Army Research Office grant DAAD190010484 and DARPA/Rome Labs grant F306029910552

y Some proofs are omitted due to space limitations conditions are satisfied. Yet other corporations have agents that dynamically adjust plans (e.g. airlines) when events occur that cause those plans to go awry (e.g. a snowstorm).

In this paper, we focus on agents that have a high volume of activity. Our work is not going to help (very much) agents that have a relatively low amount of activity. If the agent can leverage common aspects across its diverse activities so as to reduce its load, its performance will improve greatly. Much work has been done on merging activities to minimize load - such work spans databases [Shim et al., 1994] and planning [Yang et al., 1992] - however the problem of merging such activities in an optimal way is known to be NP-complete, and hence these algorithms tend to perform well when 10 to 20 activities or fewer are being merged. However, agents tracking user interests for major news organizations like CNN have a huge number of users with registered interests, and an enormous number of changes occurring continuously. The same is true in the case of stock market agents.

In this paper, we develop partitioning techniques. Such techniques work as follows: when a large set S of activities (e.g. 1000) arewaiting tobe performed, thenourmethods partition S. Such a partition breaks S into disjoint components S 1 ;; : : :;; S n where S = S 1 [ : : : [ S n . The activities in a single component may then be merged by methods for merging activities, whether they are queries or plans using methods such as those of [Shim et al., 1994; Yang et al., 1992]. The cost of executing a component is just the cost of executing the activities in the component after merging activities. The cost of a partition is the sum of the costs of the components. The cost (after merging) of the activities in a partitionmay be estimated using techniques such as those in [Shim et al., 1994; Yang et al., 1992]. We would like to find a partition with minimal (estimated) cost.

Section 2 formalizes this problem and shows that finding a partition with minimal expected cost is NP-hard. Section 3 develops three algorithms to address this problem. The first algorithm is based on the A ? algorithm-we introduce a heuristic function and show that it is admissible [Nilsson, 1986]. Hence, this algorithm is guaranteed to find a partition with minimal cost. The second algorithm is a greedy algorithmwhich is not guaranteed to find a minimal cost partition. The third algorithm is a branch and bound algorithmwhich is also guaranteed to find an optimal cost solution. We have implemented all the algorithms. Section 4 describes the results of detailed experimentation with these algorithms. The experiments show that though the greedy algorithmfinds suboptimal solutions (typically 14% worse savings are realized when compared to the optimal savings realizable), it is able to handle 1800 concurrent activities in about 16 seconds, while the other two algorithms are unable to handle a large number of activities.

2 ProblemDefinition

An agent may engage in some space of activities. For example, the space of activities associated with a database agent may be all SQL queries. The space of activities associated with a planning agent may be the set of all possible planning problems. The space of activities associated with a CNN-style news agent may be the set of all interests that could possibly be associated with users. In the sequel, we use A to denote some set of activities drawn from such an activity space. A denotes activities that the agent has to perform, but has not yet performed.

Definition 1 (Partition) A partitionP of a set A of activities is a set fA 1 ;; A 2 ;; : : : ;; A n g where each A i is a non-empty subset of A and

Each A i is called a component of the partition P. When the first condition is replaced by A  A 1 [A 2 [ : : : [A n , P is called a subpartition.

A partition P of A splits a set of activities (to be done) into components. The activities in each component A i can be separately merged, perhaps using methods for query merging [Shim et al., 1994] or plan merging [Yang et al., 1992].

Definition 2 (Cost estimation function) A cost estimation function c takes a set of activities as input and returns a real number as output. c is required to satisfy at least the following axioms: (I) c(;;) = 0, (II) A 1  A 2 ! c(A 1 )  c(A 2 ).

Intuitively, c(A i ) denotes the estimated cost of executing the activities in A i after merging. When A i = fa i g is a singleton set, we will abuse notation and write c(a i ) instead of c(fa i g). We will also assume that the computation of c takes polynomial time. This is consistent with algorithms to estimate merged costs of sets of queries such as those of [Shim et al., 1994] as well as task merging methods [Yang et al., 1992]. In this paper, capitalized A's denote sets of activities. Lower case a's denote individual activities.

Problem 1 (Activity Partitioning Problem(APP)) A set A of activities, a cost estimation function c, and a partition P of A. Is it the case that there is no other partitionP 0 of A such that P A i 2P 0 c(A i ) < P A i 2P c(A i )?

We will prove below that APP is NP-hard by using the zeroone multiple knapsack problem (MKP) [Martello and Toth, 1987; Kellerer, 1999]. MKP can be stated as: Given a set N of n items, a set M of m knapsacks, profit and weight vectors p j and w j (1  j  n), and the capacity vector c i (1  i  m),

The decision problem version of MKP takes in addition to the above parameters, an assignment of items to knapsacks. It returns true if the assignment is an optimal solution to the search problem and false otherwise.

Theorem 1 The activity partitioning problem is NP-hard.

Proof Sketch: We will transform the MKP decision problem to APP. Let m be the number of components in P. Create three tables with the following database schemas: R m (knapsackid,capacity), R n (itemid, profit, weight) and R p (knapsackid, itemid). Insert an entry for each item into R n , and an entry for each knapsack into R m . Create an entry in R p for each item, knapsack pair present in the assignment . Then, for each item i, we create an SQL query q i given by:

select * from R n , R m , R p where R p .itemid = i and R n .itemid = R p .itemid and R m .knapsackid = R p .knapsackid and sum(R n .weight) < R m .capacity

It is easy to see that the tables and queries can be constructed in polynomial time. Therefore, when we solve this instance of APP, we will minimize the total cost of the queries. As a result, the sum of the profits will be maximized in the solution. Hence, APP is NP-hard. 2

3 Activity Partitioning Algorithms

Although, we can transform the MKP problem into APP, we cannot immediately use the available approximation algorithms [Martello and Toth, 1987; Kellerer, 1999] for theMKP problem. This is because in MKP the profits of items are constants, that is they do not vary with different knapsacks. However, in our case, the cost of a set of activities not only depends on which component it belongs to, but also depends on which other activities are present in the component. Hence, we will describe new algorithms based on different heuristics to solve the query partitioning problem. We will start with an A  -based algorithm, which is guaranteed to find an optimal solution.

3.1 A  -based Algorithm

To adapt the A  algorithm [Nilsson, 1986], we first need to define the state space, the cost function g and the heuristic function h.

Definition 3 (State) A state s is any subpartition of A. State s is a goal state if it is a partition of A. Finally, the start state s 0 = ;;.

Definition 4 (Functions g(n);; h(n) and f(n)) Suppose node n has state s = fA 1 ;;A 2 ;; : : : ;;A m g, and let

incr(a;; s) = minfminfc(a [ A i ) ; c(A i ) j 1  i  mg;; c(a)g. Then, g(n) and h(n) are defined as follows: g(n) = P m i=1 c(A i ) h(n) = minfincr(a;; s) j a 2 A; ( S m i=1 A i )g f(n) = g(n) +h(n)

where c is the cost estimation function.

Intuitively, g(n) says the cost of node n is the sum of the costs of the individual components. h(n) underestimates the cost to a goal state. This is done as follows. Consider each activity a that is in A but that is not in the subpartition associated with node n. Such an activity can either be placed in one of the components of node n or may be in a new component. Evaluate the cost of each of these alternatives and choose the minimal increase incr a in cost for adding a to node n. To obtain a partition, every activity that is not in the current subpartition must be added to node n eventually, so the cost of a solution must be at least greater than the current cost by incr a for all such activities a. This provides the rationale for h(n).

Our A  -basedalgorithmis given in Figure 1. The algorithm makes use of a function, pick(s;;A), that chooses an activity from A which has not been assigned to any of the components in state s.

If the while loop of the algorithm terminates, this implies that no goal state was reached and hence there is no solution. Note that if the heuristic function h used by the A  algorithm is admissible, then the algorithm is guaranteed to find the optimum solution [Nilsson, 1986]. The heuristic h is admissible iff h(n)  h  (n) where h  (n) is the lowest actual cost of getting to a goal node from node n. The following result shows that our heuristic is admissible.

Theorem 2 (Admissibility of h) For all nodes n, h(n)  h  (n). Hence, A  -based algorithm finds an optimal partition of A.

Theorem 3 The heuristic function h satisfies the monotone restriction.

The monotone restriction requires that for all n, h(n)  h(n 0 ) + (g(n 0 ) ; g(n)). Since, the h function satisfies the monotone restriction, the first goal state found by the A  - based algorithm is guaranteed to be the optimal solution.

3.2 Greedy Algorithm

Our greedy algorithm uses the notion of a cluster graph to solve the activity partitioning problem. Given a set A of activities, a cluster graph is a weighted graph whose vertices are disjoint sets of activities. Given any set A of activities, we may associate with it, a canonical cluster graph.

Definition 5 (Canonical Cluster Graph (CCG)) A cluster graph for a set A of activities is an undirected weighted graph where:

1. V = ffa i g j a i 2 Ag, 2. E = f(fa i g;; fa j g) j a i ;; a j 2 A and c(a i ) + c(a j ) ; c(fa i ;; a j g) > 0g, 3. w(fa i g;; fa j g) = c(a i ) + c(a j ) ; c(fa i ;; a j g)

Intuitively, when we have an edge between activities a i ;; a j then this means that there is some savings to be derived by

A  -based(A) /* Input: A (a set of activities) */ /* Output: P if one exists, NIL otherwise */ OPEN := ;; forall a i 2 A do n i :state := ffa i gg compute g(n i ) and h(n i ) insert n i into OPEN sort OPEN in increasing order of f(n i ) while (OPEN 6= ;;) do n := OPEN.head delete n from OPEN s := n.state if s is a goal state then Return(s) else /* expand and generate children */ a j := pick(s, A) forall A i 2 s do /* insert a j into A i */ s 0 := fA 1 ;; : : : ;;A i;1 ;;A i [ fa j g;; : : : ;;A m g create a new node n 0 n 0 .state = s 0 compute g(n 0 ) and h(n 0 ) insert n 0 into OPEN /* also create a new component with a j */ create a new node n 0 n 0 .state := fA 1 ;; : : : ;; A m ;; fa j gg compute g(n 0 ) and h(n 0 ) insert n 0 into OPEN end(while) Return (NIL) End-Algorithm

merging the two activities together. The edge label, w(a i ;; a j ) denotes that saving. (Again, we abuse notation and write e(a i ;; a j ) instead of e(fa i g;; fa j g) and w(a i ;; a j ) instead of w(fa i g;; fa j g). )

The greedy algorithm is shown in Figure 2. Intuitively, Greedy tries to build a partition iteratively. In each iteration, it finds an edge with highest weight (savings) in the cluster graph and deletes it. If more than one such edge exists, one is arbitrarily picked. It examines the two activities associated with that edge and checks to see if either of those activities already occur in a partition. There are four cases to check depending on whether one, both or neither activities occur in an existing partition. If both a i ;; a j occur in existing different components, then it may be possible to move one of them from one component into the other. This should be done only if it yields savings. If one of a i ;; a j is in an existing component but not the other, then the other can be placed in the same component. It is easy to see that the number of iterations of the loop of this algorithm is O(card(A) 2 ). Each execution of the loop may take O(card(P)) time in the worst case to check if a i ;; a j occur in a component. It is therefore easy to see that Greedy is certainly polynomial in the size of the input A as long as the cost estimation function c runs in polynomial time.

Greedy(CCG ) /* Input: CCG (canonical cluster graph of A) */ /* Output: P */ P := ;; n := 0 while (9e 2 CCG) do e := (a i ;; a j ), s.t. w(e) is maximum in CCG delete e from CCG if (9A l 2 P s:t: a i 2 A l ) then if (9A k 6= A l 2 P s:t: a j 2 A k ) then if (c(A l [fa j g)+c(A k ;fa j g) < c(A l )+c(A k )) then delete a j fromA k insert a j into A l if (c(A k [ fa i g) + c(A l ; fa i g) < c(A l ) + c(A k )) then delete a i fromA l insert a i into A k else /* 6 9A k s:t: a j 2 A k */ insert a j into A l else /* 6 9A l s:t: a i 2 A l */ if (9A k 2 P s:t: a j 2 A k ) then insert a i into A k else n := n + 1 A n := fa i ;; a j g P := P [ fA n g end(while) Return (P) End-Algorithm

3.3 Branch and Bound Algorithm

In this section, we describe a branch and bound algorithm, which is similar to the A  -based algorithm, but uses a different search strategy.

The BAB algorithm maintains nodes n which having the following fields: state (as defined in Def. 3) , gval and uval defined below. gval specifies the value g(n) (cf. Def. 4), while uval contains u(n) which is defined below.

Definition 6 Let node n have state s = fA 1 ;; A 2 ;; : : : ;; A m g, then u(n) = P a i 2A 0 c(a i ). where A 0 = A ; S m i=1 A i , and c is the cost estimation function.

Intuitively, g(n)+u(n) overestimates the cost of the minimal cost solution reachable from node n. 1 BAB (Figure 3) also starts out with an empty partition and uses the same expansion strategy as the A  -based algorithm. The OPEN list which is organized in ascending order of g(n) + u(n) and the BAB algorithmalways chooses the first node in OPEN for expansion. If the g value of this first node exceeds that of the best solution

1 Contrast this with h(n) presented earlier that represents an underestimate.

Branch&Bound(A) /* Input: A(setofactivities)) /* Output: P */ create a new node n n.state := fg n:uval := P a i 2A c(a i ) n:gval := 0 insert n into OPEN bestV alue := n:gval + n:uval bestPartition := n:state while (OPEN 6= ;;) do n := OPEN.head delete n from OPEN if (n:gval < bestV alue) then if (n:gval + n:uval < bestV alue) then bestV alue := n:gval + n:uval bestPartition := n.state if (n is not a goal state) then /* expand and generate children */ a j := pick(s, A) forall A i 2 n:state do /* insert a j into A i */ s 0 := fA 1 ;; : : : ;;A i;1 ;;A i [ fa j g;; : : : ;;A m g create a new node n 0 n 0 .state = s 0 compute n 0 :gval and n 0 :uval insert n 0 into OPEN /* also create a new component with a j */ create a new node n 0 n 0 .state := fA 1 ;; : : : ;; A m ;; fa j gg compute n 0 ;; gval and n 0 :uval insert n 0 into OPEN end(while) Return(bestP artition) End-Algorithm

found so far, then we do not need to expand this node. If however, the g-value is less than that of the best solution found so far, then there is a chance that this node leads to a better solution and hence we expand it (unless it is a solution in which case we discard it).

Theorem 4 BAB(A) finds an optimal partition of A.

4 Implementation/Experimental Results

We have implemented all three algorithms described in this paper in C++ on a Sun Ultra1 machine with 320 MB memory running Solaris 2.6. There is a total of 1600 lines of code for our implementation and experiments. We ran two sets of experiments - one to determine which algorithm was fastest, and how many concurrent activities could be handled, and another to determine how the algorithms performed in terms of savings generated by them.

Experiment 1: We first fixed an overlap probability. Given a pair of activities from A, the overlap probability gives the probability that the pair will overlap. We then fixed an overlap degree which measures the savings obtained when two activities overlap. Suppose we know activities a 1 ;; a 2 overlap. The overlap degree in this case is c(a 1 )+c(a 2 );c(fa 1 ;;a 2 g) min(c(a 1 );;c(a 2 )) . Intuitively, the larger the overlap degree, the greater the savings obtained by merging two activities.

Once an overlap degree and overlap probability are fixed, we automatically generated sets of activities that have that overlap degree (on the average) and that overlap probability. We then ran all three algorithms on the data. For each number of activities, we took an average over 10 sets of data. Table 1 shows the results of experiments when overlap probability varies between 0:4 and 0:6 and when the overlap degree is 0:6 ( 1).

It turns out that both A  -basedand BAB ran out of memory when the number of activities exceeded about 10. The reason for this is that the OPEN list quickly grows overwhelmingly large. Hence, the above table has only 10 activities. In contrast, Greedy did not run out of space. In order to see how well Greedy could do, we continued to run experiments by increasing the number of activities. Figure 4 shows that Greedy scales well and can handle 1800 concurrent activities in about 16 seconds.

Experiment 2: As both A  -basedand BAB compute optimal solutions, but Greedy does not always do so, we wanted to see how much "worse" the solution produced by Greedy was compared to the optimal solution. When we have a set A of activities, and a partition P of A, the savings realized by P is given by ( a2A c(a)) ; ( A i 2P c(A i )).

Figure 5 shows that in our experiments, optimal solution produced by A  -based(whose savings equals that produced by BAB) yielded a saving of 21-34%, while Greedy yields savings of 17-23%.

Although we could not get the optimal solution after 10 activities, we still ran the Greedy algorithm up to 1800 activities to see the quality of partitions it produced. Figure 6 shows the results. As seen from the graph, the performance of the Greedy algorithmdid not degrade, and stayed about the same as we increased the number of activities in the input sets.

Both A  -basedand BAB are unable to perform at all when there are more than 10-20 concurrent activities. On larger sets of activities, they both quickly run out of memory - in contrast, Greedy scales up very effectively when many activities occur. In a few seconds, it can partition over a thousand concurrent activities, and produce a solution that is at most 40% worse than the optimal.

5 RelatedWork and Conclusions

Over the last few years, there has been tremendous interest in collaborative information agents. Techniques from this fertile field have found ample applications in online news sources that monitor user interests and changing news events and create personalized news reports. They have also been used extensively to make trades in financial markets for different users as stock conditions change. They have been used to dynamically bid for a variety of clients in online auctions [Schwartz and Kraus, 1997]. There are many impressive agent systems - these include Internet Softbot [Etzioni and Weld, 1994], Retzina [Decker et al., 1997], Infosleuth [Bayardo et al., 1997], SIMS [Arens et al., 1993] and many others.

There have been important efforts to optimize the performance of such agents. For instance, [Adali et al., 1996; Ashish et al., 1999] show how to use intelligent caching methods to improve the performance of systems that access different data sources.

In both planning and databases, researchers have noticed that when a server receives numerous requests, then it may make sense to leverage commonalities across those requests instead of serially processing the requests. This is accomplishedbymerging (planning requests or query requests). Important advances in this field were made by [Yang et al., 1992] and [Shim et al., 1994]. However, in both cases, the problem of merging plans and merging queries to minimize expected cost of execution is NP-hard and hence, these methods worked well when the numbers of activities (planning or querying) were limited. [Shim et al., 1994] conducted experiments with 10 concurrent queries, while [Yang et al., 1992] handled up to 18 concurrent planning problems.

In this paper, we build on these important advances. Specifically, we start by assuming the existence of some way of merging k activities or fewer. Thus, if the activities are database queries, then k may be set to 10 and the [Shim et al., 1994] algorithmmay be used. Alternatively, if the activities are planning problems, the perhaps one could set k to 18 and use the methods of [Yang et al., 1992] to merge plans. Now consider the situation where such a database or planning agent has hundreds or thousands of activities it is currently engaged in. Such a set of activities may be partitioned into components of size k (or less) so that each component's activities can be merged using an aforementioned merging algorithm such as [Yang et al., 1992; Shim et al., 1994]. If the sum of the costs of the individual components of the partition is minimized, then we would have an optimal way of executing such a large set of activities.

Unfortunately, this problem- which we call the activity partitioning problem (APP) in this paper - is shown to be NP-hard. As a consequence, there is no exact algorithm to solve this problem in polynomial time (unless P = NP which is widely believed to not be the case). We propose two exact algorithms, A  -basedand BAB, to solve this problem. As these algorithms compute exact solutions, they are easily seen to take exponential time. As expected from earlier results of [Yang et al., 1992; Shim et al., 1994], these algorithms stop performing well when over 10-20 activities are being merged. To alleviate this problem, we propose a polynomial algorithm called Greedy which exhibits the following nice properties. First, it can (in a matter of seconds) partition a set of thousands of activities which reflects an order of magnitude improvement over A  -basedand BAB. Second, the partitions it computes turn out to have at most 14% worse savings than those computed by A  -basedand BAB. As a consequence, we believe that Greedy is superior to both A  -basedand BAB for real world problems.