skip to main content

Title: Opportunistic Multi-Robot Environmental Sampling via Decentralized Markov Decision Processes
We study the problem of information sampling with a group of mobile robots from an unknown environment. Each robot is given a unique region in the environment for the sampling task. The objective of the robots is to visit a subset of locations in the environment such that the collected information is maximized, and consequently, the underlying information model matches as close to reality as possible. The robots have limited communication ranges, and therefore can only communicate when nearby one another. The robots operate in a stochastic environment and their control uncertainty is handled using factored Decentralized Markov Decision Processes (Dec-MDP). When two or more robots communicate, they share their past noisy observations and use a Gaussian mixture model to update their local information models. This in turn helps them to obtain a better Dec-MDP policy. Simulation results show that our proposed strategy is able to predict the information model closer to the ground truth version than compared to other algorithms. Furthermore, the reduction in the overall uncertainty is more than comparable algorithms.  more » « less
Award ID(s):
Author(s) / Creator(s):
Date Published:
Journal Name:
International Symposium Distributed Autonomous Robotic Systems
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Partially observable Markov decision processes (POMDPs) provide a flexible representation for real-world decision and control problems. However, POMDPs are notoriously difficult to solve, especially when the state and observation spaces are continuous or hybrid, which is often the case for physical systems. While recent online sampling-based POMDP algorithms that plan with observation likelihood weighting have shown practical effectiveness, a general theory characterizing the approximation error of the particle filtering techniques that these algorithms use has not previously been proposed. Our main contribution is bounding the error between any POMDP and its corresponding finite sample particle belief MDP (PB-MDP) approximation. This fundamental bridge between PB-MDPs and POMDPs allows us to adapt any sampling-based MDP algorithm to a POMDP by solving the corresponding particle belief MDP, thereby extending the convergence guarantees of the MDP algorithm to the POMDP. Practically, this is implemented by using the particle filter belief transition model as the generative model for the MDP solver. While this requires access to the observation density model from the POMDP, it only increases the transition sampling complexity of the MDP solver by a factor of O(C), where C is the number of particles. Thus, when combined with sparse sampling MDP algorithms, this approach can yield algorithms for POMDPs that have no direct theoretical dependence on the size of the state and observation spaces. In addition to our theoretical contribution, we perform five numerical experiments on benchmark POMDPs to demonstrate that a simple MDP algorithm adapted using PB-MDP approximation, Sparse-PFT, achieves performance competitive with other leading continuous observation POMDP solvers.

    more » « less
  2. We consider a planning problem for a robot operating in an information-degraded environment. Our contribution to the state of the art is addressing this problem when robots have limited sensing capabilities, and thus only acquire information in certain locations. We therefore need a method that balances between driving the robot to the goal and toward regions to gain information (or to reduce uncertainty). We present a novel sampling-based planner (Particle Filter based Affine Quadratic Tree --- PF-AQT) that explores the environment, and plans to reach a goal with minimal uncertainty. We then use the output trajectory from PF-AQT to initialize an optimization-based planner that finds a locally optimal trajectory that minimizes control effort and uncertainty. In doing so we reap the exploration benefits of sampling-based methods and exploitation benefits of optimization-based methods for dealing with uncertainty and limited sensing capabilities of the robot. We demonstrate our results using two dynamical systems: double integrator model and a non-holonomic car-like robot. 
    more » « less
  3. Accurately detecting, localizing, and tracking an unknown and time-varying number of dynamic targets using a team of mobile robots is a challenging problem that requires robots to reason about the uncertainties in their collected measurements. The problem is made more challenging when robots are uncertain about their own states, as this makes it difficult to both collectively localize targets and avoid collisions with one another. In this paper, we introduce the convex uncertain Voronoi (CUV) diagram, a generalization of the standard Voronoi diagram that accounts for the uncertain pose of each individual robot. We then use the CUV diagram to develop distributed multi-target tracking and coverage control algorithms that enable teams of mobile robots to account for bounded uncertainty in the location of each robot. Our algorithms are capable of safely driving mobile robots towards areas of high information distribution while maintaining coverage of the whole area of interest. We demonstrate the efficacy of these algorithms via a series of simulated and hardware tests, and compare the results to our previous work which assumes perfect localization. 
    more » « less
  4. Using robots to collect data is an effective way to obtain information from the environment and communicate it to a static base station. Furthermore, robots have the capability to communicate with one another, potentially decreasing the time for data to reach the base station. We present a Mixed Integer Linear Program that reasons about discrete routing choices, continuous robot paths, and their effect on the latency of the data collection task. We analyze our formulation, discuss optimization challenges inherent to the data collection problem, and propose a factored formulation that finds optimal answers more efficiently. Our work is able to find paths that reduce latency by up to 101% compared to treating all robots independently in our tested scenarios. 
    more » « less
  5. null (Ed.)
    Navigation and motion control of a robot to a destination are tasks that have historically been performed with the assumption that contact with the environment is harmful. This makes sense for rigid-bodied robots, where obstacle collisions are fundamentally dangerous. However, because many soft robots have bodies that are low-inertia and compliant, obstacle contact is inherently safe. As a result, constraining paths of the robot to not interact with the environment is not necessary and may be limiting. In this article, we mathematically formalize interactions of a soft growing robot with a planar environment in an empirical kinematic model. Using this interaction model, we develop a method to plan paths for the robot to a destination. Rather than avoiding contact with the environment, the planner exploits obstacle contact when beneficial for navigation. We find that a planner that takes into account and capitalizes on environmental contact produces paths that are more robust to uncertainty than a planner that avoids all obstacle contact. 
    more » « less