This paper investigates the usefulness of reasoning about the uncertain presence of obstacles during path planning, which typically stems from the usage of probabilistic occupancy grid maps for representing the environment when mapping via a noisy sensor like a stereo camera. The traditional planning paradigm prescribes using a hard threshold on the occupancy probability to declare that a cell is an obstacle, and to plan a single path accordingly while treating unknown space as free. We compare this approach against a new uncertainty-aware planner, which plans two different path hypotheses and then merges their initial trajectory segments into a single one ending in a “next-best view” pose. After this informative view is taken, the planner commits to one of the hypotheses, or to a completely new one if a collision is imminent. Simulations were conducted comparing the proposed and traditional planner. Results show the existence of planning scenarios -like when the environment contains a dead-end, or when the goal is placed close to an obstacle- in which reasoning about uncertainty can significantly decrease the robot's traveled distance and increase the chances of reaching the goal. The new planner was also validated on a real Clearpath Jackal robot equipped with a ZED 2 stereo camera.

There has been a plethora of work towards im-proving robot perception and navigation, yet their application in hazardous environments, like during a fire or an earthquake, is still at a nascent stage. We hypothesize two key challenges here: first, it is difficult to replicate such scenarios in the real world, which is necessary for training and testing purposes. Second, current systems are not fully able to take advantage of the rich multi-modal data available in such hazardous environments. To address the first challenge, we propose to harness the enormous amount of visual content available in the form of movies and TV shows, and develop a dataset that can represent hazardous environments encountered in the real world. The data is annotated with high-level danger ratings for realistic disaster images, and corresponding keywords are provided that summarize the content of the scene. In response to the second challenge, we propose a multi-modal danger estimation pipeline for collaborative human-robot escape scenarios. Our Bayesian framework improves danger estimation by fusing information from robot's camera sensor and language inputs from the human. Furthermore, we augment the estimation module with a risk-aware planner that helps in identifying safer paths out of the dangerous environment. Through extensive simulations, we exhibit the advantages of our multi-modal perception framework that gets translated into tangible benefits such as higher success rate in a collaborative human-robot mission.

We present a method for detecting and mapping trees in noisy stereo camera point clouds, using a learned 3D object detector. Inspired by recent advancements in 3-D object detection using a pseudo-lidar representation for stereo data, we train a PointRCNN detector to recognize trees in forest-like environments. We generate detector training data with a novel automatic labeling process that clusters a fused global point cloud. This process annotates large stereo point cloud training data sets with minimal user supervision, and unlike previous pseudo-lidar detection pipelines, requires no 3D ground truth from other sensors such as lidar. Our mapping system additionally uses a Kalman filter to associate detections and consistently estimate the positions and sizes of trees. We collect a data set for tree detection consisting of 8680 stereo point clouds, and validate our method on an outdoors test sequence. Our results demonstrate robust tree recognition in noisy stereo data at ranges of up to 7 meters, on 720p resolution images from a Stereolabs ZED 2 camera. Code and data are available at https://github.com/brian-h-wang/pseudolidar-tree-detection.

Planning in unstructured environments is challenging - it relies on sensing, perception, scene reconstruction, and reasoning about various uncertainties. We propose DeepSemanticHPPC, a novel uncertainty-aware hypothesis-based planner for unstructured environments. Our algorithmic pipeline consists of: a deep Bayesian neural network which segments surfaces with uncertainty estimates; a flexible point cloud scene representation; a next-best-view planner which minimizes the uncertainty of scene semantics using sparse visual measurements; and a hypothesis-based path planner that proposes multiple kinematically feasible paths with evolving safety confidences given next-best-view measurements. Our pipeline iteratively decreases semantic uncertainty along planned paths, filtering out unsafe paths with high confidence. We show that our framework plans safe paths in real-world environments where existing path planners typically fail.

