Multi-Agent Path Finding under Limited Communication Range Constraint via Dynamic Leading

• URL: http://arxiv.org/abs/2501.02770v2
• Date: Wed, 05 Feb 2025 15:32:43 GMT
• Title: Multi-Agent Path Finding under Limited Communication Range Constraint via Dynamic Leading
• Authors: Hoang-Dung Bui, Erion Plaku, Gregoy J. Stein,
• Abstract summary: This paper proposes a novel framework to handle a multi-agent path finding problem under a limited communication range constraint. We develop dynamic leading multi-agent path finding, which allows for dynamic reselection of the leading agent during path planning whenever progress cannot be made. Experiments show the efficiency of our framework, which can handle up to 25 agents with more than 90% success-rate across five environment types.
• Score: 3.522950356329991
• License:
• Abstract: This paper proposes a novel framework to handle a multi-agent path finding problem under a limited communication range constraint, where all agents must have a connected communication channel to the rest of the team. Many existing approaches to multi-agent path finding (e.g., leader-follower platooning) overcome computational challenges of planning in this domain by planning one agent at a time in a fixed order. However, fixed leader-follower approaches can become stuck during planning, limiting their practical utility in dense-clutter environments. To overcome this limitation, we develop dynamic leading multi-agent path finding, which allows for dynamic reselection of the leading agent during path planning whenever progress cannot be made. The experiments show the efficiency of our framework, which can handle up to 25 agents with more than 90% success-rate across five environment types where baselines routinely fail.

Related papers

• Communication Learning in Multi-Agent Systems from Graph Modeling Perspective [62.13508281188895]
  We introduce a novel approach wherein we conceptualize the communication architecture among agents as a learnable graph. We introduce a temporal gating mechanism for each agent, enabling dynamic decisions on whether to receive shared information at a given time.
  arXiv  Detail & Related papers  (2024-11-01T05:56:51Z)
• Learning Multi-Agent Communication from Graph Modeling Perspective [62.13508281188895]
  We introduce a novel approach wherein we conceptualize the communication architecture among agents as a learnable graph. Our proposed approach, CommFormer, efficiently optimize the communication graph and concurrently refines architectural parameters through gradient descent in an end-to-end manner.
  arXiv  Detail & Related papers  (2024-05-14T12:40:25Z)
• Fault-Tolerant Offline Multi-Agent Path Planning [5.025654873456756]
  We study a novel graph path planning problem for multiple agents that may crash at runtime, and block part of the workspace. In our setting, agents can detect neighboring crashed agents, and change followed paths at runtime. The objective is then to prepare a set of paths and switching rules for each agent, ensuring that all correct agents reach their destinations without collisions or deadlocks.
  arXiv  Detail & Related papers  (2022-11-25T05:58:32Z)
• 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)
• Planning to Practice: Efficient Online Fine-Tuning by Composing Goals in Latent Space [76.46113138484947]
  General-purpose robots require diverse repertoires of behaviors to complete challenging tasks in real-world unstructured environments. To address this issue, goal-conditioned reinforcement learning aims to acquire policies that can reach goals for a wide range of tasks on command. We propose Planning to Practice, a method that makes it practical to train goal-conditioned policies for long-horizon tasks.
  arXiv  Detail & Related papers  (2022-05-17T06:58:17Z)
• DSDF: An approach to handle stochastic agents in collaborative multi-agent reinforcement learning [0.0]
  We show how thisity of agents, which could be a result of malfunction or aging of robots, can add to the uncertainty in coordination. Our solution, DSDF which tunes the discounted factor for the agents according to uncertainty and use the values to update the utility networks of individual agents.
  arXiv  Detail & Related papers  (2021-09-14T12:02:28Z)
• 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)
• Scalable, Decentralized Multi-Agent Reinforcement Learning Methods Inspired by Stigmergy and Ant Colonies [0.0]
  We investigate a novel approach to decentralized multi-agent learning and planning. In particular, this method is inspired by the cohesion, coordination, and behavior of ant colonies. The approach combines single-agent RL and an ant-colony-inspired decentralized, stigmergic algorithm for multi-agent path planning and environment modification.
  arXiv  Detail & Related papers  (2021-05-08T01:04:51Z)
• Multi-Agent Routing Value Iteration Network [88.38796921838203]
  We propose a graph neural network based model that is able to perform multi-agent routing based on learned value in a sparsely connected graph. We show that our model trained with only two agents on graphs with a maximum of 25 nodes can easily generalize to situations with more agents and/or nodes.
  arXiv  Detail & Related papers  (2020-07-09T22:16:45Z)
• 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)
• Implicit Multiagent Coordination at Unsignalized Intersections via Multimodal Inference Enabled by Topological Braids [15.024091680310109]
  We focus on navigation among rational, non-communicating agents at unsignalized street intersections. We represent modes of joint behavior in a compact and interpretable fashion using the formalism of topological braids. We design a decentralized planning algorithm that generates actions aimed at reducing the uncertainty over the mode of the emerging multiagent behavior.
  arXiv  Detail & Related papers  (2020-04-10T19:01: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.