Miroslav Kulich

David Woller, Viktor Kozák, Miroslav Kulich et al.

The Electric Vehicle Routing Problem (EVRP) extends the classical Vehicle Routing Problem (VRP) to reflect the growing use of electric and hybrid vehicles in logistics. Due to the variety of constraints considered in the literature, comparing approaches across different problem variants remains challenging. A minimalistic variant of the EVRP, known as the Capacitated Green Vehicle Routing Problem (CGVRP), was the focus of the CEC-12 competition held during the 2020 IEEE World Congress on Computational Intelligence. This paper presents the competition-winning approach, based on the Variable Neighborhood Search (VNS) metaheuristic. The method achieves the best results on the full competition dataset and also outperforms a more recent algorithm published afterward.

David Zahrádka, David Woller, Denisa Mužíková et al.

During the execution of Multi-Agent Path Finding (MAPF) plans in real-life applications, the MAPF assumption that the fleet's movement is perfectly synchronized does not apply. Since one or more of the agents may become delayed due to internal or external factors, it is often necessary to use a robust execution method to avoid collisions caused by desynchronization. Robust execution methods - such as the Action Dependency Graph (ADG) - synchronize the execution of risky actions, but often at the expense of increased plan execution cost, because it may require some agents to wait for the delayed agents. In such cases, the execution's cost can be reduced while still preserving safety by finding a new plan either by rescheduling (reordering the agents at crossroads) or the more general replanning capable of finding new paths. However, these operations may be costly, and the new plan may not even lead to lower execution cost than the original plan: for example, the two plans may be the exact same. Therefore, we estimate the benefit that can be achieved by single replanning in scenarios with delayed agents given an immediate state of the execution with a fully connected feed-forward neural network. The input to the neural network is a set of newly designed ADG-based features describing the robust execution's state and the impact of potential delays, and the output is an estimated benefit achievable by replanning. We train and test the network on a new labeled dataset containing 12,000 experiments, and we show that our proposed method is capable of reducing the impact of delays by up to 94.6% of the achievable reduction.

Viktor Kozák, Karel Košnar, Jan Chudoba et al.

Inspection systems utilizing unmanned aerial vehicles (UAVs) equipped with thermal cameras are increasingly popular for the maintenance of photovoltaic (PV) power plants. However, automation of the inspection task is a challenging problem as it requires precise navigation to capture images from optimal distances and viewing angles. This paper presents a novel localization pipeline that directly integrates PV module detection with UAV navigation, allowing precise positioning during inspection. Detections are used to identify the power plant structures in the image and associate these with the power plant model. We define visually recognizable anchor points for the initial association and use object tracking to discern global associations. We present three distinct methods for visual segmentation of PV modules based on traditional computer vision, deep learning, and their fusion, and we evaluate their performance in relation to the proposed localization pipeline. The presented methods were verified and evaluated using custom aerial inspection data sets, demonstrating their robustness and applicability for real-time navigation. Additionally, we evaluate the influence of the power plant model's precision on the localization methods.

Miroslav Kulich, Tomáš Novák, Libor Přeucil

The pebble-motion on graphs is a subcategory of multi-agent pathfinding problems dealing with moving multiple pebble-like objects from a node to a node in a graph with a constraint that only one pebble can occupy one node at a given time. Additionally, algorithms solving this problem assume that individual pebbles (robots) cannot move at the same time and their movement is discrete. These assumptions disqualify them from being directly used in practical applications, although they have otherwise nice theoretical properties. We present modifications of the Push and Rotate algorithm [1], which relax the presumptions mentioned above and demonstrate, through a set of experiments, that the modified algorithm is applicable for planning in automated warehouses.

Miroslav Kulich, Jiří Kubalík, Libor Přeučil

This paper deals with the problem of autonomous navigation of a mobile robot in an unknown 2D environment to fully explore the environment as efficiently as possible. We assume a terrestrial mobile robot equipped with a ranging sensor with a limited range and 360 degrees field of view. The key part of the exploration process is formulated as the d-Watchman Route Problem which consists of two coupled tasks - candidate goals generation and finding an optimal path through a subset of goals - which are solved in each exploration step. The latter has been defined as a constrained variant of the Generalized Traveling Salesman Problem and solved using an evolutionary algorithm. An evolutionary algorithm that uses an indirect representation and the nearest neighbor based constructive procedure was proposed to solve this problem. Individuals evolved in this evolutionary algorithm do not directly code the solutions to the problem. Instead, they represent sequences of instructions to construct a feasible solution. The problems with efficiently generating feasible solutions typically arising when applying traditional evolutionary algorithms to constrained optimization problems are eliminated this way. The proposed exploration framework was evaluated in a simulated environment on three maps and the time needed to explore the whole environment was compared to state-of-the-art exploration methods. Experimental results show that our method outperforms the compared ones in environments with a low density of obstacles by up to 12.5%, while it is slightly worse in office-like environments by 4.5% at maximum. The framework has also been deployed on a real robot to demonstrate the applicability of the proposed solution with real hardware.

