Ing. Vojtěch Vonásek, Ph.D.

In multi-goal path planning, the task is to find a sequence to visit a set of target locations in an environment using the shortest path. Finding the order can be achieved by solving an instance of the Traveling Salesman Problem (TSP). This requires to determine paths and their lengths between the individual targets, which is solved using robotic path planning. In this paper, we propose a randomized planner for multi-goal path planning for non-holonomic mobile robots. Multiple trees are constructed simultaneously from the targets and expanded by collision-free configurations until they touch each other or obstacles. The trees are expanded using Dubins maneuvers. Therefore, the resulting trajectories satisfy the kinematic constraints of the mobile robots and they can also be used by Unmanned Aerial Vehicles flying at a constant altitude. The efficiency of the proposed planning approach is demonstrated in the multi-goal path planning for environments with tens of targets and compared to state-of-the-art approaches.

Robotic grasping and manipulation is a highly active research field. Typical solutions are usually composed of several modules, e.g. object detection, grasp selection and motion planning. However, from an industrial point of view, it is not clear which solutions can be readily used and how individual components affect each other. Benchmarks used in research are often designed with simplified settings in a very specific scenario, disregarding the peculiarities of the industrial environment. Performance in real-world applications is therefore likely to differ from benchmark results. In this paper, we present a concept for the design of general Pick&Place benchmarks, which help practitioners to evaluate the system and its components for an industrial scenario. The user specifies the workspace (obstacles, movable objects), the robot (kinematics, etc.) and chooses from a set of methods to realize a desired task. Our proposed framework executes the workflow in a physics simulation to determine a range of system-level performance measures. Furthermore, it provides introspective insights for the performance of individual components.

In this letter, we propose a novel sampling-based planner for multi-goal path planning among obstacles, where the objective is to visit predefined target locations while minimizing the travel costs. The order of visiting the targets is often achieved by solving the Traveling Salesman Problem (TSP) or its variants. TSP requires to define costs between the individual targets, which — in a map with obstacles — requires to compute mutual paths between the targets. These paths, found by path planning, are used both to define the costs (e.g., based on their length or time-to-traverse) and also they define paths that are later used in the final solution. To enable TSP finding a good-quality solution, it is necessary to find these target-to-target paths as short as possible. We propose a sampling-based planner called Space-Filling Forest (SFF*) that solves the part of finding collision-free paths. SFF* uses multiple trees (forest) constructed gradually and simultaneously from the targets and attempts to find connections with other trees to form the paths. Unlike Rapidly-exploring Random Tree (RRT), which uses the nearest-neighbor rule for selecting nodes for expansion, SFF* maintains an explicit list of nodes for expansion. Individual trees are grown in a RRT* manner, i.e., with rewiring the nodes to minimize their cost. Computational results show that SFF* provides shorter target-to-target paths than existing approaches, and consequently, the final TSP solutions also have a lower cost.

In recent years, Micro Aerial Vehicles (MAVs) have become widely available and are successfully used in many real scenarios. While the early applications like surveillance mostly utilized single MAVs or a group of multiple, yet non-cooperative MAVs, recent research is more focused on a group of cooperating MAVs. A typical example is the payload transport task, where multiple MAVs carry a single object. This problem has been studied mainly from the control theory point of view, providing robust control to cooperating MAVs using the dynamics of the whole system. Real applications, however, require operating in unknown environments with obstacles, which needs motion planning. In this paper, we propose a novel motion planning method for multiple MAVs operating in unknown environments. The proposed work is based on the Sensor-based Random Trees method (SRT), which was originally intended for exploration of unknown environments. We extend the method for online path planning of multi MAVs. In the proposed method, each MAV makes a motion plan and exchanges key waypoints with other MAVs to ensure that their mutual positions satisfy the mission constraints. The performance of the method is demonstrated in various simulation experiments.

Computation of trajectories for ligand binding and unbinding via protein tunnels and channels is important for predicting possible protein–ligand interactions. These highly complex processes can be simulated by several software tools, which provide biochemists with valuable information for drug design or protein engineering applications. This paper focuses on aiding this exploration process by introducing the DockVis visual analysis tool. DockVis operates with the multivariate output data from one of the latest available tools for the prediction of ligand transport, CaverDock. DockVis provides the users with several linked views, combining the 2D abstracted depictions of ligands and their surroundings and properties with the 3D view. In this way, we enable the users to perceive the spatial configurations of ligand passing through the protein tunnel. The users are initially visually directed to the most relevant parts of ligand trajectories, which can be then explored in higher detail by the follow‐up analyses. DockVis was designed in tight collaboration with protein engineers developing the CaverDock tool. However, the concept of DockVis can be extended to any other tool predicting ligand pathways by the molecular docking. DockVis will be made available to the wide user community as part of the Caver Analyst 3.0 software package (www.caver.cz).

High-dimensional configuration space is usually searched using sampling-based motion planning methods. The well-known issue of sampling-based planners is the narrow passage problem caused by small regions of the configuration space that are difficult to cover by random samples. Practically, the presence of narrow passages decreases the probability of finding a solution, and to cope with it, the number of random samples has to be significantly increased, which also increases the planning time. By dilating the free space, e.g., by scaling-down or thinning the robot (or obstacles), narrow passages become wider, which allows us to compute an approximate solution. Then, the configuration space can be sampled densely around the approximate solution to find the solution of the original problem. However, this process may fail if the final solution is too far from the approximate one. In this paper, we propose a method to find multiple approximate solutions in the configuration space to increase the chance of finding the final solution. The approximate solutions are computed by repeated search of the configuration space while avoiding, if possible, the already discovered solutions. This enables us to search for distinct solutions leading through different parts of the configuration space. The number of approximate solutions is automatically determined based on their similarity. All approximate solutions are then used to guide the sampling of the configuration space. The performance of the proposed approach is verified in scenarios with multiple narrow passages and the benefits of the method are demonstrated by comparing the results with the state-of-the-art planners.

Motion planning of 3D solid objects leads to a search in a 6D configuration space. Sampling-based planners randomly sample the configuration space and store the collision-free samples into a graph (roadmap) that can be searched by standard graph-search methods. The well-known issue of the sampling-based planners is the narrow passage problem. Narrow passages are small collision-free regions in the configuration space that are, due to their low volume, difficult to cover by the random samples, which prevents the sampling-based planners to find a path leading through the passages. By decreasing the size of the object, the relative volume of the narrow passages is increased, which helps to cover them more densely. This allows the planner to find an approximate solution, i.e., a solution feasible for the smaller object. The approximate solution can be then used to iteratively guide the sampling in the configuration space, while increasing the size of the object, until a solution for the original object is found. In this paper, we propose a modification of the iterative guiding process. To avoid a situation where the part of the guiding path is too close to obstacles of the configuration space, we shift it away from the obstacles. This requires to estimate the surface of the obstacle region, which is achieved by detecting its boundary configurations during the sampling process. Experiments have shown that the proposed modification outperforms the simple guiding using approximate solutions, as well as other related state-of-the-art planners.

Path planning of 3D solid objects leads to search in a six-dimensional configuration space, which can be solved by sampling-based motion planning. The well-known issue of sampling-based planners is the narrow passage problem, which is caused by the presence of small regions of the configuration space that are difficult to cover by random samples. Guided-based planners cope with this issue by increasing the probability of sampling along an estimated solution (a guiding path). In the case of six-dimensional configuration space, the guiding path needs to be computed in the configuration space rather than in the workspace. Fast computation of guiding paths can be achieved by solving a similar, yet simpler problem, e.g., by reducing the size of the robot. This results in an approximate solution (path) that is assumed to be located near the solution of the original problem. The guided sampling along this approximate solution may, however, fail if the approximate solution is too far from the desired solution. In this paper, we cope with this problem by sampling the configuration space along multiple approximate solutions. The approximate solutions are computed using a proposed iterative process: after a path (solution) is found, it forms a region where the subsequent search is inhibited, which boosts the search of new solutions. The performance of the proposed approach is verified in scenarios with multiple narrow passages and compared with the state-of-the-art planners.

