Institute for Systems Research Technical Reports
Permanent URI for this collectionhttp://hdl.handle.net/1903/4376
This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browse
Search Results
Item A Planning Approach to Declarer Play in Contract Bridge(1995) Smith, S.J.J.; Nau, D.S.; Throop, T.A.; ISRAlthough game-tree search works well in perfect-information games, it is less suitable for imperfect-information games such as contract bridge. The lack of knowledge about the opponents' possible moves gives the game tree a very large branching factor, making it impossible to search a significant portion of this tree in a reasonable amount of time.This paper describes our approach for overcoming this problem. We represent information about bridge in a task network that is extended to represent multi-agency and uncertainty. Our game-playing procedure uses this task network 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.
We have tested this approach on declarer play in the game of bridge, in an implementation called Tignum 2. On 5,000 randomly generated no-trump deals, Tignum 2 beat the strongest commercially available program by 1394 to 1302, with 2304 ties. These results are statistically significant at the a = 0.05 level. Tignum 2 searched an average of only 8745.6 moves per deal in an average time of only 27.5 seconds per deal on a Sun SPARCstation 10. Further enhancements to Tignum 2 are currently underway.
Item A Critical Look at Critics in HTN Planning(1995) Erol, Kutluhan; Hendler, James A.; Nau, D.S.; Tsuneto, R.; ISRDetecting interactions and resolving conflicts in one of the key issues for generative planning systems. Hierarchical Task Network (HTN) planning systems use critics for this purpose. Critics have provided extra efficiency and flexibility to HTN planning systems, but their procedural -- and sometimes domain- specific - - nature has not been amenable to analytical studies. As a result, little work is available on the correctness or efficiency of critics. This paper describes a principled approach to handling conflicts, as implemented in UMCP, an HTN planning system. Critics in UMCP have desirable properties such as systematicity, and the preservation of soundness and completeness.Item Improving the Efficiency of Limited-Memory Heuristic Search(1995) Ghosh, Subrata; Mahanti, Ambuj; Nau, D.S.; ISRThis paper describes a new admissible tree search algorithm called Iterative Threshold Search (ITS). ITS can be viewed as a much-simplified version of MA*[2], and a generalized version of MREC [15]. ITS's node selection and retraction (pruning) overhead is much less expensive than MA*'s. We also present the following results: 1. Every node generated by ITS is also generated by IDA*, even if ITS is given no more memory than IDA*. In addition, there are trees on which ITS generates O(N) nodes in comparison to O(N log N) nodes generated by IDA*, where N is the number of nodes eligible for generation 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.
Item Complexity Results for HTN Planning(1995) Erol, Kutluhan; Hendler, James A.; Nau, D.S.; ISRMost practical work on AI planning systems during the last fifteen years has been based on hierarchical task network (HTN) decomposition, but until now, there has been very little analytical work on the properties of HTN planners. This paper describes how the complexity of HTN planning varies with various conditions on the task networks, and how it compares to STRIPS- style planning.Item "Manufacturing-Operation Planning Versus AI Planning(1995) Nau, D.S.; Gupta, Sandeep K.; Regli, W.C.; ISRAlthough AI planning techniques can potentially be useful in several manufacturing domains, this potential remains largely unrealized. Many of the issues important to manufacturing engineers have not seemed interesting to AI researchers---but in order to adapt AI planning techniques to manufacturing, it is important to address these issues in a realistic and robust manner. Furthermore, by investigating these issues, AI researchers may be able to discover principles that, are relevant for AI planning in general.As an example, in this paper we describe the techniques for manufacturing-operation planning used in IMACS (Interactive Manufacturability Analysis and Critiquing System). We compare and contrast them with the techniques used in classical AI planning systems, and point out that some of the techniques used in IMACS may also be useful in other kinds of planning problems.
Item Manufacturing Feature Instances: Which Ones to Recognize?(1994) Gupta, Satyandra K.; Regli, W.C.; Nau, D.S.; ISRManufacturing features and feature-based representations have become an integral part of research on manufacturing systems, largely due to their ability to model correspondences between design information and manufacturing operations. However, several research challenges still must be addressed in order to place feature technologies into a solid scientific and mathematical framework: One challenge is the issue of alternatives in feature- based planning.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.
Item Extracting Alternative Machining Features: Al Algorithmic Approach(1994) Regli, W.C.; Gupta, Satyandra K.; Nau, D.S.; ISRAutomated recognition of features from CAD models has been attempted for a wide range of application domains. In this paper we address the problem of representing and recognizing the complete class of features in alternative interpretations for a given design. We present a formalism for representing feature- based design alternatives and a methodology for recognizing a class of machinable features. Our approach handles a class of volumetric features that describe material removal volumes made by operations on the three-axis vertical machining centers including: drilling, pocket-, slot-, and face-miling, chamfering, filleting, and blended surfaces. Our approach recognizes intersecting features, and is complete over all features in our class, i.e. for any given part, the algorithm produces a set containing all features in our class that correspond to possible operations for machining that part. This property is of particular significance in applications where consideration of different manufacturing alternatives is crucial. In addition, we have shown that the algorithms are, in the worst-case, euqdratic in the number solid modeling operations. This approach employs a class of machinable features expressible as MRSEVs ( a STEP- based library of machining features). An implementation of these algorithms has been done using the ACISsolid modeler and the NIH C++ class library.Item Feature Recognition for Manufacturability Analysis(1994) Regli, W.C.; Gupta, Satyandra K.; Nau, D.S.; ISRWhile automated recognition of features has been attempted for a wide range of applications, no single existing approach possesses the functionality required to perform manufacturability analysis. In this paper, we present a methodology for taking a CAD model and extracting a set of machinable features suitable for generating all alternative interpretations of the model as collections of MRSEVs (Material Removal Shape Element Volumes, a STEP-based library of machining, features). This set of MRSEVs is to be employed for manufacturability analysis. The algorithm handles a variety of features including those describing holes, pockets, slots, and chamfering and filleting operations. In addition, it considers elementary accessibility constraints for these features and is provably complete over a, significant class of machinable parts the features describe. Further, the approach has low-order polynomial-time worst-case complexity.Item Building MRSEV Models for CAM Applications(1993) Gupta, Satyandra K.; Kramer, Thomas R.; Nau, D.S.; Regli, W.C.; Zhang, G.M.; ISRIntegrating CAD and CAM applications, one major problems is how to interpret CAD information in a manner that makes sense for CAM. Our goal is to develop a general approach that can be used with a variety of CAD and CAM applications for the manufacture of machined parts.In particular, we present a methodology for taking a CAD model, extracting alternative interpretations of the model as collections of MRSEVs (Material Removal Shape Element Volumes, a STEP-based library of machining features), and evaluating these interpretations to determine which one is optimal. The evaluation criteria may be defined by the user, in order to select the best interpretation for the particular application at hand.
Item Recognition of Volumetric Features from CAD Models: Problem Formalization and Algorithms(1993) Regli, W.C.; Nau, D.S.; ISRAutomated recognition of features from CAD models has been attempted for a wide range of application domains in mechanical engineering. However, the absence of a clear mathematical formalism for the problem has made it difficult to develop a general approach - and thus most of these methods are limited in scope.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,