Michaela Brejchová, Miroslav Kulich, Jan Petrš et al.

MoleMOD is a heterogeneous self-reconfigurable modular robotic system to be employed in architecture and civil engineering. In this paper we present two components of the MoleMOD infrastructure - a test environment and a planning algorithm. The test environment for simulation and visualization of active parts as well as passive blocks of MoleMOD is based on Gazebo - a powerful general-purpose robotic simulator. The key effort has been put into preparation of realistic models of passive and active components taking into account their physical characteristics. Moreover, given a starting configuration of the MoleMOD system and a final configuration an approach to plan collision-free trajectories for a fleet of active parts is introduced.

Jakub Hvězda, Miroslav Kulich, Libor Přeučil

In this chapter, we propose a novel approach for solving the coordination of a fleet of mobile robots, which consists of finding a set of collision-free trajectories for individual robots in the fleet. This problem is studied for several decades, and many approaches have been introduced. However, only a small minority is applicable in practice because of their properties - small computational requirement, producing solutions near-optimum, and completeness. The approach we present is based on a multi-robot variant of Rapidly Exploring Random Tree algorithm (RRT) for discrete environments and significantly improves its performance. Although the solutions generated by the approach are slightly worse than one of the best state-of-the-art algorithms presented in [23], it solves problems where ter Morses algorithm fails.

Tomislav Petković, Jakub Hvězda, Tomáš Rybecký et al.

With the substantial growth of logistics businesses the need for larger and more automated warehouses increases, thus giving rise to fully robotized shop-floors with mobile robots in charge of transporting and distributing goods. However, even in fully automatized warehouse systems the need for human intervention frequently arises, whether because of maintenance or because of fulfilling specific orders, thus bringing mobile robots and humans ever closer in an integrated warehouse environment. In order to ensure smooth and efficient operation of such a warehouse, paths of both robots and humans need to be carefully planned; however, due to the possibility of humans deviating from the assigned path, this becomes an even more challenging task. Given that, the supervising system should be able to recognize human intentions and its alternative paths in real-time. In this paper, we propose a framework for human deviation detection and intention recognition which outputs the most probable paths of the humans workers and the planner that acts accordingly by replanning for robots to move out of the human's path. Experimental results demonstrate that the proposed framework increases total number of deliveries, especially human deliveries, and reduces human-robot encounters.

Miroslav Kulich, Libor Přeučil, Juan José Miranda Bront

Two variants of multi-robot search for a stationary object in a priori known environment represented by a graph are studied in the paper. The first one is a generalization of the Traveling Deliveryman Problem where more than one deliveryman is allowed to be used in a solution. Similarly, the second variant is a generalization of the Graph Search Problem. A novel heuristics suitable for both problems is proposed which is furthermore integrated into a cluster-first route second approach. A set of computational experiments was conducted over the benchmark instances derived from the TSPLIB library. The results obtained show that even a standalone heuristics significantly outperforms the standard solution based on k- means clustering in quality of results as well as computational time. The integrated approach furthermore improves solutions found by a standalone heuristics by up to 15% at the expense of higher computational complexity.

M. Estefanía Pereyra, R. Gastón Araguás, Miroslav Kulich

An algorithm for robot formation path planning is presented in this paper. Given a map of the working environment, the algorithm finds a path for a formation taking into account possible split of the formation and its consecutive merge. The key part of the solution works on a graph and sequentially employs an extended version of Dijkstra's graph-based algorithm for multiple robots. It is thus deterministic, complete, computationally inexpensive, and finds a solution for a fixed source node to another node in the graph. Moreover, the presented solution is general enough to be incorporated into high-level tasks like cooperative surveillance and it can benefit from state-of-the-art formation motion planning approaches, which can be used for evaluation of edges of an input graph. The performed experimental results demonstrate the behavior of the method in complex environments for formations consisting of tens of robots.

Miroslav Kulich, Viktor Kozák, Libor Přeučil

