Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration
This paper 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 m...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin / Heidelberg
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73714 https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0001-9632-754X |
| _version_ | 1826197110584770560 |
|---|---|
| author | Volkov, Mikhail Cornejo Collado, Alex Lynch, Nancy Ann Rus, Daniela L. |
| author2 | move to dc.description.sponsorship |
| author_facet | move to dc.description.sponsorship Volkov, Mikhail Cornejo Collado, Alex Lynch, Nancy Ann Rus, Daniela L. |
| author_sort | Volkov, Mikhail |
| collection | MIT |
| description | This paper 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. |
| first_indexed | 2024-09-23T10:42:57Z |
| format | Article |
| id | mit-1721.1/73714 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:42:57Z |
| publishDate | 2012 |
| publisher | Springer Berlin / Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/737142022-09-30T22:26:57Z Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration Volkov, Mikhail Cornejo Collado, Alex Lynch, Nancy Ann Rus, Daniela L. move to dc.description.sponsorship Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Volkov, Mikhail Cornejo Collado, Alex Lynch, Nancy Ann Rus, Daniela L. This paper 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. Singapore-MIT Alliance for Research and Technology Center (Future Urban Mobility Project) United States. Air Force Office of Scientific Research (Award FA9550-08-1-0159) National Science Foundation (U.S.) (Award CNS-0715397) National Science Foundation (U.S.) (Award CCF-0726514) National Science Foundation (U.S.) (Grant 0735953) 2012-10-10T15:26:09Z 2012-10-10T15:26:09Z 2011-11 2011-11 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-25043-9 http://hdl.handle.net/1721.1/73714 Volkov, Mikhail et al. “Environment Characterization for Non-recontaminating Frontier-Based Robotic Exploration.” Lecture Notes in Computer Science: Agents in Principle, Agents in Practice. Ed. David Kinny et al. Vol. 7047. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. 19–35. https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0001-9632-754X en_US http://dx.doi.org/10.1007/978-3-642-25044-6_5 Agents in Principle, Agents in Practice Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin / Heidelberg MIT web domain |
| spellingShingle | Volkov, Mikhail Cornejo Collado, Alex Lynch, Nancy Ann Rus, Daniela L. Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration |
| title | Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration |
| title_full | Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration |
| title_fullStr | Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration |
| title_full_unstemmed | Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration |
| title_short | Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration |
| title_sort | environment characterization for non recontaminating frontier based robotic exploration |
| url | http://hdl.handle.net/1721.1/73714 https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0001-9632-754X |
| work_keys_str_mv | AT volkovmikhail environmentcharacterizationfornonrecontaminatingfrontierbasedroboticexploration AT cornejocolladoalex environmentcharacterizationfornonrecontaminatingfrontierbasedroboticexploration AT lynchnancyann environmentcharacterizationfornonrecontaminatingfrontierbasedroboticexploration AT rusdanielal environmentcharacterizationfornonrecontaminatingfrontierbasedroboticexploration |