In this paper we propose a new algorithm for robots searching a hazardous, communications-denied area to gather information using a robot fleet that has a limited number of agents. The centralized algorithm uses robot survival along search paths as a sensor event for a distributed sensor network. As agents are lost to hazards, the search behavior adjusts to prioritize agent longevity in order to maximize information gain. In the past, related work solving this problem has assumed an infinite number of agents. In contrast, we assume that the number of agents is finite. We use Bayesian inference to update target and hazard belief maps of an area using data from the probability of survival of prior agents’ paths as well as sensor readings from the agents along those paths. Using those belief maps, the algorithm can construct paths that maximize information gain, in expectation, while taking into account the predicted decrease in future information collected when losing an agent. This behavior increases the likelihood that agents survive longer, allowing them to collect more data.Using simulations with various fleet sizes and probabilities for hazards disabling agents, we compare our algorithm to work that does not account for attrition. The results show an increase in the longevity of the fleet when hazards are more effective at disabling agents. In nearly all cases, this contributes to an increased rate in information gain when the fleet size is small. Small sized fleets, in our case 10 or less agents, do not meet a threshold of collected information necessary to direct agents away from hazards. Large fleets, over 200 agents in our scenario, collect most of the information before Our algorithm causes a noticeable change in agent behavior (as compared to existing techniques). We find that the proposed method provides the greatest advantage for mid-sized fleets, between 20 and 100 agents, and when hazards have an increased probability of immobilizing agents.

The dynamics of all real quadrotors inevitably differ even if they are the same product. In particular, the dynamics can change significantly during the flight due to additional device attachments or overheating motors. In this study, we focus on training a low-level controller, which operates in response to dynamics-changes without prior knowledge or fine-tuning of the parameters, using reinforcement learning. We randomize the dynamics of quadrotors in the simulator and train the policy based on dynamics information extracted from the state-action history through recurrent neural networks (RNNs). In addition, our experiment demonstrates the difficulties in applying existing actor-critic structures that extract dynamics information using end-to-end RNNs for unstable quadrotors; hence, we propose a novel structure with better performance. Finally, the excellent performance of the proposed controller is verified by testing experiments that stabilize quadrotors with different dynamics. The experiment videos and the code can be found at https://github.com/jackyoung96/RNN-Quadrotor-controller.

Active Learning of Gaussian process (GP) surrogates is an efficient way to model unknown environments in various applications. In this paper, we propose an adaptive exploration-exploitation active learning method (ALX) that can be executed rapidly to facilitate real-time decision making. For the exploration phase, we formulate an acquisition function that maximizes the approximated, expected Fisher information. For the exploitation phase, we employ a closed-form acquisition function that maximizes the total expected variance reduction of the search space. The determination of each phase is established with an exploration condition that measures the predictive accuracy of GP surrogates. Extensive numerical experiments in multiple input spaces validate the efficiency of our method.

Bidirectional path and motion planning approaches decrease planning time, on average, compared to their unidirectional counterparts. In single-query feasible motion planning, using bidirectional search to find acontinuousmotion plan requires an edge connection between the forward search tree and the reverse search tree. Such a tree–tree connection requires solving a two-point boundary value problem (BVP). However, obtaining a closed-form two-point BVP solution can be difficult or impossible for many systems. While numerical methods can provide a reasonable solution in many cases, they are often computationally expensive, numerically unstable, or sensitive (to an initial guess) for the purposes of single-query sampling-based motion planning. To overcome this challenge, we present a novel bidirectional search strategy that does not require solving the two-point BVP. Instead of connecting the forward and reverse trees directly, the reverse tree’s cost information is used as a guiding heuristic for forward search. This enables the forward search to quickly grow down the reverse tree—converging to a fully feasible solutionwithouta direct tree–tree connection andwithoutthe solution to a two-point BVP. In this article, we propose two algorithms that use this strategy for single-query feasible motion planning for various dynamical systems, performing experiments in both simulation and hardware testbeds. We find that these algorithms perform better than or comparable to the existing state-of-the-art methods with respect to quickly finding an initial feasible solution.

An important aspect of dynamic urban coverage is how building collision avoidance is incorporated into the overall coverage mission. We consider a multi-agent urban dynamic coverage problem in which a team of flying agents uses downward facing cameras to observe the street-level environment outside of buildings. Cameras are assumed to be ineffective above a maximum altitude (lower than building height), such that agents must move around or over buildings to complete their mission. The main objective of this paper is to compare three different building avoidance strategies that are compatible with dynamic ergodic methods. To provide context for these results, we also compare our results to three other common coverage methods including: boustrophedon coverage (lawn-mower sweep), Voronoi region based coverage, and a naive grid method. All algorithms are evaluated in simulation with respect to four performance metrics (percent coverage, revisit count, revisit time, and the integral of area viewed over time), across team sizes ranging from 1 to 25 agents, and in five types of urban environments of varying density and height. We find that the relative performance of algorithms changes based on the ratio of team size to search area, as well the height and density characteristics of the urban environment.

