Addressing robustness in time-critical, distributed, task allocation algorithms.

Journal article


Whitbrook, Amanda, Meng, Qinggang and Chung, Paul W. H. 2018. Addressing robustness in time-critical, distributed, task allocation algorithms. Applied Intelligence. https://doi.org/10.1007/s10489-018-1169-3
AuthorsWhitbrook, Amanda, Meng, Qinggang and Chung, Paul W. H.
Abstract

The aim of this work is to produce and test a robustness module (ROB-M) that can be generally applied to distributed, multi-agent task allocation algorithms, as robust versions of these are scarce and not well-documented in the literature. ROB-M is developed using the Performance Impact (PI) algorithm, as this has previously shown good results in deterministic trials. Different candidate versions of the module are thus bolted on to the PI algorithm and tested using two different task allocation problems under simulated uncertain conditions, and results are compared with baseline PI. It is shown that the baseline does not handle uncertainty well; the task-allocation success rate tends to decrease linearly as degree of uncertainty increases. However, when PI is run with one of the candidate robustness modules, the failure rate becomes very low for both problems, even under high simulated uncertainty, and so its architecture is adopted for ROB-M and also applied to MIT’s baseline Consensus Based Bundle Algorithm (CBBA) to demonstrate its flexibility. Strong evidence is provided to show that ROB-M can work effectively with CBBA to improve performance under simulated uncertain conditions, as long as the deterministic versions of the problems can be solved with baseline CBBA. Furthermore, the use of ROB-M does not appear to increase mean task completion time in either algorithm, and only 100 Monte Carlo samples are required compared to 10,000 in MIT’s robust version of the CBBA algorithm. PI with ROB-M is also tested directly against MIT’s robust algorithm and demonstrates clear superiority in terms of mean numbers of solved tasks.

KeywordsHueristic algorythms; Multi-agent systems; Computer science; Robust optimization
Year2018
JournalApplied Intelligence
PublisherSpringer
ISSN0924669X
15737497
Digital Object Identifier (DOI)https://doi.org/10.1007/s10489-018-1169-3
Web address (URL)http://hdl.handle.net/10545/622608
hdl:10545/622608
Publication dates18 Apr 2018
Publication process dates
Deposited19 Apr 2018, 15:20
Rights

Archived with thanks to Applied Intelligence

ContributorsUniversity of Derby and Loughborough University
File
File Access Level
Open
File
File Access Level
Open
Permalink -

https://repository.derby.ac.uk/item/93wxq/addressing-robustness-in-time-critical-distributed-task-allocation-algorithms

Download files

  • 57
    total views
  • 25
    total downloads
  • 1
    views this month
  • 2
    downloads this month

Export as

Related outputs

A novel distributed scheduling algorithm for time-critical multi-agent systems.
Whitbrook, Amanda, Meng, Qinggang and Chung, Paul W. H. 2015. A novel distributed scheduling algorithm for time-critical multi-agent systems. IEEE. https://doi.org/10.1109/IROS.2015.7354299
Juxtaposition of system dynamics and agent-based simulation for a case study in immunosenescence.
Figueredo, Grazziela P., Siebers, Peer-Olaf, Aickelin, Uwe, Whitbrook, Amanda and Garibaldi, Jonathan M. 2015. Juxtaposition of system dynamics and agent-based simulation for a case study in immunosenescence. PLos ONE. https://doi.org/10.1371/journal.pone.0118359
Data classification using the Dempster–Shafer method.
Chen, Qi, Whitbrook, Amanda, Aickelin, Uwe and Roadknight, Chris 2014. Data classification using the Dempster–Shafer method. Journal of Experimental & Theoretical Artificial Intelligence. https://doi.org/10.1080/0952813X.2014.886301
A conceptual framework for combining artificial neural networks with computational aeroacoustics for design development.
McKee, Claire, Harmanto, Dani and Whitbrook, Amanda 2018. A conceptual framework for combining artificial neural networks with computational aeroacoustics for design development. Industrial Engineering and Operations Management Society (IEOM).
A cloud-based path-finding framework: Improving the performance of real-time navigation in games
Rowe, Jordan, Whitbrook, Amanda and Chen, Minsi 2017. A cloud-based path-finding framework: Improving the performance of real-time navigation in games. Association of Computing Machinery. https://doi.org/10.1145/3147234.3148097
Model building
Lowdnes, Val, Berry, Stuart, Trovati, Marcello and Whitbrook, Amanda 2017. Model building. in: Springer.
Distributed task rescheduling with time constraints for the optimization of total task allocations in a multirobot system
Turner, Joanna, Meng, Qinggang, Schaefer, Gerald, Whitbrook, Amanda and Soltoggio, Andrea 2017. Distributed task rescheduling with time constraints for the optimization of total task allocations in a multirobot system. IEEE Transactions on Cybernetics. https://doi.org/10.1109/TCYB.2017.2743164
A robust, distributed task allocation algorithm for time-critical, multi agent systems operating in uncertain environments
Whitbrook, Amanda, Meng, Qinggang and Chung, Paul W. H. 2017. A robust, distributed task allocation algorithm for time-critical, multi agent systems operating in uncertain environments.
Reliable, distributed scheduling and rescheduling for time-critical, multiagent systems
Whitbrook, Amanda, Meng, Qinggang and Chung, Paul W. H. 2017. Reliable, distributed scheduling and rescheduling for time-critical, multiagent systems. IEEE Transactions on Automation Science and Engineering. https://doi.org/10.1109/TASE.2017.2679278