Cooperative carrying of large, cable-suspended payloads by a pair of cooperating unmanned aerial vehicles (UAVs) is tackled in this paper. The proposed system, involving a sampling-based motion planning algorithm and a model predictive control-based coordination of UAVs, aims to achieve a smooth and reliable flight performance in environments with obstacles. The motion planning is designed to satisfy constraints on relative positions of UAVs, which are defined from the cooperative transport task and by onboard mutual localization, which is used for real-time estimation of states of neighboring robots carrying the object. Besides, a guiding principle with a cost-driven expansion is employed to steer the growth of a Rapidly-exploring Random Tree (RRT) to keep the coupled system of UAVs and the object as close to desired mutual positions as possible. A significant deviation of the controlled system from the desired configuration, by increasing or decreasing the relative distance between UAVs carrying the cable-suspended object, is achieved only if it is required by environment constraints (e.g. in narrow passages), while the allowed limits are always satisfied. Using the guiding principle enables us to find feasible solutions of the problem in a reasonable short time using onboard computer even in environments with a complicated structure of obstacles. The proposed system was evaluated in numerous simulations, compared with state-of-the-art solutions using statistical sets of results, and its performance and reliability were verified in experiments in real-world conditions.

In the task of cooperative surveillance using Micro Aerial Vehicles (MAVs), MAVs cooperatively observe a given set of Areas of Interest (AoI). The missions are usually prepared in a decoupled manner: first, the sensing locations are found, followed by computations of the trajectories assuming GPS-based localization. The precision of GPS may, however, be insufficient to keep the MAVs in compact groups, which may lead to mutual collisions. To avoid the collisions between MAVs, a camera-based on-board localization has to be used. This however requires to maintain positions of the team members in the given range to enable reliable on-board localization (each MAV has to be visible from other ones). The task of the mission planning is to find an appropriate distribution of MAVs above AoIs together with feasible trajectories from a depot to reach these locations. The on-board localization constraints and MAV motion constraints have to be satisfied during the entire mission. We propose a modification of RRT (Rapidly Exploring Random Tree) for this mission planning. The algorithm first explores the state space to find suitable sensing locations together with feasible trajectories towards them. Then, the sensing locations are optimized using Particle Swarm optimization (PSO). The proposed method has been verified in numerous simulations and outdoor experiments. The achieved results exhibit significantly better performance in terms of lower computational power and complexity of solved scenarios than the state-of-the-art solutions.

Molecular docking is one of the key mechanisms for predicting possible interactions between ligands and proteins. This highly complex task can be simulated by several software tools, providing the biochemists with possible ligand trajectories, which have to be subsequently explored and evaluated for their biochemical relevance. This paper focuses on aiding this exploration process by introducing DockVis visual analysis tool. DockVis operates primarily with the multivariate output data from one of the latest available tools for molecular docking, CaverDock. CaverDock output consists of several parameters and properties, which have to be subsequently studied and understood. DockVis was designed in tight collaboration with protein engineers using the CaverDock tool. However, we believe that the concept of DockVis can be extended to any other molecular docking tool providing the users with corresponding computation results.

Path planning of 3D solid objects has many practical applications. Sampling-based planners like Rapidly-exploring Random Tree (RRT) tackle the problem by the randomized sampling of the configuration space. The well-known issue of the sampling-based planners is the narrow passage problem. Narrow passages are small collision-free regions in the configuration space that are, due to their low volume, difficult to cover by the random samples, which prevents the sampling-based planners from finding a path leading through the passages. To increase the success rate of the planners, the search in the configuration space can be guided using an approximate solution. An approximate solution is found, for example, considering a smaller object (robot). The performance of this planning concept depends on the way of reducing the size of the object and the ability to find an initial solution. In this paper, we propose a novel technique to reduce the geometry of the object by a combination of triangulation and iterative removal of surface triangles. This technique is suitable for both convex and non-convex objects. In many real-world applications, narrow passages can also contain the initial or goal configurations. We thus propose the extension of the goal region to increase the probability of finding the initial approximate solution. Experiments have shown that the proposed modification outperforms the simple guiding using approximate solutions, as well as other related state-of-the-art planners.

Proteins are involved in many biochemical processes. The behavior of proteins is highly influenced by the presence of internal void space, in literature denoted as tunnels or cavities. Tunnels are paths leading from an inner protein active site to its surface. The knowledge about tunnels and their evolution over time, captured in molecular dynamics simulations, provides an insight into important protein properties (e.g., their stability or activity). For each individual snapshot of molecular dynamics, tunnels can be detected using Voronoi diagrams and then aggregated over time to trace their behavior. However, this approach is suitable only when a given tunnel is detected in all snapshots of molecular dynamics. This is often not the case of traditionally used approaches to tunnel computation. When a tunnel becomes too narrow in a particular snapshot, the existing approaches cannot detect this case and the tunnel completely disappears from the results. On the other hand, this situation can be quite common as tunnels move, disappear and appear again, split, or merge. Therefore, in this paper we propose a method which enables to trace also tunnels in those missing snapshots. We call them dynamic tunnels and we use the sampling-based motion planning to compute them. The Rapidly Exploring Random Tree (RRT) algorithm is used to explore the void space in each frame of the protein dynamics. The void space is represented by a tree structure that is transferred to the next frame of the dynamics and updated to remove collisions and to cover newly emerged free regions of the void space. If the void space reaches the surface of the protein, a dynamic tunnel is reconstructed by tracking back in the tree towards a desired place (i.e., the active site).

Sampling-based motion planners are often used to solve motion planning problems for robots with many degrees of freedom. These planners explore the related configuration space by random sampling. The well-known issue of the sampling- based planners is the narrow passage problem. Narrow passages are small collision-free regions in the configuration space that are, due to their volume, difficult to cover by the random samples. The volume of the narrow passages can be artificially increased by reducing the size of the robot, e.g., by scaling-down its geometry, which increases the probability of placing the random samples into the narrow passages. This allows us to find an approximate solution (trajectory) and use it as a guide to find the solution for a larger robot. Guiding along an approximate solution may, however, fail if this solution leads through such parts of the configuration space that are not reachable or traversable by a larger robot. To improve this guiding process, we propose to compute several approximate solutions leading through different parts of the configuration space, and use all of them to guide the search for a larger robot. We introduce the concept of disabled regions that are prohibited from the exploration using the sampling process. The disabled regions are defined using trajectories already found in the space being searched. The proposed method can solve planning problems with narrow passages with higher success rate than other state-of-the-art planners.

In multi-goal path planning, the task is to find a sequence to visit a set of target locations in an environment. The combinatorial part of the problem (finding the sequence) can be solved as an instance of Traveling Salesman Problem, which requires knowledge about collision-free paths (and distances) between the individual targets. Finding the collision-free paths between the targets is essential in this task. Sampling-based planners like Probabilistic Roadmaps (PRM) and Rapidly-exploring Random Tree (RRT) can be used to find these paths. However, PRM can be computationally demanding, as it attempts to connect each node in the roadmap to its neighbors, regardless of their later usage in the solution. Contrary, RRT is a tree-based planner, and one run can only provide paths starting in the root of the tree (a single target). In this paper, we propose a novel planner for multi-goal path planning. Multiple trees (forest) are constructed simultaneously from the targets and expanded by collision-free configurations until they touch each other or obstacles. Each tree, therefore, does not explore the whole configuration space (as in the case of RRT), and its construction is faster than PRM, as it uses lower number of edges. The efficiency of this new planning approach is demonstrated in the multi-goal path planning in 2D environment with tens of targets and with narrow passages.

In many cases, protein reactions with other small molecules (ligands) occur in a deeply buried active site. When studying these types of reactions, it is crucial for biochemists to examine trajectories of ligand motion. These trajectories are predicted with in-silico methods that produce large ensembles of possible trajectories. In this paper, we propose a novel approach to the interactive visual exploration and analysis of large sets of ligand trajectories, enabling the domain experts to understand protein function based on the trajectory properties. The proposed solution is composed of multiple linked 2D and 3D views, enabling the interactive exploration and filtering of trajectories in an informed way. In the workflow, we focus on the practical aspects of the interactive visual analysis specific to ligand trajectories. We adapt the small multiples principle to resolve an overly large number of trajectories into smaller chunks that are easier to analyze. We describe how drill-down techniques can be used to create and store selections of the trajectories with desired properties, enabling the comparison of multiple datasets. In appropriately designed 2D and 3D views, biochemists can either observe individual trajectories or choose to aggregate the information into a functional boxplot or density visualization. Our solution is based on a tight collaboration with the domain experts, aiming to address their needs as much as possible. The usefulness of our novel approach is demonstrated by two case studies, conducted by the collaborating protein engineers.

