Яковлев Константин Сергеевич

Distributed Multi-Agent Navigation Based on Reciprocal Collision Avoidance and Locally Confined Multi-Agent Path Finding

2024 · CHAPTER · en

Avoiding collisions is the core problem in multiagent navigation. In decentralized settings, when agents have limited communication and sensory capabilities, collisions are typically avoided in a reactive fashion, relying on local ob-servations/communications. Prominent collision avoidance techniques, e.g. ORCA, are computationally efficient and scale well to a large number of agents. However, in numerous scenarios, involving navigation through the tight passages or confined spaces, deadlocks are likely to occur due to the egoistic behaviour of the agents and as a result, the latter can not achieve their goals. To this end, we suggest an application of the locally confined multi-agent path finding (MAPF) solvers that coordinate sub-groups of the agents that appear to be in a deadlock (to detect the latter we suggest a simple, yet efficient ad-hoc routine). We present a way to build a grid-based MAPF instance, typically required by modern MAPF solvers. We evaluate two of them in our experiments, i.e. Push And Rotate and a bounded-suboptimal version of Conflict Based Search (ecbs), and show that their inclusion into the navigation pipeline significantly increases the success rate, from 15% to 99% in certain cases.

When to Switch: Planning and Learning for Partially Observable Multi-Agent Pathfinding

2024 · ARTICLE · en

Multi-agent pathfinding (MAPF) is a problem that involves finding a set of non-conflicting paths for a set of agents confined to a graph. In this work, we study a MAPF setting, where the environment is only partially observable for each agent, i.e., an agent observes the obstacles and other agents only within a limited field-of-view. Moreover, we assume that the agents do not communicate and do not share knowledge on their goals, intended actions, etc. The task is to construct a policy that maps the agent’s observations to actions. Our contribution is multifold. First, we propose two novel policies for solving partially observable MAPF (PO-MAPF): one based on heuristic search and another one based on reinforcement learning (RL). Next, we introduce a mixed policy that is based on switching between the two. We suggest three different switch scenarios: the heuristic, the deterministic, and the learnable one. A thorough empirical evaluation of all the proposed policies in a variety of setups shows that the mixing policy demonstrates the best performance is able to generalize well to the unseen maps and problem instances, and, additionally, outperforms the state-of-the-art counterparts (Primal2 and PICO). The source-code is available at https://github.com/AIRI-Institute/when-to-switch.

Model predictive path integral for decentralized multi-agent collision avoidance

2024 · ARTICLE · en

Collision avoidance is a crucial component of any decentralized multi-agent navigation system. Currently, most of the existing multi-agent collision-avoidance methods either do not take into account the kinematic constraints of the agents (i.e., they assume that an agent might change the direction of movement instantaneously) or are tailored to specific kinematic motion models (e.g., car-like robots). In this work, we suggest a novel generalized approach to decentralized multi-agent collision-avoidance that can be applied to agents with arbitrary affine kinematic motion models, including but not limited to differential-drive robots, car-like robots, quadrotors, etc. The suggested approach is based on the seminal sampling-based model predictive control algorithm, i.e., MPPI, that originally solves a single-agent problem. We enhance it by introducing safe distributions for the multi-agent setting that are derived from the Optimal Reciprocal Collision Avoidance (ORCA) linear constraints, an established approach from the multi-agent navigation domain. We rigorously show that such distributions can be found by solving a specific convex optimization problem. We also provide a theoretical justification that the resultant algorithm guarantees safety, i.e., that at each time step the control suggested by our algorithm does not lead to a collision. We empirically evaluate the proposed method in simulation experiments that involve comparison with the state of the art in different setups. We find that in many cases, the suggested approach outperforms competitors and allows solving problem instances that the other methods cannot successfully solve.

Decentralized Unlabeled Multi-agent Navigation in Continuous Space

2024 · CHAPTER · en

Decentralized Unlabeled Multi-agent Pathfinding Via Target And Priority Swapping

2024 · CHAPTER · en

Применение управления с прогнозирующими моделями и стохастической оптимизацией в задаче децентрализованного много-агентного избегания столкновений

2024 · CHAPTER · ru

Evaluation of Topological Mapping Methods in Indoor Environments

2023 · ARTICLE · en

