Search

Coalition formation in social networks consisting of a graph of interdependent agents allows many choices of which task to select and with whom to partner in the social network. Agents communicate with agents within n network links in their surrounding network. These agents are considered part of an agent's local neighborhood. Agents maintain a database of skills possessed by agents in their local neighborhood. We introduce agents who use the information gathered from their local neighborhood to modify their network links to discover effective network structures. Egalitarian agents seek equal distribution of connections among agents, resulting in a dense network structure. Inventory agents seek to connect to agents who possess a skill not found in their current local neighborhood.

Replanning, which discards all alternatives found in previous execution, and step-by-step backtracking, which iterates back through all previous selection decisions, are two extreme ends of exception handling in agent systems. We describe a new "jump" approach to maintaining a tradeoff between them. Choice points, which are maintained in a stack, are introduced to record all plans found by the agent's planning procedures. By iterating on the stack, and reasoning about plan characteristics, an agent can find and launch a suitable plan prior to or in parallel with a compensation process for the failed path, thus achieving its goals efficiently in the presence of exceptions. Our approach combines and utilizes several beneficial features of a BDI agent, such as its data structure and deliberation cycle, together with an open nested transaction system which supports architectural-level concurrency control and distribution management.