Dynamic neighbourhood optimisation for task allocation using multi-agent
In large-scale systems there are fundamental challenges when centralised techniques are used for task allocation. The number of interactions is limited by resource constraints such as on computation, storage, and network communication. We can increase scalability by implementing the system as a distributed task-allocation system, sharing tasks across many agents. However, this also increases the resource cost of communications and synchronisation, and is difficult to scale. In this paper we present four algorithms to solve these problems. The combination of these algorithms enable each agent to improve their task allocation strategy through reinforcement learning, while changing how much they explore the system in response to how optimal they believe their current strategy is, given their past experience. We focus on distributed agent systems where the agents' behaviours are constrained by resource usage limits, limiting agents to local rather than system-wide knowledge. We evaluate these algorithms in a simulated environment where agents are given a task composed of multiple subtasks that must be allocated to other agents with differing capabilities, to then carry out those tasks. We also simulate real-life system effects such as networking instability. Our solution is shown to solve the task allocation problem to 6.7% of the theoretical optimal within the system configurations considered. It provides 5x better performance recovery over no-knowledge retention approaches when system connectivity is impacted, and is tested against systems up to 100 agents with less than a 9% impact on the algorithms' performance.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Minimal Conditions for Beneficial Local Search
This paper investigates why it is beneficial, when solving a problem, to search in the neighbourhood of a current solution. The paper identifies properties of problems and neighbourhoods that support two novel proofs tha…
Risk Budgeting Allocation for Dynamic Risk Measures
We define and develop an approach for risk budgeting allocation - a risk diversification portfolio strategy - where risk is measured using a dynamic time-consistent risk measure. For this, we introduce a notion of dynami…
An exploration for higher efficiency in multi objective optimisation with reinforcement learning
Efficiency in optimisation and search processes persists to be one of the challenges, which affects the performance and use of optimisation algorithms. Utilising a pool of operators instead of a single operator to handle…
Reinforcement LearningResource allocation in dynamic multiagent systems
Resource allocation and task prioritisation are key problem domains in the fields of autonomous vehicles, networking, and cloud computing. The challenge in developing efficient and robust algorithms comes from the dynami…
Autonomous VehiclesCloud ComputingReinforcement Learning for Accelerated Aerodynamic Shape Optimisation
We introduce a reinforcement learning (RL) based adaptive optimization algorithm for aerodynamic shape optimization focused on dimensionality reduction. The form in which RL is applied here is that of a surrogate-based, …
Dimensionality ReductionReinforcement LearningFeature Importance