Deepak Khemani · 2024
So far our approach to solving problems has been characterized by state space search. We are in a given state, and we have a desired or goal state. We have a set of moves available to us which allow us to navigate from one state to another. We search through the possible moves, and we employ a heuristic function to explore the space in an informed manner. In this chapter we study two different approaches to problem solving.One, with emphasis on knowledge that we can acquire from domain experts. We look at mechanisms to harness and exploit such knowledge. In the last century in the 1980s, an approach to express knowledge in the form of if–then rules gained momentum, and many systems were developed under the umbrella of expert systems. Although only a few lived up to expert level expectations, the technology matured into an approach to allow human users to impart their knowledge into systems. The key to this approach was the Rete algorithm that allowed an inference engine to efficiently match rules with data.The other looks at problem solving from a teleological perspective. That is, we look at a goal based approach which investigates what needs to be done to achieve a goal. In that sense, it is reasoning backwards from the goal. We look at how problems can be formulated as goal trees, and an algorithm AO* to solve them.
Cited by 0
Deepak Khemani · 2024
So far our approach to solving problems has been characterized by state space search. We are in a given state, and we have a desired or goal state. We have a set of moves available to us which allow us to navigate from one state to another. We search through the possible moves, and we employ a heuristic function to explore the space in an informed manner. In this chapter we study two different approaches to problem solving.One, with emphasis on knowledge that we can acquire from domain experts. We look at mechanisms to harness and exploit such knowledge. In the last century in the 1980s, an approach to express knowledge in the form of if–then rules gained momentum, and many systems were developed under the umbrella of expert systems. Although only a few lived up to expert level expectations, the technology matured into an approach to allow human users to impart their knowledge into systems. The key to this approach was the Rete algorithm that allowed an inference engine to efficiently match rules with data.The other looks at problem solving from a teleological perspective. That is, we look at a goal based approach which investigates what needs to be done to achieve a goal. In that sense, it is reasoning backwards from the goal. We look at how problems can be formulated as goal trees, and an algorithm AO* to solve them.
Cited by 2
Rapanotti, Lucia, Hall, Jon G., Jackson, Michael et al. · Open Research Online (The Open University) · 2003
Jackson's Problem Frames provide a means of analysing and decomposing problems. They emphasise the world outside of the computer helping the developer to focus on the problem domain instead of drifting into inventing solutions. The intention is to delay consideration of the solution space until a good understanding of the problem is gained. In contrast, early consideration of a solution architecture is common practice in software development. Software is usually developed by including existing components and/or reusing existing frameworks and architectures. This has the advantage of shortening development time though reuse, and increasing the robustness of a system through the application of tried and tested solutions. In this paper, we show how these two views can be reconciled and demonstrate how a choice of architecture can facilitate problem analysis and decomposition within the Problem Frames framework. In particular, we introduce Architectural Frames-combinations of architectural styles and Problem Frames-and illustrate their use in problem decomposition by applying them to a well-known problem from the literature.
Cited by 0Open access
Martino Ciaperoni, Aristides Gionis, Heikki Mannila · Data Mining and Knowledge Discovery · 2024
Abstract We introduce the Hadamard decomposition problem in the context of data analysis. The problem is to represent exactly or approximately a given matrix as the Hadamard (or element-wise) product of two or more low-rank matrices. The motivation for this problem comes from situations where the input matrix has a multiplicative structure. The Hadamard decomposition has potential for giving more succint but equally accurate representations of matrices when compared with the gold-standard of singular value decomposition ( svd ). Namely, the Hadamard product of two rank- $$h$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>h</mml:mi> </mml:math> matrices can have rank as high as $${h}^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>h</mml:mi> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> . We study the computational properties of the Hadamard decomposition problem and give gradient-based algorithms for solving it approximately. We also introduce a mixed model that combines svd and Hadamard decomposition. We present extensive empirical results comparing the approximation accuracy of the Hadamard decomposition with that of the svd using the same number of basis vectors. The results demonstrate that the Hadamard decomposition is competitive with the svd and, for some datasets, it yields a clearly higher approximation accuracy, indicating the presence of multiplicative structure in the data.
Cited by 5Open access
Bálint Farkas, Szilárd Gy. Révész · Springer proceedings in mathematics & statistics · 2014
Cited by 2
Daniel Jackson, Michael Jackson · Software Engineering Journal · 1996
An approach to software development problems is presented and illustrated by an example. The approach is based on the ideas ofproblem frames and structuring specifications by views. It is claimed that decompositions obtained by this approach result in a more effective separation of concerns, and that the resulting components are more likely to be reusable than those obtained by more conventional approaches. The characteristics of desirable integration mechanisms are discussed, together with some other considerations arisingfrom the presented approach.
Cited by 46
Demeter Krupka Department, Demeter Krupka · 2007
. The problem of decomposition of mixed tensor spaces by the trace operation is considered. It is shown that a tensor A = i A i 1 i 2 :::i p k1 k2 :::k q j can always be expressed as the sum of a traceless term and a linear combination of the Kronecker&apos;s ffi-tensor, with traceless coefficients. The uniqueness of this decomposition is discussed. Particular cases of the trace decomposition of tensor spaces of type (1; 2), (1; 3), and (2; 2) including the cases of the torsion and curvature tensors, are considered, and explicit decomposition formulas are given. This analysis enables us to derive the Weyl projective, and Weyl conformal curvature tensors. Key words: Trace, traceless tensor, tensor space decomposition, torsion tensor, curvature tensor. MSC 1991: 15A72, 53A55 1. Introduction Let E be a real, n-dimensional vector space, E p q the vector space of tensors of type (p; q) on E. We always use a fixed basis of E, and the induced basis of E p q . Thus, if A 2 E p q is a ten...
Cited by 0
Daniel J. Jackson, Michael Jackson · 1995
Cited by 7
Maki Yoshida, Shigeo Mitsunari, Toru Fujiwara · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2010
This paper introduces a new computational problem on a two-dimensional vector space, called the vector decomposition problem (VDP), which is mainly defined for designing cryptosystems using pairings on elliptic curves. We first show a relation between the VDP and the computational Diffie-Hellman problem (CDH). Specifically, we present a sufficient condition for the VDP on a two-dimensional vector space to be at least as hard as the CDH on a one-dimensional subspace. We also present a sufficient condition for the VDP with a fixed basis to have a trapdoor. We then give an example of vector spaces which satisfy both sufficient conditions and on which the CDH is assumed to be hard in previous work. In this sense, the intractability of the VDP is a reasonable assumption as that of the CDH.
Cited by 8
Lucia Rapanotti, Jon G. Hall, Michael Jackson et al. · 2004
Jackson's problem frames provide a means of analysing and decomposing problems. They emphasise the world outside the computer helping the developer to focus on the problem domain instead of drifting into inventing solutions. The intention is to delay consideration of the solution space until a good understanding of the problem is gained. In contrast, early consideration of a solution architecture is common practice in software development. Software is usually developed by including existing components and/or reusing existing frameworks and architectures. This has the advantage of shortening development time through reuse, and increasing the robustness of a system through the application of tried and tested solutions. In This work, we show how these two views can be reconciled and demonstrate how a choice of architecture can facilitate problem analysis, decomposition and subsequent recomposition, within the problem frames framework. In particular, we introduce architectural frames - combinations of architectural styles and problem frames - and illustrate their use by applying them to two problems from the literature.
Cited by 35
Jon G Hall, Walton Hall, Lucia Rapanotti et al. · 2004
Jackson’s Problem Frames provide a means of analysing and decomposing problems. They emphasise the world outside of the computer helping the developer to focus on the problem domain instead of drifting into inventing solutions. The intention is to delay consideration of the solution space until a good understanding of the problem is gained. In contrast, early consideration of a solution architecture is common practice in software development. Software is usually developed by including existing components and/or reusing existing frameworks and architectures. This has the advantage of shortening development time though reuse, and increasing the robustness of a system through the application of tried and tested solutions. In this paper, we show how these two views can be reconciled and demonstrate how a choice of architecture can facilitate problem analysis and decomposition within the Problem Frames framework. In particular, we introduce Architectural Frames – combinations of architectural styles and Problem Frames – and illustrate their use in problem decomposition by applying them to a well-known problem from the literature. 1
Cited by 0
Yuri Prokhorov · arXiv (Cornell University) · 2002
We discuss different generalizations of Zariski decomposition, relations between them and connections with finite generation of divisorial algebras.
Cited by 9Open access
Diego Magro , et al. · 2002
In the present work the issue of decomposing a configuration problem is approached in a framework where the domain knowledge is represented in a structured way by using a KL-One like language and whole-part relations play a major role in defining the structure of the configurable objects. The representation formalism provides also a constraint language for expressing complex relations among components and subcomponents. The paper presents a notion of boundness among constraints which assures that two components not involved in a same set of bound constraints can be independently configured. The computation of boundness among constraints is the basis for partitioning constraints associated with each component to be configured. Such a partitioning induces a decomposition of the configuration problem into independent subproblems. Both a recursive and a non recursive decomposition strategies are presented and the savings in computational time and reduction in search space are shown in the domain of PC configuration.
Cited by 0
Christos Papatheodorou, Vangelis F. Magirou, Vangelis Kiountouzis · Applied Intelligence · 1993
Cited by 1
R. Vijaykumar, Michael A. Arbib · 2005
Automatic planning of an assembly task suitable for execution by a robot system requires analysis of constraints arising from task and object geometry as well as constraints arising from the specific configuration of the robot system. This paper describes our current efforts toward building a high-level planner that plans robot assembly tasks while confining its attention to constraints arising from task and object characteristics. The robot itself is modelled in terms of its basic capabilities such as, grasp, free motion and certain fine-motion commands. The planner works from a specification of the assembly operations, the objects involved in the operations, and an incomplete geometric model of the objects. The assembly planning problem is viewed as comprising of the determination of positions and orientations of component objects relative to each other and the determination of the robot motion primitives required to achieve these relations. The paper discusses how we decompose the assembly planning problem to reflect this view, the intermediate representations used, and our current implementations by use of an example assembly task.
Cited by 25
Y.A.J. Berendsen, H.P.M. Krammer · University of Twente Research Information · 1992
The use of programming plans is an important method for decomposing problems. The goal of this study was to gain insight into the usefulness of programming plans in teaching introductory computer programming. Subjects were students at a school for higher vocational education. Subjects' use of programming plans was observed by the inspection of programming products and the analysis of thinking-aloud protocols. The results indicated that the concept of programming plans given to the subjects must be told explicitly in order to get them to use these plans
Cited by 1Open access
Justinian Rosca, Michael Patrick Johnson, Michael Patrick et al. · 2007
Modular problem decomposition is often employed to cope with complex real-world problems. An intelligent decomposition can efficiently lead to compact and general solutions but is, in most cases, the result of laborious domain analysis and engineering. Little has been done to automatically discover natural decompositions of complex problems while simultaneously solving the subproblems; usually, a decomposition architecture must be specified in advance. This paper presents the Evolutionary Speciation Genetic Programming (ESGP) framework which evolves a problem decomposition as an ensemble of species whose members collectively solve the problem. Problem decomposition emerges as a result of speciation and specialization within each species. Speciation is facilitated by the symbiotic representation of individuals. Cooperation among species emerges through coevolution. We present experiments on complex, multi-regime function approximation problems to demonstrate and analyze the basic concep...
Cited by 0
Dorian Šuc, Ivan Bratko · Lecture notes in computer science · 2000
Cited by 10Open access
Luca Anselma, Diego Magro · 2003
In this work, we show how the decomposition of a problem into a set of simpler and independent subproblems can be applied to automatic configuration. In particular, we
Cited by 0
Vernhes, Simon · theses.fr (ABES) · 2014
Les algorithmes permettant la création de stratégies efficaces pour la résolution d’ensemble de problèmeshétéroclites ont toujours été un des piliers de la recherche en Intelligence Artificielle. Dans cette optique,la planification de tâches a pour objectif de fournir à un système la capacité de raisonner pour interagiravec son environnement de façon autonome afin d’atteindre les buts qui lui ont été assignés. À partir d’unedescription de l’état initial du monde, des actions que le système peut exécuter, et des buts qu’il doit atteindre,un planificateur calcule une séquence d’actions dont l’exécution permet de faire passer l’état du monde danslequel évolue le système vers un état qui satisfait les buts qu’on lui a fixés. Le problème de planification esten général difficile à résoudre (PSPACE-difficile), cependant certaines propriétés des problèmes peuvent êtreautomatiquement extraites permettant ainsi une résolution efficace.Dans un premier temps, nous avons développé l’algorithme LMBFS (Landmark-based Meta Best-First Search).À contre-courant des planificateurs state-of-the-art, basés sur la recherche heuristique dans l’espace d’états,LMBFS est un algorithme qui réactualise la technique de décomposition des problèmes de planification baséssur les landmarks. Un landmark est un fluent qui doit être vrai à un certain moment durant l’exécutionde n’importe quel plan solution. L’algorithme LMBFS découpe le problème principal en un ensemble desous-problèmes et essaie de trouver une solution globale grâce aux solutions trouvées pour ces sous-problèmes.Dans un second temps, nous avons adapté un ensemble de techniques pour améliorer les performances del’algorithme. Enfin, nous avons testé et comparé chacune de ces méthodes permettant ainsi la création d’unplanificateur efficace.
Cited by 0Open access