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 sensible 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 thesis, we study this scenario by considering a variant of the shortest path problem (which we prove to be NP-hard) where the robot acquires in- formation 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 algorithm, an efficient feasibility test, and a polynomial time heuristic algorithm.

In diverse applicazioni, un robot, muovendosi da un posizione di partenza ad una finale, deve raccogliere dati durante il suo percorso (per esempio, un video in un scenario di monitoraggio). Il robot può avere a disposizione solo una quantità limitata di memoria per salvare i dati raccolti, per tenere i costi bassi o per motivi di sicurezza (per evitare che dati sensibili cadano nelle mani di un aggressore). Questo pone la necessità di trasmettere periodica- mente i dati ad una Base Station (BS) tramite un’infrastruttura di comuni- cazione, che, in generale, non è disponibile ovunque. In questa tesi, studiamo questo scenario considerando una variante dello shortest path problem (che dimostriamo essere NP-hard) dove il robot acquisisce informazioni lungo il percorso, li salva in una memoria limitata e si assicura che nessuna infor- mazione venga persa, trasmettendo periodicamente alla BS. Presentiamo e valutiamo, un algoritmo ottimale, un efficiente test di feasibility e un algo- ritmo euristico.