We present an algorithm to explore an orthogonal polygon using a team of $p$ robots. This algorithm combines ideas from information-theoretic exploration algorithms and computational geometry based exploration algorithms. We show that the exploration time of our algorithm is competitive (as a function of $p$) with respect to the offline optimal exploration algorithm. The algorithm is based on a single-robot polygon exploration algorithm, a tree exploration algorithm for higher level planning and a submodular orienteering algorithm for lower level planning. We discuss how this strategy can be adapted to real-world settings to deal with noisy sensors. In addition to theoretical analysis, we investigate the performance of our algorithm through simulations for multiple robots and experiments with a single robot.
This paper addresses the problem of exploration and mapping of an unknown environment by multiple robots. The mapping algorithm is an online approach to likelihood maximization that uses hill climbing to find maps that are maximally consistent with sensor data and odometry. The exploration algorithm explicitly coordinates the robots. It tries to maximize overall utility by minimizing the potential for overlap in information gain amongst the various robots. For both the exploration and mapping algorithms, most of the computations are distributed. The techniques have been tested extensively in real-world trials and simulations. The results demonstrate the performance improvements and robustness that accrue from our multirobot approach to exploration.
Roguelike games generally feature exploration problems as a critical, yet often repetitive element of gameplay. Automated approaches, however, face challenges in terms of optimality, as well as due to incomplete information, such as from the presence of secret doors. This paper presents an algorithmic approach to exploration of roguelike dungeon environments. Our design aims to minimize exploration time, balancing coverage and discovery of secret areas with resource cost. Our algorithm is based on the concept of occupancy maps popular in robotics, adapted to encourage efficient discovery of secret access points. Through extensive experimentation on NetHack maps we show that this technique is significantly more efficient than simpler greedy approaches and an existing automated player. We further investigate optimized parameterization for the algorithm through a comprehensive data analysis. These results point towards better automation for players as well as heuristics applicable to fully automated gameplay.
This paper addresses the complete area coverage problem of a known environment by multiple-robots. Complete area coverage is the problem of moving an end-effector over all available space while avoiding existing obstacles. In such tasks, using multiple robots can increase the efficiency of the area coverage in terms of minimizing the operational time and increase the robustness in the face of robot attrition. Unfortunately, the problem of finding an optimal solution for such an area coverage problem with multiple robots is known to be NP-complete. In this paper we present two approximation heuristics for solving the multi-robot coverage problem. The first solution presented is a direct extension of an efficient single robot area coverage algorithm, based on an exact cellular decomposition. The second algorithm is a greedy approach that divides the area into equal regions and applies an efficient single-robot coverage algorithm to each region. We present experimental results for two algorithms. Results indicate that our approaches provide good coverage distribution between robots and minimize the workload per robot, meanwhile ensuring complete coverage of the area.
While grid-based methods produce accurate metric maps, their complexity often prohibits efficient planning and problem solving in large-scale indoor environments. Topological maps, on the other hand, can be used much more efficiently, yet accurate and consistent topological maps are considerably difficult to learn in large-scale environments. This paper describes an approach that integrates both paradigms: grid-based and topological. Grid-based maps are learned using artificial neural networks and Bayesian integration. Topological maps are generated on top of the grid-based maps, by partitioning the latter into coherent regions. By combining both paradigms-grid-based and topological-, the approach presented here gains the best of both worlds: accuracy/consistency and efficiency. The paper gives results for autonomously operating a mobile robot equipped with sonar sensors in populated multi-room environments.