Is Limited Information Enough? An Approximate Multi-agent Coverage Control in Non-Convex Discrete Environments
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917632620363776 |
|---|---|
| author | Iwase, Tatsuya Beynier, Aurélie Bredeche, Nicolas Maudet, Nicolas Marden, Jason R. |
| author_facet | Iwase, Tatsuya Beynier, Aurélie Bredeche, Nicolas Maudet, Nicolas Marden, Jason R. |
| contents | Conventional distributed approaches to coverage control may suffer from lack of convergence and poor performance, due to the fact that agents have limited information, especially in non-convex discrete environments. To address this issue, we extend the approach of [Marden 2016] which demonstrates how a limited degree of inter-agent communication can be exploited to overcome such pitfalls in one-dimensional discrete environments. The focus of this paper is on extending such results to general dimensional settings. We show that the extension is convergent and keeps the approximation ratio of 2, meaning that any stable solution is guaranteed to have a performance within 50% of the optimal one. The experimental results exhibit that our algorithm outperforms several state-of-the-art algorithms, and also that the runtime is scalable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_03752 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Is Limited Information Enough? An Approximate Multi-agent Coverage Control in Non-Convex Discrete Environments Iwase, Tatsuya Beynier, Aurélie Bredeche, Nicolas Maudet, Nicolas Marden, Jason R. Computer Science and Game Theory Conventional distributed approaches to coverage control may suffer from lack of convergence and poor performance, due to the fact that agents have limited information, especially in non-convex discrete environments. To address this issue, we extend the approach of [Marden 2016] which demonstrates how a limited degree of inter-agent communication can be exploited to overcome such pitfalls in one-dimensional discrete environments. The focus of this paper is on extending such results to general dimensional settings. We show that the extension is convergent and keeps the approximation ratio of 2, meaning that any stable solution is guaranteed to have a performance within 50% of the optimal one. The experimental results exhibit that our algorithm outperforms several state-of-the-art algorithms, and also that the runtime is scalable. |
| title | Is Limited Information Enough? An Approximate Multi-agent Coverage Control in Non-Convex Discrete Environments |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2401.03752 |