Exploration is a critical challenge in robotics, centered on understanding unknown environments. In this work, we focus on structured indoor environments, which often exhibit predictable, repeating patterns. Conventional frontier-based exploration approaches have difficulty leveraging this predictability, relying on simple heuristics such as ‘closest first’ for exploration. More recent deep learning-based methods predict unknown regions of the map for information gain computation, but these approaches are often sensitive to the predicted map quality or fail to account for sensor coverage. To overcome these issues, our key insight is to jointly reason over what the robot can observe and its uncertainty to calculate probabilistic information gain. We introduce MapEx, a new exploration framework that uses predicted maps to form probabilistic sensor model for information gain estimation. MapEx generates multiple predicted maps based on observed information, and takes into consideration both the computed variances of predicted maps and estimated visible area to estimate the information gain of a given viewpoint. Experiments on the real-world KTH dataset showed on average 12.4% improvement than representative map-prediction based exploration and 25.4% improvement than nearest frontier approach. Website: https://mapex-explorer.github.io/

We propose a decentralised multi-robot coordination algorithm that features a rich representation for encoding and communicating each robot’s intent. This representation for “intent messages” enables improved coordination behaviour and communication efficiency in difficult scenarios, such as those where there are unknown points of contention that require negotiation between robots. Each intent message is an adaptive policy that conditions on identified points of contention that conflict with the intentions of other robots. These policies are concisely expressed as behaviour trees via algebraic logic simplification, and are interpretable by robot teammates and human operators. We propose this intent representation in the context of the Dec-MCTS online planning algorithm for decentralised coordination. We present results for a generalised multi-robot orienteering domain that show improved plan convergence and coordination performance over standard Dec-MCTS enabled by the intent representation’s ability to encode and facilitate negotiation over points of contention.

We consider the problem of multi-robot, multi-goal path planning in cluttered environments, motivated by scenarios including surveillance, object search, and package delivery in crowded office spaces and urban environments. While many solutions have been proposed for related vehicle routing problems, they typically do not generalise well for cluttered environments with obstacles due to the introduction of non-Euclidean point-to-point distances. We consider a Self-Organising Map (SOM) algorithm due to its versatility in optimising waypoints within region-based goals. Since standard SOM heavily relies on Euclidean distance-based operations, we propose a generalised SOM with several new innovations: Probabilistic Roadmap (PRM)-guided adaptation and winner selection rules, a two-level path representation for effective routing between goals, and caching operations to overcome the increased computational demands. We present simulation experiments in office and maze environments with one to three robots that show that our approach significantly outperforms standard SOM algorithms as it explicitly reasons over collision avoidance. These results demonstrate the viability of our PRM-guided SOM algorithm for tasks including surveillance in cluttered environments.

Real-time sequential decision making under uncertainty is a challenging task for autonomous robots. Such problems are even more challenging when making decisions involving heterogeneous teams of robots completing multiple tasks. Deploying autonomous taxi cabs and utilizing drones for package delivery represent relevant examples of these types of problems. In this paper, we present an effective solution to a multi-robot multi-task sequential stochastic assignment problem using a simulation-based optimization algorithm (MARP). Our algorithm employs a novel approach that uses Monte Carlo simulation to seek the deployment with the highest probability of being optimal. To demonstrate MARP's performance and robustness, we performed more than 2,000 numerical experiments in two different problem domains, evaluating MARP's performance against three different comparison algorithms. These numerical studies show that MARP significantly outperforms the comparison methods, achieving results within 5% of the maximum possible reward.

We present a new algorithm for deploying passenger robots in marsupial robot systems. A marsupial robot system consists of a carrier robot (e.g., a ground vehicle), which is highly capable and has a long mission duration, and at least one passenger robot (e.g., a short-duration aerial vehicle) transported by the carrier. We optimize the performance of passenger robot deployment by proposing an algorithm that reasons over uncertainty by exploiting information about the prior probability distribution of features of interest in the environment. Our algorithm is formulated as a solution to a sequential stochastic assignment problem (SSAP). The key feature of the algorithm is a recurrence relationship that defines a set of observation thresholds that are used to decide when to deploy passenger robots. Our algorithm computes the optimal policy in O(NR) time, where N is the number of deployment decision points and R is the number of passenger robots to be deployed. We conducted drone deployment exploration experiments on real-world data from the DARPA Subterranean challenge to test the SSAP algorithm. Our results show that our deployment algorithm outperforms other competing algorithms, such as the classic secretary approach and baseline partitioning methods, and is comparable to an offline oracle algorithm.

