{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/46558"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/46558","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Cooperative exploration under communication constraints","abstract":"The cooperative exploration problem necessarily involves communication among agents, while the spatial separation inherent in this task places fundamental limits on the amount of data that can be transmitted. However, the impact of limited communication on the exploration process has not been fully characterized. Existing exploration algorithms do not realistically model the tradeoff between expansion, which allows more rapid exploration of the area of interest, and maintenance of close relative proximity among agents, which facilitates communication. This thesis develops new algorithms applicable to the problem of cooperative exploration under communication constraints. The exploration problem is decomposed into two parts. In the first part, cooperative exploration is considered in the context of a hierarchical communication framework known as a mobile backbone network. In such a network, mobile backbone nodes, which have good mobility and communication capabilities, provide communication support for regular nodes, which are constrained in movement and communication capabilities but which can sense the environment. New exact and approximation algorithms are developed for throughput optimization in networks composed of stationary regular nodes, and new extensions are formulated to take advantage of regular node mobility. These algorithms are then applied to a cooperative coverage problem. In the second part of this work, techniques are developed for utilizing a given level of throughput in the context of cooperative estimation. The mathematical properties of the information form of the Kalman filter are leveraged in the development of two algorithms for selecting highly informative portions of the information matrix for transmission. One algorithm, a fully polynomial time approximation scheme, provides provably good results in computationally tractable time for problem instances of a particular structure. The other, a heuristic method applicable to instances of arbitrary matrix structure, performs very well in simulation for randomly-generated problems of realistic dimension.","abstract_html":"The cooperative exploration problem necessarily involves communication among agents, while the spatial separation inherent in this task places fundamental limits on the amount of data that can be transmitted. However, the impact of limited communication on the exploration process has not been fully characterized. Existing exploration algorithms do not realistically model the tradeoff between expansion, which allows more rapid exploration of the area of interest, and maintenance of close relative proximity among agents, which facilitates communication. This thesis develops new algorithms applicable to the problem of cooperative exploration under communication constraints. The exploration problem is decomposed into two parts. In the first part, cooperative exploration is considered in the context of a hierarchical communication framework known as a mobile backbone network. In such a network, mobile backbone nodes, which have good mobility and communication capabilities, provide communication support for regular nodes, which are constrained in movement and communication capabilities but which can sense the environment. New exact and approximation algorithms are developed for throughput optimization in networks composed of stationary regular nodes, and new extensions are formulated to take advantage of regular node mobility. These algorithms are then applied to a cooperative coverage problem. In the second part of this work, techniques are developed for utilizing a given level of throughput in the context of cooperative estimation. The mathematical properties of the information form of the Kalman filter are leveraged in the development of two algorithms for selecting highly informative portions of the information matrix for transmission. One algorithm, a fully polynomial time approximation scheme, provides provably good results in computationally tractable time for problem instances of a particular structure. The other, a heuristic method applicable to instances of arbitrary matrix structure, performs very well in simulation for randomly-generated problems of realistic dimension.","abstract_has_math":false,"creators":["Craparo, Emily M. (Emily Marie), 1980-"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics.","school":null,"contributors":[],"advisors":["Jonathan P. How and Eytan Modiano."],"committee_chairs":[],"committee_members":[],"year":2008,"date_issued":"2008","date_published":"2008","updated_at":"2026-07-22T22:20:57Z","subjects":["Aeronautics and Astronautics."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/46558","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Jonathan P. How and Eytan Modiano."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics."]},{"key":"dc:creator","label":"Author","values":["Craparo, Emily M. (Emily Marie), 1980-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2009-08-26T16:50:54Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2009-08-26T16:50:54Z"]},{"key":"dc:date.issued","label":"Date","values":["2008"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Aeronautics and Astronautics."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/46558"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2008.","Includes bibliographical references (leaves 131-137)."]},{"key":"dc:description.abstract","label":"Abstract","values":["The cooperative exploration problem necessarily involves communication among agents, while the spatial separation inherent in this task places fundamental limits on the amount of data that can be transmitted. However, the impact of limited communication on the exploration process has not been fully characterized. Existing exploration algorithms do not realistically model the tradeoff between expansion, which allows more rapid exploration of the area of interest, and maintenance of close relative proximity among agents, which facilitates communication. This thesis develops new algorithms applicable to the problem of cooperative exploration under communication constraints. The exploration problem is decomposed into two parts. In the first part, cooperative exploration is considered in the context of a hierarchical communication framework known as a mobile backbone network. In such a network, mobile backbone nodes, which have good mobility and communication capabilities, provide communication support for regular nodes, which are constrained in movement and communication capabilities but which can sense the environment. New exact and approximation algorithms are developed for throughput optimization in networks composed of stationary regular nodes, and new extensions are formulated to take advantage of regular node mobility. These algorithms are then applied to a cooperative coverage problem. In the second part of this work, techniques are developed for utilizing a given level of throughput in the context of cooperative estimation. The mathematical properties of the information form of the Kalman filter are leveraged in the development of two algorithms for selecting highly informative portions of the information matrix for transmission. One algorithm, a fully polynomial time approximation scheme, provides provably good results in computationally tractable time for problem instances of a particular structure. The other, a heuristic method applicable to instances of arbitrary matrix structure, performs very well in simulation for randomly-generated problems of realistic dimension."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Cooperative exploration under communication constraints"]}]}],"canonical_facts":{"dc:contributor.advisor":["Jonathan P. How and Eytan Modiano."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics."],"dc:creator":["Craparo, Emily M. (Emily Marie), 1980-"],"dc:date.accessioned":["2009-08-26T16:50:54Z"],"dc:date.available":["2009-08-26T16:50:54Z"],"dc:date.issued":["2008"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2008.","Includes bibliographical references (leaves 131-137)."],"dc:description.abstract":["The cooperative exploration problem necessarily involves communication among agents, while the spatial separation inherent in this task places fundamental limits on the amount of data that can be transmitted. However, the impact of limited communication on the exploration process has not been fully characterized. Existing exploration algorithms do not realistically model the tradeoff between expansion, which allows more rapid exploration of the area of interest, and maintenance of close relative proximity among agents, which facilitates communication. This thesis develops new algorithms applicable to the problem of cooperative exploration under communication constraints. The exploration problem is decomposed into two parts. In the first part, cooperative exploration is considered in the context of a hierarchical communication framework known as a mobile backbone network. In such a network, mobile backbone nodes, which have good mobility and communication capabilities, provide communication support for regular nodes, which are constrained in movement and communication capabilities but which can sense the environment. New exact and approximation algorithms are developed for throughput optimization in networks composed of stationary regular nodes, and new extensions are formulated to take advantage of regular node mobility. These algorithms are then applied to a cooperative coverage problem. In the second part of this work, techniques are developed for utilizing a given level of throughput in the context of cooperative estimation. The mathematical properties of the information form of the Kalman filter are leveraged in the development of two algorithms for selecting highly informative portions of the information matrix for transmission. One algorithm, a fully polynomial time approximation scheme, provides provably good results in computationally tractable time for problem instances of a particular structure. The other, a heuristic method applicable to instances of arbitrary matrix structure, performs very well in simulation for randomly-generated problems of realistic dimension."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/46558"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Aeronautics and Astronautics."],"dc:title":["Cooperative exploration under communication constraints"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:20:57Z"}