DMVP: Foremost Waypoint Coverage of Time-Varying Graphs

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