Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that every agent reaches its goal and do not collide. Most prior work on MAPF were grids, assumed agents' actions have uniform duration, time discretized into timesteps. In this work, we propose a algorithm assume any these assumptions, complete, provides provably optimal solutions. This based novel combination Safe Interval Path Planning (SIPP), continuous single planning algorithms, Conflict-Based...

The problem of finding conflict-free trajectories for multiple agents identical circular shape, operating in shared 2D workspace, is addressed the paper and decoupled, e.g., prioritized, approach used to solve this problem. Agents' workspace tessellated into square grid on which any-angle moves are allowed, e.g. each agent can move an arbitrary direction as long follows straight line segment whose endpoints tied distinct elements. A novel planner based Safe Interval Path Planning (SIPP)...

Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for agents confined graph and is typically solved in centralized fashion. Conversely, this work, we investigate the decentralized MAPF setting, when central controller that possesses all information on agents' locations goals absent have sequentially decide actions their own without having access full state environment. We focus practically important lifelong variant MAPF, which involves continuously...

Methods for centralized planning of the collision-free trajectories a fleet mobile robots typically solve discretized version problem and rely on numerous simplifying assumptions, e.g. moves uniform duration, cardinal only translations, equal speed size etc., thus resultant plans can not always be directly executed by real robotic systems. To mitigate this issue we suggest set modifications to prominent prioritized planner -- AA-SIPP(m) aimed at lifting most restrictive assumptions...

Conflict-Based Search (CBS) is a powerful algorithmic framework for optimally solving classical multi-agent path finding (MAPF) problems, where time discretized into the steps. Continuous-time CBS (CCBS) recently proposed version of that guarantees optimal solutions without need to discretize time. However, scalability CCBS limited because it does not include any known improvements CBS. In this paper, we begin close gap and explore how adapt successful improvements, namely, prioritizing...

Multi-agent pathfinding (MAPF) is a problem that generally requires finding collision-free paths for multiple agents in shared environment. Solving MAPF optimally, even under restrictive assumptions, NP-hard, yet efficient solutions this are critical numerous applications, such as automated warehouses and transportation systems. Recently, learning-based approaches to have gained attention, particularly those leveraging deep reinforcement learning. Typically, solvers augmented with additional...

Heuristic search algorithms, e.g. A*, are the commonly used tools for pathfinding on grids, i.e. graphs of regular structure that widely employed to represent environments in robotics, video games, etc. Instance-independent heuristics grid graphs, Manhattan distance, do not take obstacles into account, and thus led by such performs poorly obstacle-rich environments. To this end, we suggest learning instance-dependent heuristic proxies supposed notably increase efficiency search. The first...

The Multi-Agent Pathfinding (MAPF) problem involves finding a set of conflict-free paths for group agents confined to graph. In typical MAPF scenarios, the graph and agents' starting ending vertices are known beforehand, allowing use centralized planning algorithms. However, in this study, we focus on decentralized setting, where may observe other only locally restricted communications with each other. Specifically, investigate lifelong variant MAPF, new goals continually assigned upon...

Safe-interval path planning (SIPP) is a powerful algorithm for finding in the presence of dynamic obstacles. SIPP returns provably optimal solutions. However, many practical applications such as robots, one would like to trade-off optimality shorter time. In this paper we explore different ways build bounded-suboptimal and discuss their pros cons. We compare versions experimentally. While there no universal winner, results provide insights into when each method should be used.

Multi-agent pathfinding (MAPF) is a problem that involves finding set of non-conflicting paths for agents confined to graph. In this work, we study MAPF setting, where the environment only partially observable each agent, i.e., an agent observes obstacles and other within limited field-of-view. Moreover, assume do not communicate share knowledge on their goals, intended actions, etc. The task construct policy maps agent's observations actions. Our contribution multifold. First, propose two...

Among the main challenges associated with navigating a mobile robot in complex environments are partial observability and stochasticity. This work proposes stochastic formulation of pathfinding problem, assuming that obstacles arbitrary shapes may appear disappear at random moments time. Moreover, we consider case when environment is only partially observable for an agent. We study evaluate two orthogonal approaches to tackle problem reaching goal under such conditions: planning learning....

Abstract Multi-agent path finding arises, on the one hand, in numerous applied areas. A classical example is automated warehouses with a large number of mobile goods-sorting robots operating simultaneously. On other for this problem, there are no universal solution methods that simultaneously satisfy (often contradictory) requirements. Examples such criteria guarantee optimal solutions, high-speed operation, possibility operation partially observable environments, etc. This paper provides...

Multi-agent pathfinding (MAPF) is the problem of finding a set conflict-free paths for agents. We explore how to solve MAPF problems when each agent can move between any pair possible locations as long traversing line segment connecting them does not lead collision with obstacles. This known any-angle pathfinding. present first optimal multi-agent algorithm. Our planner based on Continuous Conflict-based Search (CCBS) algorithm and an variant Safe Interval Path Planning (TO-AA-SIPP). The...

We introduce and empirically evaluate two techniques aimed at enhancing the performance of multi-robot prioritized path planning. The first technique is deterministic procedure for re-scheduling (as opposed to well-known approach based on random restarts), second one heuristic that modifies search-space individual planner involved in finding.

Path finding is a well-studied problem in AI, which often framed as graph search. Any-angle path technique that augments the initial with additional edges to build shorter paths goal. Indeed, optimal algorithms for any-angle static environments exist. However, when dynamic obstacles are present and time objective be minimized, these can no longer guarantee optimality. In this work, we elaborate on why case what techniques used solve optimally. We two algorithms, grounded same idea, obtain...

We introduce POGEMA (https://github.com/AIRI-Institute/pogema) a sandbox for challenging partially observable multi-agent pathfinding (PO-MAPF) problems . This is grid-based environment that was specifically designed to be flexible, tunable and scalable benchmark. It can tailored variety of PO-MAPF, which serve as an excellent testing ground planning learning methods, their combination, will allow us move towards filling the gap between AI learning.

In this paper, we address the multi-agent pickup and delivery problem, a variant of path finding.Specifically, decouple problem into two parts: task allocation planning.We employ any-angle safe-interval planning algorithm introduced in our recent work study performance several strategies.Furthermore, proposed approach has been integrated control system to verify its feasibility deployment on real robots.A key part is visual localization which based detection unique artificial markers placed...