The Iterative MultiAgent Method for Solving Complex Search Problems.pdf

The Iterative Multi-Agent Method for Solving Complex Search Problems Kamran Karimi Department of Computer Science University of Regina Regina, Saskatchewan Canada S4S 0A2 karimi@cs.uregina.ca Abstract. This paper introduces a problem solving method involving independent agents and a set of partial solutions. In the Iterative Multi-Agent (IMA) method, each agent knows about a subset of the whole problem and can not solve it all by itself. An agent picks a partial solution from the set and then applies its knowledge of the problem to bring that partial solution closer to a total solution. This implies that the problem should be composed of sub- problems, which can be attended to and solved independently. When a real- world problem shows these characteristics, then the design and implementation of an application to solve it using this method is straightforward. The solution to each sub-problem can affect the solutions to other sub-problems, and make them invalid or undesirable in some way, so the agents keep checking a partial solution even if they have already worked on it. The paper gives an example of constraint satisfaction problem solving, and shows that the IMA method is highly parallel and is able to tolerate hardware and software faults. Considerable improvements in search speed have been observed in solving the example constraint satisfaction problem. 1 Introduction Encoding a real-world problem to be solved by a computer is often time consumin