Divide and (Iteratively) Conquer!

摘要

The Iterative Multi-Agent (IMA) Method works by breaking down a search problem into many sub-problems, each to be solved separately. Independent problem solving agents work on the sub-problems and use iteration to handle any interaction between the sub-problems. Each agent knows about a subset of the whole problem and cannot solve it all by itself. The agents, working in parallel, can use any method to solve their assigned sub-problem. 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 solution to the whole problem then emerges as a result of these local activities. This requires the problem to be decomposable into smaller ones. The paper gives an example of constraint satisfaction problem solving. We solve randomly generated Traveling Salesman Problems, and compare the results with those of other methods.