A Combination of Theta*, ORCA and Push and Rotate for Multi-agent Navigation

• URL: http://arxiv.org/abs/2008.01227v1
• Date: Mon, 3 Aug 2020 22:22:43 GMT
• Title: A Combination of Theta*, ORCA and Push and Rotate for Multi-agent Navigation
• Authors: Stepan Dergachev and Konstantin Yakovlev and Ryhor Prakapovich
• Abstract summary: We study the problem of multi-agent navigation in static environments when no centralized controller is present. Each agent is controlled individually and relies on three algorithmic components to achieve its goal.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of multi-agent navigation in static environments when no centralized controller is present. Each agent is controlled individually and relies on three algorithmic components to achieve its goal while avoiding collisions with the other agents and the obstacles: i) individual path planning which is done by Theta* algorithm; ii) collision avoidance while path following which is performed by ORCA* algorithm; iii) locally-confined multi-agent path planning done by Push and Rotate algorithm. The latter component is crucial to avoid deadlocks in confined areas, such as narrow passages or doors. We describe how the suggested components interact and form a coherent navigation pipeline. We carry out an extensive empirical evaluation of this pipeline in simulation. The obtained results clearly demonstrate that the number of occurring deadlocks significantly decreases enabling more agents to reach their goals compared to techniques that rely on collision-avoidance only and do not include multi-agent path planning component

Related papers

• Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
  We present the first optimal any-angle multi-agent pathfinding algorithm. Our planner is based on the Continuous Conflict-based Search (CCBS) algorithm and an optimal any-angle variant of the Safe Interval Path Planning (TO-AA-SIPP) We adapt two techniques from classical MAPF to the any-angle setting, namely Disjoint Splitting and Multi-Constraints.
  arXiv  Detail & Related papers  (2024-04-25T07:41:47Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
  arXiv  Detail & Related papers  (2024-01-30T14:26:04Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Communication-Critical Planning via Multi-Agent Trajectory Exchange [21.923724399511798]
  This paper addresses the task of joint multi-agent perception and planning. It relates to the real-world challenge of collision-free navigation for connected self-driving vehicles.
  arXiv  Detail & Related papers  (2023-03-10T16:59:24Z)
• Task-Oriented Sensing, Computation, and Communication Integration for Multi-Device Edge AI [108.08079323459822]
  This paper studies a new multi-intelligent edge artificial-latency (AI) system, which jointly exploits the AI model split inference and integrated sensing and communication (ISAC) We measure the inference accuracy by adopting an approximate but tractable metric, namely discriminant gain.
  arXiv  Detail & Related papers  (2022-07-03T06:57:07Z)
• Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
  Multi-Agent Path Finding (MAPF) is a long-standing problem in Robotics and Artificial Intelligence. We present a method that mitigates this issue to a certain extent.
  arXiv  Detail & Related papers  (2021-08-11T10:42:11Z)
• Multimodal Trajectory Prediction via Topological Invariance for Navigation at Uncontrolled Intersections [45.508973373913946]
  We focus on decentralized navigation among multiple non-communicating rational agents at street intersections without traffic signs or signals. Our key insight is that the geometric structure of the intersection and the incentive of agents to move efficiently and avoid collisions (rationality) reduces the space of likely behaviors. We design Multiple Topologies Prediction (MTP), a data-driven trajectory-prediction mechanism that reconstructs trajectory representations of high-likelihood modes in multiagent intersection scenes.
  arXiv  Detail & Related papers  (2020-11-08T02:56:42Z)
• Risk-Averse MPC via Visual-Inertial Input and Recurrent Networks for Online Collision Avoidance [95.86944752753564]
  We propose an online path planning architecture that extends the model predictive control (MPC) formulation to consider future location uncertainties. Our algorithm combines an object detection pipeline with a recurrent neural network (RNN) which infers the covariance of state estimates. The robustness of our methods is validated on complex quadruped robot dynamics and can be generally applied to most robotic platforms.
  arXiv  Detail & Related papers  (2020-07-28T07:34:30Z)
• 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)
• Tracking Road Users using Constraint Programming [79.32806233778511]
  We present a constraint programming (CP) approach for the data association phase found in the tracking-by-detection paradigm of the multiple object tracking (MOT) problem. Our proposed method was tested on a motorized vehicles tracking dataset and produces results that outperform the top methods of the UA-DETRAC benchmark.
  arXiv  Detail & Related papers  (2020-03-10T00:04:32Z)

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.