Recent developments in connected industries and internet of things identified demands for flexible reconfiguration and reprogramming of robots and machine tools. The demand for reconfiguration comes from changes in production process ordering or individual products; the demand for reprogramming comes from changing workplace organization and material flow. Yet these reconfiguration and reprogramming is often characterized by constants for a specific use-case in terms of precomputed trajectories. In this paper, we present an approach of monitoring the robot's workspace and using an online replanning of motion. We present a toolchain that is available and ready to use for a big class of industrial robots that have a position setpoint control interface. The feasibility is demonstrated in small laboratory experiments with a modular industrial robot in a common human-robot interface scenario.

The task of bin picking is to automatically unload objects from a container using a robotic manipulator. A widely used solution is to organize the objects into a predictable pattern, e.g., a workpiece carrier, in order to simplify all integral subtasks like object recognition, motion planning and grasping. In such a case, motion planning can even be solved offline as it is ensured that the objects are always at the same positions. However, there is a growing demand for non-structured bin picking, where the objects can be placed randomly in the bins. This arises from recent trends of transforming classical factories into smart production facilities allowing small lot sizes at the efficiency of mass production. Due to unknown positions of the objects in the non-structured bin picking scenario, trajectories for the manipulator cannot be precomputed, but they have to be computed online. Sampling-based motion planning methods like Rapidly Exploring Random Tree (RRT) can be used to plan the trajectories. In this paper, we propose a modification of RRT for distributed motion planning aiming to reduce the runtime. The planning task is first simplified by computing several guiding waypoints. The waypoints are distributed to a set of planners running in parallel and each planner computes a short trajectory between two given waypoints. Connecting the waypoints is easier than solving the original task, therefore each planner runs fast. In comparison to other parallel motion planning techniques, the proposed approach does not require any communication among the computational nodes, which is more suitable for cloud-based computing. The proposed work has been verified both in simulation and on a prototype of a bin picking system. (C) 2018 The Authors. Published by Elsevier B.V.

Sampling-based path planning algorithms like Rapidly-exploring Random Trees (RRT) are widely used to solve path planning problems for robots with many Degrees Of Freedom (DOF). Although the sampling-based planners are stochastic and provide different solutions in every trial, many resulting trajectories can be quite similar, e.g., because they are close to each other. Computation of di verse paths, i.e., paths leading through different parts of the configuration space, is important for online navigation of mobile robots or for finding solutions leading through different narrow passages of the configuration space. In this paper, we propose an extension of the RRT algorithm to find diverse paths in the configuration space iteratively. The idea of the proposed method is to prohibit the exploration of selected regions of the configuration space. The prohibited regions are defined using the waypoints of paths computed in the previous iterations. We show that the proposed method finds more diverse trajectories than can be achieved by repeated computations of a single sampling-based planner.

Path planning of 3D objects, where the task is to find a collision-free path for a rigid 3D object among obstacles, is studied in this paper. This task has many applications mainly in robotics, but also in other fields, e.g., in computer-aided design and computational biology. Sampling-based approaches like Rapidly Exploring Random Trees (RRT) solve the problem by randomized search in the corresponding configuration space. A well known bottleneck of sampling-based methods is the narrow passage problem. Narrow passages are small regions in the configuration space that are difficult to cover by the random samples, which prevents to find a path leading through them. In this paper, we propose a novel extension to Rapidly Exploring Random Tree (RRT) to cope with the narrow passage problem. The proposed planner first solves a simplified (relaxed) version of the problem which is achieved, e.g., by reducing the geometry of the robot. This approximate solution is then used to guide the search in the configuration space for a less relaxed version of the problem, i.e., for a larger robot. The proposed approach is compared to several state-of-the-art path planners in a set of 3D planning benchmarks. Besides, the method is verified also in the task of computing exit pathways for small molecules (ligand) from a protein.

In the bin picking problem, the task is to automatically unload objects from a container using a robotic manipulator. The task is often approached by organizing the objects into a predictable pattern, e.g., a workpiece carrier, in order to simplify all integral subtasks like object recognition, motion planning and grasping. In such a case, motion planning can even be solved offline as it is ensured that the objects are always at the same positions at known times. However, there is a growing demand for non-structured bin picking, where the objects can be placed randomly in the bins. This arises from recent trends of transforming classical factories into smart production facilities allowing small lot sizes at the efficiency of mass production. The demand for fast and highly flexible handling and manipulation abilities of industrial robots requires to solve all the bin picking methods, including motion planning, online. In this paper, we propose a novel technique for fast sampling-based motion planning of robotic manipulators using motion primitives. Motion primitives are short trajectories that boost search of the configuration space and consequently speed up the planning phase. The proposed work has been verified in a simulation and on a prototype of a bin picking system.

Proteins are involved in many biochemical processes. The behavior of proteins is influenced by internal void space such as tunnels or cavities. Tunnels are paths leading from an inner protein active site to its surface. The knowledge about tunnels and their evolution over time provides an insight into protein properties (e.g., stability). Sampling-based motion planning techniques like Rapidly Exploring Random Tree (RRT) can be used to find tunnels by sampling the corresponding configuration space. These methods can be easily adapted to operate with protein dynamics. The inner void space of proteins is very limited, which may decrease the ability of RRT to find a solution due to the narrow passage problem. In this paper, we propose to generate random samples using a Voronoi Diagram of the atoms. A subset of Voronoi vertices is dynamically maintained to support the generation of samples in promising regions inside the protein.

Behavior and properties of proteins as well as other bio-macromolecules is influenced by internal void space such as tunnels or cavities. Tunnels are paths leading from an active site inside the protein to its surface. Knowledge about tunnels and their evolution in time provides an insight into protein properties (e.g. stability or resistance to a co-solvent). Tunnels can be found using Voronoi diagrams (VD). To consider protein dynamics, that is represented by a sequence of protein snapshots, correspondences between VD in these snapshots need to be found. The computation of these correspondences is however time and memory consuming. In this paper, we propose a novel method for tunnel detection in dynamic proteins based on Rapidly Exploring Random Tree (RRT). The method builds a single configuration tree describing free space of the protein. The nodes of the tree are pruned according to protein dynamics. The proposed approach is compared to CAVER 3.0, one of the widely used freely available tools for protein analysis.

Modular robots are composed of many elementary mechatronic modules that can be connected to form a robot body of various shapes. This feature allows such a robot to adapt for a given task and particular environment. A motion of the modular robot is based on control of individual angles between the modules, and the robot locomotion can be realized using Central Pattern Generators (CPG). A robot motion in the environment with obstacles can be achieved using several locomotion controllers that are switched by a strategy based on motion planning techniques. Preparation of CPG-based gaits leads to a high-dimensional optimization that requires to design proper cost functions. Existing approaches optimize the gaits separately according to human-designed cost functions. In this paper, we investigate how to automatically derive a set of gaits suitable for modular robots without specifying low-level details about the gaits. We propose to optimize multiple gaits simultaneously using a single cost function. This cost function is based on the ability of motion planning to solve the task using the gaits being optimized. The proposed system is verified on several modular robots with unusual shapes including robots with failed modules.

A path planning in the space of multinominals integrated into a model predictive control mechanism for driving formations of autonomous mobile robots is presented in this paper. The proposed approach is designed to stabilize the formations in desired shapes, and to navigate the group into a final position in a partly known environment with dynamic obstacles. In addition, the system provides inter-vehicle coordination and collision avoidance in the event of failure of a team member. The method is aimed at reaching the final position of the formation in the desired shape, but it enables to change temporarily this shape if it is enforced by the environment (in narrow corridors, on response to an impending collision with obstacles and faulty team members, etc.). This autonomous emergent behaviour increases the robustness of the system and its usability. It enables a proper compromise to be found between the formation driving requirement and the effort to fulfil the mission objective, i.e., to move the group from the current state into the required position. In this paper, the convergence of the method and the requirements for stability are shown on the basis of the results of the Lyapunov theorems of stability. These theoretical achievements imply constraints on the applicability of the system, which are verified in numerical simulations and in various tests with real autonomous robots. The performances of the entire system and of independent sub-systems in various formation driving scenarios are also shown in these tests.