Consider a sensor that reports whether or not an event has occurredsomewherealong a path, but that has no conception ofwherealong the path that event has occurred. We name this type of sensor apath-based sensorand describe the recursive Bayesian update that can be used to calculate posterior beliefs about the presence of a sensor triggering phenomenon given a path-based sensor observation. We show how the Bayesian update can be leveraged to calculate the expected Shannon information that will be gained along a particular path. We formalize two iterative information-gathering problems that result from this scenario and present path-planning algorithms to solve them. These include: 1) gathering information about the path-based sensor triggering phenomena and 2) assuming the path-based sensor triggering event is “robot destruction,” simultaneously gather information about: 1) hazards using a path-based sensor and 2) information about another environmental phenomenon using a standard sensor, such as the locations of search and rescue targets with a camera. We evaluate our methods using Monte Carlo simulations and observe that they outperform other techniques with respect to the new problems that we consider.Note to Practitioners—This work is motivated by the problem of searching for robot-destroying hazards that are otherwise invisible to the robots. That is, we can observe whether or not a robot survives a path, but, if a robot is destroyed, then we have no idea where, along the path, its destruction has occurred. A mathematically equivalent problem happens in any scenario, in which an agent is equipped with an event sensor that can only be set/triggered once, but that requires postprocessing to figure out if the sensor has been triggered or not. For example, postprocessing is needed if the determination of whether or not a biological specimen was obtained requires a manual laboratory inspection. We also consider an extension of the hazard detection problem, in which we simultaneously collect information about search-and-rescue victims using a “victim sensor,” such as a camera. In this problem, hazards indirectly affect information gathered about victims because new information about victims is lost whenever a robot is destroyed. We provide algorithms to solve these types of problems. The algorithms work even in cases with noise such that false positives and false negatives are possible. This work is useful in any application where observations take the form of a cumulative “yes” or “no” along a path.

In multi-agent collaborative search missions, task allocation is required to determine which agents will perform which tasks. We propose a new approach for decentralized task allocation based on a decentralized genetic algorithm (GA). The approach parallelizes a genetic algorithm across the team of agents, making efficient use of their computational resources. In the proposed approach, the agents continuously search for and share better solutions during task execution. We conducted simulation experiments to compare the decentralized GA approach and several existing approaches. Two objectives were considered: a min-sum objective (minimizing the total distance traveled by all agents) and a min-time objective (minimizing the time to visit all locations of interest). The results showed that the decentralized GA approach yielded task allocations that were better on the min-time objective than those created by existing approaches and solutions that were reasonable on the min-sum objective. The decentralized GA improved min-time performance by an average of 5.6% on the larger instances. The results indicate that decentralized evolutionary approaches have a strong potential for solving the decentralized task allocation problem.

Motion planning for multi-target autonomous search requires efficiently gathering as much information over an area as possible with an imperfect sensor. In disaster scenarios and contested environments the spatial connectivity may unexpectedly change (due to aftershock, avalanche, flood, building collapse, adversary movements, etc.) and the flight envelope may evolve as a known function of time to ensure rescue worker safety or to facilitate other mission goals. Algorithms designed to handle both expected and unexpected changes must: (1) reason over a sufficiently long time horizon to respect expected changes, and (2) replan quickly in response to unexpected changes. These ambitions are hindered by the submodularity property of mutual information, which makes optimal solutions NP-hard to compute. We present an algorithm for autonomous search in changing environments that uses a variety of techniques to improve both the speed and time horizon, including using e-admissible heuristics to speed up the search.

We consider the problem of real-time path-planning in a spatiotemporally varying wind-field with moving obstacles. We are provided with changing wind and obstacle predictions along a (D + 1)-dimensional space-time lattice. We present an Any-Time algorithm that quickly finds an αβ-suboptimal solution (a path that is not longer than αβ times the optimal time-length), and then improves α and β while planning time remains or until new wind/obstacle predictions trigger a restart. The factor α comes from an α-overestimate of the A*-like cost heuristic. β is proportional to motion modeling error. Any-Time performance is achieved by: (1) improving the connectivity model of the environment from a discrete graph to a continuous cost-field (decreasing β); (2) using the established method of incrementally deflating α. Our method was deployed as the global planner on a fixed-wing unmanned aircraft system that uses Doppler radar and atmospheric models for online real-time wind sensing and prediction. We compare its performance vs. other state-of-the-art methods in simulated environments.

We present an any-com algorithm that enables a decentralized team of robots to share the work of collision checking while each robot independently calculates its own motion plan. In our method “safety-certificates” (i.e., bounds on the collision-free subspace around each collision-checked point [1]), are shared among the team so that all robots can benefit from their encoded knowledge. Future points drawn from within a certificate are guaranteed to be safe; therefore, sharing certificates among team members reduces collision checking for all robots. Experiments demonstrate that our algorithm scales well vs. both team size and vs. communication quality.