In this paper, we present an integrated solution to memory-efficient environment modeling by an autonomous mobile robot equipped with a laser range-finder. Majority of nowadays approaches to autonomous environment modeling, called exploration, employs occupancy grids as environment representation where the working space is divided into small cells each storing information about the corresponding piece of the environment in the form of a probabilistic estimate of its state. In contrast, the presented approach uses a polygonal representation of the explored environment which consumes much less memory, enables fast planning and decision-making algorithms and it is thus reliable for large-scale environments. Simultaneous localization and mapping (SLAM) has been integrated into the presented framework to correct odometry errors and to provide accurate position estimates. This involves also a refinement of the already generated environment model in case of loop closure, i.e. when the robot detects that it revisited an already explored place. The framework has been implemented in Robot Operating System (ROS) and tested with a real robot in various environments. The experiments show that the polygonal representation with SLAM integrated can be used in the real world as it is fast, memory efficient and accurate. Moreover, the refinement can be executed in real-time during the exploration process.

Jakub Hvězda, Tomáš Rybecký, Miroslav Kulich et al.

In order to ensure efficient flow of goods in an automated warehouse and to guarantee its continuous distribution to/from picking stations in an effective way, decisions about which goods will be delivered to which particular picking station by which robot and by which path and in which time have to be made based on the current state of the warehouse. This task involves solution of two suproblems: (1) task allocation in which an assignment of robots to goods they have to deliver at a particular time is found and (2) planning of collision-free trajectories for particular robots (given their actual and goal positions). The trajectory planning problem is addressed in this paper taking into account specifics of automated warehouses. First, assignments of all robots are not known in advance, they are instead presented to the algorithm gradually one by one. Moreover, we do not optimize a makespan, but a throughput - the sum of individual robot plan costs. We introduce a novel approach to this problem which is based on the context-aware route planning algorithm [1]. The performed experimental results show that the proposed approach has a lower fail rate and produces results of higher quality than the original algorithm. This is redeemed by higher computational complexity which is nevertheless low enough for real-time planning.

Estefanía Pereyra, Gastón Araguás, Miroslav Kulich

A novel multi-robot path planning approach is presented in this paper. Based on the standard Dijkstra, the algorithm looks for the optimal paths for a formation of robots, taking into account the possibility of split and merge. The algorithm explores a graph representation of the environment, computing for each node the cost of moving a number of robots and their corresponding paths. In every node where the formation can split, all the new possible formation subdivisions are taken into account accordingly to their individual costs. In the same way, in every node where the formation can merge, the algorithm verifies whether the combination is possible and, if possible, computes the new cost. In order to manage split and merge situations, a set of constraints is applied. The proposed algorithm is thus deterministic, complete and finds an optimal solution from a source node to all other nodes in the graph. The presented solution is general enough to be incorporated into high-level tasks as well as it can benefit from state-of-the-art formation motion planning approaches, which can be used for evaluation of edges of an input graph. The presented experimental results demonstrate the ability of the method to find the optimal solution for a formation of robots in environments with varying complexity.

Jakub Hvězda, Miroslav Kulich, Libor Přeučil

This paper addresses the problem of coordination of a fleet of mobile robots - the problem of finding an optimal set of collision-free trajectories for individual robots in the fleet. Many approaches have been introduced during the last decades, but a minority of them is practically applicable, i.e. fast, producing near-optimal solutions, and complete. We propose a novel probabilistic approach based on the Rapidly Exploring Random Tree algorithm (RRT) by significantly improving its multi-robot variant for discrete environments. The presented experimental results show that the proposed approach is fast enough to solve problems with tens of robots in seconds. Although the solutions generated by the approach are slightly worse than one of the best state-of-the-art algorithms presented in (ter Mors et al., 2010), it solves problems where ter Mors's algorithm fails.

Miroslav Kulich, Roman Sushkov, Libor Přeučil

Routing problems are optimization problems that consider a set of goals in a graph to be visited by a vehicle (or a fleet of them) in an optimal way, while numerous constraints have to be satisfied. We present a solution based on multidimensional scaling which significantly reduces computational time of a self-organizing neural network solving a typical routing problem -- the Travelling Salesman Problem (TSP) in a polygonal domain, i.e. in a space where obstacles are represented by polygons. The preliminary results show feasibility of the proposed approach and although the results are presented only for TSP, the method is general so it can be used also for other variants of routing problems.

Miroslav Kulich, Vojtěch Lhotský, Libor Přeučil

Exploration of an unknown environment by a mobile robot is a complex task involving solution of many fundamental problems from data processing, localization to high-level planning and decision making. The exploration framework we developed is based on processing of RGBD data provided by a MS Kinect2 sensor, which allows to take advantage of state-of-the-art SLAM (Simultaneous Localization and Mapping) algorithms and to autonomously build a realistic 3D map of the environment with projected visual information about the scene. In this paper, we describe practical issues that appeared during deployment of the framework in real indoor and outdoor environments and discuss especially properties of SLAM algorithms processing MS Kinect2 data on an embedded computer.