The task of cooperative surveillance of pre- selected Areas of Interest (AoI) in outdoor environ- ments by groups of closely cooperating Micro Aerial Vehicles (MAVs) is tackled in this paper. In the coop- erative surveillance mission, finding distributions of the MAVs in the environment to properly cover the AoIs and finding feasible trajectories to reach the obtained surveillance locations from the initial depot are crucial tasks that have to be fulfilled. In addition, motion constraints of the employed MAVs, environ- ment constraints (e.g. non-fly zones), and constraints imposed by localization of members of the groups need to be satisfied in the planning process. We for- mulate the task of cooperative surveillance as a single high-dimensional optimization problem to be able to integrate all these requirements. Due to numerous con- straints that have to be satisfied, we propose to solve the problem using an evolutionary-based optimiza- tion technique. An important aspect of the proposed method is that the cooperating MAVs are localized relatively to each other, rather than using a global localization system. This increases robustness of the system and its deploy-ability in scenarios, in which compact shapes of the MAV group with short relative distances are required.

Modular robots consist of many mechatronic modules that can be connected into various shapes and therefore adapted for a given task and environment. Motion of the robots can be achieved by locomotion generators that control joints connecting the modules. A robot can be equipped with several locomotion generators that provide basic motion primitives. A sequence of motion primitives is found using a motion planner in order to visit a given goal position. Each primitive needs to be prepared by an optimization process where parameters of a locomotion generator are tuned. Due to the possibility to create robots of various shapes, it is not easy to estimate in advance what kind of motions a robot can perform. Moreover, motion capabilities can also be influenced by failures of individual modules. Human operators may prefer motions like ‘crawl-forward’ or ‘move-left’ but such primitives might not be achievable by all robots. In this paper, we discuss how to automatically learn motion primitives that are suitable for a given robot and task. Experimental verification in simulation as well as with physical robots is presented.

Many methods have been proposed to solve the problem of shape matching, where the task is to determine similarity between given shapes. In this paper, we propose a novel method to combine many shape matching methods using procedural knowledge to increase the precision of the shape matching process in retrieval problems like place recognition task. The idea of our approach is to assign the best matching method to each template shape providing the best classification for this template. The new incoming shape is compared against all templates using their assigned method. The proposed method increases the accuracy of the classification and decreases the time complexity in comparison to generic classifier combination methods.

A system for stabilization of Micro Aerial Vehicles (MAVs), quad-rotor helicopters, flying in a compact group with an ability of fast response to changes detected in surrounding environment is presented in this paper. The core of the proposed method lies in utilization of onboard monocular cameras for visual relative localization of neighbouring MAVs. The localization cameras, which are carried by all MAVs of the group, provide an estimate of relative positions and orientations of neighbours in a limited range and viewing angle (see [1], [2] for details on the localization system). This setup allows us to gain information on close proximity of each MAV in the group in a similar way as it is done in swarms of animals in nature. The operational space of these onboard sensors is similar to sense organs of birds in flocks and fish in schools and also these sensors have similar properties. Both species gain quite precise information on relative position of the neighbors with fast update rate, but they have only a rough guess on motion prediction of the neighbors, similarly as it is provided by the onboard localization in our system.

Modular robots consist of many mechatronic modules that can be connected into various shapes and therefore adapted for a given task or environment. Motion of the robots can be achieved by locomotion generators that control joints connecting the modules. An important advantage of modular robots is their ability to recover from failures by ejecting and replacing damaged modules. This type of failure recovery may be precluded due to inability of the broken modules to cooperate or when no spare modules are available. In such a case, locomotion of a damaged robot should be adapted to allow the robot to reach a repair station or even to finish its task without the need to exchange the broken modules. In this paper, we investigate how to recover from failures using the concept of motion planning with motion primitives and how to adapt the primitives to new situations. The proposed systems allows modular robots to move even if some modules fail. Besides modular robots, the proposed system is suitable also for other robots that can be driven by locomotion generators such as legged or snake-like robots.

Modular robots may become candidates for search and rescue operations or even for future space missions, as they can change their structure to adapt to terrain conditions and to better fulfill a given task. A core problem in such missions is the ability to visit distant places in rough terrain. Traditionally, the motion of modular robots is modeled using locomotion generators that can provide various gaits, e.g. crawling or walking. However, pure locomotion generation cannot ensure that desired places in a complex environment with obstacles will in fact be reached. These cases require several locomotion generators providing motion primitives that are switched using a planning process that takes the obstacles into account. In this paper, we present a novel motion planning method for modular robots equipped with elementary motion primitives. The utilization of primitives significantly reduces the complexity of the motion planning which enables plans to be created for robots of arbitrary shapes. The primitives used here do not need to cope with environmental changes, which can therefore be realized using simple locomotion generators that are scalable, i.e., the primitives can provide motion for robots with many modules. As the motion primitives are realized using locomotion generators, no reconfiguration is required and the proposed approach can thus be used even for modular robots without self-reconfiguration capabilities. The performance of the proposed algorithm has been experimentally verified in various environments, in physical simulations and also in hardware experiments.

This paper introduces novel graph exploration based on reasoning procedure. The proposed approach does not need any markers and only a similarity measures of the places and routes are used for decisions and loop closing. The edge selection process is driven by information gain, which is computed for each edge based on the probability of the loop closure and consecutive merges performed if the loop closure take place. The edge with high probability of closing the loop and high number of edge consecutively merged and therefore eliminated from the map is preferred. A loop-closing procedure used in the exploration algorithm utilizes the information about the environment structure. A priori knowledge of the environment properties is incorporated into the reasoning procedure as logic rules. Proposed exploration algorithm were experimentally verified in simulator and with real robot in indoor environment.

This paper presents a novel motion planning algorithm for modular robots moving in environments with diverse terrain conditions. This requires the planner to generate a suitable control signal for all actuators, which can be computationally intensive. To decrease the complexity of the planning task, the concept of motion primitives is used. The motion primitives generate simple motions like ‘crawl-forward’ or ‘turn-left’ and the motion planner constructs a plan using these primitives. To preserve the efficiency and robustness of the planner on varying terrains, a novel schema called RRT-AMP (Rapidly Exploring Random Trees with Adaptive Motion Primitives) for adapting the motion primitives is introduced. The adaptation procedure is integrated into the planning process, which allows the planner simultaneously to adapt the primitives and to use them to obtain the final plan. Besides adaptation in changing environments, RRT-AMP can adapt motion primitives if some module fails. The methods is experimentally verified with robots of different morphologies to show its adaptation and planning abilities in complex environments.

Modular robots are built of many basic robotic modules that can be connected into robots of various shapes. These robots are able to recover from a failure by ejecting and replacing damaged modules. Although this type of failure recovery is usually suggested in literature, it may be precluded due inability of the broken modules to cooperate or if no spare modules are available. In such a case, locomotion of a damaged robot should be adapted to allow the robot to reach a repair station or even to finish its task without the need to exchange the broken modules. In this paper, we investigate how to adapt motions of modular robots with respect to failures using the concept of motion planning with motion primitives. The ability of the proposed system to recover from failures is verified in a simulation and also in a HW experiment.

This paper introduces a new concept for flexible motion planning and control of industrial robots. Instead of a closed monolithic architecture, an open service-based framework is proposed. The services can be run hardware-independent on a decentralized IT infrastructure (Cloud) allowing a fast reconfiguration of control modules and their multiple usage in different tasks. The services can be run on a dedicated PC or on individual virtual machines inside a single computing cluster. The proposed service-based framework was implemented and tested for the motion planning of a robotic manipulator. Effects on control performance, availability and scalability are investigated and documented.

