Konstantin Yakovlev

Motion planning for mobile robots and autonomous vehicles is a key challenge in modern robotics. The main difficulty lies in accommodating non-trivial kinematic constraints, such as trajectory smoothness and minimum turning radius limitations. One of the most effective approaches to this problem is planning in a discretized state space, which utilizes a precomputed set of kinematically feasible trajectories known as motion primitives. The quality and generation speed of these primitives directly determine the efficiency of the entire planning process. This paper proposes a novel method for generating motion primitives for systems with bicycle-type kinematics. The method is based on representing the trajectory as a curve with a polynomial curvature function. Unlike existing approaches that use polynomial coefficients as parameters, we introduce a new reparameterization based on curvature values at key points along the trajectory. This reparameterization has a more intuitive physical meaning, which improves the convergence and stability of the numerical solution-finding method. The task of generating a primitive connecting two given states (position, orientation, curvature) is reduced to solving a system of nonlinear equations using Newton's method. The conducted experiments demonstrate the advantage of the proposed reparameterization in terms of speed and robustness compared to the baseline approach.

We consider the Anonymous Multi-Agent Path-Finding (AMAPF) problem where the agents are confined to a graph, a set of goal vertices is given, and each of these vertices has to be reached by some agent. The problem is to find an assignment of the goals to the agents as well as the collision-free paths, and we seek solutions that minimize either the sum of costs of all paths (SOC) or the maximum path cost (makespan). Two assumptions are usually used for the agents’ behavior after reaching the goals. The first assumption is that agents stay at the goals after reaching them and wait for the other agents to reach their goals, while the second assumption is that agents disappear upon arrival at goal vertices. We refer to the AMAPF problem under the first assumption and to the problem under the second assumption as AMAPF and AMAPFD, respectively. AMAPF can be solved in polynomial time with respect to the makespan objective (although existing approaches have a critical bottleneck in one part of the solving process). For the SOC objective, the known optimal approaches have worst-case exponential complexity. For AMAPFD with the SOC objective, to the best of our knowledge, no dedicated optimal solver has been reported. To this end, in this paper, we enhance the existing solution of the AMAPF-makespan problem and introduce a novel solution to AMAPFD-SOC. Specifically, for the AMAPF-makespan problem, the polynomial approach to solving this problem is to reduce it to a special type of a graph search problem, i.e., to the problem of finding a Maximum Flow on an auxiliary graph induced by the input one. The size of the former graph may be very large and the search on it may become a bottleneck for the standard Maximum Flow solvers. We suggest a specific search algorithm (called Bulk Search) that leverages the idea of exploring the search space not through considering separate search states but rather bulks of them simultaneously. That is, we implicitly compress, store, and expand bulks of the search states as single states, reducing the runtime and memory consumption. Empirically, the resulting AMAPF solver outperforms the competing approach based on the standard MF solver, and solves all publicly available MAPF instances from the MovingAI benchmark in less than 30 seconds. For the AMAPFD-SOC problem, we suggest a method to reduce the problem to a Minimum-Cost Maximum-Flow (MCMF) problem on a similar auxiliary graph used in the AMAPF problem but now with non-zero edge costs. After that, we propose a modified version of Bulk Search, called Generalized Bulk Search to help solve the MCMF problem efficiently. As a result, the AMAPFD-SOC problem is solved by an efficient solver that could solve 98.5% of all MovingAI benchmark instances in less than 30 seconds.

This paper addresses the problem of coordinated motion planning for multi-link robotic manipulator systems. One of the promising modern approaches to solving this problem is conflict-based planning, which avoids constructing a high-dimensional joint search space by sequentially solving a series of lower-dimensional problems. This is achieved by introducing spatio-temporal constraints whenever conflicts arise in individual manipulator plans, followed by replanning with these constraints in place. Unfortunately, existing methods that use constraints operate with individual time points, which reduces their practical efficiency. In this work, we present a novel conflict-based planning algorithm that utilizes interval-based temporal constraints rather than point-based ones – GECBS-T. Theoretically, the proposed algorithm guarantees bounded sub-optimality of the generated solutions; that is, for any user-defined bound w > 1, the cost of the GECBS-T solution will not exceed w times the cost of the optimal solution. In practice, the proposed algorithm significantly outperforms analogous algorithms in terms of planning speed, as confirmed by experiments conducted in the MuJoCo robotics simulator involving 2–4 KUKA robotic manipulators, each with 7 degrees of freedom.

