Algorithms for limited-buffer shortest path problems in communication-restricted environments.

In several applications, a robot moving from a start to a goal location is required to gather data along its path (e.g., a video feed in a monitoring scenario). The robot can have at its disposal only a limited amount of memory to store the collected data, in order to contain costs or to avoid that sensitive data fall into the hands of an attacker. This poses the need of periodically delivering the data to a Base Station (BS) through a deployed communication infrastructure that, in general, is not available everywhere. In this paper, we study this scenario by considering a variant of the shortest path problem (which we prove to be NP-hard) where the robot acquires information along its path, stores it into a limited memory buffer, and ensures that no information is lost by periodically communicating data to the BS. We present and evaluate an optimal exponential-time algorithm, an efficient feasibility test, and a polynomial-time heuristic algorithm. • A robot gathers data along its path with limited emory and restricted communication. • We study this scenario as a constrained variant of the shortest path problem. • We show that the problem is NP-hard and propose optimal and heuristic algorithms. [ABSTRACT FROM AUTHOR]