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.


Bundle construction for the CBGA
© Copyright Policy - OpenAccess
Related In: Results  -  Collection


getmorefigures.php?uid=PMC4150994&req=5

Fig1: Bundle construction for the CBGA

Mentions: The bundle algorithm shown in Fig. 1 is similar to that in the CBBA [11] but uses different costing functions, data storage and allows multiple assignments. The bidding aspect of the algorithm will not change with the complexity of tasks; however, the cost functions will change as the deciding factor in who should complete a task. However, assignments for multi-agent tasks will function differently to the CBBA. Multi-agent tasks are added to the valid task list hij when either the task is not full (line 9, Fig. 1) or the task is full but the agent has a higher bid than smallest current bid in the task (line 11, Fig. 1). Single-agent tasks are added to the valid task list hij in the same way as the CBBA (line 17, Fig. 1) where I(·) is the unity if the argument is true and zero otherwise. From the list of valid tasks hij, the task that provides the greatest improvement in score at position ni,ji in the path pi is selected and added to the agent’s assignments. This process is repeated until the agent is unable to add any more tasks that improve its score.Fig. 1


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)

Bundle construction for the CBGA
© Copyright Policy - OpenAccess
Related In: Results  -  Collection

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

Fig1: Bundle construction for the CBGA
Mentions: The bundle algorithm shown in Fig. 1 is similar to that in the CBBA [11] but uses different costing functions, data storage and allows multiple assignments. The bidding aspect of the algorithm will not change with the complexity of tasks; however, the cost functions will change as the deciding factor in who should complete a task. However, assignments for multi-agent tasks will function differently to the CBBA. Multi-agent tasks are added to the valid task list hij when either the task is not full (line 9, Fig. 1) or the task is full but the agent has a higher bid than smallest current bid in the task (line 11, Fig. 1). Single-agent tasks are added to the valid task list hij in the same way as the CBBA (line 17, Fig. 1) where I(·) is the unity if the argument is true and zero otherwise. From the list of valid tasks hij, the task that provides the greatest improvement in score at position ni,ji in the path pi is selected and added to the agent’s assignments. This process is repeated until the agent is unable to add any more tasks that improve its score.Fig. 1

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.