Coordinating multiple robots is crucial for various real-life applications. Many Multi-Agent Path Finding (MAPF) algorithms have been proven to be successful in addressing this challenge. Nevertheless, some problems, such as unexpected delays during navigation, commonly arise when handling highlevel abstractions, potentially leading to failures or collisions in live executions. This paper proposes k-Robust Continuoustime Conflict-Based Search (kR-CCBS), a novel algorithm that overcomes some of these limitations. Our approach offers path planning with continuous time, leading to more precise routes than discrete time approaches. Additionally, we increase safety by incorporating k-robustness, enabling the system to adapt to agent failures due to delays and minimize collision risks. Comparative evaluations demonstrate that kR-CCBS outperforms similar works in effectiveness while maintaining reasonable costs, making it a promising solution for real-world multi-agent coordination scenarios.

An incompletely specified Boolean function, also known as a Boolean relation, can be described by any combination of its on-set, off-set, and don't care (DC) set pairs. To transform a Boolean relation into a Boolean function (fully specified), we have to assign the DCs from the original specification. Depending on the DCs assignment, a better function minimization may result from the original specification. This article presents a method for joining two BDDs by describing the on-set and off-set of an incompletely specified$f$function into a single BDD for a fully specified coverage of the function. The proposed method is compared with the Restrict, Constrain and LICompaction methods implemented by the CUDD package, which are references for this problem using BDDs. In addition to these methods, we also compare our results with the Join method, which is a more recent proposal for the problem of assigning and minimizing incompletely specified Boolean functions. The LI-Compaction method presented the largest number of BDD nodes among the analyzed methods. Compared to the LICompaction method, the Restrict method produced 2.12% fewer nodes, the Constrain and Join methods produced 1.95% fewer nodes, while our method produced 24.80% fewer nodes.

For a mobile robot to operate in its environment it is crucial to determine its position with respect to an external reference frame using noisy sensor readings. A scenario in which the robot is moved to another position during its operation without being told, known as the kidnapped robot problem, complicates global localisation. In addition to that, sensor malfunction and external influences of the environment can cause unexpected errors, called outliers, that negatively affect the localisation process. This paper proposes a method based on the fusion of a particle filter with bounded-error localisation, which is able to deal with outliers in the measurement data. The application of our algorithm to solve the kidnapped robot problem using simulated data shows an improvement over conventional probabilistic filtering methods.

Mobile robots can be used in numerous outdoor tasks such as patrolling, delivery and military applications. In order to deploy mobile robots in this kind of environment, where there are different challenges like slopes, elevations, or even holes, they should be able to detect such challenges and determine the best path to accomplish their tasks. In this paper, we are proposing an exploration approach based on potential fields with local distortions, in which we define preferences in uneven terrains to avoid high declivity regions without compromising the best path. The approach was implemented and tested in simulated environments, considering a ground robot embedded with two 2D LIDAR sensors, and the experiments demonstrated the efficiency of our method.

Many applications with mobile robots require self-localization in indoor maps. While such maps can be previously generated by SLAM strategies, there are various localization approaches that use 2D floor plans as reference input. In this paper, we present a localization strategy using floor plan as map, which is based on spatial density information computed from dense depth data of RGB-D cameras. We propose an interval-based model, called Interval Free-Space Density, that bounds the uncertainty of observations and minimizes the effects of movable objects in the environment. Our model was applied in a Monte Carlo Localization strategy and compared with traditional observation models. The results of experiments showed the robustness of the proposed method in single-camera and multi-camera experiments in home environments.

Proper place recognition on an environment that can change over time is fundamental for long-term SLAM. In such scenarios the observations obtained in the same region can drastically differ due to changes caused by semi-static objects, such as doors, furniture, etc. In this work, we extend a strategy that represents environment regions using words, based on spatial density information extracted from laser readings. This time, in order to deal with changes in the environment, our method not only builds words representing the real observations made by the robot, but also alternative multi-level words to account for possible changes in a place's observations generated by non-static objects. Place recognition is made by searching matches of sequences of N consecutive words (both real or alternatives). Experiments performed in real and simulated scenarios are shown, and demonstrate the advantages associated to the use of multi-level words.

An autonomous robot requires a map of the environment for many tasks. Yet, in many cases, this map is unavailable and the robot must build one in real-time, in the so-called integrated exploration task. Several integrated exploration approaches adopt some sort of loop-closing strategy combined with an online simultaneous localization and mapping (SLAM) technique. This is important because the robot can reduce the uncertainty about its pose by revisiting known areas. One solution for environment exploration is to use the vector field computed from the numeric solution of a Boundary Value Problem (BVP). This approach is called BVP Path Planner and generates smooth and free of local minima potential fields. However, this planner cannot actively close loops and does not scale well in large scenarios. In this paper we present a technique which performs active loop closure using the BVP Path Planner. Our proposal takes advantage of the potential of unexplored regions, and induces the robot to close loops by placing dynamic barriers at the visited space. The update of the potential field is boosted using a local window charged by a Voronoi diagram of the environment containing global information. We show through experimental results the effectiveness of the technique with a thorough discussion of its characteristics.

