Abstract

This thesis extends an existing bio-inspired model for decentralized task allocation and benchmarks it against alternative approaches to assess robustness in dynamic conditions, applicability to domains with ongoing and hierarchical tasks, and scalability to large teams of agents. The work addresses decentralized task allocation of simple non-communicating agents in dynamic environments of multiple tasks. Multi-area patrolling is used as the sample domain: specific number of agents is required to successfully patrol each area on each timestep, indefinitely, until the system's security needs. Agents must individually decide whether to patrol and where (i.e., task availability is not limited by task demand nor by other agents' actions). Insufficient patrolling decreases security, while excess patrolling is wasteful and can lead to interference. Additionally, patrolling efforts cannot be accumulated: patrolling more now does not reduce patrolling needs later. Patrolling is also never completed, requiring ongoing agent action from a subset of the agents. Consequently, we term such tasks as "ongoing". Other examples include exploration, perishable resource gathering, diagnostics, and maintenance. The presented research showcases the differences between adaptation and readaptation behaviors in dynamic task allocation. Experiments show that readaptation can be turned to adaptation through forgetting of learned behaviors. Stability of the emergent task allocation is first considered as averaged across multiple steps and then across individual steps. A Genetic Algorithm is implemented to evolve newly defined algorithm parameters to improve task allocation adaptability and stability at the step level. Finally, a series of experiments are performed to compare three Learning Automata amenable to the decentralized task allocation of ongoing tasks with dynamically changing demands. The approaches are compared based on how quickly and accurately agents adapt to new demands, as well as by the resulting level of agent specialization, since specialized action is generally considered beneficial to performance. Testing also addresses: whether agents can readapt after an initial adaptation; whether agents can learn to become active or to idle, as needed; and whether agents spread their work proportionately across tasks when there are too few to fulfill all task demands, or whether some tasks are continuously neglected in favor of others. Additionally, as all system tasks are always available to each agent, three task selection strategies are considered for each approach. Results showcase what adaptation behavior can be expected from each tested automata and selection strategy combination under the different domain conditions. While different tested combinations offer advantages under different testing conditions, no approach is perfect, with the observed shortcomings paving the way for future methodologies.

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

2020

Semester

Spring

Advisor

Sukthankar, Gita

Degree

Doctor of Philosophy (Ph.D.)

College

College of Engineering and Computer Science

Department

Computer Science

Degree Program

Computer Science

Format

application/pdf

Identifier

CFE0007974; DP0023115

URL

https://purls.library.ucf.edu/go/DP0023115

Language

English

Release Date

5-15-2020

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Download

Share

COinS