Minimizing Response Times in Real Time Planning and Search

1. Introduction

As the application of AI systems evolves from an art to an engineering science, we can expect more challenging applications to be addressed. Some of the most challenging and interesting applica­ tions can be found in real-time domains. An AI system operating in a real-time situation will typically need to respond within a certain deadline, or have optimal response times (for planning and execu­ tion). For example in managing defensive weapons against nuclear missiles, the system has to respond within a few seconds or minutes[l] . On the other hand, in credit approval systems[2], optimal response times are desired, but there are no hard deadlines. The deadline problem is hard and many such problems (e.g., scheduling with deadlines) are NP-complete [3] and guaranteeing an optimal solution within a fixed deadline is often not possible. The optimal response time is required in the case wherein the plan execu­ tion time is comparable to planning time. The response time is the sum of planning time and execution time, and the application has no strict short deadlines. As shown in figure 1, in general, the optimal response time is not achieved by solely minimizing execution time, as then planning time increases to offset the gains.

Currently, ad hoc techniques are used for making a system pro­ duce a real-time response , and these methods suffer from poor extensibility, brittleness and a lack of a formal proof of "reliable real time perforrnance"[4]. Traditional search algorithms like depth first search, breadth first search and depth first iterative deepening [ 5], A·[6] and IDA·[S] are useful with small search spaces and large The above mentioned real time algorithms essentially deal with the problem of deadlines in real time systems (see classification in figure 1). They ignore the execution cost of any solution and essen­ tially spend all available time (the deadline) searching. This may n~t be realistic in cases where executing the solution takes some appreci­ able amount of time and it is no longer possible to ignore iL Our research concerns the other class of real-time applications where response time is importanL

To optimize the response time, a real time system bas to con­ sider the tradeoff between execution and planning costs. A greater planning cost may possibly lead to a lower execution cost, but the extra time spent planning may also lead to a potential increase in the response time as shown in Fig.l. Thus it is crucial that a real time system be able to decide upon the appropriate moment to stop

planning and start executing the best solution plan obtained till then. Our focus in this paper is to formalize the trade-off between planning cost -and execution cost in such real time systems and prove bounds on the optimality of the results obtained. We present a search algo­ rithm for providing near optimal response times. We provide correctness proofs and bounds on the optimality of the response time performance obtained. We describe an implementation of our algo­ rithm in a real-time application of query planning [13], which sub­ stantiates our results experimentally. Finally we explore the combi­ nation of our algorithm with A ·.

The structure of this paper is as follows. Section 2 describes our search algorithm, correctness proofs and other results. Section 3 and 4 describes the application of our proposed algorithm in two example domains: query optimization (planning) and the A* heuris­ tic search algorithm[14] . Finally, section 5 summarizes our contri­ butions and lists directions for future research.

2. Optimizing Response Time

For a real time system with optimal response time requirement, the total time for responding to a situation can be conceptually modeled as consisting of the time for planning a path to solution, and the time for actually executing the chosen solution path. In some situations we need to generalize the planning and execution times to planning and execution costs or utilities [10,11] to account for vari­ ous other aspects of the problem domain.

For simplicity, we will adopt to the model given by Korf, and consider costs as equivalent to the-times required for planning and execution. In this context, the process of planning a response can be modeled as a search among different possible responses or actions for the best possible action. The space of different possible actions can be very large, and as the sequence of search for finding the best possible action is (usually) not known apriori, the process of plan­ ning (to find the best action) can take prohibitively large amounts of time, so as to thwart the desired optimality of the response time of the real time system. Thus it is important to devise algorithms which not only allow a real time system to suitably terminate the planning phase, but also prove some bounds on how well it bas done as com­ pared to the optimal response time.

2.1. NORA (Near Optimal Response-time Algorithm)

In this sub-section, we shall describe NORA, a simple and intuitively appealing algorithm for providing near optimal response times in real time systems that satisfies the above-mentioned con­ cerns. Blind exhaustive searches like BFS or DFS are generally applicable to limited domains. Most heuristic search algorithms require the ability to recognize the goal node (i.e., the best action). This is not always possible, (e.g., recognizing the cheapest query execution plan in query optimization[15] ) and one needs other ter­ mination criteria to stop the search.

Given a search algorithm, a real time system bas to make a cru­ cial decision of determining the time to stop searching so as to pro­ vide a near optimal response time. This problem is simplified for small search spaces (where it may be possible to search the entire search space quickly) or when it is possible to recognize the best action (so that the search can be stopped as soon as the best action is found). In general it may not be possible to characterize apriori the best action and even if it is possible to characterize it for recognition, reaching it in the many search traversal algorithms may require prohibitively large time. Thus a real time system must have some algorithm for appropriately balancing the planning and execution costs.

