| Presentation | 2019-05-11 Ring Exploration Algorithms for Myopic Luminous Robots with Larger Visibility Shota Nagahama, Fukuhito Ooshita, Michiko Inoue, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we investigate ring exploration algorithms for autonomous mobile robots. The robots are myopic, that is, they observe nodes within a certain fixed distance, and luminous, that is, they have light devices that can emit a constant number of colors. We consider the constraint that the visible distance is any constant of at least two and the number of colors of lights is two. As a main contribution, we prove that 1) two robots are necessary and sufficient to achieve perpetual exploration, and 2) three robots are necessary and sufficient to achieve terminating exploration. These results show that the number of robots required for exploration can be reduced by extending their visibility compared to the previous work. We also show that the proposed perpetual exploration algorithm is universal, that is, the algorithm achieves perpetual exploration from any solvable initial configuration with two robots. On the other hand, we show that no universal algorithm exists for terminating exploration with three robots. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | autonomous mobile robots / exploration problem / discrete environments |
| Paper # | COMP2019-7 |
| Date of Issue | 2019-05-03 (COMP) |
| Conference Information | |
| Committee | COMP / IPSJ-AL |
|---|---|
| Conference Date | 2019/5/10(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kumamoto University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshihiro Fujito(Toyohashi Univ. of Tech.) / 瀧本 英二(九州大学) |
| Vice Chair | Shinichi Nakano(Gunma Univ.) |
| Secretary | Shinichi Nakano(Kyoto Univ.) / (Kumamoto Univ) |
| Assistant | Kazuhisa Seto(Seikei Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Ring Exploration Algorithms for Myopic Luminous Robots with Larger Visibility |
| Sub Title (in English) | |
| Keyword(1) | autonomous mobile robots |
| Keyword(2) | exploration problem |
| Keyword(3) | discrete environments |
| 1st Author's Name | Shota Nagahama |
| 1st Author's Affiliation | Nara Institute of Science and Technology(NAIST) |
| 2nd Author's Name | Fukuhito Ooshita |
| 2nd Author's Affiliation | Nara Institute of Science and Technology(NAIST) |
| 3rd Author's Name | Michiko Inoue |
| 3rd Author's Affiliation | Nara Institute of Science and Technology(NAIST) |
| Date | 2019-05-11 |
| Paper # | COMP2019-7 |
| Volume (vol) | vol.119 |
| Number (no) | COMP-21 |
| Page | pp.pp.83-90(COMP), |
| #Pages | 8 |
| Date of Issue | 2019-05-03 (COMP) |