Browsing by Author "Nau, Dana S."
Results Per Page
Sort Options
Item An Algebraic Approach to Feature Interactions.(1989) Nau, Dana S.; Karinthi, Raghu R.; ISRVarious approaches have been proposed to provide communication between CAD systems and process planning systems, including automated feature extraction, design by features, and human- supervised feature extraction. Regardless of which approach is used, a major problem is that due to geometric interactions among features, there may be several equally valid sets of manufacturable features describing the same part - and different sets of features may differ in their manufacturability. Thus, to produce a good process plan - or, in some cases, even to produce a process plan at all - it may be necessary to interpret the part as a different set of features than the one initially obtained from the CAD model. This paper proposes a way to address this problem, based on an algebra of features. Given a set of features describing a machinable part, other equally valid interpretations of the part can be produced by performing operations in the algebra. This will enable automated process planning systems (such as [Nau87]) to examine these interpretations in order to see which one is most appropriate for use in manufacturing.Item Automated Manufacturability Analysis: A Survey(1995) Das, Diganta; Gupta, Satyandra K.; Regli, W.C.; Nau, Dana S.; ISRIn the marketplace of the 21st century, there is no place for traditional ``over-the-wall'' communications between design and manufacturing. In order to ``design it right the very first time,'' designers must ensure that their products are both functional and easy to manufacture. Software tools have had some successes in reducing the barriers between design and manufacturing. Manufacturability analysis systems are emerging as one such tool---enabling identification of potential manufacturing problems during the design phase and providing suggestions to designers on how to eliminate them.In this paper, we provide a survey of current state of the art in automated manufacturability analysis. We present the historical context in which this area has emerged and outline characteristics to compare and classify various systems. We describe the two dominant approaches to automated manufacturability analysis and overview representative systems based on their application domain. We describe support tools that enhance the effectiveness of manufacturability analysis systems. Finally, we attempt to expose some of the existing research challenges and future directions.
Item Comparing Minimax and Product in a Variety of Games.(1987) Chi, Ping-Chung; Nau, Dana S.; ISRIn applications of game tree searching, the most widely used back-up rule is the minimax rule. Research has shown that minimax does not perform well in some games - and this has led to interest in alternatives to minimax, such as the product rule.Item Complexity Results for HTN Planning(1998-10-15) Erol, Kutluhan; Hendler, James; Nau, Dana S.(Also cross-referenced as ISR-TR-95-10) Most 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. (Also cross-referenced as UMIACS-TR-94-32)Item Complexity, Decidability and Undecidability Results for Domain-Independent Planning: A Detailed Analysis(1998-10-15) Erol, Kutluhan; Nau, Dana S.; Subrahmanian, V.S.In this paper, we examine how the complexity of domain-independent planning with STRIPS-like operators depends on the nature of the planning operators. We show conditions under which plannning is decidable and undecidable. Our results on this topic solve an open problem posed by Chapman [4], and clear up some difficulties with his undecidability theorems. For those cases where planning is decidable, we show how the time complexity varies depending on a wide variety of conditions: . whether or not function symbols are allowed; . whether or not delete lists are a]]owed; . whether or not negative preconditions are allowed; . whether or not the predicates are restricted to be propositional(i.e., 0-ary); . whether the planning operators are given as part of the input to the planning prob]em, or instead are fixed in advance. (Also cross-referenced as UMIACS-TR-91-154)Item Complexity, Decidability and Undecidability Results for Rule- Based Expert Systems(1992) Blanksteen, Scott; Hendler, James A.; Nau, Dana S.; ISRWe prove the equivalence of domain-independent planning systems and rule-based expert systems. We use this equivalence to examine how the complexity of deriving conclusions in rule-based expert systems depends on the nature of the rules. We show conditions under which conclusion derivation is decidable and undecidable. For those cases where the problem is decidable, we show how the time complexity varies depending on a wide variety of conditions: whether or not function symbols are allowed; whether or not rules may retract facts; whether or not negative conditions are allowed; whether or not the rules are allowed to take arguments; and whether the rules are given as part of the input to the expert system, or instead are fixed in advance.Item Current Trends and Future Challenges in Automated Manufacturability Analysis(1995) Gupta, Satyandra K.; Das, Diganta; Regli, W.C.; Nau, Dana S.; ISRIn the marketplace of the 21st century, there is no place for traditional communications between design and manufacturing. In order to ``design it right the first time,'' designers must ensure that their products are both functional and easy to manufacture. Software tools have had some successes in reducing the barriers between design and manufacturing. Manufacturability analysis systems are emerging as one such tool---enabling identification of potential manufacturing problems during the design phase and providing suggestions to designers on how to eliminate them.In this paper, we survey of current state of the art in automated manufacturability analysis. We describe the two dominant approaches to automated manufacturability analysis and overview representative systems based on their application domain. Finally, we attempt to expose some of the existing research challenges and future directions.
Item Estimation of Setup Time for Machined Parts: Accounting for Work-Holding Constraints(1995) Das, Diganta; Gupta, Satyandra K.; Nau, Dana S.; ISRFor machined parts, setup time is a major component of the total time required to create a machined part. If the setup time can be reduced, this will not only decrease the machining time, but will also ensure better machining accuracy, require fewer work- holding devices and increase machine usage time.To achieve any improvement in setup time, first we need to estimate the setup time accurately. In this paper we propose a methodology to estimate the setup time for machining prismatic parts in a three axis vertical machining center. We consider three major factors in estimating the number of setups, namely---the precedence constraints among machining operations, the feasibility of work holding using vise clamping, and the availability of datum faces for locating the workpiece.
Item Feature Recognition for Interactive Applications: Exploiting Distributed Resources(1998-10-15) Regli, William C.; Gupta, Satyandra K.; Nau, Dana S.The availability of low-cost computational power is a driving force behind the growing sophistication of CAD software. Tools designed to reduce time-consuming build-test-redesign iterations are essential for increasing engineering quality and productivity. However, automation of the design process poses many difficult computational problems. As more downstream engineering activities are being considered during the design phase, guaranteeing reasonable response times within design systems becomes problematic. Design is an interactive process and speed is a critical factor in systems that enable designers to explore and experiment with alternative ideas during the design phase. Achieving interactivity requires an increasingly sophisticated allocation of computational resources in order to perform realistic design analyses and generate feedback in real time. This paper presents our initial efforts to develop techniques to apply distributed algorithms to the problem of recognizing machining features from solid models. Existing work on recognition of features has focused exclusively on serial computer architectures. Our objective is to show that distributed algorithms can be employed on realistic parts with large numbers of features and many geometric and topological entities to obtain significant improvements in computation time using existing hardware and software tools. Migrating solid modeling applications toward a distributed computing framework enables interconnection of many of the autonomous and geographically diverse software tools used in the modern manufacturing enterprise. (Also cross-referenced as UMIACS-TR-94-126.1)Item Generating Redesign Suggestions to Reduce Setup Cost: A Step towards Automated Redesign(1995) Das, Diganta; Gupta, Satyandra K.; Nau, Dana S.; ISRAll mechanical designs pass through a series of formal and informal redesign steps, involving the analysis of functionality, manufacturability, cost and other life-cycle factors. The speed and efficacy of these steps has a major influence on the lead time of the product from conceptualization to launching. In this paper we propose a methodology for automatically generating redesign suggestions for reducing setup costs for machined parts.Given an interpretation of the design as a collection of machinable features, our approach is to generate alternate machining features by making geometric changes to the original features, and add them to the feature set of the original part to create an extended feature set. The designer may provide restrictions on the design indicating the type and extent of modifications allowed on certain faces and volumes, in which case all redesign suggestions generated by our approach honor those restrictions.
By taking combinations of features from the extended feature set generated above, we can generate modified versions of the original design that still satisfy the designer's intent. By considering precedence constraints and approach directions for the machining operations as well as simple fixturability constraints, we can estimate the setup time that will be required for each design. Any modified design whose setup time is less than that of the original design can be presented to the designer as a possible way to modify the original design.
Item A Geometric Algorithm for Finding the Largest Milling Cutter(2001) Yao, Zhiyang; Gupta, Satyandra K.; Nau, Dana S.; ISRIn this paper, we describe a new geometric algorithm to determine the largest feasible cutter size for 2-D milling operations to be performed using a single cutter. In particular:1. We give a general definition of the problem as the task of covering a target region without interfering with an obstruction region. This definition encompasses the task of milling a general 2-D profile that includes both open and closed edges.2. We discuss three alternative definitions of what it means for a cutter to be feasible, and explain which of these definitions is most appropriate for the above problem.3. We present a geometric algorithm for finding the maximal cutter for 2-D milling operations, and we show that our algorithm is correct.Item A Geometric Algorithm for Finding the Largest Milling Cutter(2000) Yao, Zhiyang; Gupta, Satyandra K.; Nau, Dana S.; ISRIn this paper, we describe a new geometric algorithm to determine the largest feasible cutter size for2-D milling operations to be performed using a single cutter. In particular:1. We give a general definition of the problem as the task of covering a target region without interfering with anobstruction region. This definition encompasses the task of milling a general 2-D profile that includes bothopen and closed edges.
2. We discuss three alternative definitions of what it means for a cutter to be feasible, and explain which of thesedefinitions is most appropriate for the above problem.
3. We present a geometric algorithm for finding the maximal cutter for 2-D milling operations, and we show thatour algorithm is correct.
Item A Geometric Algorithm for Multi-Part Milling Cutter Selection(2000) Yao, Zhiyang; Gupta, Satyandra K.; Nau, Dana S.; ISRMass customization results in smaller batch sizes in manufacturing that require large numbers of setup and tool changes. The traditional process planning that generates plans for one part at a time is no longer applicable.In this paper, we propose the idea of process planning for small batch manufacturing, i.e., we simultaneously consider multiple parts and exploit opportunities for sharing manufacturing resources such that the process plan will be optimized over the entire set of parts. In particular, we discuss a geometric algorithm for multiple part cutter selection in 2-1/2D milling operations.
We define the 2-1/2D milling operations as covering the target region without intersecting with the obstruction region. This definition allows us to handle the open edge problem. Based on this definition, we first discuss the lower and upper bond of cutter sizes that are feasible for given parts. Then we introduce the geometric algorithm to find the coverable area for a given cutter. Following that, we discuss the approach of considering cutter loading time and changing time in multiple cutter selection for multiple parts. We represent the cutter selection problem as shortest path problem and use Dijkstra's algorithm to solve it. By using this algorithm, a set of cutters is selected to achieve the optimum machining cost for multiple parts.
Our research illustrates the multiple parts process planning approach that is suitable for small batch manufacturing. At the same time, the algorithm given in this paper clarifies the 2-1/2D milling problem and can also help in cutter path planning problem.
Item An HTN Planner That can Reason About Time(2002-12-19) Yaman, Fusun; Nau, Dana S.In this paper we present a formalism for explicitly representing time in HTN planning. Actions can have durations and intermediate effects in this formalism. Methods can specify qualitative and quantitative temporal constraints on decompositions. Based on this formalism we defined a planning algorithm TimeLine that can produce concurrently executable plans in the presence of numeric state variables. We state and prove the soundness of the algorithm. We also present the experimental results of the TimeLine implementation that shows the feasibility of our approach. UMIACS-TR-2002-105Item HTN Planning in Answer Set Programming(2002-05-22) Dix, Jurgen; Kuter, Ugur; Nau, Dana S.In this paper we introduce a formalism for solving Hierarchical Task NEtwork (HTN) Planning using Answer Set Programming (ASP). The ASP paradigm evolved out of the stable semantics for logic programs in recent years and is strongly related to nonmonotonic logics. We consider the formulation of HTM planning as described in the SHOP planning system and define a systematic translation method from SHOP's representation of the planning problems into logic programs with negation. We show that our translation is sound and complete: answer sets of the logic programs obtained by our translation correspond exactly to the solutions of the planning problems. Our approach does not rly on a particular system for computing answer sets. It can therefore serve as a means to evaluate ASP systems by using well-established benchmarks from the planning community. We tested our method on various such benchmarks and used smodels and DLV for computing answer sets. We compared our method to (1) similar approaches based on non-HTN planning and (2) SHOP, a dedicated planning system. We show that our approach outperforms non-HTN methods and that its performance is closer to that of SHOP, when we are using ASP systems which allow for nonground programs. (Also UMIACS-TR-2002-18)Item IMPACTing SHOP: Foundations for integrating HTN Planning and Multi-Agency(2000-02-08) Munoz-Avila, Hector; Dix, Juergen; Nau, Dana S.; Cao, YueIn this paper we describe a formalism for integrating the SHOP HTN planning system with the IMPACT multi-agent environment. Our formalism provides an agentized adaptation of the SHOP planning algorithm that takes advantage of IMPACT's capabilities for interacting with external agents, performing mixed symbolic/numeric computations, and making queries to distributed, heterogeneous information sources (such as arbitrary legacy and/or specialized data structures or external databases). We show that this agentized version of SHOP will preserve soundness and completeness if certain conditions are met. (This technical report is the updated version of CS-TR-4085) (Also cross-referenced as UMIACS-TR-2000-02)Item Improving the Efficiency of Limited-Memory Heuristic Search(1998-10-15) Ghosh, Subrata; Mahanti, Ambuj; Nau, Dana S.This paper describes a new admissible tree search algorithm called Iterative Threshold Search (ITS). ITS can be viewed as a much-simplified version of MA*, and a generalized version of MREC 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 0(N) nodes in comparison to 0(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 nodegeneration 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 rake of costs grows in proportion to the problem size, then IDA* is not asymptotically optimal. ITS's asymptotic complexity in the latter case depends on the amount of memory available to it. (Also cross-referenced as UMIACS-TR-95-23)Item Integrating DFM with CAD through Design Critiquing(1998-10-15) Gupta, Satyandra K.; Regli, William C.; Nau, Dana S.The increasing focus on design for manufacturability (DFM) in research in concurrent engineering and engineering design is expanding the scope of traditional design activities in order to identify and eliminate manufacturing problems during the design stage. Manufacturing a product generally involves many different kinds of manufacturing activities, each having different characteristics. A design that is good for one kind of activity may not be good for another, for example, a design that is easy to assemble may not be easy to machine. One obstacle to DFM is the difficulty involved in building a single system that can handle the various manufacturing domains relevant to a design. In this paper we propose an architecture for integrating CAD with DFM. As the designer creates a design multiple critiquing systems analyze its manufacturability with respect to different manufacturing domains such as machining, fixturing, assembly, and inspection. Using this analysis, each critiquing system offers advice about potential ways of improving the design and an integration module mediates conflicts among the different critiquing systems in order to provide feedback to improve the overall design. We anticipate that this approach can be used to build a multi-domain environment that will allow designers to create higher-quality products that can be more economically manufactured. This will reduce the need for redesign and reduce product cost and lead time. (Also cross-referenced as UMIACS-TR-94-96)Item Integrating Tradeoff Analysis and Plan-Based Evaluation of Designs for Microwave Modules(1996) Trichur, Vinai S.; Ball, Michael O.; Baras, John S.; Hebbar, Kiran; Minis, Ioannis; Nau, Dana S.; Smith, Stephen J.J.; ISRPreviously, we have described two systems, EDAPS and EXTRA, which support design and process planning for the manufacture of microwave modules, complex devices with both electrical and mechanical attributes. EDAPS integrates electrical design, mechanical design, and process planning for both mechanical and electrical domains. EXTRA accesses various component and process databases to help the user define design and process options. It then supports the user in choosing among these options with an optimization bases tradeoff analysis module.In this paper, we describe our current work towards the integration and enhancement of the capabilities of EDAPS and EXTRA. We integrate EXTRA's functionality with the initial design step of EDAPS. in the resultant system, the user, supported by an enhanced tradeoff analysis capability, can select and describe a promising preliminary design and process plan based on the analysis of a variety of alternatives from both an electrical and mechanical perspective. This preliminary design is then subjected top further analysis and refinement using existing EDAPS capabilities. In addition to the integration of these two systems, specific new functions have been developed, including tradeoff analysis over a much broader set of criteria, and the ability of the tradeoff module to query the process planner to determine costs of individual options.
Item Knowledge Representation and Reasoning Techniques for Process Planning: Extending SIPS to do Tool Selection.(1987) Nau, Dana S.; Luce, Mark; ISRSIPS (Semi-Intelligent Process Selector) was originally developed to use AI techniques for generative process selection. SIPS considers a metal part to be a collection of machinable features - and for each feature, it generates a sequence of machining process to use in creating that feature. It does this by reasoning about the intrinsic capabilities of each manufacturing operation.