Current research on multi-agent coordination and distributed problem solving is still not robust or scalable enough to build large real-world collaborative agent societies because it relies on either centralised components with full knowledge of the domain or pre-defined social structures. Our approach allows overcoming these limitations by using a generic coordination framework for distributed problem solving on totally unstructured environments that enables each agent to decompose problems into sub-problems, identify those which it can solve and search for other agents to delegate the sub-problems for which it does not have the necessary knowledge or resources. Regarding the problem decomposition process, we have developed two distributed versions of the Graphplan planning algorithm. To allow an agent to discover other agents with the necessary skills for dealing with unsolved sub-problems, we have created two peer-to-peer search algorithms that build and maintain a semantic overlay network that connects agents relying on dependency relationships, which improves future searches. Our approach was evaluated using two different scenarios, which allowed us to conclude that it is efficient, scalable and robust, allowing the coordinated distributed solving of complex problems in unstructured environments without the unacceptable assumptions of alternative approaches developed thus far.

--

Multi-agent systems,Distributed planning,Coordination

• Computer and Information Sciences - Natural Sciences
• Electrical Engineering, Electronic Engineering, Information Engineering - Engineering and Technology

This publication is an output of the following project(s):

• Task Decomposition And Delegation Algorithms For Coordinating Agent Cooperation In Unstructured Open Agent Societies