The field of reconfigurable swarms of modular robots has achieved a current status of performance that allows applications in diverse fields that are characterized by human support (e.g. exploratory and rescue tasks) or even in human-less environments. The main goal of the EC project REPLICATOR [1] is the development and deployment of a heterogeneous swarm of modular robots that are able to switch autonomously from a swarm of robots, into different organism forms, to reconfigure hese forms, and finally to revert to the original swarm mode [2]. To achieve these goals three different types of robot modules have been developed and an extensive suite of embodied distributed cognition methods implemented [3]. Hereby the methodological key aspects address principles of self-organization. In order to tackle our ambitious approach a Grand Challenge has been proposed of autonomous operation of 100 robots for 100 days (100 days, 100 robots). Moreover, a framework coined the SOS-cycle (SOS: Swarm-Organism-Swarm) is developed. It controls the transitions between internal phases that enable the whole system to alternate between different modes mentioned above. This paper describes the vision of the Grand Challenge and the implementation and the results of the different phases of the SOS-cycle.

Physical simulation are frequently used in robotics for evaluation of control strategies or planning techniques. In this paper, a novel, light-weight open-source robotic simulator is introduced. It provides both physical and sensor simulation and it was designed to be run in a headless mode, i.e., without any visualization, which makes it suitable for com- putational grids. Despite this fact, the progress of the simulation can be later visualized using external tools like Blender 3D. This brings advantage in comparison to more general and powerful simulators that cannot be easily run on such machines. The paper briefly introduces architecture of the simulator with description of its utilization in evolutionary modular robotics.

An algorithm for autonomous deployment of groups of Micro Aerial Vehicles (MAVs) in the cooperative surveillance task is presented in this paper. The algorithm enables to find a proper distributions of all MAVs in surveillance locations together with feasible and collision free trajectories from their initial position. The solution of the MAV-group deployment satisfies motion constraints of MAVs, environment constraints (non-fly zones) and constraints imposed by a visual onboard relative localization. The onboard relative localization, which is used for stabilization of the group flying in a compact formation, acts as an enabling technique for utilization of MAVs in situations where an external local system is not available or lacks the sufficient precision.

An approach for coordination and control of 3D heterogeneous formations of unmanned aerial and ground vehicles under hawk-eye like relative localization is presented in this paper. The core of the method lies in the use of visual top-view feedback from flying robots for the stabilization of the entire group in a leader-follower formation. We formulate a novel Model Predictive Control (MPC) based methodology for guiding the formation. The method is employed to solve the trajectory planning and control of a virtual leader into a desired target region. In addition, the method is used for keeping the following vehicles in the desired shape of the group. The approach is designed to ensure direct visibility between aerial and ground vehicles, which is crucial for the formation stabilization using the hawk-eye like approach. The presented system is verified in numerous experiments inspired by search and rescue applications, where the formation acts as a searching phalanx. In addition, stability and convergence analyses are provided to explicitly determine the limitations of the method in real-world applications.

Modular robots, which are systems made of many robotic modules, can utilize various types of locomotion. Different approaches can be used to generate these basic motion skills — motion primitives. To move in a complex environment, several motion primitives are needed and a mechanism to switch them is required. This can be realized using a high-level motion planning. To enable autonomous operation of modular robots equipped with limited computational resources, it is necessary to generate the motion plans on-board, i.e., without external computers. In this paper, we propose a novel simplified motion model of a modular robot, which allows the robot to employ the motion planner as a fast on-board replanner. The proposed approach has been verified both in simulations as well as with real robots.

A fault-tolerant method for stabilization and navigation of 3D heterogeneous formations is proposed in this paper. The presented Model Predictive Control (MPC) based approach enables to deploy compact formations of closely cooperating autonomous aerial and ground robots in surveillance scenarios without the necessity of a precise external localization. Instead, the proposed method relies on a top-view visual relative localization provided by the micro aerial vehicles flying above the ground robots and on a simple yet stable visual based navigation using images from an onboard monocular camera. The MPC based schema together with a fault detection and recovery mechanism provide a robust solution applicable in complex environments with static and dynamic obstacles. The core of the proposed leader-follower based formation driving method consists in a representation of the entire 3D formation as a convex hull projected along a desired path that has to be followed by the group. Such an approach provides non-collision solution and respects requirements of the direct visibility between the team members. The uninterrupted visibility is crucial for the employed top-view localization and therefore for the stabilization of the group. The proposed formation driving method and the fault recovery mechanisms are verified by simulations and hardware experiments presented in the paper.

Modular robots consist of many modules that can be connected into various structures. This allows modular robots to adapt their shape according to a given task and environment. To visit a desired place in an environment, motion planning is required. To generate feasible plans for these robots with many degrees of freedom and many kinematic and dynamic constraints, a physical simulation is required to precisely model motion of the robots. As the physical simulation can be time consuming, motion planners need to be extended to decrease the number of simulation queries. In this paper, we propose a novel motion planning for modular robots based on guided sampling of configuration space. The guided sampling utilizes a precomputed simple path in the environment, along which the configuration space of the robot is sampled with higher probability. This approach significantly decreases the number of calls of physical simulations which increases the speed of the planning process.

Modular robots are highly flexible systems that are able to reconfigure to various shapes and to perform diverse locomotions. To visit a desired place in a complex environment, a robot can be equipped with several motion primitives that are switched using a high-level motion planning. The utilization of the high-level motion planning allows to simplify the motion primitives, which only need to provide short motions in a vicinity of the robot. This paper investigates how to automatically optimize these motion primitives of modular robots using an evolutionary approach. The proposed optimization is experimentally verified in simulated scenarios and in experiments with real robots.

High-level planning can be defined as the process of selection of an appropriate solution from a set of possible candidates. This process typically evaluates each candidate according to some reward function consisting of (1) cost, i.e., effort needed to accomplish the candidate and (2) the utility of accomplishing it and then selects the best one according to this evaluation.The key problem lies in the fact that the reward function can be rarely evaluated precisely. At the example of the problem of exploration of an unknown environment by a modular robot we show that precise simulation-based estimation of the cost function leads to better decisions of high-level planning and thus improves exploration process performance. State-of-the-art techniques compute the cost function in goal-selection as a length of the path from the current robot position to a goal-candidate. This is sufficient for robots with simple kinematics for which time to reach a candidate highly correlates with a path length. As this does not hold for complex (modular) robots, we introduce the approach that generates a feasible trajectory to each goal-candidate (taking into account kinematic constrains of the robot) and determines the cost function as time needed to perform this trajectory in a simulator. The experimental results with a robot consisting of eight modules operating in several environments show that the proposed simulation-based solution outperforms standard solutions.

In future space missions, versatile, robust, autonomous and adaptive robotic systems will be required to perform complex tasks. This can be realized using modular robots with the ability to reconfigure to various structures, which allows them to adapt to the environment as well as to a given task. As it is not possible to program beforehand the robots to cope with every possible situation, they will have to adapt autonomously. In this paper, we introduce a novel framework which allows modular robots to adapt physically (i.e., to change the structure) as well as internally (i.e. to learn the behavior) to achieve high-level tasks (e.g. ’climb-up the cliff’). The framework utilizes evolutionary methods for structure adaptation as well as to find a suitable behavior. The main idea of the framework is the utilization of simple motion skills combined by a motion planner to achieve the high-level task. This allows to achieve complex task easily without need to optimize complex behaviors of the robot.

A leader-follower formation driving algorithm developed for control of heterogeneous groups of unmanned micro aerial and ground vehicles stabilized under a top-view relative localization is presented in this paper. The core of the proposed method lies in a novel avoidance function, in which the entire 3D formation is represented by a convex hull projected along a desired path to be followed by the group. Such a representation of the formation provides non-collision trajectories of the robots and respects requirements of the direct visibility between the team members in environment with static as well as dynamic obstacles, which is crucial for the top-view localization. The algorithm is suited for utilization of a simple yet stable visual based navigation of the group (referred to as GeNav), which together with the on-board relative localization enables deployment of large teams of micro-scale robots in environments without any available global localization system. We formulate a novel Model Predictive Control (MPC) based concept that enables to respond to the changing environment and that provides a robust solution with team members' failure tolerance included. The performance of the proposed method is verified by numerical and hardware experiments inspired by reconnaissance and surveillance missions.

Place recognition is crucial for environment map- ping as well as for localization. Although vision-based place recognition is well studied, where various feature-based meth- ods can be employed, less number of works has been dedicated to laser-based place recognition. As data from laser range- finder can be represented as 2D shapes, various shape matching methods can be used to find similarities in these data. In this paper, we discuss the usage of shape matching methods for place recognition in a mapping task. Several state-of-the-art pattern recognition methods are compared on real as well as synthetic datasets. The experimental results show, that selected shape matching methods surpass the state-of-the-art robotic FLIRT feature-based algorithm in both the precision and speed.

