Asymptotically Optimal Planning for Non-myopic Multi-Robot Information Gathering
A recent paper by members of the DCIST alliance develops a novel highly scalable sampling-based planning algorithm for multi-robot active information acquisition tasks in complex environments. Active information gathering scenarios include target localization and tracking, active Simultaneous Localization and Mapping (SLAM), surveillance, environmental monitoring and others. The goal is to compute control policies for mobile robot sensors which minimize the accumulated uncertainty of a dynamic hidden state over an a priori unknown horizon. To design optimal sensor policies, we propose a novel nonmyopic sampling-based approach that simultaneously explores both the robot motion space and the information space reachable by the sensors. We show that the proposed algorithm is probabilistically complete, asymptotically optimal, and convergences exponentially fast to the optimal solution. Moreover, we demonstrate that by biasing the sampling process towards regions that are expected to be informative, the proposed method can quickly compute sensor policies that achieve user-specified levels of uncertainty in large-scale estimation tasks that may involve large multi-robot teams, workspaces, and dimensions of the hidden state. We provide extensive simulation results that corroborate the theoretical analysis and show that the proposed algorithm can address large-scale estimation tasks.
Target localization and tracking scenario: Two robots with limited field-of-view (blue ellipses) navigate an environment with obstacles to localize and track six targets of interest. Target uncertainty is illustrated in red.
Source: Yiannis Kantaros, Brent Schlotfeldt, Nikolay Atanasov, and George J. Pappas: ‘Asymptotically Optimal Planning for Non-myopic Multi-Robot Information Gathering’ In Proceedings of the 2019 Robotics: Science and Systems (RSS), Freiburg, Germany, June 2019.
Points of Contact: George J. Pappas
navigation. A recent paper by members of the DCIST alliance tackles the problem of autonomous mapping of unknown environments using information theoretic metrics and signed distance field maps. Signed distance fields are discrete representations of environmental occupancy in which each cell of the environment stores a distance to the nearest obstacle surface, with negative distances indicating that the cell is within an obstacle. Such a representation has many benefits over the more traditional occupancy grid map including trivial collision checking, and easy extraction of mesh representations of the obstacle surfaces. The researchers use a truncated signed distance field, which only keeps track of cells near obstacle surfaces, and model each cell as a Gaussian random variable with an expected distance and a variance determined incrementally using a realistic RGB-D sensor noise model. The use of Gaussian random variables enables the closed form computation of Shannon mutual information between a Gaussian sensor measurement and the Gaussian cells it intersects. This allows for efficient evaluations of expected information when planning and evaluating possible future trajectories. Using these tools, a robot is able to efficiently evaluate a large number of trajectories before choosing the best next step to increase its information about the environment. The researchers show the resulting active exploration algorithm running on several simulated 2D environments of varying complexity. The figure shows a snapshot of the robot exploring the most complex of the three environments. These simulations can be viewed in more detail in the video linked below.