More Like this

1. SOUPS: A Variable Ordering Metric for the Saturation Algorithm

   https://doi.org/10.1109/ACSD.2018.000-4  

   Smith, Benjamin; Ciardo, Gianfranco (June 2018, 2018 18th International Conference on Application of Concurrency to System Design (ACSD) (2018))

   Multivalued decision diagrams are an excellent technique to study the behavior of discrete-state systems such as Petri nets, but their variable order (mapping places to MDD levels) greatly affects efficiency, and finding an optimal order even just to encode a given set is NP-hard. In state-space generation, the situation is even worse, since the set of markings to be encoded keeps evolving and is known only at the end. Previous heuristics to improve the efficiency of the saturation algorithm often used in state-space generation seek a variable order minimizing a simple function of the Petri net, such as the sum over each transition of the top variable position (SOT) or variable span (SOS). This, too, is NP-hard, so we cannot compute orders that minimize SOT or SOS in most cases but, even if we could, it would have limited effectiveness. For example, SOT and SOS can be led astray by multiple copies of a transition (giving more weight to it), or transitions with equal inputs and outputs (giving weight to transitions that should be ignored). These anomalies inspired us to define SOUPS, a new heuristic that only takes into account the \emph{unique} and \emph{productive} portion of each transition. The SOUPS metric can be easily computed, allowing us to use it in standard search techniques like simulated annealing to find good orders. Experiments show that SOUPS is a much better proxy for the quantities we really hope to improve, the memory and time for MDD manipulation during state-space generation. 

   more » « less
2. Variable Reordering in Binary Decision Diagrams

   Jiang, Chuan; Babar, Junaid; Ciardo, Gianfranco; Miner, Andrew S.; Smith, Benjamin (January 2017, 26th International Workshop on Logic & Synthesis)

   The size of a BDD heavily depends on its variable order. Significant efforts have been made to find good variable orders, statically or dynamically. This paper concentrates on a related issue, transforming a BDD from one variable order to another, as needed when an application must cope with BDDs having different variable orders. Instead of rebuilding BDDs as done in previous work, we accomplish such transformation through a sequence of adjacent variable swaps. Since there are many ways to schedule these swaps, we propose and compare several heuristics to determine good schedules. 

   more » « less
3. Identifying Multiple Levels of Heuristic Reasoning Used in Scientific Model Construction: A Framework Grounded in Imagistic Processing

   https://doi.org/10.1007/978-3-031-94709-4_8  

   Clement, John J (August 2025, Springer Nature Switzerland)

   Ippoliti, E; Sterpetti, F (Ed.)

   This chapter first consolidates a set of important heuristic strategies used for constructing innovative scientific models from three books, including studies in the history of genetics and electromagnetism, and an expert think-aloud study in mechanics. Twenty-four strategies are identified, most of which are field-general. Patterns in their use suggest a partially organized hierarchy of interconnected strategies and substrategies, contrary to the view that heuristics are simply tried in random order. Strategies at four different size and time scale levels are described, including larger Modeling Cycle Phases of model generation, evaluation, and modification, each of which can utilize many smaller Tactical Heuristics as substrategies, e.g., analogy, or testing predictions from the model. These in turn can utilize Grounded Imagistic Processes, such as imagistic mental simulation, an important alternative to deduction for evaluating a model by running it. The framework links higher level, serially organized processes with lower level, imagery-based processes. Its intermediate degree of organization is neither anarchistic, nor fully algorithmic. Possible benefits of organization are narrowing the search space involved and balancing sources of model construction and criticism for productive creativity. Unorganized, spontaneous processes are also discussed, along with their possible benefits. 

   more » « less
4. Computing a High-Dimensional Euclidean Embedding from an Arbitrary Smooth Riemannian Metric

   Zhong, Zichun; Wang, Wenping; Lévy, Bruno; Hua, Jing; Guo, Xiaohu (January 2018, ACM transactions on graphics)

   This article presents a new method to compute a self-intersection free high-dimensional Euclidean embedding (SIFHDE^2) for surfaces and volumes equipped with an arbitrary Riemannian metric. It is already known that given a high-dimensional (high-d) embedding, one can easily compute an anisotropic Voronoi diagram by back-mapping it to 3D space. We show here how to solve the inverse problem, i.e., given an input metric, compute a smooth intersection-free high-d embedding of the input such that the pullback metric of the embedding matches the input metric. Our numerical solution mechanism matches the deformation gradient of the 3D -> higher-d mapping with the given Riemannian metric. We demonstrate the applicability of our method, by using it to construct anisotropic Restricted Voronoi Diagram (RVD) and anisotropic meshing, that are otherwise extremely difficult to compute. In SIFHDE^2 -space constructed by our algorithm, difficult 3D anisotropic computations are replaced with simple Euclidean computations, resulting in an isotropic RVD and its dual mesh on this high-d embedding. Results are compared with the state-of-the-art in anisotropic surface and volume meshings using several examples and evaluation metrics. 

   more » « less
5. Framework for the Evolution of Heuristics in Advanced Manufacturing

   https://doi.org/10.1115/1.4055622  

   Fillingim, Kenton B.; Fu, Katherine (January 2023, Journal of Mechanical Design)

   Abstract This study works toward addressing a knowledge gap in understanding how heuristics are developed, retrieved, employed, and modified by designers. Having a better awareness of one’s own set of heuristics can be beneficial for relaying to other team members, improving a team’s training processes, and aiding others on their path to design expertise. The ability to understand and justify the use of a heuristic should lead to more effective decision-making in systems design. To do this, the heuristics and their characteristics must be extracted using a repeatable scientific research methodology. This study describes a unique extraction and characterization process compared to prior literature. It includes some of the first work towards documenting heuristics for both designers and operators in a hybrid manufacturing setting. Eight participants performed a series of two design journals, two interviews, and one survey. Heuristics were extracted and refined between each method and then verified by participants in the survey. The surveys produced novel statistically significant findings in regard to heuristic characterizations, impacting how participants view how often a heuristic is used, the reliability of the heuristic, and the evolution of the heuristic. Lastly, an alternate perspective of heuristics as an error management bias is highlighted and discussed. 

   more » « less