This paper proposes a method for controlling formations of autonomous nonholonomic vehicles in order to reach a desired target region. The approach is based on utilization of pairs of virtual leaders whose control inputs are obtained in a single optimization process using model predictive control (MPC) methodology. The obtained solution of the optimization includes both a complete plan for the formation including the overall structure of robots’ workspace and control inputs for each vehicle. This ensures collision-free trajectories between the robots as well as dynamic obstacles. The proposed method enables to autonomously design arbitrary manoeuvres, like reverse driving or rotations of compact formations of car-like robots. Such a complicated behavior is illustrated by simulations and by experiments. Furthermore, the requirements that guarantee convergence of the group to the target region are formulated.

The ability to move in complex environments is a key property required for deployment of modular robots in challenging applications like search & rescue missions or space exploration. Wide range of motion types like crawling or walking can be achieved using Central Pattern Generators producing periodic control signals. Although these motions can be very effective to steer robots in their vicinity or in a given direction, they need to be switched to reach a far position in the environment. This paper presents a novel modification of Rapidly Exploring Random Tree (RRT) algorithm for modular robots. For efficient exploration of the configuration space, predefined motion primitives are used. While the motion primitives provide effective local motions, the RRT-based planner switches them in order to reach the desired global goal.

The Cable-Driven Parallel Multiple Manipulator is a supporting tool for development of control and navigation strategies of a swarm of Micro Aerial Vehicles (MAV). A crucial part of the system is a motion planning required to move the effectors representing individual MAVs to positions determined by a high-level algorithm controlling behavior of the swarm. Due to many degrees of freedom of such a system, finding feasible trajectories requires search in a high-dimensional configuration space, which is solved using a planner based on Rapidly Exploring Random Tree algorithm (RRT).

A leader-follower formation driving algorithm developed for control of heterogeneous groups of unmanned micro aerial and ground vehicles stabilized under a top-view relative localization is presented in this paper. The core of the proposed method lies in a novel avoidance function, in which the entire 3D formation is represented by a convex hull projected along a desired path to be followed by the group. Such a representation of the formation provides non-collision trajectories of the robots and respects requirements of the direct visibility between the team members in environment with static as well as dynamic obstacles, which is crucial for the top-view localization. The algorithm is suited for utilization of a simple yet stable visual based navigation of the group (referred to as GeNav), which together with the on-board relative localization enables deployment of large teams of micro-scale robots in environments without any available global localization system. We formulate a novel Model Predictive Control (MPC) based concept that enables to respond to the changing environment and that provides a robust solution with team members' failure tolerance included. The performance of the proposed method is verified by numerical and hardware experiments inspired by reconnaissance and surveillance missions.

Physical simulation is frequently used in robotics, as it allows evaluation of control strategies or planning techniques in situations, where experiments with real robots are time consuming or limited due to power resources or reliability issues. Such an example is locomotion generation for modular robots formed from many small robotic modules. To find a suitable locomotion for such a complex robot, evolutionary principles can be used, which requires to conduct many experiments. To speed up this process, a robot simulator can be employed. In this paper, a novel, light-weight open-source simulator for the modular robots is introduced. It provides both physical and sensor simulation and it was designed to be run in a headless mode, i.e., without any visualization. This allows to run it on e.g. on computational grids. Despite this fact, the progress of the simulation can be later visualized using external tools like Blender 3D. This brings advantage in comparison to more general and powerful simulators that cannot be easily run on such machines. The paper briefly introduces architecture of the simulator with description of its utilization in evolutionary modular robotics.

This article presents a control approach that enables an autonomous operation of fleets of unmanned snow ploughs at large airports. The proposed method is suited for the special demands of tasks of the airport snow shovelling. The robots have to keep a compact formation of variable shapes during moving into the locations of their deployment and for the autonomous sweeping of runways surfaces. These tasks are solved in two independent modes of the airport snow shoveling. The moving and the sweeping modes provide a full-scale solution of the trajectory planning and coordination of vehicles applicable in the specific airport environment. Nevertheless, they are suited for any multi-robot application that requires complex manoeuvres of compact formations in dynamic environment. The approach encapsulates the dynamic trajectory planning and the control of the entire formation into one merged optimization process via a novel Model Predictive Control (MPC) based methodology. The obtained solution of the optimization includes a complete plan for the formation. It respects the overall structure of the workspace and actual control inputs for each vehicle to ensure collision avoidance and coordination of team members. The presented method enables to autonomously design arbitrary manoeuvres, like reverse driving or turning of compact formations of car-like robots, which frequently occur in the airport sweeping application. Examples of such scenarios verifying the performance of the approach are shown in simulations and hardware experiments in this article. Furthermore, the requirements that guarantee a convergence of the group to a desired state are formulated for the formation acting in the sweeping and moving modes.

This paper is concerned with a variant of the multi-goal path planning in which goals are represented as convex polygons. The problem is to find a closed shortest path in a polygonal map such that all goals are visited. The proposed solution is based on a self-organizing map (SOM) algorithm for the traveling salesman problem. Neurons’ weights are considered as nodes inside the polygonal domain and connected nodes represent a path that evolves according to the proposed adaptation rules. In addition, a reference algorithm based on the solution of the traveling salesman problem and the consecutive touring polygons problem is provided to find high quality solutions of the created set of problems. The problems are designed to represent various inspection and patrolling tasks and can form a kind of benchmark set for multi-goal path planning algorithms. The performance of the algorithms is examined in this problem set, which includes an instance of the watchman route problem with restricted visibility range. The proposed SOM based algorithms provide a unified approach to solve various visibility based routing problems in polygonal maps while they provide a competitive quality of solutions to the reference algorithm with significantly lower computational requirements.

A navigation and stabilization scheme for 3D heterogeneous (UAVs and UGVs) formations acting under a hawk-eye like relative localization is presented in this paper. We formulate a novel Model Predictive Control (MPC) based concept for formation driving in a leader-follower constellation into a required target region. The formation to target region problem in 3D is solved using the MPC methodology for both: i) the trajectory planning and control of a virtual leader, and ii) the control and stabilization of followers - UAVs and UGVs. The core of the method lies in a novel avoidance function based on a model of the formation respecting requirements of the direct visibility between the team members in environment with obstacles, which is crucial for the hawk-eye localization.

Several navigation tasks utilizing a low-cost Micro Aerial Vehicle (MAV) platform AR-drone are presented in this paper to show how it can be used in an experimental verification of scientific theories and developed methodologies. An important part of this paper is an attached video showing a set of such experiments. The presented methods rely on visual navigation and localization using on-board cameras of the AR-drone employed in the control feedback. The aim of this paper is to demonstrate flight performance of this platform in real world scenarios of mobile robotics.

Motion planning of self-reconfigurable robots in an environment is a challenging task. In this paper, we propose a sampling-based motion planning approach to plan locomotion of an organism with many degrees of freedom. The proposed approach is based on the Rapidly Exploring Random tree algorithm, which uses physical simulation to explore the configuration space of the highly articulated robots. Due to large number of actuators in such organisms, a novel randomized strategy for generating input signals is proposed. We demonstrate the performance of the proposed planner on a set of complex robots moving on a plane as well as on a rough surface.

This paper presents a multi-goal path planning framework based on a self-organizing map algorithm and a model of the navigation describing evolution of the localization error. The framework combines finding a sequence of goals' visits with a goal-to-goal path planning considering localization uncertainty. The approach is able to deal with local properties of the environment such as expected visible landmarks usable for the navigation. The local properties affect the performance of the navigation, and therefore, the framework can take the full advantage of the local information together with the global sequence of the goals' visits to find a path improving the autonomous navigation. Experimental results in real outdoor and indoor environments indicate that the framework provides paths that effectively decreases the localization uncertainty; thus, increases the reliability of the autonomous goals' visits.

