Browsing by Author "Ghosh, Subrata"
Results Per Page
Sort Options
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 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 Manufacturing Cell Formation by State-Space Search(1993) Ghosh, Subrata; Mahanti, Ambuj; Nagi, Rakesh; Nau, Dana; ISRThis paper addresses the problem of grouping machines in order to design cellular manufacturing cells, with an objective to minimize intercell flow. This problem is replaced to one of the major aims of group technology (GT): to decompose the manufacturing system into manufacturing cells that are as independent as possible.This problem is NP-hard. Thus, nonheuristic methods cannot address problems of typical industrial dimensions because they would require exorbitant amounts of computing time, while fast heuristic methods may suffer from sub-optimality.
We present a branch-and-bound state-space search algorithm that attempts to overcome both these deficiencies. One of the major strengths of this algorithm is its efficient branching and search strategy. In addition, the algorithm employs the efficient Inter-Cell Traffic Minimization Method to provide good upper bounds, and computes lower bounds based on a relaxation of merging.
Item Modeling and Analysis of the Grinding Process(1993) Ghosh, Subrata; Zhang, G.M.; ISRProduct quality assurance is a very important concern in industries these days. Surface quality is an important constituent of the overall product quality. Although the desired surface quality of a product is dependent on the functional requirements of the product, the actual surface quality of the finished product depends mainly on the chosen manufacturing processes. In the case of machining, it depends mostly on the finishing process. One of the commonly used finishing processes is grinding. And therefore, it is important to understand the surface quality produced during a grinding process.In grinding surface quality depends on the grain geometry, the kinematics of the grinding process and the dynamics of the grinding system. In this thesis work, a grinding model is formulated taking the random wheel topography into consideration. An analytical representation of the ideal ground surface is developed. To include the effect of grinding wheel vibration on ground surface topography generation, a grinding force model and a mathematical model representing the grinding system are developed.
The above three models are implemented in a simulation package which can predict the behavior of the surface grinding process. With the help of this package, surfaces ground at different cutting conditions can be compared quantitatively and qualitatively. The simulation package facilitates the selection of a proper grinding wheel and cutting conditions to achieve the desired surface quality.
Item On the Asymptotic Performance of IDA*(1995) Mahanti, Ambuj; Ghosh, Subrata; Nau, D.S.; Pal, A.K.; Kanal, L.N.; ISRSince best-first search algorithms such as A* require large amounts of memory, they sometimes cannot run to completion, even on problem instances of moderate size. This problem has led to the development of limited-memory search algorithms, of which the best known is IDA* [9, 10]. This paper presents the following results about IDA* and related algorithms: The analysis of asymptotic optimality for IDA* in [10] is incorrect. There are trees satisfying the asymptotic optimality conditions given in [10] for which IDA* is not asymptotically optimal.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*.
Item Study of the Formation of Macro-and-Micro-Cracks during Machining of Ceramics(1993) Zhang, G.M.; Anand, Davinder K.; Ghosh, Subrata; Ko, Wing F.; ISRThis paper presents an experimental study on the formation of macro- and micro- cracks formed during the machining of ceramic materials. Aluminum oxide (Al2O3) was used as the testing material and polycrystalline diamond tipped carbide inserts were used for material removal. The cutting force was recorded during machining and surface finish was measured after machining. an environmental SEM was used to obtain high-magnification images of macro- and microcracks induced by machining. With the assistance of a computer-based vision system, qualification of fracture surfaces with respect to crack nucleation, growth, and cleavage was attempted. Results from this research provide an insight into the prevailing mechanisms of material removal during the machining of ceramics, and suggest the development of crack- controlled machining technologies.