We present an algorithm for learning behavior trees for robotic task planning, which alleviates the need for time-intensive or infeasible manual design of control architectures. Our method involves representing the search space of behavior trees as a formal grammar and searching over this grammar by means of a new generalization of Monte Carlo tree search (MCTS) for directed acyclic graphs (DAGs), named MCDAGS. Additionally, our method employs simulated annealing to expedite the aggregation of the most functional subtrees. We present simulated experiments for a marine target search and response scenario, and an abstract task selection problem. Our results demonstrate that the learned behavior trees compare favorably with a manually-designed tree, and outperform baseline learning methods. Overall, these results show that our method is a viable technique for the automatic design of behavior trees for robotic task planning.

This paper presents a new coordination algorithm for decentralised multi-robot information gathering. We consider planning for an online variant of the multi-agent orienteering problem with neighbourhoods. This formulation closely aligns with a number of important tasks in robotics, including inspection, surveillance, and reconnaissance. We propose a decentralised variant of the self-organising map (SOM) learning procedure, named Dec-SOM, which efficiently plans sequences of waypoints for a team of robots. Decentralisation is achieved by performing a distributed allocation scheme jointly with a series of SOM adaptations. We also offer an efficient heuristic to select when to perform negotiations, which reduces communication resource usage. Simulation results in two settings, including an infrastructure inspection scenario with a real-world dataset of oil rigs, demonstrate that Dec-SOM outperforms baseline methods and other SOM variants, is competitive with centralised SOM, and is a viable solution for decentralised information gathering.

Robotic exploration requires adaptively selecting navigation goals that result in the rapid discovery and mapping of an unknown world. In many real-world environments, subtle structural cues can provide insight about the unexplored world, which may be exploited by a decision maker to improve the speed of exploration. In sparse subterranean tunnel networks, these cues come in the form of topological features, such as loops or dead-ends, that are often common across similar environments. We propose a method for learning these topological features using techniques borrowed from topological image segmentation and image inpainting to learn from a database of worlds. These world predictions then inform a frontier-based exploration policy. Our simulated experiments with a set of real-world mine environments and a database of procedurally-generated artificial tunnel networks demonstrate a substantial increase in the rate of area explored compared to techniques that do not attempt to predict and exploit topological features of the unexplored world.

We consider the problem of reconstructing regions of interest of a scene using multiple robot arms and RGB-D sensors. This problem is motivated by a variety of applications, such as precision agriculture and infrastructure inspection. A viewpoint evaluation function is presented that exploits predicted observations and the geometry of the scene. A recently proposed non-myopic planning algorithm, Decentralised Monte Carlo tree search, is used to coordinate the actions of the robot arms. Motion planning is performed over a navigation graph that considers the high-dimensional configuration space of the robot arms. Extensive simulated experiments are carried out using real sensor data and then validated on hardware with two robot arms. Our proposed targeted information gain planner is compared to state-of-the-art baselines and outperforms them in every measured metric. The robots quickly observe and accurately detect fruit in a trellis structure, demonstrating the viability of the approach for real-world applications.

We present an algorithm for selecting when to communicate during online planning phases of coordinated multi-robot missions. The key idea is that a robot decides to request communication from another robot by reasoning over the predicted information value of communication messages over a sliding time-horizon, where communication messages are probability distributions over action sequences. We formulate this problem in the context of the recently proposed decentralised Monte Carlo tree search (Dec-MCTS) algorithm for online, decentralised multi-robot coordination. We propose a particle filter for predicting the information value, and a polynomial-time belief-space planning algorithm for finding the optimal communication schedules in an online and decentralised manner. We evaluate the benefit of informative communication planning for a multi-robot information gathering scenario with 8 simulated robots. Our results show reductions in channel utilisation of up to four-fifths with surprisingly little impact on coordination performance.