A heterogeneous, mobile, self-reconfigurable and modular robot platform is being developed in the projects SYMBRION and REPLICATOR. The locomotion of the robots as well as forming of the robot organisms will be controlled using evolutionary and bio-inspired techniques. As the robots are not available at the beginning of the projects and experiments are time consuming and carry risks of damaging the robots, the evolutionary algorithms will be run using a simulation. The simulation has to provide realistic movements of a swarm of robots, simulating the docking procedure between the robots as well as simulating organism motion. High requirements are imposed on such a simulator. We developed the Robot3D simulator, which dynamically simulates a swarm of mobile robots as well as robot organisms. In this paper we will give an overview of the simulation framework, we will show first results of performance tests and we will present applications for which Robot3D has already been used.

In modular robotics, complex structures can be formed from basic modules to solve tasks which would be difficult for a single robot. The development of techniques for adaptation and evolution of multi-robot organisms is the subject of Symbrion project. In the project, the bio-inspired evolutionary algorithms are massively simulated prior to run them on a real hardware. It is crucial to evolve behaviors of the robots in a simulation, that is close to a real world. Hence, accurate and efficient representation of an environment in the simulation is needed. Here, the environment is modeled using set of 3D objects (usually triangle meshes). The robots learn simple motion primitives or complex movement patterns during many runs of the evolution. The learned skills are then used during experiments with a real hardware. In this paper, we present methods for building 3D model of a real arena using a laser rangefinder. The resulting 3D models consist of triangles. They can be constructed in various level of details using state-of-the-art methods for 3D reconstruction. We will show, how the size of the models influences the speed of the simulation.

This paper concerns a variant of the multi-goal path planning problem in which goals may be polygonal regions. The problem is to find a closed shortest path in a polygonal map such that all goals are visited. The proposed solution is based on a self-organizing map algorithm for the traveling salesman problem, which is extended to the polygonal goals. Neurons' weights are considered as nodes inside the polygonal domain and connected nodes represent a path that evolves according to the proposed adaptation rules. Performance of the rules is evaluated in a set of problems including an instance of the watchman route problem with restricted visibility range. Regarding the experimental results the proposed algorithm provides flexible approach to solve various NP-hard routing problems in polygonal maps.

In this paper, a novel sampling schema for Rapidly Exploring Random Trees (RRT) is proposed to address the narrow passage issue. The introduced method employs a guiding path to steer the tree growth towards a given goal. The main idea of the proposed approach stands in a preference of the sampling of the configuration space C along a given guiding path instead of sampling of the whole space. While for a low-dimensional C the guiding path can be found as a geometric path in the robot workspace, such a path does not provide useful information for efficient sampling of a high-dimensional C. We propose an iterative scaling approach to find a guiding path in such high-dimensional configuration spaces. The approach starts with a scaled geometric model of the robot to a fraction of its original size for which a guiding path is found using the RRT algorithm. Then, such a path is iteratively used in the proposed RRT-Path algorithm for a larger robot up to its original size

An application of the self-organizing map (SOM) to the Traveling Salesman Problem (TSP) has been reported by many researchers, however these approaches are mainly focused on the Euclidean TSP variant.We consider the TSP as a problem formulation for the multi-goal path planning problem in which paths among obstacles have to be found.Weapply a simple approximation of the shortest path that seems to be suitable for the SOM adaptation procedure. The approximation is based on a geometrical interpretation of SOM, where weights of neurons represent nodes that are placed in the polygonal domain. The approximation is verified in a set of real problems and experimental results show feasibility of the proposed approach for the SOM based solution of the non-Euclidean TSP.

This paper presents the AR-Drone quadrotor helicopter as a robotic platform usable for research and education. Apart from the description of hardware and software, we discuss several issues regarding drone equipment, abilities and performance. We show, how to perform basic tasks of position stabilization, object following and autonomous navigation. Moreover, we demonstrate the drone ability to act as an external navigation system for a formation of mobile robots. To further demonstrate the drone utility for robotic research, we describe experiments in which the drone has been used. We also introduce a freely available software package, which allows researches and students to quickly overcome the initial problems and focus on more advanced issues.

Two neural network (NN) based techniques for building a simulation environment, which is employed for evolution of modular robots in the Symbrion project, are presented in this paper. The methods are able to build models of real world with variable accuracy and amount of stored information depending upon the performed tasks and evolutionary processes. In this paper, the presented algorithms are verified via experiments in scenarios designed to demonstrate the process of autonomous creation of complex artificial organisms. Performance of the methods is compared in experiments with real data and their employability in modular robotics is discussed. Beside these, the entire process of environment data acquisition and pre-processing during the real evolutionary experiments in the Symbrion project will be briefly described.

A formation driving approach based on spline path planning and vehicles coordination using the model predictive control is investigated in this paper. The proposed system enables to control all members of the team as well as to navigate the formation itself fully autonomously in a dynamic environment. Both necessary sub-tasks, robots' control and path planning for the formation, are formulated as optimization problems solved by various numerical methods in the paper. Applicability and robustness of all approaches and the entire system itself are verified by simulations as well as by real robotic experiments.

The formations of mobile robots can accomplish more challenging tasks than a single robot. However current methods for formation control rely on accurate localization of the robots within the formation. In this paper we propose a localization and navigation system for a formation of autonomous robots. In our method the robots within the formation are localized using camera data from a helicopter flying above the formation. The proposed localization system has been experimentally verified in a search & rescue scenario.

A system for autonomous roads sweeping by applying formations of mobile robots is presented in this paper. The proposed approach based on Receding Horizon Control solves the formation navigation, planning and stabilization in real-world environments with static and dynamic obstacles. The formations employed for sweeping are built up ad-hoc, taking into account length of robots' effectors (e.g. shovels, sweepers) and width of the working area. Presented method enables to smoothly merge smaller teams with the view of sweeping the larger roads (e.g. runways, highways). The formations can operate in two modes: sweeping and moving. In the sweeping mode, the formations are guided with an aim to effectively cover the cleaning roads, while in the moving mode, the planning system emphasizes the effort to reach a desired target. Furthermore, the moving mode enables to autonomously design complex formation maneuvers, as is reverse driving or turning on spot.

In this paper, we present a mobile robot navigation system used in the RoboTour challenge. We describe the basic principles of the navigation methods and show how to combine monocular vision and odometry. We propose to use the monocular vision to determine only the robot's heading and the odometry to estimate only the traveled distance. We show that the heading estimation itself can suppress odometric cumulative errors and outline a mathemtical proof of this statement. The practical result of the proof is that even simple algorithms capable to estimate just the heading can be used as a base for "record and replay" techniques. Beside the navigational principles, practical implementation of our navigation system is described. It is based on image processing algorithms for path following and landmark-based crossing traversing. An overview of experimental results is presented as well.

In this paper, we present our approach to the navigation system for the RoboTour challenge. We describe our intentions, ideas and main principles of our navigation methods which lead to the system that won in years 2008 and 2009. The main idea of our system is a simple yet novel method of position estimation based on monocular vision and odometry. Unlike in other systems, the monocular vision is used to determine only the robot's heading and the odometry is used to estimate only the traveled distance. We show that the heading estimation itself can suppress odometric cumulative errors and prove this statement mathematically and experimentally. The practical result of the proof is that even simple algorithms capable to estimate just the heading can be used as a base for ``record and replay'' techniques. Beside the navigational principles, practical implementation of our navigation system is described.

In this paper, we present results of a feasibility study of airport snow shoveling with multiple formations of autonomous snowplow robots. The main idea of the approach is to form temporary coalitions of vehicles, whose size depends on the width of the roads to be cleaned. We propose to divide the problem of snow shoveling into the subproblems of task allocation and motion coordination. For the task allocation we designed a multi-agent method applicable in the dynamic environment of airports. The motion coordination part focuses on generating trajectories for the vehicle formations based on the output of the task allocation module. Furthermore, we have developed a novel approach of formation stabilization into variable shapes depending on the width of runways.

In this paper, we present a framework that applies multiple groups of autonomous snowploughs for efficiently removing the snow from airfields. The proposed approach includes formation stabilization into variable shapes depending on the width of runways. The paper is focused on trajectory planning and control during splitting and coupling of formations for cleaning smaller auxiliary roads surrounding main runways. We propose a general method using a receding horizon control for iterative formation assignment. The algorithm is adapted for the kinematics of car-like robots and can be utilized in arbitrary static and dynamic airport assemblage. The proposed approach has been verified by simulations and by hardware experiments.

