Enhancing Lifelong Multi-Agent Path Finding with Cache Mechanism

• URL: http://arxiv.org/abs/2501.02803v1
• Date: Mon, 06 Jan 2025 06:44:13 GMT
• Title: Enhancing Lifelong Multi-Agent Path Finding with Cache Mechanism
• Authors: Yimin Tang, Zhenghong Yu, Yi Zheng, T. K. Satish Kumar, Jiaoyang Li, Sven Koenig,
• Abstract summary: Lifelong MAPF (L-MAPF) offers a more realistic approximation of real-world warehouse scenarios. We introduce a novel mechanism called Lifelong MAPF with Cache Mechanism (L-MAPF-CM), which integrates high-level cache storage with low-level path planning. L-MAPF-CM has demonstrated performance improvements particularly with high cache hit rates and smooth traffic conditions.
• Score: 25.575748142768298
• License:
• Abstract: Multi-Agent Path Finding (MAPF), which focuses on finding collision-free paths for multiple robots, is crucial in autonomous warehouse operations. Lifelong MAPF (L-MAPF), where agents are continuously reassigned new targets upon completing their current tasks, offers a more realistic approximation of real-world warehouse scenarios. While cache storage systems can enhance efficiency and reduce operational costs, existing approaches primarily rely on expectations and mathematical models, often without adequately addressing the challenges of multi-robot planning and execution. In this paper, we introduce a novel mechanism called Lifelong MAPF with Cache Mechanism (L-MAPF-CM), which integrates high-level cache storage with low-level path planning. We have involved a new type of map grid called cache for temporary item storage. Additionally, we involved a task assigner (TA) with a locking mechanism to bridge the gap between the new cache grid and L-MAPF algorithm. The TA dynamically allocates target locations to agents based on their status in various scenarios. We evaluated L-MAPF-CM using different cache replacement policies and task distributions. L-MAPF-CM has demonstrated performance improvements particularly with high cache hit rates and smooth traffic conditions.

Related papers

• MPIC: Position-Independent Multimodal Context Caching System for Efficient MLLM Serving [32.56855948056532]
  This paper proposes position-independent caching as a more effective approach for multimodal information management. We have designed and implemented a caching system, named MPIC, to address both system-level and algorithm-level challenges.
  arXiv  Detail & Related papers  (2025-02-04T03:13:09Z)
• Multi-Agent Motion Planning For Differential Drive Robots Through Stationary State Search [5.9176395108304805]
  Multi-Agent Motion Planning (MAMP) finds various applications in fields such as traffic management, airport operations, and warehouse automation. This paper introduces a three-level framework called MASS to address these challenges. MASS combines MAPF-based methods with our proposed stationary state search planner to generate high-quality kinodynamically-feasible plans.
  arXiv  Detail & Related papers  (2024-12-17T22:17:42Z)
• Efficient Inference of Vision Instruction-Following Models with Elastic Cache [76.44955111634545]
  We introduce Elastic Cache, a novel strategy for efficient deployment of instruction-following large vision-language models. We propose an importance-driven cache merging strategy to prune redundancy caches. For instruction encoding, we utilize the frequency to evaluate the importance of caches. Results on a range of LVLMs demonstrate that Elastic Cache not only boosts efficiency but also notably outperforms existing pruning methods in language generation.
  arXiv  Detail & Related papers  (2024-07-25T15:29:05Z)
• Caching-Augmented Lifelong Multi-Agent Path Finding [25.575748142768298]
  Lifelong MAPF, where targets are reassigned to agents as soon as they complete their initial targets, offers a more accurate approximation of real-world warehouse planning. We present a novel mechanism named Caching-Augmented Lifelong MAPF (CAL-MAPF) designed to improve the performance of Lifelong MAPF.
  arXiv  Detail & Related papers  (2024-03-20T09:07:23Z)
• Emergency Caching: Coded Caching-based Reliable Map Transmission in Emergency Networks [9.423705897088672]
  We propose a three-layer architecture of caching networks focusing on data collection and reliable transmission. We propose a disaster map collection framework that integrates coded caching technologies. Our proposed scheme is more effective than the non-coding caching scheme, as validated by simulation.
  arXiv  Detail & Related papers  (2024-02-27T14:44:11Z)
• Collaborative Intelligent Reflecting Surface Networks with Multi-Agent Reinforcement Learning [63.83425382922157]
  Intelligent reflecting surface (IRS) is envisioned to be widely applied in future wireless networks. In this paper, we investigate a multi-user communication system assisted by cooperative IRS devices with the capability of energy harvesting.
  arXiv  Detail & Related papers  (2022-03-26T20:37:14Z)
• Accelerating Deep Learning Classification with Error-controlled Approximate-key Caching [72.50506500576746]
  We propose a novel caching paradigm, that we named approximate-key caching. While approximate cache hits alleviate DL inference workload and increase the system throughput, they however introduce an approximation error. We analytically model our caching system performance for classic LRU and ideal caches, we perform a trace-driven evaluation of the expected performance, and we compare the benefits of our proposed approach with the state-of-the-art similarity caching.
  arXiv  Detail & Related papers  (2021-12-13T13:49:11Z)
• Learning Space Partitions for Path Planning [54.475949279050596]
  PlaLaM outperforms existing path planning methods in 2D navigation tasks, especially in the presence of difficult-to-escape local optima. These gains transfer to highly multimodal real-world tasks, where we outperform strong baselines in compiler phase ordering by up to 245% and in molecular design by up to 0.4 on properties on a 0-1 scale.
  arXiv  Detail & Related papers  (2021-06-19T18:06:11Z)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  We consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill various intralogistics tasks. One approach is to construct an Action Dependency Graph (ADG) which encodes the ordering of AGVs as they proceed along their routes. If the workspace is shared by dynamic obstacles such as humans or third party robots, AGVs can experience large delays. We present an online method to repeatedly modify acyclic ADG to minimize route completion times of each AGV.
  arXiv  Detail & Related papers  (2020-10-11T14:39:50Z)
• Caching Placement and Resource Allocation for Cache-Enabling UAV NOMA Networks [87.6031308969681]
  This article investigates the cache-enabling unmanned aerial vehicle (UAV) cellular networks with massive access capability supported by non-orthogonal multiple access (NOMA) We formulate the long-term caching placement and resource allocation optimization problem for content delivery delay minimization as a Markov decision process (MDP) We propose a Q-learning based caching placement and resource allocation algorithm, where the UAV learns and selects action with emphsoft $varepsilon$-greedy strategy to search for the optimal match between actions and states.
  arXiv  Detail & Related papers  (2020-08-12T08:33:51Z)
• Lifelong Multi-Agent Path Finding in Large-Scale Warehouses [26.017429163961328]
  Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents to their goal locations without collisions. We propose a new framework for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances.
  arXiv  Detail & Related papers  (2020-05-15T06:07:15Z)

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.