Abstract
In this paper we attempt to develop a problem representation technique which enables the decomposition of a problem into subproblems such that their solution in sequence constitutes a strategy for solving the problem. An important issue here is that the subproblems generated should be easier than the main problem. We propose to represent a set of problem states by a statement which is true for all the members of the set. A statement itself is just a set of atomic statements which are binary predicates on state variables. Then, the statement representing the set of goal states can be partitioned into its subsets each of which becomes a subgoal of the resulting strategy. The techniques involved in partitioning a goal into its subgoals are presented with examples.
Similar content being viewed by others
References
Amarel, S. (1968), ‘On Representation of Problems of Reasoning about Actions’, in D. Michie, ed.,Machine Intelligence 3, Edinburgh, Scotland: Edinburgh University Press.
Banerji, R. B. (1980),Artificial Intelligence: a Theoretical Approach New York, NY: North-Holland.
Ernst, G. W. and Goldstein, M. M. (1982), ‘Mechanical Discovery of Classes of Problem-Solving Strategies’,Journal of ACM 29, pp 1–23.
Ernst, G. W. and Newell, A. (1969),GPS: A Case Study in Generality and Problem Solving, New York, N.Y.: Academic Press.
Guvenir, H. A. and Ernst, G. W. (1990), ‘Learning Problem Solving Strategies Using Refinement and Marco Generation’,Artificial Intelligence 44, pp. 209–243.
Korf, R. E. (1985),Learning to Solve Problems by Searching for Macro-Operators, Boston, MA: Pitman Advanced Publishing Program.
Lauriere, J.-L. (1990),Problem Solving and Artificial Intelligence, London: Prentice-Hall.
Newell, A. and Simon, H. A. (1972),Human Problem Solving, Englewood Cliffs, N.J.: Prentice Hall.
Nourse, J. G. (1981),The Simple Solution to Rubik's Cube, New York: Bantam Books.
Simon, H. A. (1983), ‘Search and Reasoning in Problem Solving’,Artificial Intelligence 21, pp. 7–29.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Guvenir, H.A., Akman, V. Problem representation for refinement. Mind Mach 2, 267–282 (1992). https://doi.org/10.1007/BF02454223
Issue Date:
DOI: https://doi.org/10.1007/BF02454223