The goal of the research that led to the original introduction of Neurosolver was to design a neuromorphic device that would be able to solve problems in the framework of the state space paradigm. Fundamentally, in this paradigm, a question is asked how to navigate a system through its state space so it transitions from the current state into some desired goal state. The states of a system are expressed as points in an n-dimensional space. Trajectories in such spaces formed by state transitions represent behavioral patterns of the system. A problem is presented in this paradigm as a pair of two states: the current state and the desired, or goal, state. A solution to the problem is a trajectory between the two states in the state space.

The Neurosolver can solve such problems by first building a behavioral model of the system and then by traversing the recorded trajectories during both searches and resolutions as will be described in the next section.

The learning in the Neurosolver is probabilistic, so in many respects this approach is similar to Markov Models (Markov, 2006).

Inspirations from Neuroscience

The original research on Neurosolver modeling was inspired by Burnod’s monograph on the workings of the human brain. The class of systems that employ state spaces to present and solve problems has its roots in the early stages of AI research that derived many ideas from the studies of human information processing; among them on General Problem Solver (GPS) (Newell and Simon, 1963). This pioneering work led to very interesting problem solving (e.g. SOAR (Laird, Newell, and Rosenbloom, 1987)) and planning systems (e.g. STRIPS (Nillson, 1980)).

The Neurosolver employs activity spreading techniques that have their root in early work on semantic networks (e.g., (Collins and Loftus, 1975) and (Anderson, 1983)).

Neurosolver

The Neurosolver is a network of interconnected nodes. Each node is associated with a state in a problem space. Rather than considering all possible states of the subject system, Neurosolver generates nodes only for states that were explicitly used during the training, although in principle, in the future, some hardware platform could be easier to implement with provisions for all states rather than creating them on demand. In its original application, the Neurosolver is presented with a problem by two signals: the goal associated with
the desired state and the sensory signal associated with the current state. A sequence of firing nodes that the Neurosolver generates represents a trajectory in the state space. Therefore, a solution to the given problem is a succession of firing nodes starting
with the node corresponding to the current state of the system, and ending with the node corresponding to the desired state of the system.

The node used in the Neurosolver is based on a biological cortical column. It consists of two divisions: the upper and the lower, as illustrated in the figure. The upper division is a unit int
egrating internal signals from other upper divisions and from the
control center providing the limbic input (i.e., a goal or — using more psychological terms — a drive or desire). The activity of the upper division is transmitted to the lower division where it is subsequently integrated with signals from other lower divisions and the thalamic (i.e., sensory) input. The upper divisions constitute a network of units that propagate search activity from the goal, while the lower divisions constitute a network of threshold units that integrate search and sensory signals. A sequence of outputs of the lower divisions of the network constitutes Neurosolver’s output: a response of the network to the input stimuli

The function of the network of upper divisions is to spread the search activity along the intra-cortical (i.e., upper-to-upper division) connections starting at the original source of activity: the node associated with the goal state that receives the limbic input (representing what is desired). This can be described as a search network because the activity spreads out in reverse order from that node along the learned trajectories in hope of finding a node that receives excitatory thalamic input that indicates that the node corresponds to the current state of the system. At that node, the activities of the upper and lower divisions are integrated, and if the combined activity exceeds the output threshold, the node fires. The firing node is the trigger of a resolution. The resolution might be only one of many, but due to the probabilistic learning it is best in the sense that it was the most common in the training. The process of spreading activity in a search tree is called goal regression (Nillson, 1980).

 

The purpose of the network composed of lower divisions and their connections is to generate a sequence of output signals from firing nodes (along the connections shown in the figure). Such a sequence corresponds to a path between the current state and the goal state, so it can be considered a solution to the problem. As we said, a firing of the node representing the current state triggers a solution. Each subsequent firing node sends action potentials through the outgoing connections of its lower division. These signals may cause another node to fire especially if that node’s attention (i.e., the activity in the upper division; also called expectation) is sufficiently high, as that may indicate that the node is part of the search tree. In a way, the process of selecting the successor in the resolution path is a form of selecting the node most susceptible to firing. A firing node is inhibited for some time afterwards to avoid oscillations. The length of the inhibition determines the length of cycles that can be prevented. Neurosolver exhibits goal-oriented behavior similar to that introduced in (Deutsch, 1960).

Two approaches to determining connection strength of inter-nodal connections has been implemented. In the probabilistic approach, the strength is computed as a function of two probabilities: the probability that a firing source node will generate an action potential in this particular connection, and the probability that the target node will fire upon receiving an action potential from the connection. To compute the probabilities, statistics for each division of the node (upper and lower) and each connection are collected. The number of transmissions of an action potential T_out is recorded for each connection. The total number of cases when a division positively influenced other nodes S_out is collected for each division. A positive influence means that an action potential sent from a division of a firing node to another node caused that second node to fire in the next time tick. In addition, statistical data that relate to incoming signals is also collected. T_in is the number of times when an action potential transmitted over the connection contributed to the firing of the target node and is collected for each connection. S_in, collected for each division, is the total number of times when any node positively influenced the node. With such statistical data, we can calculate the probability that an incoming action potential will indeed cause the target node to fire. The final formula that is used for computing the strength of a connection (shown in Equation 1) is the likelihood that a firing source node will induce an action potential in the outgoing connection, multiplied by the likelihood that the target node will fire due to an incoming signal from that connection:

P = Pout⋅Pin = (Tout/Sout)⋅(Tin/ Sin)

(1)

 

In the second approach, following the principle of Hebbian learning that is biologically more plausible, the strength of the connection is determined by its weight that is adjusted at every presentation of a training pattern (a sequence) that includes the nodes linked by the connection. In this traditional method used in most neural networks, the weights are adjusted by a small value. In Neurosolver, the weights are normalized to keep their growth under control.

Exploratory Applications

The Neurosolver’s capabilities have been tested in a number of applications. Please check the publications section for details.

Classical Blocks World

Rat Maze Running

Towers of Hanoi

TicTacToe

References

Newell, A. and Simon, H. A., 1963. GPS: A program that simulates human thought. In Feigenbaum, E. A. and Feldman, J. (Eds.), Computer and Thought. New York, NJ: McGrawHill.

Burnod, Y., 1988. An Adaptive Neural Network: The Cerebral Cortex, Paris, France: Masson.

Laird, J. E., Newell, A. and Rosenbloom, P. S., 1987. SOAR: An architecture for General Intelligence. In Artificial Intelligence, 33: 1–64.

Nillson, N. J., 1980. Principles of Artificial Intelligence, Palo Alto, CA: Tioga Publishing Company.

Deutsch, M., 1960. The Effect Of Motivational Orientation Upon Trust And Suspicion. In Human Relations, 13: 123–139.

Collins, Allan M.; Loftus, Elizabeth F., 1975. A Spreading-Activation Theory of Semantic Processing. In Psychological Review. Vol 82(6) 407-428.

Anderson, J. R., 1983. A spreading activation theory of memory. In Journal of Verbal Learning and Verbal Behavior, 22, 261-295.

Stewart, B. M. and Frame, J. S., 1941. Solution to Advanced Problem 3819. In The American Mathematical Monthly Vol. 48, No. 3 (Mar., 1941), pp. 216-219

Markov, A. A., 2006. An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains (translation. by David Link). In Science in Context 19.4: 591-600.

Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.). Upper Saddle River, NJ: Prentice Hall, pp. 111-114.