DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
This work addresses navigation challenges in dynamic environments for robotics or logistics, but it is incremental as it builds on existing TVG theory.
The paper tackles the Dynamic Map Visitation Problem (DMVP), where agents must quickly visit critical locations in a changing environment, by analyzing it using time-varying graphs (TVGs) and providing hardness results, inapproximability in some classes, and tractability in others.
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.