This paper introduces and studies a graph-based variant of the path planning problem arising in hostile environments. We consider a setting where an agent (e.g. a robot) must reach a given destination while avoiding being intercepted by probabilistic entities which exist in the graph with a given probability and move according to a probabilistic motion pattern known a priori. Given a goal vertex and a deadline to reach it, the agent must compute the path to the goal that maximizes its chances of survival. We study the computational complexity of the problem, and present two algorithms for computing high quality solutions in the general case: an exact algorithm based on Mixed-Integer Nonlinear Programming, working well in instances of moderate size, and a pseudo-polynomial time heuristic algorithm allowing to solve large scale problems in reasonable time. We also consider the two limit cases where the agent can survive with probability 0 or 1, and provide specialized algorithms to detect these kinds of situations more efficiently.

In the Multiagent Connected Path Planning problem (MCPP), a team of agents moving in a graph-represented environment must plan a set of start-goal joint paths which ensures global connectivity at each time step, under some communication model. The decision version of this problem asking for the existence of a plan that can be executed in at most a given number of steps is claimed to be NP-complete in the literature. The NP membership proof, however, is not detailed. In this paper, we show that, in fact, even deciding whether a feasible plan exists is a PSPACE-complete problem. Furthermore, we present three algorithms adopting different search paradigms, and we empirically show that they may efficiently obtain a feasible plan, if any exists, in different settings.

In this paper, we consider the problem of maintaining and restoring connectivity among a set of agents (humans or robots) by incrementally redeploying a team of mobile robots acting as communication relays. This problem is relevant in numerous scenarios where humans and robots are jointly deployed for tasks like urban search and rescue, surveillance, and the like. In this case, as the humans move in the environment, connectivity may be broken, and consequently, robots need to reposition themselves to restore it. We study the computational complexity of the problem, also in terms of approximation hardness, and present an Integer Linear Programming formulation to compute optimal solutions. We then analyze the performance of the proposed resolution approach against a heuristic algorithm taken from the literature, and we demonstrate how our method favorably compares in terms of solution quality and scalability.

In several multirobot applications in which communication is limited, the mission could require the robots to iteratively take coordinated joint decisions on how to spread out in the environment and on how to reconnect with each other to share data and compute plans. Exploration and surveillance are examples of these applications. In this paper, we consider the problem of computing robots' paths on a graph-represented environment for restoring connections at minimum traveling cost. We call it the multirobot reconnection problem, we show its NP-hardness and hardness of approximation on some important classes of graphs, and we provide optimal and heuristic algorithms to solve it in practical settings. The techniques we propose are then exploited to derive a new efficient planning algorithm for a relevant connectivity-constrained multirobot planning problem addressed in the literature, the multirobot informative path planning with periodic connectivity problem.

The importance of communication in many multirobot information-gathering tasks requires the availability of reliable communication maps. These provide estimates of the radio signal strength and can be used to predict the presence of communication links between different locations of the environment. In the problem we consider, a team of mobile robots has to build such maps autonomously in a robot-to-robot communication setting. The solution we propose models the signal's distribution with a Gaussian Process and exploits different online sensing strategies to coordinate and guide the robots during their data acquisition. Our methods show interesting operative insights both in simulations and on real TurtleBot 2 platforms.

In multirobot exploration under centralized control, communication plays an important role in constraining the team exploration strategy. Recurrent connectivity is a way to define communication constraints for which robots must connect to a base station only when making new observations. This paper studies effective multirobot exploration strategies under recurrent connectivity by considering a centralized and asynchronous planning framework. We formalize the problem of selecting the optimal set of locations robots should reach, provide an exact formulation to solve it, and devise an approximation algorithm to obtain efficient solutions with a bounded loss of optimality. Experiments in simulation and on real robots evaluate our approach in a number of settings.

Cooperative Multi-Robot Observation of Multiple Moving Targets (CMOMMT) denotes a class of problems in which a set of autonomous mobile robots equipped with limited-range sensors are used to keep under observation a (possibly larger) set of mobile targets. Robots cooperatively plan their motion in order to maximize the time during which each target lies within the sensing range of at least one robot.

We consider the problem of computing patrolling strategies under communication constraints for a team of autonomous robots employed in repeated surveillance missions on a set of predefined locations. We assume the presence of a communication infrastructure providing only some regions of the environment with a communication link to a mission control center (MCC). We define the problem of computing a joint patrolling strategy that minimizes communication latencies, defined as the delays between inspecting some locations and reporting the outcome to the MCC. We provide and experimentally evaluate a MILP formulation and a heuristic method.