{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/78847"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/78847","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Competitive Algorithms and System for Multi-Robot Exploration of Unknown Environments","abstract":"We present an algorithm to explore an orthogonal polygon using a team of p robots. This algorithm combines ideas from information-theoretic exploration algorithms and computational geometry based exploration algorithms. The algorithm is based on a single-robot polygon exploration algorithm and a tree exploration algorithm. We show that the exploration time of our algorithm is competitive (as a function of p) with respect to the offline optimal exploration algorithm. We discuss how this strategy can be adapted to real-world settings to deal with noisy sensors. In addition to theoretical analysis, we investigate the performance of our algorithm through simulations for multiple robots and experiments with a single robot.","abstract_html":"We present an algorithm to explore an orthogonal polygon using a team of p robots. This algorithm combines ideas from information-theoretic exploration algorithms and computational geometry based exploration algorithms. The algorithm is based on a single-robot polygon exploration algorithm and a tree exploration algorithm. We show that the exploration time of our algorithm is competitive (as a function of p) with respect to the offline optimal exploration algorithm. We discuss how this strategy can be adapted to real-world settings to deal with noisy sensors. In addition to theoretical analysis, we investigate the performance of our algorithm through simulations for multiple robots and experiments with a single robot.","abstract_has_math":false,"creators":["Premkumar, Aravind Preshant"],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Computer Engineering","degree_department":"Electrical and Computer Engineering","school":null,"contributors":[],"advisors":[],"committee_chairs":["Tokekar, Pratap"],"committee_members":["Stilwell, Daniel J.","Raghvendra, Sharath"],"year":2017,"date_issued":"2017-09-08","date_published":"2017-09-08","updated_at":"2026-07-22T22:19:44Z","subjects":["Robotics","Multi-robot Exploration"],"languages":[],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:12666"],"render_values":[{"text":"vt_gsexam:12666","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/78847","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Tokekar, Pratap"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Stilwell, Daniel J.","Raghvendra, Sharath"]},{"key":"dc:contributor.department","label":"Department","values":["Electrical and Computer Engineering"]},{"key":"dc:creator","label":"Author","values":["Premkumar, Aravind Preshant"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2017-09-09T08:00:26Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2017-09-09T08:00:26Z"]},{"key":"dc:date.issued","label":"Date","values":["2017-09-08"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Robotics","Multi-robot Exploration"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:12666"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/78847"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["We present an algorithm to explore an orthogonal polygon using a team of p robots. This algorithm combines ideas from information-theoretic exploration algorithms and computational geometry based exploration algorithms. The algorithm is based on a single-robot polygon exploration algorithm and a tree exploration algorithm. We show that the exploration time of our algorithm is competitive (as a function of p) with respect to the offline optimal exploration algorithm. We discuss how this strategy can be adapted to real-world settings to deal with noisy sensors. In addition to theoretical analysis, we investigate the performance of our algorithm through simulations for multiple robots and experiments with a single robot."]},{"key":"dc:description.abstractgeneral","label":"General Abstract","values":["In applications such as disaster recovery, the layout of the environment is generally unknown. Hence, there is a need to explore the environment in order to effectively perform search and rescue. Exploration of unknown environments using a single robot is a well studied problem. We present an algorithm to perform the task with a team of p robots for the specific case of orthogonal polygons, i.e. polygonal environments where each side is aligned with either the X or the Y axis. The algorithm is based on a single-robot polygon exploration algorithm and a tree exploration algorithm. We show that the exploration time of our algorithm is competitive (as a function of p) with respect to the optimal offline algorithm. We then optimize the information gain of the path followed by the robots by allowing local detours in order to decrease the entropy in the map."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["ETD"]},{"key":"dc:title","label":"Title","values":["Competitive Algorithms and System for Multi-Robot Exploration of Unknown Environments"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Tokekar, Pratap"],"dc:contributor.committeemember":["Stilwell, Daniel J.","Raghvendra, Sharath"],"dc:contributor.department":["Electrical and Computer Engineering"],"dc:creator":["Premkumar, Aravind Preshant"],"dc:date.accessioned":["2017-09-09T08:00:26Z"],"dc:date.available":["2017-09-09T08:00:26Z"],"dc:date.issued":["2017-09-08"],"dc:description.abstract":["We present an algorithm to explore an orthogonal polygon using a team of p robots. This algorithm combines ideas from information-theoretic exploration algorithms and computational geometry based exploration algorithms. The algorithm is based on a single-robot polygon exploration algorithm and a tree exploration algorithm. We show that the exploration time of our algorithm is competitive (as a function of p) with respect to the offline optimal exploration algorithm. We discuss how this strategy can be adapted to real-world settings to deal with noisy sensors. In addition to theoretical analysis, we investigate the performance of our algorithm through simulations for multiple robots and experiments with a single robot."],"dc:description.abstractgeneral":["In applications such as disaster recovery, the layout of the environment is generally unknown. Hence, there is a need to explore the environment in order to effectively perform search and rescue. Exploration of unknown environments using a single robot is a well studied problem. We present an algorithm to perform the task with a team of p robots for the specific case of orthogonal polygons, i.e. polygonal environments where each side is aligned with either the X or the Y axis. The algorithm is based on a single-robot polygon exploration algorithm and a tree exploration algorithm. We show that the exploration time of our algorithm is competitive (as a function of p) with respect to the optimal offline algorithm. We then optimize the information gain of the path followed by the robots by allowing local detours in order to decrease the entropy in the map."],"dc:description.degree":["Master of Science"],"dc:format.medium":["ETD"],"dc:identifier.other":["vt_gsexam:12666"],"dc:identifier.uri":["http://hdl.handle.net/10919/78847"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["Robotics","Multi-robot Exploration"],"dc:title":["Competitive Algorithms and System for Multi-Robot Exploration of Unknown Environments"],"dc:type":["Thesis"],"thesis:degree_discipline":["Computer Engineering"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:44Z"}