The basic idea of NORA is simple and intuitive. Conceptually, the search space can be thought of as a set of nOdes with inter­ connecting arcs. Each node represents one possible action (or set of actions) and bas an associated execution cost. A search traversal algorithm specifies the order of traversal of these nodes and there are costs associated with this traversal. These costs include the cost of actually moving from node to node and any associated computation costs at each node (for example, to estimate the execution cost of the actions at the node). The chosen search traversal algorithm goes from node to node in some order to find the node with the best action (or here for simplicity, the least action time). At each node, NORA keeps track of two metrics:

1. Planning cost so far: this represents all associated costs of plan­ ning so far and includes all cost of traversing the search space.
2. Least execution cost so far: this is the node with the least exe­ cution cost so far.

The search space traversal is terminated whenever the planning cost exceeds some fraction of the best execution cost fo1md so far, i.e., when the following condition is satisfied:

where A. defines the fraction. As shown in the next sub-section, this simple stopping criterion allows us to achieve a near-optimal response time (when the search is terminated with the above condi­ tion satisfied) satisfying the following bound:

This is for the general case, in which we are unable to recognize apriori the best action. In cases, where it is possible to recognize the best action, a direct comparison can be made for a crisper bound (see section 3.2). As evident, the choice of A. is crucial and at the end of the next sub-section, we describe bow we can obtain heuristics for the choice of an appropriate A.. We further note that the bound holds for any given search space traversal ordering (e.g. A*).

2.2. Correctness of NORA

In this section, we provide a correctness proof for NORA. Some notation used in the proof below is introduced in Table 2.1. We structure the search space as a interconnected set of nodes Q;, each node representing a possible action (or set of actions).

Correctness Theorem for NORA: If the following search ter­ minating criterion is used,

the following upper bound on RT(i) is obtained,

Proof: Supposing the search terminates after examining Q; · There are following two cases,

. A positive quantity ~ is added to the numerator to make the equahty hold. It satisfies the condition 0 s ~ s Opt cost in current step.

Combining the results of the cases above we have,

The bound provided by the above theorem is not very tight, and the termination criterion performs much better in practice. This was observed when we ran an experiment, details of which are discussed elsewhere[ 16] .

Corollary 1: If the planning is the compile-and-store type, and is expected to be executed a times, the above bound changes to,

Proof' Identical to the above theorem.

Heuristics For Choice Of A.

The choice of A. depends on the size of the search space, and the time available for planning. For a small search space, we would usu­ ally expect Case [a] to occur when the search terminates, i.e. ~ E SP(i). Thus,

Small Space=> Case [a]

=> choose large A. for tight bound

=> less planning is good for response time

For a large search space, we would usually expect Case [b] to occur when the search terminates, i.e. Q.,, r1. SP(i). Thus,

Large Space => Case [b]

=> choose small A for tight bound

=> more planning is good for response time

Rule of Thumb for choosing A.: Above analysis shows that the thumb-rule is to choose a large A. .if the search space is small and vice versa. It is not a certain rule because of the approximate implications (=>)shown above.

3. Query Optimization: A Real-time Application

We implemented our algorithm for optimizing the response time of query optimizer for data-bases. Most databases are on-line and users access desired information via a query, represented in a suitable query language. Queries involve operations like join, select, and project, and can be answered by executing several different execution-plans each with different execution-times. The query optimizer generates and examines many execution plans to choose the one with the least execution-time. The planning time increases exponentially, as the optimizer expands its search of possible execu­ tion plans.

The optimization cost can be comparable to the cost of query execution. The tradeoff between optimization time and the cost of query execution becomes a major issue in optimizing the total cost of query processing. We further note that it is not possible to apriori specify the query with the least execution cost, while traversing the search space.

We tested NORA for semantic query optimization for a ship­ ping database of six relations. The database schema, the relation sizes, semantic integrity constraints and the various indexes available are reported elsewhere[16, 17]. The first step in our experiment was to generate the search space. The NORA algorithm was simulated on the search space. The stopping rule of NORA terminates the search when the following condition becomes true : 't(i) > t(i) 1 A The stopping rule was examined for the values A.= 2, I, and 112. The results are presented in Table 3 .1 .

:t This aaswnptioo is justified by many planners, e.g. query optimizers. t Irr(i) = 't(i) + at (i ), and repreoents an intcgralcd cost.

The result can be verified for all the three values of A.. Here we shall illustrate the validation for A.= 1. The search stops after itera­ tion 3, since the stopping criterion of NORA evaluates to (163)(1) + (5X5) > 127.0 => 188 > 127.0, which is true. The optimiza­ tion cost and best execution cost estimate are,

We see that stopping rule is quite effective. Especially notable is the fact that even though we attempt to minimize a weighted sum of 't(i) and t(i), and not t(i) alone, the value of t(i) obtained is actu­ ally quite close to the minimum. We believe a more careful analysis of the algorithm would help us get a better bound.

4. NORA and Heuristic Search Algorithm A·

