# Environment Characterization for Non-recontaminating Frontier-Based Robotic Exploration

### From DRLWiki<span style="display: none;">[[Image:http://people.csail.mit.edu/mikhail/volkov2011environment.pdf]]</span>

This work addresses the problem of obtaining a concise description of a physical environment for robotic exploration. We aim to determine the number of robots required to clear an environment using non-recontaminating exploration. We introduce the medial axis as a configuration space and derive a mathematical representation of a continuous environment that captures its underlying topology and geometry.We show that this representation provides a concise description of arbitrary environments, and that reasoning about points in this representation is equivalent to reasoning about robots in physical space.We leverage this to derive a lower bound on the number of required pursuers. We provide a transformation from this continuous representation into a symbolic representation. Finally, we present a generalized pursuit-evasion algorithm. Given an environment we can compute how many pursuers we need, and generate an optimal pursuit strategy that will guarantee the evaders are detected with the minimum number of pursuers.

## People

Mikhail Volkov

Alex Cornejo

Nancy Lynch

Daniela Rus

## References

*Mikhail Volkov, Alejandro Cornejo, Nancy Lynch, Daniela Rus*-

**Environment characterization for non-recontaminating frontier-based robotic exploration**

- PRIMA 2011: The 14th International Conference on Principles and Practice of Multi-Agent Systems pp. 19--35, Wollongong, NSW, Australia, November 2011
- Pdf Bibtex
**Author :**Mikhail Volkov, Alejandro Cornejo, Nancy Lynch, Daniela Rus**Title :**Environment characterization for non-recontaminating frontier-based robotic exploration**In :**PRIMA 2011: The 14th International Conference on Principles and Practice of Multi-Agent Systems -**Address :**Wollongong, NSW, Australia**Date :**November 2011