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 for tasks that require previous tasks completed. Exp #1 used multi-agent tasks with no task dependency. Exp #2 and #3 both added task dependencies but Exp #3 removed the time requirement on follow-up tasks. Markers (×) used to show communication steps for consensus
© Copyright Policy - OpenAccess
Related In: Results  -  Collection


getmorefigures.php?uid=PMC4150994&req=5

Fig10: Comparison of total score and number of communication steps for tasks that require previous tasks completed. Exp #1 used multi-agent tasks with no task dependency. Exp #2 and #3 both added task dependencies but Exp #3 removed the time requirement on follow-up tasks. Markers (×) used to show communication steps for consensus

Mentions: Figures 10 and 11 show the introduction of tasks that have prerequisites where a specific task must be scheduled for completion before the task with the prerequisite requirement is assigned. It shows that compared to CBGA tasks found in experiment #1, the number of communication messages sent to reach a consensus is usually lower with the additional restrictions. By putting these prerequisite requirements on half the tasks in the simulation, we reduce the number of tasks that agents find conflict over, with the follow-up tasks having fewer conflicts. Experiment #2 contained a problem where the task time window for completion was randomly generated. In some cases, this meant a task with requirements was set before that of the requirement. This error created a number of tasks that could never be achieved and therefore limited the overall score obtainable. Interestingly, when these time limits were removed in experiment three, the average score decreased even though more tasks had become available. This might be because only agents who were involved in the prerequisite could attempt the follow-up task, but often they would be busy completing other tasks. Although in contrast after opening up accessibility on these tasks, the overall communication levels increased. When tasks are made accessible to everyone, points of conflict are amplified and therefore the number of communication steps required to come to a consensus is also increased. By limiting tasks to a small subset of agents, the overall requirements on communication for consensus decrease.Fig. 10


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 for tasks that require previous tasks completed. Exp #1 used multi-agent tasks with no task dependency. Exp #2 and #3 both added task dependencies but Exp #3 removed the time requirement on follow-up tasks. Markers (×) used to show communication steps for consensus
© Copyright Policy - OpenAccess
Related In: Results  -  Collection

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

Fig10: Comparison of total score and number of communication steps for tasks that require previous tasks completed. Exp #1 used multi-agent tasks with no task dependency. Exp #2 and #3 both added task dependencies but Exp #3 removed the time requirement on follow-up tasks. Markers (×) used to show communication steps for consensus
Mentions: Figures 10 and 11 show the introduction of tasks that have prerequisites where a specific task must be scheduled for completion before the task with the prerequisite requirement is assigned. It shows that compared to CBGA tasks found in experiment #1, the number of communication messages sent to reach a consensus is usually lower with the additional restrictions. By putting these prerequisite requirements on half the tasks in the simulation, we reduce the number of tasks that agents find conflict over, with the follow-up tasks having fewer conflicts. Experiment #2 contained a problem where the task time window for completion was randomly generated. In some cases, this meant a task with requirements was set before that of the requirement. This error created a number of tasks that could never be achieved and therefore limited the overall score obtainable. Interestingly, when these time limits were removed in experiment three, the average score decreased even though more tasks had become available. This might be because only agents who were involved in the prerequisite could attempt the follow-up task, but often they would be busy completing other tasks. Although in contrast after opening up accessibility on these tasks, the overall communication levels increased. When tasks are made accessible to everyone, points of conflict are amplified and therefore the number of communication steps required to come to a consensus is also increased. By limiting tasks to a small subset of agents, the overall requirements on communication for consensus decrease.Fig. 10

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.