Danny Kriz̧anc

Stefan Dobrev, Konstantinos Georgiou, Evangelos Kranakis et al.

We study a problem of online targets coverage by a drone or a sensor that is equipped with a camera or an antenna of fixed half-angle of view $α$. The targets to be monitored appear at arbitrary positions on a line barrier in an online manner. When a new target appears, the drone has to move to a location that covers the newly arrived target, as well as already existing targets. The objective is to design a coverage algorithm that optimizes the total length of the drone's trajectory. Our results are reported in terms of an algorithm's competitive ratio, i.e., the worst-case ratio (over all inputs) of its cost to that of an optimal offline algorithm. In terms of upper bounds, we present three online algorithms and prove bounds on their competitive ratios for every $α\in [0, π/2]$. The best of them, called \FA is significantly better than the other two for $π/6 < α< π/3$. In particular, for $α=π/4$, its worst case, \FA has competitive ratio $1.25$, while the other two have competitive ratio $\sqrt{2}$. Finally, we prove a lower bound on the competitive ratio of online algorithms for a drone with half-angle $α\in [0, π/4]$; this bound is a function of $α$ that achieves its maximum value at $α= π/4$ equal to $(1+\sqrt{2})/2 \approx 1.207$.

Aaron Foote, Danny Krizanc

Along with accurate prediction, understanding the contribution of each feature to the making of the prediction, i.e., the importance of the feature, is a desirable and arguably necessary component of a machine learning model. For a complex model such as a random forest, such importances are not innate -- as they are, e.g., with linear regression. Efficient methods have been created to provide such capabilities, with one of the most popular among them being permutation feature importance due to its efficiency, model-agnostic nature, and perceived intuitiveness. However, permutation feature importance has been shown to be misleading in the presence of dependent features as a result of the creation of unrealistic observations when permuting the dependent features. In this work, we develop TRIP (Test for Reliable Interpretation via Permutation), a test requiring minimal assumptions that is able to detect unreliable permutation feature importance scores that are the result of model extrapolation. To build on this, we demonstrate how the test can be complemented in order to allow its use in high dimensional settings. Through testing on simulated data and applications, our results show that the test can be used to reliably detect when permutation feature importance scores are unreliable.

J. Czyzowicz, K. Georgiou, R. Killick et al.

We introduce and study a new search-type problem with ($n+1$)-robots on a disk. The searchers (robots) all start from the center of the disk, have unit speed, and can communicate wirelessly. The goal is for a distinguished robot (the queen) to reach and evacuate from an exit that is hidden on the perimeter of the disk in as little time as possible. The remaining $n$ robots (servants) are there to facilitate the queen's objective and are not required to reach the hidden exit. We provide upper and lower bounds for the time required to evacuate the queen from a unit disk. Namely, we propose an algorithm specifying the trajectories of the robots which guarantees evacuation of the queen in time always better than $2 + 4(\sqrt{2}-1) \fracπ{n}$ for $n \geq 4$ servants. We also demonstrate that for $n \geq 4$ servants the queen cannot be evacuated in time less than $2+\fracπ{n}+\frac{2}{n^2}$.

J. Czyzowicz, E. Kranakis, D. Krizanc et al.

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.

Eric Aaron, Danny Krizanc, Elliot Meyerson

We consider the Dynamic Map Visitation Problem (DMVP), in which a team of agents must visit a collection of critical locations as quickly as possible, in an environment that may change rapidly and unpredictably during the agents' navigation. We apply recent formulations of time-varying graphs (TVGs) to DMVP, shedding new light on the computational hierarchy $\mathcal{R} \supset \mathcal{B} \supset \mathcal{P}$ of TVG classes by analyzing them in the context of graph navigation. We provide hardness results for all three classes, and for several restricted topologies, we show a separation between the classes by showing severe inapproximability in $\mathcal{R}$, limited approximability in $\mathcal{B}$, and tractability in $\mathcal{P}$. We also give topologies in which DMVP in $\mathcal{R}$ is fixed parameter tractable, which may serve as a first step toward fully characterizing the features that make DMVP difficult.