Institute for Systems Research Technical Reports

To correct the above problem, we state and prove necessary and sufficient for asymptotic optimality of IDA* on trees. On trees not satisfying our conditions, we show that no best-first limited- memory search algorithm can be asymptotically optimal.

On graphs, IDA* can perform quite poorly. In particular, there are graphs on which IDA* does (22N) node expansions where N is the number of nodes expanded by A*.

2. Experimental tests show that if the heuristic branching factor is low and the node- generation time is high (as in most practical problems), then ITS can provide significant savings in both number of node generations and running time.

3. Our experimental results also suggest that on the Traveling Salesman Problem, both IDA* and ITS are asymptotically optimal on the average if the costs between the cities are drawn from a fixed range. However, if the range of costs grows in proportion to the problem size, then IDA* is not asymptotically optimal. ITS's asymptotic complexity in the later case depends on the amount of memory available to it.

Even after one has decided upon al abstract set of features to use for representing manufacturing operations, the set of feature instances used to represent a complex part is by no means unique. For a complex part, many (sometimes infinitely many) different manufacturing operations can potentially be used to manufacture various portions of the part - - and thus many different feature instances can be used to represent these portions of the part. Some of these feature instances will appear in useful manufacturing plans, and others will not. If the latter feature instances can be discarded at the outset, this will reduce the number of alternative manufacturing plans to be examined in order to find a useful one. Thus, what is required is a systematic means of specifying which feature instances are of interest.

This paper addresses the issue of alternatives by introducing the notion of primary feature instances, which we contend are sufficient to generate all manufacturing plans of interest. To substantiate our argument, we describe how various instances in the primary feature set can be used to produce the desired plans. Furthermore, we discuss how this formulation overcomes computational difficulties faced by previous work, and present some complexity results for this approach in the domain of machined parts.

As a step toward deeper understanding of how forward pruning affects quality of play, in this paper we set up a model of forward pruning on two abstract classes of binary game trees, and we use this model to investigate how forward pruning affects the accuracy of the minimax values returned. The primary result of our study is that forward pruning does better when there is a high correlation among the minimax values of sibling nodes in a game tree.

This result suggests that forward pruning may possibly be a useful decision-making technique in certain kinds of games. In particular, we believe that bridge may be such a game.

In this paper, we develop a formalization of the problem of recognizing a class of machinable features expressed as MRSEVs ( a PDES/STEP library of machining features) [19], and an algorithm for solving this problem. Some of the characteristics of this approach are: the algorithm handles a large variety of hole and pocket features along with elementary accessibility constraints and blends for those features; it is provably complete, even if the features interest with each other in complex ways; it has O(n4) worst-case time complexity,

2. In an AND/OR tree where multiple problem- reduction steps are possible, problem reduction produces a much more dramatic improvement: both the time complexity and the space complexity decrease from doubly exponential to singly exponential.

3. For iterative-deepening procedures like IDA* that only remember the nodes on the current path, the space complexity decreases but the time complexity increases - by exponential amounts in Korf's model, and doubly exponential amounts in the AND/OR-tree model. This is true even for IDAO*, a new procedure that improves IDA*'s performance by combining it with problem reduction.

These results lead to the following conclusions: In general, problem reduction can save huge amounts of both time and space.

 Whether to use a procedure that remembers every node it has visited, or instead use a limited-memory iterative-deepening procedure, depends on whether the primary objective is to save space or save time.

1. It is NP-hard to tell, given a plan P and a ground atom p, whether P is possibly true in P's final situation. This is true despite the fact that modal truth criterion can be computed in a polynomial time.

2. The reason for this discrepancy is that the "possible truth" version of the modal truth criterion is incorrect. It tells whether - p is not necessarily true --- but this is different from telling whether p is possibly true. Possible truth is not the dual of necessary truth, as Chapman had thought it was.

3. Instead, possible truth is the dual of another problem, which is co-NP-hard: the problem of determining whether p is true over all executable completions of a plan.

Despite the above problems, the "necessary truth" version of the modal truth criterion (and hence the TWEAK planner) are still correct.