Multi-Agent Path Finding (MAPF) is a problem of finding collision-free paths for a group of agents in a shared discrete environment. The agents often need to wait in place for one or more discrete time steps to avoid each other, and they frequently have multiple locations where they can wait. While the locations may be equally good from the waiting agent’s perspective, they impact the rest of the fleet because no other agent can pass through the location in the meantime. Where exactly an agent waits is decided while planning its path and only takes into consideration the agent’s own preferences. Giving the other agents the option to influence the waiting location can improve the quality of solutions found by MAPF solvers, and in case of solvers which do not re-plan, even improve their success rate. We present the Partially Safe Interval (PSI) which allows to postpone the decision about exact waiting locations while preserving safety. PSI can be obtained by a simple post-processing procedure, and by following an exact set of rules, the waiting locations can be decided whenever an exact path is necessary or when there is only one remaining option. We demonstrate the benefits of PSI using an extension of the Prioritized Safe Interval Path Planning algorithm, which improves the average Sum of Delays by up to 4.12% and the success rate by up to 5% on benchmark maps. We also provide context for the improvement by comparing the results with the state-of-the-art suboptimal methods PIBT and LaCAM.

Honeybees are one of the most important pollinators in the ecosystem. Unfortunately, the dynamics of living honeybee colonies are not well understood due to their complexity and difficulty of observation. In our project “RoboRoyale”, we build and operate a robot to be a part of a bio-hybrid system, which currently observes the honeybee queen in the colony and physically tracks it with a camera. Apart from tracking and observing the queen, the system needs to monitor the state of the honeybee comb which is most of the time occluded by workerbees. This introduces a necessary tradeoff between tracking the queen and visiting the rest of the hive to create a daily map. We aim to collect the necessary data more effectively. We evaluate several mapping methods that consider the previous observations and forecasted densities of bees occluding the view. To predict the presence of bees, we use previously established maps of dynamics developed for autonomy in human-populated environments. Using data from the last observational season, we show significant improvement of the informed comb mapping methods over our current system. This will allow us to use our resources more effectively in the upcoming season.

Visibility is a fundamental concept in computational geometry, with numerous applications in surveillance, robotics, and games. This software paper presents TřiVis, a C++ library developed by the authors for computing numerous visibility-related queries in highly complex polygonal environments. Adapting the triangular expansion algorithm, TřiVis stands out as a versatile, high-performance, more reliable and easy-to-use alternative to current solutions that is also free of heavy dependencies. Through evaluation on a challenging dataset, TřiVis has been benchmarked against existing visibility libraries. The results demonstrate that TřiVis outperforms the competing solutions by at least an order of magnitude in query times, while exhibiting more reliable runtime behavior. TřiVis is freely available for private, research, and institutional use at https://github.com/janmikulacz/trivis.

The Multi-agent Multi-item Pickup and Delivery problem (MAMPD) stands for a problem of finding collision-free trajectories for a fleet of mobile agents transporting a set of items from their initial positions to specified locations. Each agent can carry multiple items up to a given capacity. We study the solution quality of the naive decoupled approach, which decouples the problem into task assignment (TA) and Multi-Agent Pathfinding (MAPF). By computing the gap between the lower bound of the MAMPD cost, estimated using the TA cost, and the upper bound, given by the final MAMPD cost, we show that the decoupled approach is able to obtain near-optimal solutions in a wide range of cases.

Path planning in the presence of dynamic obstacles is challenging as the time dimension has to be considered. A prominent approach to tackle this problem known to be complete and optimal is the A*-based Safe-interval Path Planning (SIPP). Bounded-suboptimal variants of SIPP employing the ideas of Weighted A* (WSIPP) and Focal Search (FocalSIPP) have been introduced recently, trading-off optimality for decreased planning time. In this paper, we revisit FocalSIPP and design several secondary heuristics for Focal Search with the intention to narrow the search in the direction of a preplanned optimal single-agent path not considering dynamic obstacles. The experimental results on various maps show that the designed heuristics generally outperform the hops-to-the-goal heuristic used in the original FocalSIPP and successfully compete with WSIPP as well.

