The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs
We show that two cooperating robots can learn exactly any strongly-connected directed graph with n indistinguishable nodes in expected time polynomial in n. We introduce a new type of homing sequence for robots, which helps the robots recognize certain previously-seen nodes. We represent an algorith...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149248 |
| _version_ | 1826209815252172800 |
|---|---|
| author | Bender, Michael A. Slonim, Donna K. |
| author_facet | Bender, Michael A. Slonim, Donna K. |
| author_sort | Bender, Michael A. |
| collection | MIT |
| description | We show that two cooperating robots can learn exactly any strongly-connected directed graph with n indistinguishable nodes in expected time polynomial in n. We introduce a new type of homing sequence for robots, which helps the robots recognize certain previously-seen nodes. We represent an algorithm in which the robots learn the graph and the homing sequence simultaneously by actively wandering through the graph. |
| first_indexed | 2024-09-23T14:31:20Z |
| id | mit-1721.1/149248 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T14:31:20Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1492482023-03-30T03:24:29Z The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs Bender, Michael A. Slonim, Donna K. We show that two cooperating robots can learn exactly any strongly-connected directed graph with n indistinguishable nodes in expected time polynomial in n. We introduce a new type of homing sequence for robots, which helps the robots recognize certain previously-seen nodes. We represent an algorithm in which the robots learn the graph and the homing sequence simultaneously by actively wandering through the graph. 2023-03-29T14:39:18Z 2023-03-29T14:39:18Z 1995-09 https://hdl.handle.net/1721.1/149248 MIT-LCS-TM-535 application/pdf |
| spellingShingle | Bender, Michael A. Slonim, Donna K. The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs |
| title | The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs |
| title_full | The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs |
| title_fullStr | The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs |
| title_full_unstemmed | The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs |
| title_short | The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs |
| title_sort | power of team exploration two robots can learn unlabeled directed graphs |
| url | https://hdl.handle.net/1721.1/149248 |
| work_keys_str_mv | AT bendermichaela thepowerofteamexplorationtworobotscanlearnunlabeleddirectedgraphs AT slonimdonnak thepowerofteamexplorationtworobotscanlearnunlabeleddirectedgraphs AT bendermichaela powerofteamexplorationtworobotscanlearnunlabeleddirectedgraphs AT slonimdonnak powerofteamexplorationtworobotscanlearnunlabeleddirectedgraphs |