An Efficient and Continuous Approach to Information-Theoretic Exploration
Exploration of unknown environments is embedded and essential in many robotics applications. Traditional algorithms, that decide where to explore by computing the expected information gain of an incomplete map from future sensor measurements, are limited to very powerful computational platforms. In...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/130465 |
| _version_ | 1811082709956558848 |
|---|---|
| author | Henderson, Theia Sze, Vivienne Karaman, Sertac |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Henderson, Theia Sze, Vivienne Karaman, Sertac |
| author_sort | Henderson, Theia |
| collection | MIT |
| description | Exploration of unknown environments is embedded and essential in many robotics applications. Traditional algorithms, that decide where to explore by computing the expected information gain of an incomplete map from future sensor measurements, are limited to very powerful computational platforms. In this paper, we describe a novel approach for computing this expected information gain efficiently, as principally derived via mutual information. The key idea behind the proposed approach is a continuous occupancy map framework and the recursive structure it reveals. This structure makes it possible to compute the expected information gain of sensor measurements across an entire map much faster than computing each measurements' expected gain independently. Specifically, for an occupancy map composed of |M| cells and a range sensor that emits |Θ| measurement beams, the algorithm (titled FCMI) computes the information gain corresponding to measurements made at each cell in O(|Θ||M|) steps. To the best of our knowledge, this complexity bound is better than all existing methods for computing information gain. In our experiments, we observe that this novel, continuous approach is two orders of magnitude faster than the state-of-the-art FSMI algorithm. |
| first_indexed | 2024-09-23T12:07:42Z |
| format | Article |
| id | mit-1721.1/130465 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:07:42Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1304652022-09-28T00:19:44Z An Efficient and Continuous Approach to Information-Theoretic Exploration Henderson, Theia Sze, Vivienne Karaman, Sertac Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Microsystems Technology Laboratories Exploration of unknown environments is embedded and essential in many robotics applications. Traditional algorithms, that decide where to explore by computing the expected information gain of an incomplete map from future sensor measurements, are limited to very powerful computational platforms. In this paper, we describe a novel approach for computing this expected information gain efficiently, as principally derived via mutual information. The key idea behind the proposed approach is a continuous occupancy map framework and the recursive structure it reveals. This structure makes it possible to compute the expected information gain of sensor measurements across an entire map much faster than computing each measurements' expected gain independently. Specifically, for an occupancy map composed of |M| cells and a range sensor that emits |Θ| measurement beams, the algorithm (titled FCMI) computes the information gain corresponding to measurements made at each cell in O(|Θ||M|) steps. To the best of our knowledge, this complexity bound is better than all existing methods for computing information gain. In our experiments, we observe that this novel, continuous approach is two orders of magnitude faster than the state-of-the-art FSMI algorithm. 2021-04-13T14:36:37Z 2021-04-13T14:36:37Z 2020-09 2020-05 2021-04-12T17:15:41Z Article http://purl.org/eprint/type/ConferencePaper 9781728173955 2577-087X https://hdl.handle.net/1721.1/130465 Henderson, Theia et al. "An Efficient and Continuous Approach to Information-Theoretic Exploration." 2020 IEEE International Conference on Robotics and Automation, May-August 2020, virtual event (Paris, France), Institute of Electrical and Electronics Engineers, September 2020. © 2020 IEEE en http://dx.doi.org/10.1109/icra40945.2020.9196592 2020 IEEE International Conference on Robotics and Automation Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Henderson, Theia Sze, Vivienne Karaman, Sertac An Efficient and Continuous Approach to Information-Theoretic Exploration |
| title | An Efficient and Continuous Approach to Information-Theoretic Exploration |
| title_full | An Efficient and Continuous Approach to Information-Theoretic Exploration |
| title_fullStr | An Efficient and Continuous Approach to Information-Theoretic Exploration |
| title_full_unstemmed | An Efficient and Continuous Approach to Information-Theoretic Exploration |
| title_short | An Efficient and Continuous Approach to Information-Theoretic Exploration |
| title_sort | efficient and continuous approach to information theoretic exploration |
| url | https://hdl.handle.net/1721.1/130465 |
| work_keys_str_mv | AT hendersontheia anefficientandcontinuousapproachtoinformationtheoreticexploration AT szevivienne anefficientandcontinuousapproachtoinformationtheoreticexploration AT karamansertac anefficientandcontinuousapproachtoinformationtheoreticexploration AT hendersontheia efficientandcontinuousapproachtoinformationtheoreticexploration AT szevivienne efficientandcontinuousapproachtoinformationtheoreticexploration AT karamansertac efficientandcontinuousapproachtoinformationtheoreticexploration |