Published: by

TIGRIS: An Informed Sampling-based Algorithm for Informative Path Planning

Informative path planning is an important and challenging problem in robotics that remains to be solved in a manner that allows for wide-spread implementation and real-world practical adoption. Among various reasons for this, one is the lack of approaches that allow for informative path planning in high-dimensional spaces and non-trivial sensor constraints. In this work we present a sampling-based approach that allows us to tackle the challenges of large and high-dimensional search spaces. This is done by performing informed sampling in the high-dimensional continuous space and incorporating potential information gain along edges in the reward estimation. This method rapidly generates a global path that maximizes information gain for the given path budget constraints.

An example scenario for an informative path planning problem of searching for a missing hiker. The UAV plans a path of maximum information gain over a prior belief distribution of the hiker's location.

Testing Implementation

We implemented TIGRIS with the objective of reducing entropy with a bias toward increasing belief probabilities. Our data gathering is performed using a fixed wing UAV and a static forward facing camera.

A visualization of the edge reward approximation and variable definitions given a fixed forward-facing camera.

Testing

We compare our approach to a sampling-based planner baseline and run 12,000 Monte Carlo simulations with 1-12 randomly placed target belief centroids. Through testing we show how our contributions allow our approach to consistently out-perform the baseline by 18.0%. An example test result is shown in the figure below. Detailed results and analysis can be found in our paper.

Example results in the testing environment. Red regions are areas of high reward and blue is low reward. The blue lines is the TIGRIS solution and the pink line is baseline planner. The bottom right image shows a 3D view of the environment, and the bottom left graph shows the best path reward of the planners over time.

Video

The video below gives a general overview of the planner and visualization of a potential application.

Please refer to our paper for details.

Future Work

Future work directions include replanning on the fly with TIGRIS, searching for and tracking moving target, local optimization of the final path, and local optimization over path segments within the planning framework.

Additional Info

Citation

@inproceedings{moon2022_tigris,
  doi = {10.48550/ARXIV.2203.12830},
  url = {https://arxiv.org/abs/2203.12830},
  author = {Moon, Brady and Chatterjee, Satrajit and Scherer, Sebastian},
  title = {TIGRIS: An Informed Sampling-based Algorithm for Informative Path Planning},
  publisher = {arXiv},
  booktitle={arXiv preprint arXiv:2203.12830},
  year = {2022},
  video = {https://youtu.be/bMw5nUGL5GQ}
}

Contributors

Term of use

BSD 4-Clause License