We consider a class of multi-robot motion planning problems where each robot is associated with multiple objectives and decoupled task specifications. The problems are formulated as an open-loop non-cooperative differential game. A distributed anytime algorithm is proposed to compute a Nash equilibrium of the game. The following properties are proven: (i) the algorithm asymptotically converges to the set of Nash equilibrium; (ii) for scalar cost functionals, the price of stability equals one; (iii) for the worst case, the computational complexity and communication cost are linear in the robot number.

In sampling-based motion planning algorithms the initial step at every iteration is to generate a new sample from the obstacle-free portion of the configuration space. This is usually accomplished via rejection sampling, i.e., repeatedly drawing points from the entire space until an obstacle-free point is found. This strategy is rarely questioned because the extra work associated with sampling (and then rejecting) useless points contributes at most a constant factor to the planning algorithm's asymptotic runtime complexity. However, this constant factor can be quite large in practice. We propose an alternative approach that enables sampling from a distribution that provably converges to a uniform distribution over only the obstacle-free space. Our method works by storing empirically observed estimates of obstacle-free space in a point-proximity data structure, and then using this information to generate future samples. Both theoretical and experimental results validate our approach.

We propose and study the navigation with foraging problem, where an agent with a limited sensor range must simultaneously: (1) navigate to a global goal and (2) forage en route as opportunities to forage are detected. Each foraging act causes a deviation from the shortest path to the long-term goal, with consequences for path length, mission duration, and fuel usage. We analytically calculate and/or bound the expected distance the robot actually travels, given the initial distance to the the global goal. In particular, for either of two non-trivial greedy strategies: (A) forage the point that minimizes goal-heading deviation. (B) forage the closest point ahead of the robot. Our results generalize to problems in higher dimensions.

C-FOREST is a parallelization framework for single-query sampling-based shortest path-planning algorithms. Multiple search trees are grown in parallel (e.g., 1 per CPU). Each time a better path is found, it is exchanged between trees so that all trees can benefit from its data. Specifically, the path's nodes increase the other trees' configuration space visibility, while the length of the path is used to prune irrelevant nodes and to avoid sampling from irrelevant portions of the configuration space. Experiments with a robotic team, a manipulator arm, and the alpha benchmark demonstrate that C-FOREST achieves significant superlinear speedup in practice for shortest path-planning problems (team and arm), but not for feasible path panning (alpha).

This paper introduces the Object Interaction Language (OIL) that allows programming and coordination of distributed, heterogeneous sensor-actuator networks, such as sensor networks and multi-robot systems. OIL is an interpreted, object oriented language and is contained in an OIL environment. An OIL environment provides communication between agents and allows agents to exchange code snippets among each other. Possible implementations of OIL environments can be - in the simplest case - a sheet of paper with OIL code literally printed on it, or a computational agent endowed with sensors, actuators and wireless communication. The atomic primitive in OIL is the intent for which implementation is resolved during runtime, potentially using code from other OIL environments and leading to distributed execution. We develop the structure of the language and demonstrate its key properties using a distributed computation task that is parallelized via an OIL environment. We evaluate the algorithm empirically by running OIL code on a team of six computational agents that communicate wirelessly. We then show experimentally how OIL can be used to allocate sensing and mobility in a multi-robot system using a case study in navigation, where one robot dynamically provides laser range data to another robot which is blind to its environment.

Algorithms such as Field-D* use linear interpolation to infer continuous fields of costdistance-to-goal, where costdistance is cost integrated over distance. Traditionally, field values have been used as direct input to trajectory planners. In contrast, we focus on extracting a minimum costdistance path between two points, given the continuous field. We identify a suboptimal phenomenon that occurs when standard path extraction techniques are used on linearly interpolated quantity-to-goal fields. The phenomenon causes paths to drift sideways toward their horizontal or vertical bounds, resulting in increased path length and unnecessary turns. We find that the sub-optimality is a mathematical consequence of the linear interpolation used to create the costdistance-to-goal field. We present a possible improvement that calculates path segment directions using an interpolation between the costdistance-to-goal gradient vectors, and perform a series of experiments comparing this method with the current state-of-the-art. We find that the proposed method can achieve a significant reduction in path length error, and we provide discussion and examples of when it should and should not be used.

An approach to stereo based local path planning in unstructured environments is presented. The approach differs from previous stereo based and image based planning systems (e.g. top-down occupancy grid planners, autonomous highway driving algorithms, and view-sequenced route representation), in that it uses specialized cost functions to find paths through an occupancy grid representation of the world directly in the image plane and forgoes a projection of cost information from the image plane down onto a top-down 2D Cartesian cost map. We discuss three cost metrics for path selection in image space. We present a basic image based planning system, discuss its susceptibility to rotational and translational oscillation, and present and implement two extensions to the basic system that overcome these limitations - a cylindrical based image system and a hierarchical planning system. All three systems are implemented in an autonomous robot and are tested against a standard top-down 2D Cartesian planning system on three outdoor courses of varying difficulty. We find that the basic image based planning system fails under certain conditions; however, the cylindrical based system is well suited to the task of local path planning and for use as a high resolution local planning component of a hierarchical planning system.