Learning to Solve the Min-Max Mixed-Shelves Picker-Routing Problem via Hierarchical and Parallel Decoding

• URL: http://arxiv.org/abs/2502.10233v1
• Date: Fri, 14 Feb 2025 15:42:30 GMT
• Title: Learning to Solve the Min-Max Mixed-Shelves Picker-Routing Problem via Hierarchical and Parallel Decoding
• Authors: Laurin Luttmann, Lin Xie,
• Abstract summary: The Mixed-Shelves Picker Routing Problem (MSPRP) is a fundamental challenge in logistics, where pickers must navigate a mixed-shelves environment to retrieve SKUs efficiently. We propose a novel hierarchical and parallel decoding approach for solving the min-max variant of the MSPRP via multi-agent reinforcement learning. Experiments show state-of-the-art performance in both solution quality and inference speed, particularly for large-scale and out-of-distribution instances.
• Score: 0.3867363075280544
• License:
• Abstract: The Mixed-Shelves Picker Routing Problem (MSPRP) is a fundamental challenge in warehouse logistics, where pickers must navigate a mixed-shelves environment to retrieve SKUs efficiently. Traditional heuristics and optimization-based approaches struggle with scalability, while recent machine learning methods often rely on sequential decision-making, leading to high solution latency and suboptimal agent coordination. In this work, we propose a novel hierarchical and parallel decoding approach for solving the min-max variant of the MSPRP via multi-agent reinforcement learning. While our approach generates a joint distribution over agent actions, allowing for fast decoding and effective picker coordination, our method introduces a sequential action selection to avoid conflicts in the multi-dimensional action space. Experiments show state-of-the-art performance in both solution quality and inference speed, particularly for large-scale and out-of-distribution instances. Our code is publicly available at http://github.com/LTluttmann/marl4msprp.

Related papers

• O-MAPL: Offline Multi-agent Preference Learning [5.4482836906033585]
  Inferring reward functions from demonstrations is a key challenge in reinforcement learning (RL) We introduce a novel end-to-end preference-based learning framework for cooperative MARL. Our algorithm outperforms existing methods across various tasks.
  arXiv  Detail & Related papers  (2025-01-31T08:08:20Z)
• Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization [17.392822956504848]
  We propose a reinforcement learning framework designed to construct high-quality solutions for multi-agent tasks efficiently. PARCO integrates three key components: (1) transformer-based communication layers to enable effective agent collaboration during parallel solution construction, (2) a multiple pointer mechanism for low-latency, parallel agent decision-making, and (3) priority-based conflict handlers to resolve decision conflicts via learned priorities. We evaluate PARCO in multi-agent vehicle routing and scheduling problems where our approach outperforms state-of-the-art learning methods and demonstrates strong generalization ability and remarkable computational efficiency.
  arXiv  Detail & Related papers  (2024-09-05T17:49:18Z)
• Design Optimization of NOMA Aided Multi-STAR-RIS for Indoor Environments: A Convex Approximation Imitated Reinforcement Learning Approach [51.63921041249406]
  Non-orthogonal multiple access (NOMA) enables multiple users to share the same frequency band, and simultaneously transmitting and reflecting reconfigurable intelligent surface (STAR-RIS) deploying STAR-RIS indoors presents challenges in interference mitigation, power consumption, and real-time configuration. A novel network architecture utilizing multiple access points (APs), STAR-RISs, and NOMA is proposed for indoor communication.
  arXiv  Detail & Related papers  (2024-06-19T07:17:04Z)
• Ensembling Prioritized Hybrid Policies for Multi-agent Pathfinding [18.06081009550052]
  Multi-Agent Reinforcement Learning (MARL) based Multi-Agent Path Finding (MAPF) has recently gained attention due to its efficiency and scalability. Several MARL-MAPF methods choose to use communication to enrich the information one agent can perceive. We propose a new method, Ensembling Prioritized Hybrid Policies (EPH)
  arXiv  Detail & Related papers  (2024-03-12T11:47:12Z)
• A Novel Point-based Algorithm for Multi-agent Control Using the Common Information Approach [8.733794945008562]
  We propose a new algorithm for multi-agent control problems, called coordinator's search value (CHSVI) The algorithm combines the CI approach and point-based POMDP algorithms for large action spaces. We demonstrate the algorithm through optimally solving several benchmark problems.
  arXiv  Detail & Related papers  (2023-04-10T01:27:43Z)
• Expeditious Saliency-guided Mix-up through Random Gradient Thresholding [89.59134648542042]
  Mix-up training approaches have proven to be effective in improving the generalization ability of Deep Neural Networks. In this paper, inspired by the superior qualities of each direction over one another, we introduce a novel method that lies at the junction of the two routes. We name our method R-Mix following the concept of "Random Mix-up" In order to address the question of whether there exists a better decision protocol, we train a Reinforcement Learning agent that decides the mix-up policies.
  arXiv  Detail & Related papers  (2022-12-09T14:29:57Z)
• Multi-agent Deep Covering Skill Discovery [50.812414209206054]
  We propose Multi-agent Deep Covering Option Discovery, which constructs the multi-agent options through minimizing the expected cover time of the multiple agents' joint state space. Also, we propose a novel framework to adopt the multi-agent options in the MARL process. We show that the proposed algorithm can effectively capture the agent interactions with the attention mechanism, successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
  arXiv  Detail & Related papers  (2022-10-07T00:40:59Z)
• Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
  Multi Agent Path Finding (MAPF) requires identification of conflict free paths for spatially-extended agents. These find application in real world problems like Convoy Movement Problem, Train Scheduling etc. Our proposed approach, Decentralised Multi Agent Path Finding (DeMAPF), handles MAPF as a sequence of pathplanning and allocation problems.
  arXiv  Detail & Related papers  (2021-06-03T18:07:26Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  Decentralized multi-agent reinforcement learning algorithms are sometimes unpractical in complicated applications. We propose a flexible fully decentralized actor-critic MARL framework, which can handle large-scale general cooperative multi-agent setting. Our framework can achieve scalability and stability for large-scale environment and reduce information transmission.
  arXiv  Detail & Related papers  (2020-04-17T14:56:29Z)

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.