Data processing: artificial intelligence – Neural network – Learning method
Reexamination Certificate
1997-03-31
2001-10-30
Davis, George B. (Department: 2122)
Data processing: artificial intelligence
Neural network
Learning method
C706S016000, C706S010000, C706S044000
Reexamination Certificate
active
06311174
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a data processing unit, more specifically to a problem solving apparatus for processing symbols, and provides a learning function for the problem solving apparatus.
2. Description of the Related Art
In the field of artificial intelligence, most problem solving methods being developed are based on a trial-and-error search concept. That is, a problem is solved by searching for one solution in a space where the solution can exist. The present invention is based on a problem solving apparatus operated by a tree searching method in the symbol process.
The tree searching method in the symbol process is described below by referring to a simple example.
FIGS. 1A and 1B
show an 8-tile puzzle. In this puzzle, there is an empty space of one frame and eight numbered tiles which are freely movable in the up, down, right, and left directions in a 3×3-block frame. When one of the numbered tiles above, below, right, and left of the space is moved into the space, the previous position of the moved number tile becomes the space. In other words, when the number tile is moved, the space appears to have moved.
In the 8-tile puzzle, a problem is that, for example, a starting pattern as shown in
FIG. 1A
is to be converted into a goal pattern as shown in FIG.
1
B. Assuming that moving the space once is regarded as one step, a solution is obtained by tracing a path to the goal pattern shown in
FIG. 1B
in the smallest possible number of steps.
FIG. 2
shows an example of the result of the tree searching process to solve the problem shown in
FIGS. 1A and 1B
.
In the tree structure, one state of the arrangement of the numbered tiles in the 8-tile puzzle is referred to as a “node”. That is,
FIG. 1A
shows the arrangement at a starting node,
FIG. 1B
shows the arrangement at a goal node. In the tree structure, each node has only one parent node except the starting node, which is a specific node having no parent node.
In the tree search, the efficiency of the searching process is greatly affected by the order from the starting node to the child nodes, that is, by how the nodes are expanded.
The order can be determined by, for example, a breadth-first method, a depth-first method, etc.
FIG. 2
shows a result of the breadth-first method. In the breadth-first method, nodes are sequentially expanded in the order in which the nodes were generated. In
FIG. 2
, the three child nodes
2
,
3
, and
4
are generated from the starting node
1
. That is, the nodes are first generated in the horizontal direction by priority, and the nodes in the first row (depth
1
), second row (depth
2
), . . . are generated in this order.
On the other hand, the last generated node is first expanded in the depth-first method. That is, nodes are generated in the order from the starting node
1
to nodes
2
,
5
,
10
,
20
,
11
,
21
, . . . That is, the nodes are expanded in the vertical direction by priority.
In
FIG. 2
, the goal node is obtained as a child node to node
26
, and the solution path to the problem shown in
FIGS. 1A and 1B
in the 8-tile puzzle is indicated by bold lines. By moving the space 5 times (in 5 steps), the starting pattern (
FIG. 1A
) is converted into the goal pattern (FIG.
1
B), and the goal node cannot be reached with a smaller number of times of moving the space.
FIG. 3
is a block diagram showing the configuration of the conventional problem solving apparatus operated in a symbol process.
In
FIG. 3
, a problem is generated by a problem generating apparatus
101
, and the generated problem is provided for the problem solving apparatus
100
.
The problem solving apparatus
100
performs the problem solving process as shown in
FIG. 2
until a solution can be obtained through a tree search, and comprises a node expanding apparatus
102
and a node evaluating apparatus
103
.
The node expanding apparatus
102
generates a child node from a parent node, that is, it expands nodes.
The node evaluating apparatus
103
evaluates the node expanded by the node expanding apparatus
102
as to whether or not the node refers to a goal node.
The processes of the node expanding apparatus
102
and node evaluating apparatus
103
are repeated until the solution is successfully obtained.
However, if a random searching method is followed by either the depth-first method or breadth-first method in the tree search, then the process of detecting a path to the goal node refers to a wasteful process. When the number of nodes expanded before the optimum path is detected is too large, a considerably long time and a large amount of stored information are spent on the search.
Conventionally, a solution can be obtained in a reduced search space and in a reasonable time by introducing information indicating the rule of thumb, that is, information referred to as heuristic knowledge. The word “heuristic” means “serving to discover”. The heuristic information is used to help a goal node be reached in the search by extending the most probable node first from experience.
In using the above described method, it is necessary for a user to appropriately detect the required heuristic knowledge and provide it to a problem solving apparatus, involving a great expenditure of labor and time.
Furthermore, in solving a problem already solved, the conventional problem solving apparatus again requires the process time spent in practically solving the problem first. That is, a problem similar to a problem solved already, requires the same process time, without shortening it.
SUMMARY OF THE INVENTION
The present invention aims at providing a problem solving apparatus having a learning function. The problem solving apparatus obtains a solution in a reasonable time without heuristic knowledge or through simple heuristic knowledge and obtains a solution within a short when solving the problem based on the leaving result of the already solved problem.
The problem solving apparatus having the learning function according to the present invention includes a problem solving unit for obtaining a solution in a symbol process upon receipt of a given problem, a (first) associative storage device for providing a (first) hint on solving the problem for the problem solving unit, and a learning control unit for making the (first) associative storage device perform a learning process.
The present invention can further include a second associative storage device for outputting a second hint on solving the problem upon receipt of the given problem, and a selecting unit for selecting the first hint output by the first associative storage device or the second hint output by the second associative storage device, and providing the selected hint for the problem solving unit.
When the problem solving unit of the above described problem solving apparatus receives a problem similar to a problem already solved, it obtains a solution within a short time by receiving a hint on solving the problem based on the learning result of the problem already solved.
REFERENCES:
patent: 5095443 (1992-03-01), Watanabe
patent: 5485545 (1996-01-01), Kojima et al.
patent: 5909681 (1999-06-01), Passera et al.
patent: 5995651 (1999-11-01), Gelenbe et al.
D.E. Moriarty and R. Miikkulainen, “Evolving Neural Networks to Focus Minimax Search,” Proceedings of the 12th National Conference on Artificial Intelligence, vol. 2, 1994, pp. 1371-1377, 1994.*
D.E. Moriarty and R. Miikkulainen, “Improving Game-Tree Search with Evolutionary Neural Networks,” Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, vol. 1, pp. 496-501, Jun. 1994.*
D.E. Moriarty and R. Miikkulainen, “Discovering Complex Othello Strategies Through Evolutionary Neural Networks,” Connection Science, vol. 7, (3), 1995, pp. 195-209.*
Y.-S. Chen and T.-H. Chu, A Neural Network Classification Tree, Proceedings of the IEEE International Conference on Neural Networks, 1995, vol. 1, pp. 409-413, Dec. 1995.*
Skapura, “a connectionist approach to heuristically pruning la
Davis George B.
Fujitsu Limited
Staas & Halsey , LLP
LandOfFree
Problem solving apparatus having learning function does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Problem solving apparatus having learning function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Problem solving apparatus having learning function will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2610751