Limits...
A Consensus-Based Grouping Algorithm for Multi-agent Cooperative Task Allocation with Complex Requirements.

Hunt S, Meng Q, Hinde C, Huang T - Cognit Comput (2014)

Bottom Line: Inspiration is taken from the cognitive behaviours of eusocial animals for cooperation and improved assignments.Further extensions are provided to improve task complexity handling by the agents with added equipment requirements and task dependencies.Simulation results demonstrate reduced data usage and communication time to come to a consensus on multi-agent tasks.

View Article: PubMed Central - PubMed

Affiliation: Department of Computer Science, Loughborough University, Loughborough, UK.

ABSTRACT
This paper looks at consensus algorithms for agent cooperation with unmanned aerial vehicles. The foundation is the consensus-based bundle algorithm, which is extended to allow multi-agent tasks requiring agents to cooperate in completing individual tasks. Inspiration is taken from the cognitive behaviours of eusocial animals for cooperation and improved assignments. Using the behaviours observed in bees and ants inspires decentralised algorithms for groups of agents to adapt to changing task demand. Further extensions are provided to improve task complexity handling by the agents with added equipment requirements and task dependencies. We address the problems of handling these challenges and improve the efficiency of the algorithm for these requirements, whilst decreasing the communication cost with a new data structure. The proposed algorithm converges to a conflict-free, feasible solution of which previous algorithms are unable to account for. Furthermore, the algorithm takes into account heterogeneous agents, deadlocking and a method to store assignments for a dynamical environment. Simulation results demonstrate reduced data usage and communication time to come to a consensus on multi-agent tasks.

No MeSH data available.


Comparison of total score and number of communication steps between the CBBA, CBGA and using both. Markers (×) used to show communication steps for consensus
© Copyright Policy - OpenAccess
Related In: Results  -  Collection


getmorefigures.php?uid=PMC4150994&req=5

Fig5: Comparison of total score and number of communication steps between the CBBA, CBGA and using both. Markers (×) used to show communication steps for consensus

Mentions: To test the relative effectiveness of multi-agent task assignments, comparisons are drawn to that of the CBBA where each task requires a single agent. Using the CBGA, Fig. 4 shows the successful assignment of multi-agent tasks where each task requires two agents, the experiment is run in three dimensions but for easier visualisation only displayed in one dimension over time. Figure 5 has three experiments plotted that tested both algorithms, single-agent tasks use the CBBA and multi-agent tasks use the CBGA. The first experiment used just the CBBA where each task required a single agent to complete it. The second experiment tested the CBGA by requiring two agents to complete each task, and the assignments are seen in Fig. 4. The final experiment used both types of tasks making the agents consensus on assignments for 10 multi-agent tasks and 10 single-agent tasks.Fig. 4


A Consensus-Based Grouping Algorithm for Multi-agent Cooperative Task Allocation with Complex Requirements.

Hunt S, Meng Q, Hinde C, Huang T - Cognit Comput (2014)

Comparison of total score and number of communication steps between the CBBA, CBGA and using both. Markers (×) used to show communication steps for consensus
© Copyright Policy - OpenAccess
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC4150994&req=5

Fig5: Comparison of total score and number of communication steps between the CBBA, CBGA and using both. Markers (×) used to show communication steps for consensus
Mentions: To test the relative effectiveness of multi-agent task assignments, comparisons are drawn to that of the CBBA where each task requires a single agent. Using the CBGA, Fig. 4 shows the successful assignment of multi-agent tasks where each task requires two agents, the experiment is run in three dimensions but for easier visualisation only displayed in one dimension over time. Figure 5 has three experiments plotted that tested both algorithms, single-agent tasks use the CBBA and multi-agent tasks use the CBGA. The first experiment used just the CBBA where each task required a single agent to complete it. The second experiment tested the CBGA by requiring two agents to complete each task, and the assignments are seen in Fig. 4. The final experiment used both types of tasks making the agents consensus on assignments for 10 multi-agent tasks and 10 single-agent tasks.Fig. 4

Bottom Line: Inspiration is taken from the cognitive behaviours of eusocial animals for cooperation and improved assignments.Further extensions are provided to improve task complexity handling by the agents with added equipment requirements and task dependencies.Simulation results demonstrate reduced data usage and communication time to come to a consensus on multi-agent tasks.

View Article: PubMed Central - PubMed

Affiliation: Department of Computer Science, Loughborough University, Loughborough, UK.

ABSTRACT
This paper looks at consensus algorithms for agent cooperation with unmanned aerial vehicles. The foundation is the consensus-based bundle algorithm, which is extended to allow multi-agent tasks requiring agents to cooperate in completing individual tasks. Inspiration is taken from the cognitive behaviours of eusocial animals for cooperation and improved assignments. Using the behaviours observed in bees and ants inspires decentralised algorithms for groups of agents to adapt to changing task demand. Further extensions are provided to improve task complexity handling by the agents with added equipment requirements and task dependencies. We address the problems of handling these challenges and improve the efficiency of the algorithm for these requirements, whilst decreasing the communication cost with a new data structure. The proposed algorithm converges to a conflict-free, feasible solution of which previous algorithms are unable to account for. Furthermore, the algorithm takes into account heterogeneous agents, deadlocking and a method to store assignments for a dynamical environment. Simulation results demonstrate reduced data usage and communication time to come to a consensus on multi-agent tasks.

No MeSH data available.