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.


Agent’s paths through time for 3 agent types (A, B and C) completing 3 different types of tasks (TA, TB and TC)
© Copyright Policy - OpenAccess
Related In: Results  -  Collection


getmorefigures.php?uid=PMC4150994&req=5

Fig9: Agent’s paths through time for 3 agent types (A, B and C) completing 3 different types of tasks (TA, TB and TC)

Mentions: As task complexity increases, heterogenous agents are introduced. Figure 8 shows three experiments involving heterogenous agents and tasks: experiment #1 has two agent types A and B complete solo tasks half requiring agent type A and half requiring agent B. Experiment #2 contains the same scenario as found in experiment #1 except a third type of task is added that requires both agents A and B. Finally, experiment #3 contains three types of agents and three different tasks requiring agents A, AB and ABC, respectively. Agents are split evenly between the three types with uneven splits focusing on agent A then B first. Tasks are fixed at 20 in each simulation with a split of 8–6–6 between the three tasks A, AB and ABC. Figure 9 shows a typical assignment of experiment #3 with reduced tasks for visual clarity. A reduction in the communication required to meet a consensus is observed once a task requires all three equipped agent types. These results might be a consequent of the time constraints on the tasks which will limit the available options from the maximum 20 tasks down to a much easier to manage set of the earliest obtainable. In Fig. 9, for equipment-dependant multi-agent tasks, it is seen how agent C has very little choice in its assignments and causes no conflict with other agents because it must depend on its teammates to arrive and aid its tasks. Agent A freely moves between its tasks and, when required, aids its teammates. The reduced options for each agent greatly reduce the length of communication time required between team mates. More importantly, the reduced amount of conflicts caused helps agents come to a quick consensus with smaller communication exchanges.Fig. 8


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)

Agent’s paths through time for 3 agent types (A, B and C) completing 3 different types of tasks (TA, TB and TC)
© Copyright Policy - OpenAccess
Related In: Results  -  Collection

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

Fig9: Agent’s paths through time for 3 agent types (A, B and C) completing 3 different types of tasks (TA, TB and TC)
Mentions: As task complexity increases, heterogenous agents are introduced. Figure 8 shows three experiments involving heterogenous agents and tasks: experiment #1 has two agent types A and B complete solo tasks half requiring agent type A and half requiring agent B. Experiment #2 contains the same scenario as found in experiment #1 except a third type of task is added that requires both agents A and B. Finally, experiment #3 contains three types of agents and three different tasks requiring agents A, AB and ABC, respectively. Agents are split evenly between the three types with uneven splits focusing on agent A then B first. Tasks are fixed at 20 in each simulation with a split of 8–6–6 between the three tasks A, AB and ABC. Figure 9 shows a typical assignment of experiment #3 with reduced tasks for visual clarity. A reduction in the communication required to meet a consensus is observed once a task requires all three equipped agent types. These results might be a consequent of the time constraints on the tasks which will limit the available options from the maximum 20 tasks down to a much easier to manage set of the earliest obtainable. In Fig. 9, for equipment-dependant multi-agent tasks, it is seen how agent C has very little choice in its assignments and causes no conflict with other agents because it must depend on its teammates to arrive and aid its tasks. Agent A freely moves between its tasks and, when required, aids its teammates. The reduced options for each agent greatly reduce the length of communication time required between team mates. More importantly, the reduced amount of conflicts caused helps agents come to a quick consensus with smaller communication exchanges.Fig. 8

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.