A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916179634814976 |
|---|---|
| author | Feng, Ying Paul, Adittyo Chen, Zhe Li, Jiaoyang |
| author_facet | Feng, Ying Paul, Adittyo Chen, Zhe Li, Jiaoyang |
| contents | One area of research in multi-agent path finding is to determine how replanning can be efficiently achieved in the case of agents being delayed during execution. One option is to reschedule the passing order of agents, i.e., the sequence in which agents visit the same location. In response, we propose Switchable-Edge Search (SES), an A*-style algorithm designed to find optimal passing orders. We prove the optimality of SES and evaluate its efficiency via simulations. The best variant of SES takes less than 1 second for small- and medium-sized problems and runs up to 4 times faster than baselines for large-sized problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_18145 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution Feng, Ying Paul, Adittyo Chen, Zhe Li, Jiaoyang Artificial Intelligence Multiagent Systems Robotics One area of research in multi-agent path finding is to determine how replanning can be efficiently achieved in the case of agents being delayed during execution. One option is to reschedule the passing order of agents, i.e., the sequence in which agents visit the same location. In response, we propose Switchable-Edge Search (SES), an A*-style algorithm designed to find optimal passing orders. We prove the optimality of SES and evaluate its efficiency via simulations. The best variant of SES takes less than 1 second for small- and medium-sized problems and runs up to 4 times faster than baselines for large-sized problems. |
| title | A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution |
| topic | Artificial Intelligence Multiagent Systems Robotics |
| url | https://arxiv.org/abs/2403.18145 |