Source author record

J. Opatrny

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Robotics

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Graph Exploration by Energy-Sharing Mobile Agents

We consider the problem of collective exploration of a known $n$ -node edge-weighted graph by $k$ mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbitrary subset of nodes in the graph, and each agent has an initial, possibly different, amount of energy. The goal of the exploration problem is for every edge in the graph to be traversed by at least one agent. The amount of energy used by an agent to travel distance $x$ is proportional to $x$ . In our model, the agents can {\em share} energy when co-located: when two agents meet, one can transfer part of its energy to the other. For an $n$ -node path, we give an $O(n+k)$ time algorithm that either finds an exploration strategy, or reports that one does not exist. For an $n$ -node tree with $\ell$ leaves, we give an $O(n+ \ell k^2)$ algorithm that finds an exploration strategy if one exists. Finally, for the general graph case, we show that the problem of deciding if exploration is possible by energy-sharing agents is NP-hard, even for 3-regular graphs. In addition, we show that it is always possible to find an exploration strategy if the total energy of the agents is at least twice the total weight of the edges; moreover, this is asymptotically optimal.

preprint2014arXiv

Optimal online and offline algorithms for robot-assisted restoration of barrier coverage

Cooperation between mobile robots and wireless sensor networks is a line of research that is currently attracting a lot of attention. In this context, we study the following problem of barrier coverage by stationary wireless sensors that are assisted by a mobile robot with the capacity to move sensors. Assume that $n$ sensors are initially arbitrarily distributed on a line segment barrier. Each sensor is said to cover the portion of the barrier that intersects with its sensing area. Owing to incorrect initial position, or the death of some of the sensors, the barrier is not completely covered by the sensors. We employ a mobile robot to move the sensors to final positions on the barrier such that barrier coverage is guaranteed. We seek algorithms that minimize the length of the robot's trajectory, since this allows the restoration of barrier coverage as soon as possible. We give an optimal linear-time offline algorithm that gives a minimum-length trajectory for a robot that starts at one end of the barrier and achieves the restoration of barrier coverage. We also study two different online models: one in which the online robot does not know the length of the barrier in advance, and the other in which the online robot knows the length of the barrier. For the case when the online robot does not know the length of the barrier, we prove a tight bound of $3/2$ on the competitive ratio, and we give a tight lower bound of $5/4$ on the competitive ratio in the other case. Thus for each case we give an optimal online algorithm.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.