A* :j:[18) is probably the best known heuristic search algorithm for finding a solution path from an initial stan node to a goal node, when the execution costs are negligible. It finds an optimal solution path in optimal planning time if the heuristic function, h(n), is mono­ tone and admissible, i.e., it satisfies triangle inequality and it never overestimates the actual cost of reaching a goal node. A* ignores execution time and essentially concentrates on minimizing the searching time instead on response time. Furthermore A* terminates by recognizing the goal node. Thus the problem definition must pro­ vide adequate characterization of the goal node, so that it can be recognized easily.

To apply NORA formalism to A* we generalize A* in two respects: (a) introduce the notion of execution time, (b) relax the assumption that the search algorithm can recognize the goal node during the search process, even though one can define heuristic func­ tions. We use a more general stopping criteria for search termina­ tion.

To introduce execution costs in A*, we proceed as follows. Associated with any node n, in the search space, Jet g. (n) represent the execution time for executing the partial solution (corresponding to the path from the start node to node n) found so far and let h. (n) represent the heuristic estimate of the cost of execution from the par­ tial solution to a goal node (corresponding to a path from node n to a goal node). Note that g,(n) and h,(n) are distinct from the conven­ tional g and h functions of A*. While g(n) estimates the cost of expanding the search tree from the start node to the node n and thus contributes to the planning costs for finding a solution path from the initial state to the partial solution state specified by node n, g. (n) estimates the cost of actually executing that partial solution path in the real world. Similarly, while h(n) estimates the planning cost of further expanding the search tree from node n to a goal node, h, (n ) estimates the actual cost of execution while trying to reach a goal from the partial solution state specified by node n. These functions can be computed as it is possible to apriori precisely characterize the goal state.

; a best-first search of the search space, where the merit of a node, f(n) is the sum of the actual cost, g(n), of reaching that node, n, from the start node, S, and the estimated cost, h(n), of reaching a goal node, G, from that node.

While trying to optimize response times in real time planning and search using A*, it is possible that we may decide to terminate the search (based on a chosen search stopping criterion, e.g., as specified by NORA) at some node i, before reaching a goal node, G. Assume that stopping at some node i, (i ¢ goal node), forces us to incur some penalty for execution in real time (caused by the distance from the partial solution state, node i, to a goal node), and Jet it be represented by h, (i). We assume that h, (i) is proportional to the dis­ tance of the node i from a goal node and that it monotonically decreases as i approaches a goal node.

4.1. Applying Stopping Criterion of NORA

Let us assume that the A* heuristic evaluation function, h, satisfies the monotone t restriction and is admissible. Under these conditions, A* never expands any nodes other than those that lie on the optimal solution path and thus at any node, i, (i ¢goal node), on the optimal solution path, the total planning cost so far is given by g(i) and the best estimate of the execution cost is given by the sum of g. (i) and h. (i). Let G represent the goal node, and thus the planning cost for reaching the goal node is g(G) and the execution cost is given by the sum of g. (G). The stopping criterion as specified by NORA would be: stop when

Writing the ratio of the response time, RT(i), when stopping at node i over the response time, RT(G), when stopping at goal node, G, we have:

Note that g(G) "<!g(i)+ h(i) ash is assumed to be admissible. Since h(i) is positive, we can ignore it from the denominator and on substi­ tuting the stopping condition we get:

Dividing both numerator and denominator by g(i), we get:

as both g,(G) and g(i) are positive. Thus the bound of NORA is satisfied. Note that as 1.. is positive, 1 +A. is greater than 1.

Thus result provides an interesting extension of A* for minim­ izing response time for the real-time problems, where plan-execution time is not negligible. Use of stopping criteria of NORA leads to a near optimal response time, which is shown to be near-optimal even when h. (goal) = 0. We have verified this assertion for the best case

of A*, ie the case of monotone admissible heuristic functions. It can easily be verified that the assertion holds in all cases.

5. Conclusions

We have looked at real-time AI applications, where planning and execution costs are equally important. We have presented a classification of real-time problem solving systems, and an algorithm for producing near optimal response times. We proved that balanc­ ing planning cost with execution cost, can lead to near-optimal response time, and provided bounds on the worst-case deviation from the optimal point. We have then provided an empirical valida­ tion of the algorithm, via a real-time application of query planning for databases. Experimental results show that the performance of our algorithm is often much better than the worst case bounds. We have also developed a framework for obtaining bounds on response times in the context of real time heuristic search using A · .

The results can be extended in many directions. The bounds on the performance of the algorithm are far from tight as illustrated by experiments. We would like to prove tighter bounds on the optimality of our algorithm. Secondly, our termination criterion can be used with any search algorithm like A*, RTA* etc. More research needs to be done in this direction. In particular we would like to combine it with RTA*[ 9] and explore the properties of that algorithm. Finally, we are exploring the applicability of our results in domains.

6. Acknowledgements

We would like to thank Prof. Srivastava, Univ. of Minnesota, for help with the implementation and performance evaluation of the semantic query optimization example, and Prof. Korf and Dr. Hor­ vitz for fruitful discussions on real time search.

7. References