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

Improving Continuous-time Conflict Based Search

2021 · CHAPTER · en

Conflict-Based Search (CBS) is a powerful algorithmic framework for optimally solving classical multi-agent path finding (MAPF) problems, where time is discretized into the time steps. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. However, the scalability of CCBS is limited because it does not include any known improvements of CBS. In this paper, we begin to close this gap and explore how to adapt successful CBS improvements, namely, prioritizing conflicts (PC), disjoint splitting (DS), and high-level heuristics, to the continuous time setting of CCBS. These adaptions are not trivial, and require careful handling of different types of constraints, applying a generalized version of the Safe interval path planning (SIPP) algorithm, and extending the notion of cardinal conflicts. We evaluate the effect of the suggested enhancements by running experiments both on general graphs and 2 k -neighborhood grids. CCBS with these improvements significantly outperforms vanilla CCBS, solving problems with almost twice as many agents in some cases and pushing the limits of multiagent path finding in continuous-time domains.

Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles

2021 · CHAPTER · en

Revisiting Bounded-Suboptimal Safe Interval Path Planning

2020 · CHAPTER · en

Map-Merging Algorithms for Visual SLAM: Feasibility Study and Empirical Evaluation

2020 · CHAPTER · en

Simultaneous localization and mapping, especially the one relying solely on video data (vSLAM), is a challenging problem that has been extensively studied in robotics and computer vision. State-of-the-art vSLAM algorithms are capable of constructing accurate-enough maps that enable a mobile robot to autonomously navigate an unknown environment. In this work, we are interested in an important problem related to vSLAM, i.e. map merging, that might appear in various practically important scenarios, e.g. in a multi-robot coverage scenario. This problem asks whether different vSLAM maps can be merged into a consistent single representation. We examine the existing 2D and 3D map-merging algorithms and conduct an extensive empirical evaluation in realistic simulated environment (Habitat). Both qualitative and quantitative comparison is carried out and the obtained results are reported and analyzed.

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

2020 · CHAPTER · en

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.

Automatic Tool for Gazebo World Construction: From a Grayscale Image to a 3D Solid Model

2020 · CHAPTER · en

Laser Rangefinder and Monocular Camera Data Fusion for Human-Following Algorithm by PMB-2 Mobile Robot in Simulated Gazebo Environment

2020 · CHAPTER · en

Multi-Agent Pathfinding with Continuous Time

2019 · CHAPTER · en

Multi-Agent Pathfinding (MAPF) is the problem offinding paths for multiple agents such that everyagent reaches its goal and the agents do not col-lide. Most prior work on MAPF was on grids, as-sumed agents’ actions have uniform duration, andthat time is discretized into timesteps. We proposea MAPF algorithm that does not rely on these as-sumptions, is complete, and provides provably op-timal solutions. This algorithm is based on a noveladaptation of Safe interval path planning (SIPP), acontinuous time single-agent planning algorithm,and a modified version of Conflict-based search(CBS), a state of the art multi-agent pathfinding al-gorithm. We analyze this algorithm, discuss its prosand cons, and evaluate it experimentally on severalstandard benchmarks.

Real-time Vision-based Depth Reconstruction with NVidia Jetson

2019 · CHAPTER · en

Vision-based depth reconstruction is a challenging problem extensively studied in computer vision but still lacking universal solution. Reconstructing depth from single image is particularly valuable to mobile robotics as it can be embedded to the modern vision-based simultaneous localization and mapping (vSLAM) methods providing them with the metric information needed to construct accurate maps in real scale. Typically, depth reconstruction is done nowadays via fully-convolutional neural networks (FCNNs). In this work we experiment with several FCNN architectures and introduce a few enhancements aimed at increasing both the effectiveness and the efficiency of the inference. We experimentally determine the solution that provides the best performance/accuracy tradeoff and is able to run on NVidia Jetson with the framerates exceeding 16FPS for 320 × 240 input. We also evaluate the suggested models by conducting monocular vSLAM of unknown indoor environment on NVidia Jetson TX2 in real-time. Open-source implementation of the models and the inference node for Robot Operating System (ROS) are available at https://github.com/CnnDepth/tx2_fcnn_node.

Prioritized Multi-Agent Path Finding for Differential Drive Robots

2019 · CHAPTER · en

Methods for centralized planning of the collision-free trajectories for a fleet of mobile robots typically solve the discretized version of the problem and rely on numerous simplifying assumptions, e.g. moves of uniform duration, cardinal only translations, equal speed and size of the robots etc., thus the resultant plans can not always be directly executed by the real robotic systems. To mitigate this issue we suggest a set of modifications to the prominent prioritized planner - AA-SIPP(m) - aimed at lifting the most restrictive assumptions (syncronized translation only moves, equal size and speed of the robots) and at providing robustness to the solutions. We evaluate the suggested algorithm in simulation and on differential drive robots in typical lab environment (indoor polygon with external video-based navigation system). The results of the evaluation provide a clear evidence that the algorithm scales well to large number of robots (up to hundreds in simulation) and is able to produce solutions that are safely executed by the robots prone to imperfect trajectory following. The video of the experiments can be found at https://youtu.be/Fer_irn4BG0.