Name
Title | ||
|---|---|---|
Algorithms for limited-buffer shortest path problems in communication-restricted environments |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.robot.2019.06.005 | Robotics and Autonomous Systems |
Keywords | Field | DocType |
Path planning,Communication constraints,Limited memory | Motion planning,Base station,Exponential function,Shortest path problem,Computer science,Heuristic (computer science),Algorithm,Time complexity,Robot,Memory buffer register | Journal |
Volume | ISSN | Citations |
119 | 0921-8890 | 1 |
PageRank | References | Authors |
0.35 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alessandro Riva | 1 | 3 | 3.09 |
| Arlind Rufi | 2 | 1 | 0.35 |
| Jacopo Banfi | 3 | 15 | 8.04 |
| Francesco Amigoni | 4 | 649 | 63.67 |