Exploiting the Physics of State-Space Search

Robert Levinson

This paper is a blueprint for the development of a fully domain-independent single agent and multi-agent heuristic search system. The paper gives a graph-theoretic representation of search problems based on conceptual graphs, and outlines two different learning systems. One, an "informed learner" makes use of the the graph-theoretic definition of a search problem or game in playing and adapting to a game in the given environment. The other a "blind learner" is not given access to the rules of a domain, but must discover and then exploit the underlying mathematical structure of a given domain. These learning agents are based on generalizing the understanding obtained with the Morph chess system to all games involving the interactions of abstract mathematical relations. Blind learner can be viewed as a type of neural network that makes explicit use of fuzzy graph-isomorphism to exploit at a "meta-level" analogous states of the net itself. Publically available software has been developed for supporting research in blind learning and informed learning in the context of general problem-solving. The paper is based on studying the graph-theoretic structure of large open problems in machine learning research and giving a reasoned, unifying, framework for working toward their solution. In a field seeking comprehensive theories and general testbeds we hope that providing such a framework and software for exploration is an important contribution. The ultimate success of the framework awaits further investigation.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.