Asynchronous partitioning framework

A new general framework for agent cooperation and coordination in solving distributed constraint satisfaction problems (DCSPs) is presented. The Asynchronous Partitioning Framework (APF) first partitions agents into groups of agents, based on some heuristic, prior to any search being conducted. During the partitioning phase one of the agents in each group is assigned the role of a group leader. Next, two distinct types of search processes among the agents are performed concurrently. The first type of search is conducted within each group, in parallel and asynchronously to all searches in other groups. The second type of search, the global search, is conducted between the groups, and treats each group as if it is a single agent represented by its group leader. The structure of the groups remains static throughout the search processes. Two distinct algorithms implementing APF are presented, and the advantages of APF are evaluated experimentally.