Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.19564 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918044847046656 |
|---|---|
| author | Amir, Michael Bruckstein, Alfred M. |
| author_facet | Amir, Michael Bruckstein, Alfred M. |
| contents | We investigate the algorithmic problem of uniformly dispersing a swarm of robots in an unknown, gridlike environment. In this setting, our goal is to study the relationships between performance metrics and robot capabilities. We introduce a formal model comparing dispersion algorithms based on makespan, traveled distance, energy consumption, sensing, communication, and memory. Using this framework, we classify uniform dispersion algorithms according to their capability requirements and performance. We prove that while makespan and travel can be minimized in all environments, energy cannot, if the swarm's sensing range is bounded. In contrast, we show that energy can be minimized by ``ant-like'' robots in synchronous settings and asymptotically minimized in asynchronous settings, provided the environment is topologically simply connected, by using our ``Find-Corner Depth-First Search'' (FCDFS) algorithm. Our theoretical and experimental results show that FCDFS significantly outperforms known algorithms. Our findings reveal key limitations in designing swarm robotics systems for unknown environments, emphasizing the role of topology in energy-efficient dispersion. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_19564 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Time, Travel, and Energy in the Uniform Dispersion Problem Amir, Michael Bruckstein, Alfred M. Robotics Discrete Mathematics Multiagent Systems 68T40 I.2.9 We investigate the algorithmic problem of uniformly dispersing a swarm of robots in an unknown, gridlike environment. In this setting, our goal is to study the relationships between performance metrics and robot capabilities. We introduce a formal model comparing dispersion algorithms based on makespan, traveled distance, energy consumption, sensing, communication, and memory. Using this framework, we classify uniform dispersion algorithms according to their capability requirements and performance. We prove that while makespan and travel can be minimized in all environments, energy cannot, if the swarm's sensing range is bounded. In contrast, we show that energy can be minimized by ``ant-like'' robots in synchronous settings and asymptotically minimized in asynchronous settings, provided the environment is topologically simply connected, by using our ``Find-Corner Depth-First Search'' (FCDFS) algorithm. Our theoretical and experimental results show that FCDFS significantly outperforms known algorithms. Our findings reveal key limitations in designing swarm robotics systems for unknown environments, emphasizing the role of topology in energy-efficient dispersion. |
| title | Time, Travel, and Energy in the Uniform Dispersion Problem |
| topic | Robotics Discrete Mathematics Multiagent Systems 68T40 I.2.9 |
| url | https://arxiv.org/abs/2404.19564 |