A Novel Multi-Agent System for Complex Scheduling Problems

• URL: http://arxiv.org/abs/2004.09312v1
• Date: Mon, 20 Apr 2020 14:04:58 GMT
• Title: A Novel Multi-Agent System for Complex Scheduling Problems
• Authors: Peter Hillmann, Tobias Uhlig, Gabi Dreo Rodosek, Oliver Rose
• Abstract summary: This paper is the conception and implementation of a multi-agent system that is applicable in various problem domains. We simulate a NP-hard scheduling problem to demonstrate the validity of our approach. This paper highlights the advantages of the agent-based approach, like the reduction in layout complexity, improved control of complicated systems, and extendability.
• Score: 2.294014185517203
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Complex scheduling problems require a large amount computation power and innovative solution methods. The objective of this paper is the conception and implementation of a multi-agent system that is applicable in various problem domains. Independent specialized agents handle small tasks, to reach a superordinate target. Effective coordination is therefore required to achieve productive cooperation. Role models and distributed artificial intelligence are employed to tackle the resulting challenges. We simulate a NP-hard scheduling problem to demonstrate the validity of our approach. In addition to the general agent based framework we propose new simulation-based optimization heuristics to given scheduling problems. Two of the described optimization algorithms are implemented using agents. This paper highlights the advantages of the agent-based approach, like the reduction in layout complexity, improved control of complicated systems, and extendability.

Related papers

• Exploring Multi-Agent Reinforcement Learning for Unrelated Parallel Machine Scheduling [2.3034630097498883]
  The study introduces the Reinforcement Learning environment and conducts empirical analyses. The experiments employ various deep neural network policies for single- and Multi-Agent approaches. While Single-Agent algorithms perform adequately in reduced scenarios, Multi-Agent approaches reveal challenges in cooperative learning but a scalable capacity.
  arXiv  Detail & Related papers  (2024-11-12T08:27:27Z)
• Agent-Oriented Planning in Multi-Agent Systems [54.429028104022066]
  We propose a novel framework for agent-oriented planning in multi-agent systems, leveraging a fast task decomposition and allocation process. We integrate a feedback loop into the proposed framework to further enhance the effectiveness and robustness of such a problem-solving process.
  arXiv  Detail & Related papers  (2024-10-03T04:07:51Z)
• PARCO: Learning Parallel Autoregressive Policies for Efficient Multi-Agent Combinatorial Optimization [17.392822956504848]
  This paper introduces PARCO, a novel approach that learns fast surrogate solvers for multi-agent problems with reinforcement learning. We propose a model with a Multiple Pointer Mechanism to efficiently decode multiple decisions simultaneously by different agents, enhanced by a Priority-based Conflict Handling scheme.
  arXiv  Detail & Related papers  (2024-09-05T17:49:18Z)
• An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programming [5.070542698701157]
  This paper proposes a novel end-to-end approach to solving scheduling problems by means of CP and Reinforcement Learning (RL) Our approach leverages existing CP solvers to train an agent learning a Priority Dispatching Rule (PDR) that generalizes well to large instances, even from separate datasets.
  arXiv  Detail & Related papers  (2023-06-09T08:24:56Z)
• Efficient lifting of symmetry breaking constraints for complex combinatorial problems [9.156939957189502]
  This work extends the learning framework and implementation of a model-based approach for Answer Set Programming. In particular, we incorporate a new conflict analysis algorithm in the Inductive Logic Programming system ILASP.
  arXiv  Detail & Related papers  (2022-05-14T20:42:13Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
  We propose a novel framework called Jump-Operator Dynamic Programming for quickly computing solutions within a super-exponential space of sequential sub-goal tasks. This approach involves controlling over an ensemble of reusable goal-conditioned polices functioning as temporally extended actions. We then identify classes of objective functions on this subspace whose solutions are invariant to the grounding, resulting in optimal zero-shot transfer.
  arXiv  Detail & Related papers  (2020-07-06T05:13:20Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  We propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed. An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed. We show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity.
  arXiv  Detail & Related papers  (2020-06-15T02:57:57Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.