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. / Master of Science / 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.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/78847 |
| Date | 08 September 2017 |
| Creators | Premkumar, Aravind Preshant |
| Contributors | Electrical and Computer Engineering, Tokekar, Pratap, Stilwell, Daniel J., Raghvendra, Sharath |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Thesis |
| Format | ETD, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
Page generated in 0.002 seconds