We provide a framework for the assignment of multiple robots to goal locations, when robot travel times are uncertain. Our premise is that time is the most valuable asset in the system. Hence, we make use of redundant robots to counter the effect of uncertainty and minimize the average waiting time at destinations. We apply our framework to transport networks represented as graphs, and consider uncertainty in the edge costs (i.e., travel time). Since solving the redundant assignment problem is strongly NP-hard, we exploit structural properties of our problem to propose a polynomial-time solution with provable sub-optimality bounds. Our method uses distributive aggregate functions, which allow us to efficiently (i.e., incrementally) compute the effective cost of assigning redundant robots. Experimental results on random graphs show that the deployment of redundant robots through our method reduces waiting times at goal locations, when edge traversals are uncertain.
Submodular optimization for combinatorial problems has has also gained considerable traction in the domain of multi-robot systems. Applications include coordinated robot routing for environmental monitoring @cite_17 , leader selection in leader-follower systems @cite_12 , sensor scheduling for localization @cite_20 , and path planning for orienteering missions @cite_18 . Typically, the aforementioned studies develop explicit objective functions that are specific to the considered problem domains. The authors then go about proving the submodularity property and devising the appropriate assignment algorithms. This general methodology is similar to the one presented in our paper. The particularity of our work lies in the specificity of our objective function for redundant robot assignments under uncertain travel times, which is not captured by objective functions developed in prior work.
@cite_18 @cite_20 @cite_12 @cite_17
2032239956 2123030512 1519517979 2125069195
We introduce a graph-based informative path planning algorithm for a mobile robot which explicitly handles time. The objective function must be submodular in the samples taken by the robot, and the samples obtained are allowed to depend on the time at which the robot visits each location. Using a submodular objective function allows our algorithm to handle problems with diminishing returns, e.g. the case when taking a sample provides less utility when other nearby points have already been sampled. We give a formal description of this framework wherein an objective function that maps the path of the robot to the set of samples taken is defined. We also show how this framework can handle the case in which the robot takes samples along the edges of the graph. A proof of the approximation guarantee for the algorithm is given. Finally, quantitative results are shown for three problems: one simple example with a known Gaussian process model, one simulated example for an underwater robot planning problem using data from a well-known ocean modeling system, and one field experiment using an autonomous surface vehicle (ASV) measuring wireless signal strength on a lake. Abstract Planning optimal paths for large numbers of robots is computationally expensive. In this paper, we introduce a new framework for multirobot path planning called subdimensional expansion, which initially plans for each robot individually, and then coordinates motion among the robots as needed. More specifically, subdimensional expansion initially creates a one-dimensional search space embedded in the joint configuration space of the multirobot system. When the search space is found to be blocked during planning by a robot–robot collision, the dimensionality of the search space is locally increased to ensure that an alternative path can be found. As a result, robots are only coordinated when necessary, which reduces the computational cost of finding a path. We present the M ⁎ algorithm, an implementation of subdimensional expansion that adapts the A ⁎ planner to perform efficient multirobot planning. M ⁎ is proven to be complete and to find minimal cost paths. Simulation results are presented that show that M ⁎ outperforms existing optimal multirobot path planning algorithms. Many robotic path planning applications, such as search and rescue, involve uncertain environments with complex dynamics that can be only partially observed. When selecting the best subset of observation locations subject to constrained resources (such as limited time or battery capacity) it is an important problem to trade off exploration (gathering information about the environment) and exploitation (using the current knowledge about the environment most effectively) for efficiently observing these environments. Even the nonadaptive setting, where paths are planned before observations are made, is NP-hard, and has been subject to much research. In this paper, we present a novel approach to adaptive informative path planning that addresses this exploration-exploitation tradeoff. Our approach is nonmyopic, i.e. it plans ahead for possible observations that can be made in the future. We quantify the benefit of exploration through the adaptivity gap'' between an adaptive and a nonadaptive algorithm in terms of the uncertainty in the environment. Exploiting the submodularity (a diminishing returns property) and locality properties of the objective function, we develop an algorithm that performs provably near-optimally in settings where the adaptivity gap is small. In case of large gap, we use an objective function that simultaneously optimizes paths for exploration and exploitation. We also provide an algorithm to extend any single robot algorithm for adaptive informative path planning to the multi-robot setting while approximately preserving the theoretical guarantee of the single robot algorithm. We extensively evaluate our approach on a domain and a scientific monitoring problem using a real robotic system. The need for efficient monitoring of spatio-temporal dynamics in large environmental applications, such as the water quality monitoring in rivers and lakes, motivates the use of robotic sensors in order to achieve sufficient spatial coverage. Typically, these robots have bounded resources, such as limited battery or limited amounts of time to obtain measurements. Thus, careful coordination of their paths is required in order to maximize the amount of information collected, while respecting the resource constraints. In this paper, we present an efficient approach for near-optimally solving the NP-hard optimization problem of planning such informative paths. In particular, we first develop eSIP (efficient Single-robot Informative Path planning), an approximation algorithm for optimizing the path of a single robot. Hereby, we use a Gaussian Process to model the underlying phenomenon, and use the mutual information between the visited locations and remainder of the space to quantify the amount of information collected. We prove that the mutual information collected using paths obtained by using eSIP is close to the information obtained by an optimal solution. We then provide a general technique, sequential allocation, which can be used to extend any single robot planning algorithm, such as eSIP, for the multi-robot problem. This procedure approximately generalizes any guarantees for the single-robot problem to the multi-robot case. We extensively evaluate the effectiveness of our approach on several experiments performed infield for two important environmental sensing applications, lake and river monitoring, and simulation experiments performed using several real world sensor network data sets.