In this paper, we address the multi-agent pickup and delivery problem, a variant of multi-agent path finding.\nSpecifically, we decouple the problem into two parts: task allocation and path planning. We employ the\nany-angle safe-interval path planning algorithm introduced in our recent work and study the performance\nof several task allocation strategies. Furthermore, the proposed approach has been integrated into a control\nsystem to verify its feasibility in deployment on real robots. A key part of the system is a visual localization\nsystem which is based on the detection of unique artificial markers placed in the working environment. The\nconducted experiments show that generated plans can be safely executed on a real system.\n

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.

We present a novel approach to mobile robot search for non-stationary objects in partially known environments. We formulate the search as a path planning problem in an environment where the probability of object occurrences at particular locations is a function of time. We propose to explicitly model the dynamics of the object occurrences by their frequency spectra. Using this spectral model, our path planning algorithm can construct plans that reflect the likelihoods of object locations at the time the search is performed. Three datasets collected over several months containing person and object occurrences in residential and office environments were chosen to evaluate the approach. Several types of spatio-temporal models were created for each of these datasets and the efficiency of the search method was assessed by measuring the time it took to locate a particular object. The results indicate that modeling the dynamics of object occurrences reduces the search time by 25% to 65% compared to maps that neglect these dynamics.

In this article we introduce the problem of finding an optimal path in order to find a stationary object placed in the environment whose map is not a-priory known. At first sight the problem seems to be similar to exploration which has been thoroughly studied by the robotic community. We show that a general framework for search can be derived from frontier-based exploration, but exploration strategies for selection of a next goal to which navigate a robot cannot be simply reused. We present three goal selection strategies (greedy, traveling salesmen based, and traveling deliveryman based) and statistically evaluate and discuss their performance for search in comparison to exploration.

In this paper, we discuss the problem of goal assignment in the multi-robot exploration task. The presented work is focused on the underlying optimal assignment problem of the multi-robot task allocation that is addressed by three state-of-the art approaches. In addition, we propose a novel exploration strategy considering allocation of all current goals (not only immediate goal) for each robot, which leads to the multiple traveling salesman problem formulation. Although the problem is strongly NP-hard, we show its approximate solution is computationally feasible and its overall requirements are competitive to the previous approaches. The proposed approach and three well-known approaches are compared in series of problems considering various numbers of robots and sensor ranges. Based on the evaluation of the results the proposed exploration strategy provides shorter exploration times than the former approaches.

Performance of exploration strategies strongly depends on the process of determination of a next robot goal. Current approaches define different utility functions how to evaluate and select possible next goal candidates. One of the mostly used evaluation criteria is the distance cost that prefers candidates close to the current robot position. If this is the only criterion, simply the nearest candidate is chosen as the next goal. Although this criterion is simple to implement and gives feasible results there are situations where the criterion leads to wrong decisions. This paper presents the distance cost that reflects traveling through all goal candidates. The cost is determined as a solution of the Traveling Salesman Problem using the Chained Lin-Kernighan heuristic. The cost can be used as a stand-alone criterion as well as it can be integrated into complex decision systems. Experimental results for open-space and office-like experiments show that the proposed approach outperforms the standard one in the length of the traversed trajectory during the exploration while the computational burden is not significantly increased.

Accurate models of the environment are a crucial requirement for autonomous mobile robots. The process of how to acquire knowledge about the operating environment is one of the most challenging problems in this research area. The quality of the model depends on the number and types of sensors used. Occupancy grids are the most common low-level models of the environment used in robotics for fusion of noisy data. This paper first introduces a novel method for building an occupancy grid from a monocular color camera. The next part of the work describes a method for fusion of camera data with data from a rangefinder. The final part presents a new method for measuring the quality of the occupancy grid based on the quality of the path created by the grid. The methods were experimentally verified with an indoor experimental robot at the Czech Technical University.