Placement of charging stations for energy-constrained robots in spider graphs

• Lucas Cardoso Pereira UNICAMP https://orcid.org/0009-0003-3167-3187
• Santiago Valdés Ravelo UNICAMP https://orcid.org/0000-0001-7434-2642

DOI: https://doi.org/10.5753/etc.2026.23745

Resumo

In the MIN-STATION problem, we are given a simple graph G = (V,E), a set of m robots initially positioned on vertices in S ⊆ V , and a set of target vertices T ⊆ V , with |S| = |T| = m, along with a positive integer r. The goal is to determine the minimum number of charging stations to place on the vertices so that each robot can move from a distinct vertex in S to a distinct vertex in T without running out of energy, given that each robot can traverse at most r edges between consecutive recharges. This work reviews existing results in the literature for paths, which admit an O(|V|)-time algorithm, and presents a more general linear-time solution for spider graphs, achieving O(|V|) time complexity.

Referências

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.

A. K. Das. Charging Station Placement for Limited Energy Robots, pages 97–108. Springer Nature Switzerland, 2025.

T. Kundu and I. Saha. Approximation algorithms for charging station placement for mobile robots. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4770–4776. IEEE, 2023.

G. P. Strimel and M. M. Veloso. Coverage planning with finite resources. In 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2950–2956. IEEE, 2014.