Reliable, distributed scheduling and rescheduling for time-critical, multiagent systems

Journal article


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
AuthorsWhitbrook, Amanda, Meng, Qinggang and Chung, Paul W. H.
Abstract

This paper addresses two main problems with many heuristic task allocation approaches – solution trapping in local minima and static structure. The existing distributed task allocation algorithm known as PI (Performance Impact) is used as the vehicle for developing solutions to these problems as it has been shown to out-perform the state-of-the-art Consensus Based Bundle Algorithm (CBBA) for time-critical problems with tight deadlines, but is both static and sub-optimal with a tendency towards trapping in local minima. The paper describes two additional modules that are easily integrated with PI. The first extends the algorithm to permit dynamic online rescheduling in real time, and the second boosts performance by introducing an additional soft max action selection procedure that increases the algorithm’s exploratory properties. The paper demonstrates the effectiveness of the dynamic rescheduling module and shows that the average time taken to perform tasks can be reduced by up to 9% when the soft max module is used. In addition, the solution of some problems that baseline PI cannot handle is enabled by the second module. These developments represent a significant advance in the state-of-the-art for multi-agent, time-critical task assignment.

This paper addresses two main problems with many heuristic task allocation approaches – solution trapping in local minima and static structure. The existing distributed task allocation algorithm known as PI (Performance Impact) is used as the vehicle for developing solutions to these problems as it has been shown to out-perform the state-of-the-art Consensus Based Bundle Algorithm (CBBA) for time-critical problems with tight deadlines, but is both static and sub-optimal with a tendency towards trapping in local minima. The paper describes two additional modules that are easily integrated with PI. The first extends the algorithm to permit dynamic online rescheduling in real time, and the second boosts performance by introducing an additional soft max action selection procedure that increases the algorithm’s exploratory properties. The paper demonstrates the effectiveness of the dynamic rescheduling module and shows that the average time taken to perform tasks can be reduced by up to 9% when the soft max module is used. In addition, the solution of some problems that baseline PI cannot handle is enabled by the second module. These developments represent a significant advance in the state-of-the-art for multi-agent, time-critical task assignment.

KeywordsAdaptive systems; Auction-based scheduling; Distributed task allocation; Multi-agent systems
Year2017
JournalIEEE Transactions on Automation Science and Engineering
PublisherIEEE
ISSN1545-5955
15583783
Digital Object Identifier (DOI)https://doi.org/10.1109/TASE.2017.2679278
Web address (URL)http://hdl.handle.net/10545/621610
hdl:10545/621610
Publication dates26 Apr 2017
Publication process dates
Deposited10 May 2017, 18:17
Rights

Archived with thanks to IEEE Transactions on Automation Science and Engineering

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

https://repository.derby.ac.uk/item/95255/reliable-distributed-scheduling-and-rescheduling-for-time-critical-multiagent-systems

Download files

  • 13
    total views
  • 1
    total downloads
  • 1
    views this month
  • 0
    downloads this month

Export as

Related outputs

Addressing robustness in time-critical, distributed, task allocation algorithms.
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
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.