Decentralized multi-agent navigation under uncertainty is a complex task that arises in numerous robotic applications. It requires collision avoidance strategies that account for both kinematic constraints, sensing and action execution noise. In this paper, we propose a novel approach that integrates the Model Predictive Path Integral (MPPI) with a probabilistic adaptation of Optimal Reciprocal Collision Avoidance. Our method ensures safe and efficient multi-agent navigation by incorporating probabilistic safety constraints directly into the MPPI sampling process via a Second-Order Cone Programming formulation. This approach enables agents to operate independently using local noisy observations while maintaining safety guarantees. We validate our algorithm through extensive simulations with differential-drive robots and benchmark it against state-of-the-art methods, including ORCA-DD and B-UAVC. Results demonstrate that our approach outperforms them while achieving high success rates, even in densely populated environments. Additionally, validation in the Gazebo simulator confirms its practical applicability to robotic platforms. A source code is available at http://github.com/PathPlanning/MPPI-Collision-Avoidance.

Multi-agent pathfinding (MAPF) is a problem that generally requires finding collision-free paths for multiple agents in a shared environment. Solving MAPF optimally, even under restrictive assumptions, is NP-hard, yet efficient solutions for this problem are critical for numerous applications, such as automated warehouses and transportation systems. Recently, learning-based approaches to MAPF have gained attention, particularly those leveraging deep reinforcement learning. Typically, such learning-based MAPF solvers are augmented with additional components like single-agent planning or communication. Orthogonally, in this work we rely solely on imitation learning that leverages a large dataset of expert MAPF solutions and transformer-based neural network to create a foundation model for MAPF called MAPF-GPT. The latter is capable of generating actions without additional heuristics or communication. MAPF-GPT demonstrates zero-shot learning abilities when solving the MAPF problems that are not present in the training dataset. We show that MAPF-GPT notably outperforms the current best-performing learnable MAPF solvers on a diverse range of problem instances and is computationally efficient during inference.

Mapping is one of the crucial tasks enabling autonomous navigation of a mobile robot. Conventional mapping methods output a dense geometric map representation, e.g. an occupancy grid, which is not trivial to keep consistent for prolonged runs covering large environments. Meanwhile, capturing the topological structure of the workspace enables fast path planning, is typically less prone to odometry error accumulation, and does not consume much memory. Following this idea, this letter introduces PRISM-TopoMap – a topological mapping method that maintains a graph of locally aligned locations not relying on global metric coordinates. The proposed method involves original learnable multimodal place recognition paired with the scan matching pipeline for localization and loop closure in the graph of locations. The latter is updated online, and the robot is localized in a proper node at each time step. We conduct a broad experimental evaluation of the suggested approach in a range of photo-realistic environments and on a real robot, and compare it to state of the art. The results of the empirical evaluation confirm that PRISM-Topomap consistently outperforms competitors computationally-wise, achieves high mapping quality and performs well on a real robot.

In this work, we study the problem where a group of mobile agents needs to reach a set of goal locations, but it does not matter which agent reaches a specific goal. Unlike most of the existing works on this topic that typically assume the existence of the centralized planner (or controller) and limit the agents' moves to a predefined graph of locations and transitions between them, in this work we focus on the decentralized scenarios, when each agent acts individually relying only on local observations/communications and is free to move in arbitrary direction at any time. Our iterative approach involves agents individually selecting goals, exchanging them, planning paths, and at each time step choose actions that balance between progressing along the paths and avoiding collisions. The proposed method is shown to be complete under specific assumptions on how agents progress towards their current goals, and our empirical evaluation demonstrates its superiority over a baseline decentralized navigation approach in success rate (i.e. is able to solve more problem instances under a given time limit) and a comparison with the centralized TSWAP algorithm reveals its efficiency in minimizing trajectory lengths for mission accomplishment.