 |
    |
Automated Extraction of Problem Structure
Anthony Bucci*1, Jordan B. Pollack1, and Edwin de Jong2
1DEMO Lab, Brandeis University, Waltham MA 02454, USA
abucci@cs.brandeis.edu
pollack@cs.brandeis.edu
http://demo.cs.brandeis.edu/
2Decision Support Systems Group, Universiteit Utrecht
dejong@cs.uu.nl
Abstract. Most problems studied in artificial intelligence possess some form of structure, but a precise way to define such structure is so far lacking. We investigate how the notion of problem structure can be made precise, and propose a formal definition of problem structure. The definition is applicable to problems in which the quality of candidate solutions is evaluated by means of a series of tests. This specifies a wide range of problems: tests can be examples in classification, test sequences for a sorting network, or opponents for board games. Based on our definition of problem structure, we provide an automatic procedure for problem structure extraction, and results of proof-of-concept experiments. The definition of problem structure assigns a precise meaning to the notion of the underlying objectives of a problem, a concept which has been used to explain how one can evaluate individuals in a coevolutionary setting. The ability to analyze and represent problem structure may yield new insight into existing problems, and benefit the design of algorithms for learning and search.
*Corresponding author
LNCS 3102, p. 501 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004