We consider a multi-robot variant of the mission monitoring problem. This problem arises in tasks where a robot observes the progress of another robot that is stochastically following a known trajectory, among other applications. We formulate and solve a variant where multiple tracker robots must monitor a single target robot, which is important because it enables the use of multi-robot systems to improve task performance in practice, such as in marine robotics missions. Our algorithm coordinates the behaviour of the trackers by computing optimal single-robot paths given a probabilistic representation of the other robots' paths. We employ a decentralised scheme that optimises over probability distributions of plans and has useful analytical properties. The planned trajectories collectively maximise the probability of observing the target throughout the mission with respect to probabilistic motion and observation models. We report simulation results for up to 8 robots that support our analysis and indicate that our algorithm is a feasible solution for improving the performance of mission monitoring systems.

We consider an optimal stopping formulation of the mission monitoring problem, in which a monitor vehicle must remain in close proximity to an autonomous robot that stochastically follows a predicted trajectory. This problem arises in a diverse range of scenarios, such as autonomous underwater vehicles supervised by surface vessels, pedestrians monitored by aerial vehicles, and animals monitored by agricultural robots. The key problem characteristics we consider are that the monitor must remain stationary while observing the robot, robot motion is modeled in general as a stochastic process, and observations are modeled as a spatial probability distribution. We propose a resolution-complete algorithm that runs in a polynomial time. The algorithm is based on a sweep-plane approach and generates a motion plan that maximizes the expected observation time and value. A variety of stochastic models may be used to represent the robot trajectory. We present results with data drawn from real AUV missions, a real pedestrian trajectory dataset and Monte Carlo simulations. Our results demonstrate the performance and behavior of our algorithm, and relevance to a variety of applications.

We propose a self-organising map (SOM) algorithm as a solution to a new multi-goal path planning problem for active perception and data collection tasks. We optimise paths for a multi-robot team that aims to maximally observe a set of nodes in the environment. The selected nodes are observed by visiting associated viewpoint regions defined by a sensor model. The key problem characteristics are that the viewpoint regions are overlapping polygonal continuous regions, each node has an observation reward, and the robots are constrained by travel budgets. The SOM algorithm jointly selects and allocates nodes to the robots and finds favourable sequences of sensing locations. The algorithm has polynomial-bounded runtime independent of the number of robots. We demonstrate feasibility for the active perception task of observing a set of 3D objects. The viewpoint regions consider sensing ranges and self-occlusions, and the rewards are measured as discriminability in the ensemble of shape functions feature space. Simulations were performed using a 3D point cloud dataset from a real robot in a large outdoor environment. Our results show the proposed methods enable multi-robot planning for budgeted active perception tasks with continuous sets of candidate viewpoints and long planning horizons.

In this paper, we address the Orienteering problem (OP) by the unsupervised learning of the self-organizing map (SOM). We propose to solve the OP with a new algorithm based on SOM for the Traveling salesman problem (TSP). Both problems are similar in finding a tour visiting the given locations; however, the OP stands to determine the most valuable tour that maximizes the rewards collected by visiting a subset of the locations while keeping the tour length under the specified travel budget. The proposed stochastic search algorithm is based on unsupervised learning of SOM and it constructs a feasible solution during each learning epoch. The reported results support feasibility of the proposed idea and show the performance is competitive with existing heuristics. Moreover, the key advantage of the proposed SOM-based approach is the ability to address the generalized OP with Neighborhoods, where rewards can be collected by traveling anywhere within the neighborhood of the locations. This problem generalization better fits data collection missions with wireless data transmission and it allows to save unnecessary travel costs to visit the given locations.

Contextual cues can provide a rich source of information for robots that operate in the presence of other agents such as people, animals, vehicles and fellow robots. We are interested in context, in the form of the behavioural intent of an agent, for enhanced trajectory prediction. We present a Bayesian framework that estimates both the intended goal destination and future trajectory of a mobile agent moving among multiple static obstacles. Our method is based on multi-modal hypotheses of the intended goal, and is focused primarily on the long-term trajectory of the agent. We propose a computationally efficient solution and demonstrate its behaviour in a pedestrian scenario with a real-world data set. Results show the benefits of our method in comparison to traditional trajectory prediction methods and illustrate the feasibility of integration with higher-level planning algorithms.