Mapping is one of the key components of mobile robot navigation. Representing a map as a topological structure is suitable for fast path planning and does not require high positioning precision or high computational resources, which is particularly useful in large environments. In recent years, numerous methods of topological graph building have emerged. Most of these methods build a topological graph in conjunction with a metric map, and during tests and benchmarks, the performance of metric maps is typically assessed. However, topological graph quality is also crucial for robot navigation. In this study, we conducted an extensive evaluation of five open-source topological mapping methods (Hydra, S-graphs+, IncrementalTopo, ETPNav, and TSGM) using a large simulated indoor dataset with precise and noisy positioning. We used novel metrics to measure topological graph quality in our comparison. We found that all the methods except TGSM build an unconnected graph with both precise and noisy positioning. Hydra and S-graphs are more robust to position noise, but their graphs have a high percent of the edges crossing an obstacle. TSGM builds connected graphs, and it is not sensitive to positional noise because it does not use position as an input. However, its graphs have a high percent of the edges crossing an obstacle. IncrementalTopo has fewer edges passing through the obstacles; however, with noisy positioning, its graph becomes highly disconnected, which may also cause navigation failures. Thus, all the evaluated methods have their own advantages and drawbacks, and none of them builds a graph suitable for navigation out of the box. Overall, our study pinpoints the advantages and disadvantages of the state-of-the-art topological mapping methods and may aid researchers and practitioners in choosing a proper available algorithm for their specific setup.

Multi-agent Pathfinding With Continuous Time

2022 · ARTICLE · en

Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that each agent reaches its goal and the agents do not collide. In recent years, variants of MAPF have risen in a wide range of real-world applications such as warehouse management and autonomous vehicles. Optimizing common MAPF objectives, such as minimizing sum-of-costs or makespan, is computationally intractable, but state-of-the-art algorithms are able to solve optimally problems with dozens of agents. However, most MAPF algorithms assume that (1) time is discretized into time steps and (2) the duration of every action is one time step. These simplifying assumptions limit the applicability of MAPF algorithms in real-world applications and raise non-trivial questions such as how to discretize time in an effective manner. We propose two novel MAPF algorithms for finding optimal solutions that do not rely on any time discretization. In particular, our algorithms do not require quantization of wait and move actions' durations, allowing these durations to take any value required to find optimal solutions. The first algorithm we propose, called Continuous-time Conflict-Based Search (CCBS), draws on ideas from Safe Interval Path Planning (SIPP), a single-agent pathfinding algorithm designed to cope with dynamic obstacles, and Conflict-Based Search (CBS), a state-of-the-art search-based MAPF algorithm. SMT-CCBS builds on similar ideas, but is based on a different state-of-the-art MAPF algorithm called SMT-CBS, which applied a SAT Modulo Theory (SMT) problem-solving procedure. CCBS guarantees to return solutions that have minimal sum-of-costs, while SMT-CCBS guarantees to return solutions that have minimal makespan. We implemented CCBS and SMT-CCBS and evaluated them on grid-based MAPF problems and general graphs (roadmaps). The results show that both algorithms can efficiently solve optimally non-trivial MAPF problems.

Towards a Complete Multi-agent Pathfinding Algorithm for Large Agents

2022 · CHAPTER · en

Multi-agent pathfinding (MAPF) is a challenging problem which is hard to solve optimally even when simplifying assumptions are adopted, e.g. planar graphs (typically – grids), discretized time, uniform duration of move and wait actions etc. On the other hand, MAPF under such restrictive assumptions (also known as the Classical MAPF) is equivalent to the so-called pebble motion problem for which non-optimal polynomial time algorithms do exist. Recently, a body of works emerged that investigated MAPF beyond the basic setting and, in particular, considered agents of arbitrary size and shape. Still, to the best of our knowledge no complete algorithms for such MAPF variant exists. In this work we attempt to narrow this gap by considering MAPF for large agents and suggesting how this problem can be reduced to pebble motion on (general) graphs. The crux of this reduction is the procedure that moves away the agents away from the edge which is needed to perform a move action of the current agent. We consider different variants of how this procedure can be implemented and present a variant of the pebble motion algorithm which incorporates this procedure. Unfortunately, the algorithm is still incomplete, but empirically we show that it is able to solve much more MAPF instances (under the strict time limit) with large agents on arbitrary non-planar graphs (roadmaps) compared to the state-of-the-art MAPF solver – Continous Conflict-Based Search (CCBS).

2.5D Mapping, Pathfinding and Path Following For Navigation Of A Differential Drive Robot In Uneven Terrain

2022 · CHAPTER · en

Safe navigation in uneven terrains is an important problem in robotic research. In this paper we propose a 2.5D navigation system which consists of elevation map building, path planning and local path following with obstacle avoidance. For local path following we use Model Predictive Path Integral (MPPI) control method. We propose novel cost-functions for MPPI in order to adapt it to elevation maps and motion through unevenness. We evaluate our system on multiple synthetic tests and in a simulated environment with different types of obstacles and rough surfaces.