Estimating the robot localization is a fundamental requirement for applications in robotics. For many years, Monte Carlo Localization (MCL) has been one of the most popular approaches to solve the global localization when using range finders, like sonars or lasers. It generally weights the estimates about the robot state by comparing raw sensor readings with simulated readings computed for each estimate. In this paper, we propose an observation model for localization that associates a kernel density estimate (KDE) to each point in the space. This single-valued density measure is independent of orientation, what allows an efficient pre-caching step, substantially boosting the computation time of the process. Using the gradient of the densities field, our strategy is able to estimate orientation information that helps to restrict the localization search space. Additionally, we can combine densities obtained by kernels of different sizes and profiles to improve the quality of the acquired information. We show through experiments in comparison with traditional approaches that our method is efficient, even working with large sets of particles, and effective.

Place recognition is the frond-end of Simultaneous Localization and Mapping (SLAM). Topological representations depend on good association of vertices, which ultimately depends on the front-end. In this paper, we consider a robot lost in an unknown environment trying to construct a topological map to localize itself using a laser range finder and odometry information. The algorithm makes use of an efficient observation model based on kernel density estimates (KDEs) to detect loops. The observation model separates the map into regions denominated words, classified based on the density of free space, number of observations and segment orientation. Loop closing results from the matching of sequences of N consecutive words (n-grams). The proposed approach is orders of magnitude faster than a sequence of Iterative Closest Point (ICP) matches. The method is evaluated varying input parameters in real and simulated scenarios.

Digital printers have consistently improved their speed in the past years. Meanwhile, the need for document personalization and customization has increased. As a consequence of these two facts, the traditional rasterization process has become a highly demanding computational step in the printing workflow. Moreover, Print Service Providers are now using multiple RIP engines to speed up the whole document rasterization process, and depending on the input document characteristics the rasterization process may not achieve the print-engine speed creating a unwanted bottleneck. In this scenario, we developed a tool called Job Adaptive Router (JAR) aiming at improving the throughput of the rasterization process through a clever load balance among RIP engines which is based on information obtained by the analysis of input documents content. Furthermore, along with this tool we propose some strategies that consider relevant characteristics of documents, such as transparency and reusability of images, to split the job in a more intelligent way. The obtained results confirm that the use of the proposed tool improved the rasterization process performance.

Integrated exploration is the most complete task in mobile robotics, and corresponds to the union of mapping, localization and motion planning. A powerful integrated exploration solution must take into account decisions that improve the quality of the map construction, such as closing loops, at the same time that the environment is explored. Potential fields and boundary value problems (BVP) have been used with success in tasks of planning, localization and exploration, but not yet in integrated strategies. In this paper, we present an integrated exploration strategy using a time varying BVP-based exploration. Our strategy consists of creating potential rails that guide the robot to regions that are either unexplored or were visited a long time ago. We also apply local distortions in the potential field to generate a loop closure strategy. Experimental results demonstrate that our method improves the quality of the map construction, keeping the balance between revisiting and exploratory activities.

Probabilistic approaches are extensively used to solve high-dimensionality problems in many different fields. The particle filter is a prominent approach in the field of Robotics, due to its adaptability to non-linear models with multi-modal distributions. Nonetheless, its result is strongly dependent on the quality and the number of samples required to cover the space of possible solutions. In contrast, interval analysis deals with high-dimensionality problems by reducing the space enclosing the actual solution. Notwithstanding, it cannot precise where in the resulting subspace the actual solution is. We devised a strategy that combines the best of both worlds. Our approach is illustrated by solving the global localization problem for underwater robots.

Simultaneous Localization and Mapping (SLAM) is one of the most difficult tasks in mobile robotics. While the construction of consistent and coherent local solutions is simple, the SLAM remains a critical problem as the distance travelled by the robot increases. To circumvent this limitation, many strategies divide the environment in small regions, and formulate the SLAM problem as a combination of multiple precise submaps. In this paper, we propose a new submap-based particle filter algorithm called Segmented DP-SLAM, that combines an optimized data structure to store the maps of the particles with a probabilistic map of segments, representing hypothesis of submaps topologies. We evaluate our method through experimental results obtained in simulated and real environments.

Digital presses have consistently improved their speed in the past ten years. Meanwhile, the need for document personalization and customization has increased. As a consequence of these two facts, the traditional RIP (Raster Image Processing) process has became a highly demanding computational step in the print workflow. Print Service Providers (PSP) are now using multiple RIP engines and parallelization strategies to speed up the whole ripping process which is currently based on a per-page base. Nevertheless, these strategies are not optimized in terms of assuring the best Return On Investment (ROI) for the RIP engines. Depending on the input document jobs characteristics, the ripping step may not achieve the print-engine speed creating a unwanted bottleneck. The aim of this paper is to present a way to improve the ROI of PSPs proposing a profiling strategy which enables the optimal usage of RIPs for specific jobs features ensuring that jobs are always consumed at least at engine speed. The profiling strategy is based on a per-page analysis of input PDF jobs identifying their key components. This work introduces a profiler tool to extract information from jobs and some metrics to predict a job ripping cost based on its profile. This information is extremely useful during the job splitting step, since jobs can be split in a clever way. This improves the load balance of the allocated RIPs engines and makes the overall process faster. Finally, experimental results are presented in order to evaluate both, the profiler and the proposed metrics.

This paper presents a new parallel implementation for solving dense interval linear systems with verified computing. The use of intervals appears as one possible way to handle the uncertainty of input data in real problems. A verified method using midpoint-radius arithmetic and directed roundings was combined with optimized libraries such as SCALAPACK and PBLAS to provide a free, fast, reliable and accurate solver. Accuracy and performance results for executing this implementation in a cluster are shown. It is the authors opinion that the combination of verified and parallel computing is a powerful tool that could be used for several other mathematical problems.