Improving the Performances of Asynchronous Algorithms by Combining the Nogood Processors with the Nogood Learning Techniques

Article type: Research Article

Authors: Muscalagiu, Ionel | Cretu, Vladimir

Affiliations: The Faculty of Engineering of Hunedoara, The Politehnica University of Timisoara, Hunedoara, str. Revolutiei, nr. 5, Romania, e-mail: mionel@fih.utt.ro | Computers Science and Engineering Department Timisoara, The Politehnica University of Timisoara, Timisoara, str. V. Parvan, nr. 2, Romania, e-mail: vcretu@cs.utt.ro

Abstract: The asynchronous techniques that exist within the programming with distributed constraints are characterized by the occurrence of the nogood values during the search for the solution. The nogood type messages are sent among the agents with the purpose of realizing an intelligent backtrack and of ensuring the algorithm's completion. In this article we analyzed the way in which a technique of obtaining efficient nogood values could combine with a technique of storing these values. In other words we try combining the resolvent-based learning technique introduced by Yokoo with the nogood processor technique in the case of asynchrounous weak-commitment search algorithm (AWCS). These techniques refer to the possibility of obtaining efficient nogoods, respectively to the way the nogood values are stored and the later use of information given by the nogoods in the process of selecting a new value for the variables associated to agents. Starting from this analysis we proposed certain modifications for the two known techniques. We analyzed the situations in which the nogoods are distributed to more nogood processors handed by certain agents. We proposed a solution of distributing the nogood processors to the agents regarding the agents' order, with the purpose of reducing the storing and searching costs. We also analyzed the benefits the combining of nogood processor technique with the resolved-based learning technique could bring to the enhancement of the performance of AWCS technique. Finally, we analyzed the behavior of the techniques obtained in the case of messages filtering.

Keywords: artificial intelligence, distributed programming, constraints, agents, nogood messages

Journal: Informatica, vol. 17, no. 1, pp. 39-54, 2006