|Résumé||A set of identical, mobile agents is deployed in a network. Every network edge has a weight representing the distance between its endpoints. Each agent possesses a battery - a power source allowing to move along the network edges. Agents’ movement uses its battery proportionally to the distance travelled. The agent may stop at any point of network edge. Agents have a simple sensing device permitting to detect other agents - present at the same time at the same point of the network. At the beginning each agent has its initial information. The agents may exchange their information when they meet. The agents collaborate in order to achieve a common goal, which is convergecast, i.e., the initial information of all agents must be eventually concentrated at one agent. We investigate what is the minimal value of power, initially available to all agents, so that convergecast may be achieved. We study the problem in the centralized setting, when the problem must be solved by a centralized authority knowing the network and the initial positions of all agents in the network, and in the distributed setting, when each agent has to perform an algorithm being unaware of its initial position and the presence of other agents.
Intervenant: Jurek Czyzowicz |