Premium
Constraint reasoning with learning automata
Author(s) -
Ricci Francesco
Publication year - 1994
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.4550091203
Subject(s) - backtracking , learning automata , computer science , speedup , constraint learning , set (abstract data type) , automaton , constraint satisfaction problem , constraint satisfaction , constraint (computer aided design) , artificial intelligence , mathematical optimization , algorithm , theoretical computer science , constraint logic programming , mathematics , probabilistic logic , geometry , programming language , operating system
This article presents a decision‐maker model, called learning automaton, exhibiting adaptive behavior in highly uncertain stochastic environments. This learning model is used in solving constraint satisfaction problems (CSPs) by a procedure that can be viewed as hill climbing in probability space. the use of a fast learning algorithm that relaxes previous common assumptions is investigated. It is proven that the algorithm converges with probability 1 to a solution of the CSP and a set of test problems show that good performance can be achieved. In particular, it is shown that this method achieves a higher level of performance than that presented in a previous similar approach. Finally, it is estimated the speedup of a parallel implementation and the proposed algorithm is compared with a backtracking algorithm enhanced with standard CSP techniques. © 1994 John Wiley & Sons, Inc.