Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks

Area of Science:

• Computational Neuroscience
• Artificial Intelligence
• Cognitive Science

Background:

• Decision-making relies on satisfying constraints from external and internal sources.
• Constraint satisfaction problems (CSPs) are fundamental in various computational and cognitive tasks.

Purpose of the Study:

• To demonstrate that specific classes of CSPs can be solved using neural networks with neocortical-like connectivity.
• To explore the computational principles underlying decision-making in neural circuits.

Main Methods:

• Designing networks of homogeneous cooperative-competitive modules with winner-take-all dynamics.
• Utilizing programming neurons to embed constraints for problems like graph coloring, maximum independent set, and Sudoku.
• Employing nonsaturating linear threshold neurons and analyzing network dynamics, including recurrent excitation and inhibition.

Main Results:

• Successfully mapped CSPs, including planar four-color graph coloring, maximum independent set, and Sudoku, onto the proposed neural substrate.
• Provided mathematical proofs for the convergence of graph coloring problems.
• Demonstrated that network instability, driven by recurrent excitation, is crucial for exploring the problem space.
• Showed performance benefits for hard problems using nonlinear multiplicative inhibition compared to linear inhibition.

Conclusions:

• Neural networks with specific modular and connectivity patterns can solve complex constraint satisfaction problems.
• Network instability and dual inhibitory mechanisms (linear and nonlinear) are vital for efficient neural computation and decision-making.