Ačkoliv existuje mnoho definic inteligence, většina se shoduje v tom, že inteligence zahrnuje pochopení a porozumění okolního světa. Skutečně inteligentní robot tedy musí umět vnímat okolní prostředí a data získaná svými senzory přeměňovat na informace o svém okolí. V robotice se sice využívají především dálkoměrné senzory umožňující jednoduše detekovat okolní objekty, ale v posledních letech se stále více prosazují kamery.

V tomto díle si vystačíme s notebookem, který bude robota v budoucnu řídit. Nejprve se budeme věnovat získání obrazu, tj. jeho přenesení do řídicího počítače robota. Budeme používat software, který dokáže vyčítat obraz z kamery a zobrazovat ho na displej.

V tomto díle představíme jednoduchou metodu, která umožní robotovi sledovat objekt s předem známou barvou. Předtím se seznámíme s některými parametry kamer, jejichž nastavení ovlivňuje kvalitu pořízeného obrazu a tím i spolehlivost robotických aplikací.

V minulém díle jsme představili jednoduché algoritmy pro hledání objektů v obraze a ukázali jsme, jak tyto algoritmy využít k řízení robotu. V tomto díle se zaměříme na zdokonalení a zefektivnění těchto metod. Ukážeme si, jak automaticky nastavovat expozici kamery tak, aby získaný obraz byl vhodný pro další zpracování.Zrychlíme metodu porovnávající daný pixel s naučeným vzorem a algoritmus hledání středů barevných objektů vylepšíme tak, aby se vyrovnal s větším počtem objektů hledané barvy.

V minulém díle jsme zdokonalili naše algoritmy pro vyhledávání objektů dané barvy a ukázali si, jak automaticky nastavovat expozici kamery tak, aby náš obraz byl vhodný k dalšímu zpracování. Dnes popíšeme jednoduchý algoritmus pro rozpoznávání cesty v obraze a představíme dva roboty, na kterých jsme naše algoritmy odzkoušeli.

The paper describes a method for motion planning for a mobile robot on a rough terrain. The proposed method is based on Rapidly exploring random tree method. For robot moving on a surface the physical interactions between robot's wheels and underneath surface have to be considered. We employ a simulator to predict the response of the robot to various input values to its controller. This allows as to make a more realistic plans. To speed up the process the guide path is used.

Complex maneuvers of formations of car-like autonomous vehicles are investigated in this paper. The proposed algorithm provides a complete plan for the formation to solve desired tasks and actual control inputs for each robot to ensure collision-free trajectories with respect to neighboring robots as well as dynamic obstacles. The method is based on utilization of complementary virtual leaders whose control inputs are obtained in one merged optimization process using receding horizon control methodologies. The functionality of the system, which enables reverse driving and arbitrary rotations of formations of nonholonomic robots, is verified by simulations of multi-robot tasks and by hardware experiments.

Koncem září minulého roku proběhl v brněnském parku Lužánky čtvrtý ročník soutěže autonomních robotů RoboTour 2009. Soutěž je zjednodušenou analogií orientačního běhu pro mobilní roboty.

Motion is one of the basic skills of mobile robots. Many methods have been introduced for solving the motion planning problem. The methods are however mainly intended to indoor environments. As mobile robots are expected to be helpful in difficult or even dangerous tasks, the need for the motion planning on a terrain is increased. Example of such a~task is mining or extraterrestrial planet exploration. This paper presents a novel method for planning a motion of a rover on a rough terrain. We assume partial knowledge about the terrain which is modeled by a triangular mesh. The model can be obtained e.g. by reconstruction of data provided by a laser rangefinder sensor. The proposed planning method uses sampling-based paradigm for finding a trajectory for a mobile robot. The presented approach considers the terrain properties (e.g. coefficient of friction) in order to generate more realistic plans.

This article describes a simple monocular navigation system for a mobile robot based on the map-and-replay technique. The presented method is robust, easy to implement, does not require sensor calibration or structured environment and its computational complexity is independent of the environment size. The method can navigate a robot while sensing only one landmark at a time, making it more robust than other monocular approaches. The aforementioned properties of the method allow even low-cost robots to effectively act in large outdoor and indoor environments with natural landmarks only. The basic idea is to utilize a monocular vision to correct only the robot's heading and leaving distance measurements just to the odometry. The heading correction itself can suppress the odometric error and prevent the overall position error from diverging. The influence of a map-based heading estimation and odometric errors on the overall position uncertainty is examined.

This paper presents a new multi-goal path planning method that incorporates the localization uncertainty in a visual inspection surveillance task. It is shown that the reliability of the executed found plan is increased if the localization uncertainty of the used navigation method is taken into account during the path planning. The navigation method follows the map&replay technique based on a combination of monocular vision and dead-reckoning. The mathematical description of the navigation method allows efficient computation of the evolution of the robot position uncertainty that is used in the proposed path planning algorithm. The algorithm minimizes the length of the inspection path while the robot position error at the goals is decreased. The presented experimental results indicate that probability of the goals visits can be increased by the proposed algorithm.

Cílem projektu "Ven ze tmy" je vývoj elektronické orientační pomůcky (EOP) pro nevidomé dovedený až do stadia otestovaného prototypu připraveného pro sériovou výrobu. Pomůcka umožní nevidomým samostatný a bezpečný pohyb v neznámém prostředí. Její funkce spočívá v prozkoumání prostoru bezprostředně se nacházejícím před uživatelem a informace o zjištěných překážkách je pak zpracována mikropočítačem a předána uživateli, který se tak může potenciálně nebezpečné překážce vyhnout.

The aim of this paper is to present an intelligent autonomous robot capable of small object manipulation. The design of the robot is influenced mainly by the rules of EUROBOT 09 competition. In this challenge, two robots pick up objects scattered on a planar rectangular playfield and use these elements to build models of Hellenistic temples. This paper describes the robot hardware, i.e. electro-mechanics of the drive, chassis and manipulator, as well as the software, i.e. localization, collision avoidance, motion control and planning algorithms.

During last decade Rapidly Exploring RandomTrees (RRT) became widely used for solving a motion planningproblem in mobile robotics. Poor performance of thealgorithm in environments with narrow passages has been noticed and several methods were proposed to improve the performance of the algorithm in such environments. This paper describes a novel approach for improving the performance of the RRT algorithm in environments with narrow passages. The proposed method uses precomputed auxiliary path which guides the RRT algorithm through the environment. The proposed method has been compared with several RRT-like algorithms. The results show that proposed algorithm can find the result in shorter time compared to other RRT-like algorithms.

The Large Maps framework is intended to acquire, store and handle spatial knowledge about large diverse environments. The framework focuses on providing information suitable for navigation, localization, spatial reasoning, planning, human-machine and machine-machine interaction. Framework stores information necessary to know how to distinguish one place from another and to traverse between them. Modular architecture allows incorporation and cooperation of methods, sensors and behaviors in this framework.

Each year, the EUROBOT association hosts a robotic competition. This competition is organized for students, young scientists and all people who are interested in robotics. This challenge allows people from different countries chance to share experience and exchange new ideas. For the second year a robotic team called "FelBot" prepared an intelligent autonomous robot for this challenge. To make a robot means not only developing robot hardware, e.i. Chassis or electromechanics of drive, but also equipping robot with software, like collision avoidance, planning algorithms, localization etc. This paper describes a mobile robot built by the "FelBot" team for this robotic cup.

Koncem září proběhl v brněnském parku Lužánky čtvrtý ročník soutěže autonomních robotů RoboTour 2009. Z patnácti soutěžících týmů se na prvním místě umístiltým LEE z katedry kybernetiky FEL ČVUT s 218 body, na druhém místě skončil brněnský tým RoboAuto s 168 body a třetí místo obsadil tým Radioklubu Písek s 56 body.

During last decade Rapidly Exploring random trees (RRT) became widely used for solving a motion planning problem in various areas. Poor performance of these algorithms has been noticed in environments with narrow passages. Several variants have been developed to address this issue. This paper presents a new variation of the RRT designed for sampling environments with narrow passages. Performance of the proposed method has been experimentally verified and results are compared with the original RRT, RRT-Bidirectional na RRT-Blossom algorithms.