Institute for Systems Research Technical Reports

In this paper, we propose an architecture for integrating CAD with DFM. This involves the use of multiple critiquing systems, each one dedicated to one type of manufacturing domain. In the proposed framework, as the designer creates a design, a number of critiquing systems analyze its manufacturability with respect to different manufacturing domains (machining, fixturing, assembly, inspection, and, so forth), and offer advice about potential ways of improving the design.

We anticipate that this approach can be used to build an environment that will allow designers to create high-quality products that can be manufactured more economically. This will reduce the need for redesign, thus reducing product cost and lead time.

Evaluating the manufacturability of a proposed design involves determining whether or not it is manufacturable with a given set of manufacturing operations - and if so, then finding the associated manufacturing efficiency. Since there can be several different ways to manufacture a proposed design, this requires us to consider different ways to manufacture it, in order to determine which one best meets the design and manufacturing objectives.

The first step in our approach is to identify all machining operations which can potentially be used to create the given design. Using these operations, we generate different operation plans for machining the part. Each time we generate a new operation plan, we examine whether it can produce the desired shape and tolerances, and calculate its manufacturability rating. If no operation plan can be found that is capable of producing the design, then the given design is considered unmachinable; otherwise, the manufacturability rating for the design is the rating of the best operation plan.

We anticipate that by providing feedback about possible problems with the design, this work will help in speeding up the evaluation of new product designs in order to decide how or whether to manufacture them. Such a capability will be useful in responding quickly to changing demands and opportunities in the marketplace.

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 describe our approach for overcoming this problem. We develop a model of imperfect-information games, and describe how to represent information about the game using a modified version of a task network that is extended to represent multi-agency and uncertainty. We present a game-playing procedure that uses this approach to generate game trees in which the set of alternative choices is determined not by the set of possible actions, but by the set of available tactical and strategic schemes.

In our tests of this approach on the game of bridge, we found that it generated trees having a much smaller branching factor than would have been generated by conventional game-tree search techniques. Thus, even in the worst case, the game tree contained only about 1300 nodes, as opposed to the approximately 6.01 44, x 10 nodes that would have been produced by a brute-force game tree search in the worst case. Furthermore, our approach successfully solved typical bridge problems that matched situations in its knowledge base. These preliminary tests suggest that our approach has the potential to yield bridge-playing programs much better than existing ones - and thus we have begun to build a full implementation.

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.